A Trie adatstruktúra (előtagfa)

Az A Trie(más néven előtagfa) egy speciális típusú fa, amelyet asszociatív adatszerkezetek tárolására használnak

A trie (ejtsd próbálkozás) a nevét a re trie val-ról kapja - felépítése csillagillesztõ algoritmussá teszi.

Kontextus

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. 

A héten a Make School's Product Academy-n kaptam ezt a kihívást.

A szövegfájlban szereplő szavakat új sorok választják el. Formázása megkönnyíti a szavak adatstruktúrába helyezését. Egyelőre egy listában tárolom őket - minden elem egyetlen szó a fájlból.

A kihívás egyik megközelítése:

  • véletlenszerűen keverje össze a karaktereket a karakterláncban
  • majd ellenőrizze az összes olyan szót, amely a / usr / share / dict / words fájlban található, hogy ellenőrizze, hogy ez egy valódi szó.

Ez a megközelítés azonban megköveteli, hogy ellenőrizzem, hogy az új karaktersorozat véletlenszerűen megkevert karakterei megegyeznek-e a fájl 235 887 szójának egyikével - ez 235 887 műveletet jelent minden egyes karaktersorozat esetében , amelyet valódi szóként szeretnék ellenőrizni.

Ez számomra elfogadhatatlan megoldás volt. Először utánanéztem a már megvalósított könyvtáraknak, hogy ellenőrizzem, léteznek-e szavak egy nyelven, és megtaláltam a hangulatot. Először a könyvtár használatával teljesítettem a kihívást, néhány kódsorban.

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)

Pár könyvtári függvény használata a kódomban gyors és egyszerű megoldás volt. Azonban nem sokat tanultam azzal, hogy könyvtárat találtam a probléma megoldására.

Abban biztos voltam, hogy a könyvtár nem az előbb említett megközelítést alkalmazta. Kíváncsi voltam, és átástam a forráskódon - találtam egy trie-t.

Trie

A trie „lépésekben” tárolja az adatokat. Minden lépés egy csomópont a trie-ben.

A szavak tárolása tökéletes felhasználási lehetőség egy ilyen fához, mivel véges mennyiségű betű állítható össze egy húr készítéséhez.

A nyelv minden egyes lépése vagy csomópontja a szó egy betűjét fogja képviselni. A lépések akkor kezdenek elágazni, amikor a betűk sorrendje eltér a trie többi szavától, vagy amikor egy szó véget ér.

Csináltam egy Trie ki könyvtárak én Desktop láthatóvá lelép a csomópontokat. Ez egy trie, amely két szót tartalmaz: alma és kb.

Vegye figyelembe, hogy a szó végét '$' jelöli. Azért használom a „$” szót, mert ez egy egyedi karakter, amely egyetlen szóban sem jelenik meg egyetlen nyelven sem.

Ha ehhez a trie-hez hozzáadnám az „aperture” szót, akkor az „aperture” szó betűit áthúznám, miközben egyidejűleg lelépnék a trie csomópontjain. Ha a betű az aktuális csomópont gyermekeként létezik, lépjen le. Ha a betű nem létezik az aktuális csomópont gyermekeként, hozza létre, majd lépjen le. A lépések vizualizálása a könyvtáram segítségével:

Amíg a trie-ről lelépek, az apertúra első két betűje már jelen van a trie-ben, ezért belépek ezekbe a csomópontokba.

A harmadik „e” betű azonban nem a „p” csomópont gyermeke. Új csomópont jön létre az 'e' betű képviseletére, amely elágazik a trie többi szavától. Új csomópontok jönnek létre a következő betűk számára is.

A szó fájlból egy trie előállításához ez a folyamat minden szónál megtörténik, amíg az egyes szavak összes kombinációját el nem tárolja.

Gondolhatod: „Várj, nem fog sokáig tartani a trie előállítása abból a szövegfájlból, benne 235 887 szó? Mi értelme az egyes szavak minden egyes karakterének átlapolása?

Igen, a trie előállításához minden szó minden karakterének ismétlése eltart egy ideig. A trie létrehozásához szükséges idő azonban megéri - mert annak ellenőrzése, hogy létezik-e szó a szövegfájlban, legfeljebb annyi műveletet igényel, mint maga a szó hossza . Sokkal jobb, mint a korábban végrehajtott 235 887 művelet.

A trie legegyszerűbb változatát írtam beágyazott szótárak segítségével. Ez nem a leghatékonyabb módja annak megvalósítására, de jó gyakorlat megérteni a trie mögött rejlő logikát.

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

Az anagramma-generátor megoldását a Github-on láthatja. Az algoritmus felfedezése óta úgy döntöttem, hogy ezt a blogbejegyzést a sok közül választom - mindegyik bejegyzés egy algoritmust vagy adatszerkezetet tartalmaz. A kód elérhető az Algoritmusok és az Adatszerkezetek oldalamon, majd frissítse a csillaggal, hogy naprakész legyen!

Következő lépések

Javaslom, nézze meg Ray Wenderlich trie repóját. Bár Swiftben írták, értékes forrás a különféle algoritmusok magyarázatához.

A trie-hez hasonló (de memória-hatékonyabb) egy utótagfa vagy radix. Röviden, ahelyett, hogy minden csomópontban egyetlen karaktert tárolna, a szó végét, annak utótagját tárolja, és az utakat viszonylag létrehozzák.

A radix megvalósítása azonban bonyolultabb, mint egy trie. Javaslom, ha érdekel, vessen egy pillantást Ray Wenderlich radix repójára.

Ez az algoritmus- és adatstruktúra-sorozatom első bejegyzése. Minden bejegyzésben bemutatok egy problémát, amelyet jobban megoldhatunk algoritmussal vagy adatstruktúrával, hogy szemléltessük magát az algoritmust / adatstruktúrát.

Jelölje be algoritmusaimat a Github-on, és kövesse a Twitteren, ha szeretné követni!

Értéket szerzett a cikk elolvasásával? Kattintson ide, hogy megossza a Twitteren! Ha gyakrabban szeretne ilyen tartalmat látni, kövessen a Mediumon, és iratkozzon fel az alábbi havi egyszeri hírlevelemre. Nyugodtan vegyen nekem is egy kávét.