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

  1. 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.
  2. Ezután ismétlődik a szóban, egy-egy karakterrel, kezdve az első karakterrel.
  3. Ellenőrzi, hogy az aktuális „csomópontnak” (a gyökércsomópontra mutató folyamat elején) van-e gyermekcsomópont ezzel a karakterrel.
  4. 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.
  5. Ha nem található, akkor egyszerűen hozzáad egy új csomópontot az aktuális csomópont gyermekeként.
  6. 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:

  1. A gyökércsomóponttal és a keresendő előtaggal kezdődik.
  2. 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.
  3. 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)
  4. Ha nem található, akkor False értéket ad vissza, jelezve, hogy az előtag nem létezik.
  5. 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 a hammers-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!