Etuliite puu

Etuliitepuu (myös poraus [1] , säde [2] , ladattu puu [3] , englanninkielinen trie [4] ) on tietorakenne , johon voit tallentaa assosiatiivisen taulukon , jonka avaimet ovat merkkijonoja. Se on juurtunut puu , jonka jokainen reuna on merkitty jollakin symbolilla, joten minkä tahansa solmun kaikki reunat, jotka yhdistävät tämän solmun sen pojiin, on merkitty eri symboleilla. Jotkut etuliitepuun solmut valitaan (ne on merkitty numeroilla kuvassa) ja katsotaan, että etuliitepuu sisältää tietyn merkkijonoavaimen, jos ja vain jos tämä merkkijono voidaan lukea polulla juuresta johonkin ( ainoa tälle merkkijonolle) valittu solmu. Joissakin sovelluksissa on kätevää pitää kaikki puun solmut valittuina.

Siten toisin kuin binäärihakupuut , avainta, joka identifioi tietyn puun solmun, ei ole eksplisiittisesti tallennettu kyseiseen solmuun, vaan se annetaan kyseisen solmun sijainnin perusteella. Voit saada avaimen kirjoittamalla riviin merkkejä, jotka merkitsevät polun reunat juuresta solmuun. Puun juuriavain on tyhjä merkkijono. Usein omistetut solmut tallentavat avaimeen liittyvää lisätietoa, ja tyypillisesti vain lehdet ja mahdollisesti jotkin sisäiset solmut ovat omistettuja.

Toiminnot etuliitepuussa

Etuliitepuussa on kolme päätoimintoa: tarkastetaan, onko puussa avain, avaimen poistaminen puusta ja uuden avaimen lisääminen (ehkä lisätietojen kera). Jokainen näistä toiminnoista toteutetaan laskemalla puu juuresta, mutta tällaisen toiminnan tehokkuus riippuu suoraan solmujen läpi navigoinnin järjestämisestä. Tämän ongelman eri lähestymistapojen myöhempää analysointia varten merkitään pyydetyn /poistettavan/lisätyn merkkijonon pituus ja aakkosten koko eli eri merkkien määrä tietyn etuliitepuun reunoilla . Anna tällä solmulla olla poikia (ja ). Merkitään viittauksilla näihin poikiin ja symboleilla, jotka merkitsevät vastaaviin poikiin yhdistäviä reunoja . $n$ $\sigma$ $x$ $k$ $k\leq \sigma$ ${\displaystyle x_{1},x_{2},\ldots ,x_{k))$ ${\displaystyle a_{1},a_{2},\ldots ,a_{k))$ $x$

Helpoin tapa järjestää navigointi on tallentaa dynaaminen joukko . Tällä lähestymistavalla kaikki kolme toimintoa suoritetaan . Jos lisäystä ja poistamista ei käytetä, on parempi lajitella parit avaimen mukaan, ja sitten avaimen läsnäolon tarkistaminen etuliitepuussa voidaan suorittaa käyttämällä solmujen binaarihakua . $x$ ${\näyttötyyli (a_{i},x_{i})}$ $O(n\sigma )$ $a_{i}$ $O(n\log \sigma )$
On mahdollista saavuttaa suoritusajat kaikille kolmelle operaatiolle tallentamalla avaimen mukaan lajiteltuja pareja johonkin tasapainotettuun binäärihakupuuhun , kuten punamustapuuhun tai AVL-puuhun . Useimmissa ohjelmointikielissä jonkinlaisen tasapainotetun hakupuun toteutus sisältyy standardikirjastoon assosiatiivisen taulukon muodossa . $O(n\log \sigma )$ ${\näyttötyyli (a_{i},x_{i})}$ $a_{i}$
Toinen suosittu tapa järjestää navigointi on tallentaa parit avaimella hash - taulukkoon . Tällä lähestymistavalla kaikki kolme toimintoa suoritetaan odotetussa ajassa (kun taas kahdella edellisellä vaihtoehdolla on taattu suoritusaika). Monissa ohjelmointikielissä hash-taulukot sisältyvät vakiokirjastoon. Ajoitustakuuta voi parantaa entisestään korvaamalla hash-taulukon käkihaja- tai vastaavalla rakenteella: tällainen tiiviste mahdollistaa avainten kyselyn ja poistamisen taatussa ajassa, ja vain lisäys tapahtuu odotetussa ajassa . $x$ ${\näyttötyyli (a_{i},x_{i})}$ $a_{i}$ $Päällä)$ $Päällä)$ $Päällä)$

Pakattu etuliitepuu

