Trie-datastrukturen (præfiks-træ)

A Trie, (også kendt som et præfiks-træ) er en speciel type træ, der bruges til at gemme associative datastrukturer

En trie (udtalt prøve) får sit navn fra re trie val - dens struktur gør det til en stjernematchende algoritme.

Sammenhæng

Write your own shuffle method to randomly shuffle characters in a string. 
Use the words text file, located at /usr/share/dict/words, and your shuffle method to create an anagram generator that only produces real words.
Given a string as a command line argument, print one of its anagrams. 

Jeg blev præsenteret for denne udfordring i denne uge på Make School's Product Academy.

Ordene i tekstfilen er adskilt af nye linjer. Dens formatering gør det meget nemmere at placere ordene i en datastruktur. For nu gemmer jeg dem på en liste - hvert element er et enkelt ord fra filen.

En tilgang til denne udfordring er at:

  • bland tilfældigt tegnene i strengen
  • Kontroller derefter det mod alle ord, der var i / usr / share / dict / ord for at kontrollere, at det er et rigtigt ord.

Denne fremgangsmåde kræver dog, at jeg kontrollerer, at de tilfældigt blandede tegn i den nye streng matcher et af 235.887 ord i den fil - det betyder 235.887 operationer for hver streng, som jeg vil bekræfte som et rigtigt ord.

Dette var en uacceptabel løsning for mig. Jeg kiggede først op på biblioteker, der allerede var implementeret for at kontrollere, om ord findes på et sprog, og fandt pyenchant. Jeg afsluttede først udfordringen ved hjælp af biblioteket i nogle få linjer kode.

def generateAnagram(string, language="en_US"): languageDict = enchant.Dict(language) numOfPossibleCombinationsForString = math.factorial(len(string)) for i in range(0, numOfPossibleCombinationsForString): wordWithShuffledCharacters = shuffleCharactersOf(string)
 if languageDict.check(wordWithShuffledCharacters): return wordWithShuffledCharacters return "There is no anagram in %s for %s." % (language, string)

Brug af et par biblioteksfunktioner i min kode var en hurtig og nem løsning. Jeg lærte dog ikke meget ved at finde et bibliotek til at løse problemet for mig.

Jeg var overbevist om, at biblioteket ikke brugte den tilgang, jeg nævnte tidligere. Jeg var nysgerrig og gravede igennem kildekoden - jeg fandt en trie.

Trie

En trie gemmer data i "trin". Hvert trin er en knude i trien.

Opbevaring af ord er et perfekt anvendelsestilfælde for denne slags træ, da der er en begrænset mængde bogstaver, der kan sættes sammen for at skabe en streng.

Hvert trin eller knudepunkt i en sprogtrie repræsenterer et bogstav i et ord. Trinene begynder at forgrene sig, når rækkefølgen af ​​bogstaverne afviger fra de andre ord i trie, eller når et ord slutter.

Jeg oprettede et trie ud af mapper på mit skrivebord for at visualisere at gå ned gennem noder. Dette er en trie, der indeholder to ord: æble og app.

Bemærk, at slutningen af ​​et ord er betegnet med en '$'. Jeg bruger '$', fordi det er en unik karakter, der ikke vil være til stede i noget ord på noget sprog.

Hvis jeg tilføjede ordet 'blænde' til denne trie, ville jeg løbe over bogstaverne i ordet 'blænde', mens jeg samtidig trak ned ad knudepunkterne i trien. Hvis brevet findes som barn af den aktuelle node, skal du træde ned i det. Hvis brevet ikke eksisterer som barn af den aktuelle node, skal du oprette det og derefter træde ned i det. For at visualisere disse trin ved hjælp af mine mapper:

Mens jeg træder ned trien, er de to første bogstaver i 'blænde' allerede til stede i trien, så jeg træder ned i disse noder.

Det tredje bogstav, 'e', ​​er imidlertid ikke et barn af 'p' noden. En ny node oprettes til at repræsentere bogstavet 'e', ​​der forgrener sig fra de andre ord i trie. Der oprettes også nye noder til de følgende bogstaver.

For at generere en trie fra en ordfil, vil denne proces ske for hvert ord, indtil alle kombinationer for hvert ord er gemt.

Du tænker måske: ”Vent, tager det ikke rigtig lang tid at generere trie fra den tekstfil med 235.887 ord i den? Hvad er meningen med at løbe over hvert enkelt tegn i hvert enkelt ord? ”

Ja, det tager lidt tid at gentage hvert tegn i hvert ord for at generere en trie. Det er dog det værd at tage den tid, det tager at oprette trie - for at kontrollere, om der findes et ord i tekstfilen, tager det højst lige så mange operationer som selve ordets længde . Meget bedre end de 235.887 operationer, den skulle tage før.

Jeg skrev den enkleste version af en trie ved hjælp af indlejrede ordbøger. Dette er ikke den mest effektive måde at implementere en på, men det er en god øvelse at forstå logikken bag en trie.

endOfWord = "$"
def generateTrieFromWordsArray(words): root = {} for word in words: currentDict = root for letter in word: currentDict = currentDict.setdefault(letter, {}) currentDict[endOfWord] = endOfWord return root
def isWordPresentInTrie(trie, word): currentDict = trie for letter in word: if letter in currentDict: currentDict = currentDict[letter] else: return False return endOfWord in currentDict

Du kan se min løsning til anagramgeneratoren på min Github. Siden jeg udforskede denne algoritme, har jeg besluttet at gøre dette blogindlæg til et af mange - hvert indlæg dækker en algoritme eller datastruktur. Koden er tilgængelig på mine algoritmer og datastrukturer repo - stjerne den for at holde sig opdateret!

Næste skridt

Jeg foreslår at tjekke Ray Wenderlichs trie repo. Selvom det er skrevet i Swift, er det en værdifuld kilde til forklaringer på forskellige algoritmer.

Svarende til trie (er mere hukommelseseffektiv) er et suffiksetræ eller radix. Kort sagt, i stedet for at gemme enkelte tegn ved hver node, gemmes slutningen af ​​et ord, dets suffiks, og stierne oprettes relativt.

En radix er dog mere kompliceret at implementere end en trie. Jeg foreslår at tage et kig på Ray Wenderlichs radix repo, hvis du er interesseret.

Dette er det første indlæg i min algoritme- og datastrukturserie. I hvert indlæg præsenterer jeg et problem, der kan løses bedre med en algoritme eller datastruktur for at illustrere algoritmen / datastrukturen i sig selv.

Stjern min algoritmer repo på Github og følg mig på Twitter, hvis du gerne vil følge med!

Fik du værdi ved at læse denne artikel? Klik her for at dele det på Twitter! Hvis du gerne vil se indhold som dette oftere, skal du følge mig på Medium og abonnere på mit nyhedsbrev en gang om måneden nedenfor. Du er også velkommen til at købe mig en kop kaffe.