Trie megvalósítása Pythonban (kevesebb mint 100 kódsorban)
Bevezetés
Hadd kérdezzek valamit. Valami érdekes, amivel gyakran találkozunk, és (majdnem) mindig figyelmen kívül hagyjuk.
Minden bizonnyal emlékszik a nagyszerű funkcióra a mobil billentyűzetéről, ahol elkezd beírni egy szót, és az elkezd javaslatokat mutatni. Rohadt kényelmes! Valójában ennek köszönhetően szinte mindig tudtam helyesírási hibák nélkül írni angol szavakat.
Mit gondol, a számítógép (igen! az Ön okostelefonja is számítógép) hogyan találja ki ezeket a javaslatokat?
Nos, kiderült, hogy sok ilyen eset egy bizonyos adatszerkezetet használ a motorháztető alatt, hogy szójavaslatokat jelenítsen meg gépelés közben. Ennek az adatszerkezetnek a neve Trie.
Szóval, mi az a Trie? Mielőtt belevágnék a meghatározásába, hadd mutassak egy képet.
Amint a fenti képen látható, ez egy faszerű struktúra, ahol minden csomópont egy adott karakterlánc egyetlen karakterét képviseli. A bináris fákkal ellentétben egy csomópontnak kettőnél több gyermeke lehet.
Elemezzünk egy példát. Feltételezzük, hogy a nulláról indulunk, ami azt jelenti, hogy csak egy üres gyökércsomópontunk van, semmi más. Kezdjük a „vásárlás” szóval. A képen jól látható, hogy a Trie implementációnk nem tárol karaktert a gyökércsomópontban. Tehát az első karaktert, azaz a „b”-t adjuk hozzá gyermekcsomópontként. Úgy csináljuk, hogy egyik gyereknél sem volt meg ez a karakter. Ellenkező esetben kihagytuk volna a gyermek csomópont hozzáadását. Ahogy már megvan. Aztán jön az „u” karakter. A karakter hozzáadásakor egy dologgal tisztában kell lennünk, hogy meg kell keresnünk, hogy az „u” szerepel-e „b” (utoljára hozzáadott csomópontunk) gyermekcsomópontjaiban, és nem a gyökéret
És ugyanez igaz az „y”-re is. Tehát, ha a teljes „vásárlás” szó hozzáadásának művelete befejeződött, a Trie így néz ki:
És most itt a „bika” ideje. Ugyanezeket a lépéseket megismételjük a „bika” hozzáadásához a Trie-nkhoz. Csak ezúttal nem adjuk hozzá újra a „b” és „u” betűket. Ahogy már léteznek. Tehát a művelet befejezése után így néz ki:
Azt hiszem, ez jó képet ad arról, hogy mi az a Trie, és hogyan működik a karakter hozzáadásának művelete. A részletekért látogasson el a "Wikipedia" oldalra.
A „Hackerrank” kihívásának megoldása közben találkoztam ezzel a kissé szokatlan és kevésbé tárgyalt adatszerkezettel. És néhány óra kóddal való babrálás után sikeresen fel tudtam kódolni és megoldani a kihívást. És így néz ki a kódom -
A kód
Hogyan működik?
Most egy rövid áttekintést adok az algo fő lépéseinek kiemelésére
- Az első dolog, amit meg kell fontolni, hogy hogyan adjunk hozzá új szavakat a Trie-hez. A
add
függvény pontosan ezt teszi. A működése nagyon egyszerű. Bemenetként veszi a gyökércsomópontot (azt, amelyhez nincs karakterérték hozzárendelve) és az egész szót. - Ezután ismétlődik a szóban, egy-egy karakterrel, kezdve az első karakterrel.
- Ellenőrzi, hogy az aktuális „csomópontnak” (a gyökércsomópontra mutató folyamat elején) van-e gyermekcsomópont ezzel a karakterrel.
- Ha megtalálja, akkor csak növeli az adott csomópont számlálóját, jelezve, hogy az adott karakter ismétlődően előfordult.
- Ha nem található, akkor egyszerűen hozzáad egy új csomópontot az aktuális csomópont gyermekeként.
- Mindkét esetben (4 és 5) a gyermek csomópontot rendeli hozzá „aktuális csomópontként” (ami azt jelenti, hogy a következő iterációban innen indul), mielőtt a szó következő karakterével kezdené.
Ez annyit jelent, hogy egy szót kell hozzáadni a Trie-hez. Még egy dolog, hogy megjelöli a szó végét, miután az egész folyamat befejeződött. Ez azt jelenti, hogy a Trie minden egyes levélcsomópontjában a word_finished
True lesz.
Az előtag kereséséhez néhány egyszerű lépés szükséges:
- A gyökércsomóponttal és a keresendő előtaggal kezdődik.
- Egyszerre egy karaktert vesz el az előtagból, és az „aktuális csomópont” gyermekei között keres (az elején, amely a gyökércsomópontra mutat), hogy megtalálja az adott karaktert tartalmazó csomópontot.
- Ha megtalálja, akkor újra hozzárendeli az utódcsomópontot „aktuális csomópontként” (ami azt jelenti, hogy a következő iterációs lépésben innen indul)
- Ha nem található, akkor False értéket ad vissza, jelezve, hogy az előtag nem létezik.
- Ebben az algoritmusban van egy kis csavar annak az esetnek a kezelésére, amikor olyan előtagot próbálnak találni, amely nagyobb, mint maga a szó. Ez azt jelenti, hogy a
hammer
Trie-t használjuk, és ahammers
-et keressük
Ez pedig egy általános célú Trie adatstruktúra felépítéséről és bejárásáról szól a Pythonban.
Az itt megadott kód újrafelhasználható (és jól kommentálható :) ) és nyilvános. Ha szüksége van rá, nyugodtan használja, ahogy akarja!
Ez van, srácok! Remélem, hogy tetszett a cikk, és ha igen, kérjük, tapsoljon annyiszor, ahányszor csak akarja. Ha bármilyen visszajelzése vagy javaslata van, kérjük, tudassa velem megjegyzésekben vagy közvetlenül a „Linkedin”-en keresztül. Ezek arra ösztönöznek, hogy a jövőben még több cikket írjak. Hamarosan találkozunk!