Tarkastellaan etuliitepuuta, joka sisältää kaikki pituisen merkkijonon päätteet . Tässä puussa on ainakin solmuja ja se vie muistia. Tässä esimerkissä tämä turha muistinkulutus johtuu suuresta määrästä solmuja, joissa on vain yksi lapsi. Tämän ongelman torjumiseksi Donald Morrison [5] kehitti etuliitepuun muunnelman, jota kutsutaan pakatuksi etuliitepuuksi (on myös vaihtoehtoja kompakti etuliitepuu, peruspuu , puristettu poraus , kompakti poraus , puristettu palkki , pakattu ladattu puu ; Morrison itse [5] kutsui sen rakennetta "PATRICIA-puuksi" ja tämä nimi löytyy joskus edelleen). ${\textstyle \underbrace {aa\cdots a} _{k{\text{ times}}}b\underbrace {aa\cdots a} _{k{\text{ times}}}b}$ $n=2k+2$ $k^{2}=\Theta (n^{2})$ $\Theta (n^{2})$

Määritelmä ja säilytysmenetelmät

Pakattu etuliitepuu, joka sisältää annetut merkkijonot , on pienin puu solmujen lukumäärän suhteen, jonka jokainen reuna on merkitty ei-tyhjällä merkkijonolla (eikä symbolilla, kuten tavallisessa etuliitepuussa), jotta mikä tahansa merkkijono voi luetaan polulla juuresta johonkin (valittuun) solmuun, ja minkä tahansa solmun kaikkien alisolmun reunojen tarrojen ensimmäiset merkit ovat erilaisia. Esimerkiksi kuvassa näkyvä pakattu etuliitepuu sisältää kahdeksan venäjän kielen sanaa ja siinä vain lehdet ovat valittuja solmuja. ${\displaystyle s_{1},s_{2},\ldots ,s_{k))$ $si}$

Pakattu etuliitepuu saadaan tavallisesta avaimet sisältävästä etuliitepuusta poistamalla peräkkäin jokainen solmu (juurta lukuun ottamatta), jolla on vain yksi poika ja jota ei ole valittu, samalla kun poistettavan solmun isä ja poika yhdistetään ja tuloksena oleva reuna on merkitty merkkijonolla, joka on saatu yhdistämällä emo-solmun ja solmun-poika reunoilla olevat tarrat (vaikka tätä pakatun etuliitepuun rakentamismenetelmää ei suositella ${\displaystyle s_{1},s_{2},\ldots ,s_{k))$ [ kenen toimesta? ] ).

Pakatun etuliitepuun tehokkuus johtuu tavasta, jolla reunatunnisteet esitetään. Koska jokainen otsikko on jonkin merkkijonon osamerkkijono , se voidaan esittää käyttämällä numerotriplettiä , jossa ( merkitsee tässä merkkijonon osamerkkijonoa, joka alkaa paikasta ja päättyy kohtaan ). Jos kaikki merkkijonot ovat yhden tietyn merkkijonon osamerkkijonoja , tunnisteet voidaan esittää osamerkkijonoja vastaavilla numeropareilla . Navigointi solmuissa on järjestetty samalla tavalla kuin tavallisessa etuliitepuussa, mutta solmu-poika-reunojen tarrojen ensimmäiset merkit toimivat viitemerkkeinä: esimerkiksi kuvan pakatussa etuliitepuussa vastaava solmu merkkijonolla "länsi" on kolme poikaa ja tämän solmun viitesymbolit ovat "i", "n", "b", jotka ovat ensimmäiset merkit otsikoissa "ib", "nick", "b". solmupojan reunat. Voidaan osoittaa, että pakatussa merkkijonojoukon etuliitepuussa on yhteensä enintään solmuja ja se vie siis muistia paitsi itse merkkijonojen tallentamiseen tarvittavan muistin . $t$ ${\displaystyle s_{h))$ $t$ ${\näyttötyyli (h,i,j)}$ $s_{h}[i..j]=t$ $s_{h}[i..j]$ ${\displaystyle s_{h))$ $i$ $j$ ${\displaystyle s_{h))$ $s$ $(i,j)$ $s[i..j]$ ${\displaystyle s_{1},s_{2},\ldots ,s_{k))$ $2k$ $O(k)$ ${\displaystyle s_{1},s_{2},\ldots ,s_{k))$

Toiminnot pakatussa etuliitepuussa

Pakatun etuliitepuun kysely-, poisto- ja lisäystoiminnot voidaan suorittaa samalla tavalla kuin tavallisessa etuliitepuussa juuresta laskeutuen. Tässä tapauksessa algoritmista tulee hieman monimutkaisempi, koska tarran sisältö on luettava yhden merkkijonon vastaavasta osamerkkijonosta, kun lasketaan reunoja, jotka on merkitty merkkijonoilla, joiden pituus on kaksi tai enemmän . Teoreettisesti tällaisen algoritmin ajoaika voidaan arvioida samalla tavalla kuin tavallisella etuliitepuulla (eli , , riippuen navigoinnin organisoinnista solmuissa), mutta käytännössä toiminnot pakatun etuliitepuun kanssa usein muuttuvat nopeammiksi, koska suurin osa polusta juuresta solmuun kulkee reunoja pitkin eikä solmujen tietorakenteisiin tarvitse usein viitata. ${\displaystyle s_{1},s_{2},\ldots ,s_{k))$ $O(n\sigma )$ $O(n\log \sigma )$ $Päällä)$

Jos kaikkien rivien pituudet ovat suhteellisen pieniä (esimerkiksi yhden välimuistirivin pituudessa , joka on 64 tavua monilla nykyaikaisilla prosessoreilla), niin toistuvista hyppyistä eri otsikoiden välillä aiheutuvat välimuistihäiriöt voidaan välttää käyttämällä toista puun laskeutumismenetelmää ( juuri tämä menetelmä kuvattiin Morrisonin paperissa [5] ). Harkitse esimerkiksi algoritmia, jolla etsitään tietyn merkkijonon pisin etuliite, joka voidaan lukea polulla juuresta johonkin solmuun tietyssä pakatussa etuliitepuussa; muut toiminnot voidaan toteuttaa analogisesti. $si}$ $t$

Algoritmi koostuu siitä, että ensimmäisessä ajossa kysellään vain puun solmut, ohittaen reunat ja siten laskeutuen puussa mahdollisimman alas, etsitään joukosta merkkijono, jolla on pisin yhteinen etuliite merkkijonon kanssa . Sitten sinun on laskettava yhteinen etuliite ja tavallinen naiivi algoritmi ja palautettava tulos. Alla olevassa C :n kaltaisessa pseudokoodissa s[i] tarkoittaa merkkijonoa , root tarkoittaa puun juuria ja jokainen solmu x sisältää seuraavat kentät/menetelmät: x->len on x:n reunassa olevan etiketin pituus. x:n isälle; x->child(c) on viittaus solmun x lapsiin, joka on yhdistetty x:ään reunalla, jonka nimi on c:llä tai nullptr:llä, jos sellaista poikaa ei ole; x->src on luku, jonka merkkijono polulla juuresta x:ään on merkkijonon etuliite . $si}$ ${\displaystyle s_{1},s_{2},\ldots ,s_{k))$ $t$ $t$ $si}$ $si}$ ${\displaystyle s_{x{-}{>}src))$

koko_t löydä_pitin_etuliite ( merkkijono t ) { struct solmu_t * x = juuri ; for ( koko_t i = 0 ; i < t . pituus (); i += x -> len ) if ( x -> lapsi ( t [ i ]) != nullptr ) x = x -> lapsi ( t [ i ]); muu tauko ; palauttaa t :n ja s :n yhteisen etuliitteen pituus [ x -> src ]; }

Sovellukset

Rakennetta käytetään laajasti hakualgoritmeissa ja muissa sovelluksissa.

Etuliitepuuta käytetään Aho-Korasik-algoritmissa useiden merkkijonojen etsimiseen annetusta merkkijonosta.
Etuliitepuuta käytetään myös Lempel-Ziv-Welch-algoritmissa .
Pakattua etuliitepuuta, joka sisältää kaikki tietyn merkkijonon päätteet, kutsutaan suffiksipuuksi, ja sillä on kriittinen rooli hakualgoritmeissa.
Pakattua etuliitepuuta käytetään erityisesti luonnollisten kielten jäsentämiseen [6] .
Pakattu etuliitepuu on yksi Linux-ytimen tietorakenteista [7] .

Muistiinpanot

↑ Knuthin monografian ensimmäisessä käännöksessä.
↑ Knuthin monografian myöhemmissä käännöksissä.
↑ Aho, Hopcroft, Ulman, 2003 , s. 152.
↑ Fredkin, 1960 .
↑ 1 2 3 Morrison, 1968 .
↑ Pymorphy 2 https://habrahabr.ru/post/176575/ Arkistoitu kopio 24. elokuuta 2017 Wayback Machinessa
↑ Robert Love. Linux-ytimen kehitys. kolmas painos. 2010.

Kirjallisuus

Knut D.E. Ohjelmoinnin taito. Osa 3. Lajittelu ja haku = The Art of Computer Programming. Osa 3. Lajittelu ja haku / toim. V. T. Tertyshny (luku 5) ja I. V. Krasikov (luku 6). - 2. painos - Moskova: Williams, 2007. - T. 3. - 832 s. — ISBN 5-8459-0082-1 .
Aho A. V. , Hopcroft J. E. , Ulman J. D. Tietorakenteet ja algoritmit = Data Structures and Algorithms / toim. S. N. Triguba ; per. englannista. A. A. Minko . - M .: Williams, 2003. - 384 s. — ISBN 5-8459-0122-7 .
Crochemore M. , Rytter W. Jewels of Stringology. Singapore: World Publishing Scientific Co. Pte. Ltd., 2002. - 306 s. — ISBN 981-02-4782-6 .
Fredkin E. Trie Muisti // ACM:n viestintä . - 1960. - V. 3 , nro 9 . — S. 490–499 . - doi : 10.1145/367390.367400 .
Morrison DR :n käytännön algoritmi aakkosnumeerisiksi koodattujen tietojen hakemiseksi // Journal of the ACM . - 1968. - T. 15 , nro 4 . — S. 514–534 . - doi : 10.1145/321479.321481 .

Linkit

Bentley, John; Sedgewick, Robert (1998-04-01). "Ternaariset hakupuut" . DR. Dobbin päiväkirja (Dr Dobb's). Arkistoitu alkuperäisestä 2008-06-23.
Algoritmit ja tietorakenteet Tutkimus- ja viitemateriaali: Yritykset Arkistoitu 6. maaliskuuta 2013 Wayback Machinessa , kirjoittanut Lloyd Allison, Monash University.
Algoritmit ja tietorakenteet tutkimus- ja viitemateriaali: PATRICIA Arkistoitu 22. toukokuuta 2018 Wayback Machinessa , kirjoittanut Lloyd Allison, Monash University.
Patricia Tree Arkistoitu 30. joulukuuta 2017 the Wayback Machine , NIST Dictionary of Algorithms and Data Structures.
Crit-bit trees Arkistoitu 31. joulukuuta 2007 Wayback Machinessa , kirjoittanut Daniel J. Bernstein.
Radix Tree API Linux-ytimessä Arkistoitu 8. marraskuuta 2020 Wayback Machinessa , kirjoittanut Jonathan Corbet.
Kart (key alteration radix tree) Arkistoitu 7. elokuuta 2008 Wayback Machinessa , kirjoittanut Paul Jarc .

Puu (tietorakenne)
Binäärihakupuu Puu (graafiteoria) puun rakenne
Binääripuut	binäärinen puu T-puu
Itsetasapainottavat binaaripuut	AA puu AVL puu Puna-musta puu Splay-puu puu sakkoilla karteesinen puu Fibonacci puu B-puu T-puu
B-puut	2-3-puu B⁺-puu B*-puu B x -puu UB puu 2-3-4 puu (a,b)-puu tanssiva puu
etuliite puita	suffiksi puu Pakattu etuliitepuu Kolmiosainen hakupuu
Avaruuden binaarinen osiointi	k-ulotteinen puu VP-puu
Ei-binääripuut	Quadtree oktreen Harva Voxel Octree eksponentiaalinen puu PQ puu
Avaruuden hajottaminen	R-puu Hilbert R-puu R+-puu R*-puu X-puu M-puu Fenwick puu Segmenttipuu
Muut puut	pino hash puu sormipuu metrinen puu Päällystyspuu BK-puu Kaksiketjuinen puu iDistance Linkistä leikattu puu LSM puu
Algoritmit	Leveys ensimmäinen haku Ensimmäinen syvyyshaku DSW-algoritmi kattava puu protokolla

jouset
Merkkijonojen samankaltaisuusmitat	Etäisyys Damerausta Loewensteiniin Levenshtein etäisyys Hammingin etäisyys Jaro-Winkler yhtäläisyydet
Alimerkkijonohaku	Boyer-Mooren algoritmi Boyer-Moore-Horspool-algoritmi Knuth-Morris-Pratt-algoritmi Rabin-Karp algoritmi etuliitetoiminto Z-toiminto Algoritmi Aho - Korasik
palindromit	palindromipuu Manakerin algoritmi
Jakson tasaus	Needleman-Wunsha-algoritmi Smith-Waterman-algoritmi
Suffiksirakenteet	Suffiksitaulukko Suffiksiautomaatti suffiksi puu etuliite puu
muu	jäsentäminen Kuvioiden yhteensopivuus Suurin yhteinen osasarja Suurin yhteinen osamerkkijono