Suffiksi puu

Suffiksipuu on puu , joka sisältää kaikki jonkin merkkijonon loppuliitteet (ja vain ne). Voit selvittää, sisältyykö merkkijono w alkuperäiseen merkkijonoon t O (|w|) -ajassa , missä |w| on merkkijonon pituus w .

Perusmääritelmät ja rakenteen kuvaus

$\Sigma$ on ei-tyhjä äärellinen symbolien joukko , jota kutsutaan aakkosiksi. Aakkosten merkkijono (mahdollisesti tyhjä) on merkitty kirjaimilla r , s ja t . on käänteinen merkkijono. Yksittäiset merkit on merkitty kirjaimilla x, y tai z. - tyhjä rivi. $t^{{-1}}$ $\varepsilon$
Aakkosten symbolit ovat kirjaimet a, b, … . Vaikka aakkosten koko otetaan vakiona. |t| tarkoittaa merkkijonon pituutta t . ovat kaikki merkkijonoja, joiden pituus on m, ja . $\Sigma ^{m}$ $\Sigma ^{*}=\bigcup \limits _{{i=0}}^({\infty }}\Sigma ^{i}$ $\Sigma ^{+}=\Sigma ^{*}\backslash \{\varepsilon \}$

Merkkijonon t etuliite w on merkkijono, jossa wv = t jollekin (mahdollisesti tyhjälle) merkkijonolle v . Etuliitettä kutsutaan oikeaksi , jos |v| 0. $\neq$

Merkkijonon t w - liite on merkkijono, jossa vw = t jollekin (mahdollisesti tyhjälle) merkkijonolle v . Suffiksia kutsutaan oikeaksi, jos |v| 0. Esimerkiksi merkkijonolle "alimerkkijono" alimerkkijono "sub" on sen oma etuliite, "rengas" on sen oma pääte. $\neq$

Merkkijonon t osamerkkijonoa w kutsutaan oikeaksi haaraksi , jos t voidaan esittää kuten joidenkin merkkijonojen kohdalla ja samoin kuin kirjaimet x y . Vasen haara määritellään samalla tavalla. Esimerkiksi "eabceeabcd" alimerkkijono "abc" on oikea haara, koska sen molemmissa esiintymisissä t :ssä on eri merkkejä sen oikealla puolella, mutta sama osamerkkijono ei ole vasen haara, koska sama merkki " e". $uwxv$ $u'wyv'$ $sinä, v, u'$ $v'$ $\neq$

$\Sigma ^{+}$ - puu T on juurtunut puu , jonka reunat on merkitty sekvenssillä . Jokaisella aakkosten merkillä a on puun T jokaisella solmulla enintään yksi reuna, jonka nimi alkaa merkillä a . Reuna t :stä s :hen , jonka tunniste on v , merkitään . $\Sigma ^{+}$ $t\longrightarrow _{v}s$

Olkoon k -puun T solmu , jolloin polku(k) on merkkijono, joka on kaikkien reunatunnisteiden ketjutus juuresta k :hen . Kutsumme sijaintia w , jolle polku( ) = w . $\Sigma ^{+}$ $\overline {w}$ $\overline {w}$

Koska jokainen haara on ainutlaatuinen, jos polku( t ) = w , voimme nimetä solmun t nimellä . Solmun alipuu on merkitty . -puussa T esitetyt sanat annetaan joukolla, joka on merkitty sanoilla( T ). Sana w sisältyy joukkosanoihin ( T ) jos ja vain jos on olemassa merkkijono v (mahdollisesti tyhjä), joka on puun T solmu . $\overline {w}$ $\overline {w}$ $T_{{\overline {w))}$ $\Sigma ^{+}$ $\overline {wv}$

Jos merkkijono w sisältyy sanoihin( T ), w = uv , on puun T solmu , paria kutsutaan linkkipariksi w suhteessa puuhun T . Jos u on pisin etuliite, joka on linkkipari, kutsumme sitä kanoniseksi linkkipariksi . Sitten kirjoitetaan . Sijainnin sanotaan olevan eksplisiittinen, jos |v| = 0 ja implisiittisesti muuten. $\overline {u}$ $(\overline {u},v)$ $(\overline {u},v)$ $(\overline {u},v)$ $\widehat {w}=(\overline {u},v)$ $\widehat {w}=(\overline {u},v)$

$\Sigma ^{+}$ -puuta T , jossa jokainen reuna on merkitty yhdellä symbolilla, kutsutaan atomiksi (sillä jokainen sijainti on eksplisiittinen). -puuta T , jossa jokainen solmu on joko juuri tai lehti tai haarasolmu, kutsutaan kompaktiksi . $\Sigma ^{+}$

Atomipuuta kutsutaan myös (palkiksi). Atomi ja kompakti -puu määritellään yksilöllisesti niiden sisältämien sanojen perusteella. $\Sigma ^{+}$ $kokeile$ $\Sigma ^{+}$

Merkkijonon t päätepuu on -puu, jossa sanat( T ) = { w | w on sanan t } osasana. Merkkijonolle t atomiliitepuu merkitään ast( t ), kompakti suffiksipuu on merkitty cst( t ). $\Sigma ^{+}$

Merkkijonon t käänteinen etuliitepuu on merkkijonon jälkiliitepuu . $t^{{-1}}$

Sisäkkäinen jälkiliite on jälkiliite, joka sisältyy merkkijonoon t jossain muualla. Pisintä sisäkkäistä päätettä kutsutaan merkkijonon t aktiiviseksi päätteeksi .

Suffiksipuiden ominaisuudet

Lemma. W : n sijainti on eksplisiittinen kompaktissa suffiksipuussa, jos ja vain jos w on t : n ei-sisäkkäinen pääte tai w on oikea haara.

Todiste. . Jos se on eksplisiittinen, se voi olla joko lehti tai haarapiste tai juuri (tässä tapauksessa w on myös t :n sisäkkäinen pääte ). $\Nuoli oikealle$ $\overline {w}$ $w=\varepsilon$

Jos on lehti, niin se on myös jälkiliite t . Se ei siis saa olla sisäkkäinen pääte, koska muuten se esiintyisi jossain muualla merkkijonossa t : v on t:n pääte siten , että w on v : n etuliite . Tämä solmu ei voi olla lehti. $\overline {w}$ $\olemassa$

Jos on haarasolmu, lähtevää reunaa on oltava vähintään kaksi eri tunnisteilla. Tämä tarkoittaa, että on olemassa kaksi erilaista päätettä u , v , että w on u :n etuliite ja w on v:n etuliite , missä v = wxs , u = , x . Siksi w on oikea haara. $\overline {w}$ $\overline {w}$ $wx:n$ $\neq x'$

$\Vasen nuoli$ . Jos w on t :n sisäkkäinen pääte , sen on oltava lehti. Jos w on oikea haara, on kaksi päätettä u ja v , u = wxs , v = , x , silloin w on haarasolmu. Lemma on todistettu . $wx:n$ $\neq x'$

Nyt on helppo ymmärtää, miksi vastaus kysymykseen, onko sana w merkkijonossa t , löytyy O(|w|) -ajassa : tarvitsee vain tarkistaa, onko w sijainti (eksplisiittinen vai implisiittinen) kielessä cst( t ).

Reunatunnisteiden tulee olla osoittimia merkkijonon paikkaan, jotta suffiksipuu kuluttaa O(n) muistia . Reunanimike (p, q) tarkoittaa alimerkkijonoa tai tyhjää merkkijonoa, jos p > q. $t_{p}\ldots t_{q}$

Ukkonen ottaa käyttöön nimen avoimet reunat lehtiin päättyville reunoille. Avoimen reunan otsikot kirjoitetaan muodossa (p, ) $\infty$ eikä (p, |t|) , missä on pituus, aina suurempi kuin |t| . $\infty$

Olkoon T -puu . Olkoon solmu T , v on pisin pääte w , joka on myös solmu T . Merkitsemätöntä reunaa välillä - kutsutaan suffiksilinkiksi . Jos v = w , sitä kutsutaan atomiksi . $\Sigma ^{+}$ $\overline {aw}$ $\overline {v}$ $\overline {aw}$ $\overline {v}$

lausunto. Kohdissa ast( t ) ja cst( t$ ), missä $ t , kaikki suffiksilinkit ovat atomisia. $\ei sisällä$

Todiste. $ -symbolia kutsutaan vartijasymboliksi . Ensimmäinen osa (ast( t )) seuraa määritelmästä, koska sijainnit ovat eksplisiittisiä. Todistaaksemme toisen osan (tapaus cst( t )) on osoitettava, että jokaiselle solmulle on myös solmu cst( t ). Jos on solmu cst( t ), se on joko lehti tai haarasolmu. Jos on lehti, aw ei ole t :n sisäkkäinen jälkiliite . Vartiosymbolin ansiosta lemmasta seuraa, että kaikki jälkiliitteet (myös juuri, tyhjä pääte) ovat eksplisiittisiä, koska vain juuri on upotettu jälkiliite. Siksi w on lehti tai juuri. Jos on haarasolmu, niin aw on oikea haara, kuten w . Siksi sijainti on eksplisiittinen lemmalla. Väite on todistettu. $\overline {aw}$ $\overline {w}$ $\overline {aw}$ $\overline {aw}$ $\overline {w}$

Kuten tästä todistuksesta seuraa, vartiosymboli takaa lehtien olemassaolon kaikille päätteille. Tällaisella merkillä ei voi olla muita sisäkkäisiä jälkiliitteitä kuin tyhjiä. Jos jätämme pois vartijamerkin, jotkin jälkiliitteet saattavat sisäkkäin ja niiden sijainnit tulevat epäsuoraksi.

Suffiksipuun muistivaatimukset

lausunto. Kompakti suffiksipuu voidaan esittää muodossa, joka vaatii O(n) muistia.

Todiste. Suffiksipuussa on korkeintaan yksi lehti päätettä kohden (täsmälleen yksi, jossa on huoltajamerkki). Jokaisen sisäisen solmun on oltava haarasolmu, joten sisäisellä solmulla on vähintään kaksi lasta. Jokainen haara lisää lehtien määrää vähintään yhdellä, joten meillä on enintään n sisäistä solmua ja enintään n lehtiä.

Käytämme lähdemerkkijonon indeksointia edellä kuvatulla tavalla edustaaksemme merkkijonoja, jotka ovat reunatunnisteita. Jokaisella solmulla on enintään yksi vanhempi, joten reunojen kokonaismäärä ei ylitä 2n .

Vastaavasti jokaisessa solmussa on enintään yksi suffiksilinkki, jolloin myös suffiksilinkkien kokonaismäärä on rajoitettu 2n :ään . Väite on todistettu.

Esimerkkinä suffiksipuusta, jossa on 2n-1 solmua, harkitse sanan puuta . Merkkijonon t atomiliitepuun koko on O( ) . $a^{n}\$$ $n^{2}$

Puun rakentaminen lineaarisessa ajassa. mcc- algoritmi . (McCreight's Algorithm)

Mcc - algoritmi alkaa tyhjästä puusta ja lisää jälkiliitteitä pisimmästä alkaen. Mcc - algoritmi ei ole online-algoritmi, eli sen toimintaan tarvitaan koko rivi. Oikea toiminta edellyttää, että merkkijono päätetään muista erillään olevalla erikoismerkillä, jotta mikään pääte ei ole toisen päätteen etuliite. Jokainen puun pääte vastaa lehteä. Algoritmille määritetään - nykyinen pääte (vaiheessa ), ( head ) - päätteen suurin etuliite , joka on myös toisen päätteen etuliite , jossa . ( häntä ) määritellään . $suf_{i}$ $i$ $pää_{i}$ $suf_{i}$ $suf_{j}$ $j<i$ $häntä_{i}$ $suf_{i}-head_{i}$

Mcc-algoritmin avainidea on suhde ja . $pää_{i}$ $pää_{{i-1}}$

Lemma. Jos missä on aakkosten kirjain, on merkkijono (voi olla tyhjä), niin on etuliite . $head_{{i-1}}=aw$ $a$ $w$ $w$ $pää_{i}$

Todiste. Anna . Sitten on olemassa , sellainen, joka on sekä etuliite että etuliite . Sitten on etuliite ja on siksi pään etuliite . Lemma on todistettu. $head_{{i-1}}=aw$ $j$ $j<i$ $aw$ $suf_{{i-1}}$ $suf_{{j-1}}$ $w$ $suf_{i}$ $suf_{j}$ $w$ $pää_{i}$

Tiedämme sijainnin , ja jos meillä on jälkiliitteen linkki, voimme nopeasti hypätä pääetuliitteen sijaintiin ilman , että meidän tarvitsee löytää polkua puun juuresta. Mutta sijainti ei ehkä ole eksplisiittinen (jos sijainti ei ollut eksplisiittinen edellisessä vaiheessa) ja päätelinkkiä ei ehkä ole vielä asetettu solmulle . McCrayn ratkaisu löytää solmun kahdessa vaiheessa: "uudelleenskannaus" ja "skannaus". Kuljemme puuta ylös solmusta, kunnes löydämme päätelinkin, seuraamme sitä ja skannaamme sitten polun uudelleen sijaintiin (mikä on yksinkertaista, koska tiedämme pituuden ja sijainnin olemassa, joten meidän ei tarvitse lukea koko reunaa tarrat liikkuvat alas puussa, voimme vain tarkistaa vain alkukirjaimet ja sanojen pituuden). $head_{{i-1}}=aw$ $w$ $pää_{i}$ $\overline {w}$ $\overline {head_{{i-1}}}$ $\overline {head_{{i-1}}}$ $\overline {head_{i}}$ $\overline {head_{{i-1}}}$ $w$ $w$

Kuva osoittaa tämän ajatuksen. Sen sijaan , että algoritmi yrittäisi löytää polun juuresta solmuun , se hyppää kohtaan , seuraa päätettä kohtaan , skannaa uudelleen polun (mahdollisesti implisiittiseen) sijaintiin ja jää löytääkseen polun osoitteeseen , kiertäen merkki merkiltä. $f$ $a$ $d$ $e$ $f$

Algoritmi koostuu kolmesta osasta.

1. Ensin se määrittää edellisen pään rakenteen, etsii seuraavan käytettävissä olevan suffiksilinkin ja seuraa sitä.

2. Sen jälkeen se skannaa uudelleen sen osan edellisestä päästä, jonka pituus on tiedossa (tämä osa on nimeltään ). $\beeta$

3. Lopuksi algoritmi asettaa loppuliitteen linkin , skannaa loput (nimeltään ) ja lisää uuden lehden kohteelle . $pää_{{i-1}}$ $pää_{i}$ $\gamma$ $häntä_{i}$

Haarasolmu luodaan uudelleenskannauksen toisessa vaiheessa, jos sijaintia ei ole olemassa . Tässä tapauksessa skannaus ei ole tarpeen, koska jos se olisi pidempi kuin , niin se olisi oikea haara, mutta lemman mukaan se on myös oikea haara, joten solmun täytyy olla jo olemassa. Solmu luodaan kolmannessa vaiheessa, jos sijainti ei ole jo selvä. $w$ $pää_{i}$ $\alpha \beta$ $\alpha \beta \gamma$ $\alpha \beta$ $\overline {\alpha \beta }$ $\overline {head_{i}}$

Algoritmi 1 (mcc, McCreight) Syöte: merkkijono t 1: T : = tyhjä puu; 2: pää 0 := ;

\epsilon

3: n := pituus(t) ; 4: i : = 1 - n tee 5: etsi , , sellainen, että

\chi

\alpha

\beeta

a. pää i-1 = ,

\chi \alpha \beta

b. jos solmun pään i-1 esi-isä ei ole juuri ( root ), merkitse se , muuten c. ja ( | pää i-1 |=0)

\overline {\chi \alpha }

|\alpha |=0

|\chi |\leq 1

|\chi |=0\Nuoli vasemmalle oikealle

6: jos ( >0) niin 7: seuraa päätelinkkiä solmusta ;

|\alpha |

\overline {\chi \alpha }

\overline {\alpha }

8: loppu jos 9: := Tarkista uudelleen( ) ;

\overline {\alpha \beta }

\overline {\alpha },\beta

10: aseta liitelinkki arvoon 11: ( , tail i ) := Tarkista ( , suf i - );

\overline {head_{{i-1}}}

\overline {\alpha \beta }

\overline {head_{{i}}}

\overline {\alpha \beta }

\alpha \beta

12: lisää häntää i vastaava lehti ; 13: loppu for

Huomaa, että jos silloin ja tunnistetaan yhtä nopeasti kuin algoritmin rivin 7 mukaisen jälkiliitteen linkin jälkeen. $|\alpha |=0$ $\overline {\alpha }=juuri$

Uudelleenskannaus etsii paikan . Jos sijainti ei ole vielä selvä, uusi solmu lisätään. Tämä tapaus tapahtuu, kun päätä ( ) tarkastellaan kokonaisuudessaan: jos pää on pidempi (ja solmu on jo määritetty), sen on oltava useamman kuin kahden päätteen etuliite ja se on myös :n vasen haara . Sijainti voi olla eksplisiittinen vain, jos kyseinen solmu on jo haarasolmu, ja jos vasenta haaraa ei ollut, sen täytyi olla pidempi, koska havaittiin pidempi etuliite. $\alpha \beta$ $\overline {\alpha \beta }$ $pää$ $\alpha \beta$ $t$ $\overline {\alpha \beta }$ $\alpha \beta$ $pää_{{i-1}}$

Scan - toiminto etsii puun syvyyttä ja palauttaa sijainnin.

Toimenpide 1 Uudelleenskannaus(n, ) Syöte : solmu n , rivi 1: i :=1;

\beeta

\beeta

2: kun minä | | tee 3: etsi reuna e=n n' , w 1 = 1 ;

\leq

\beeta

{{\stackrel {w}{\longrightarrow }}}

\beeta

4: jos i +| w |>| |+1 sitten 5: k :=| -i +1 ;

\beeta

\beeta

6: jaa reuna e uudella solmulla m ja reunat n m ja m n' ;

{{\stackrel {w_{1}\ldots w_{k}}{\longrightarrow }}}

{{\stackrel {w_{{k+1}}\ldots w_{{|w|}}}{\longrightarrow }}}

7: paluu m ; 8: loppu, jos 9: i := i +| w |; 10: n := n' ; 11: loppu, kun 12: paluu n' ; Toimenpide 2 Scan(n, ) Syöte : solmu n , rivi 1: i :=1;

\gamma

\gamma

2: vaikka on reuna e = n n' , w 1 = i do 3: k :=1;

{{\stackrel {w}{\longrightarrow }}}

\gamma

4: kun taas w k = i ja k | w | do 5: k := k +1;

\gamma

\leq

6: i := i +1; 7: loppu, kun taas 8: jos k >| w | sitten 9: n := n' ; 10: else 11: jaa reuna e uudella solmulla m ja reunat n m ja m n' ;

{{\stackrel {w_{1}\ldots w_{{k-1}}}{\longrightarrow }}}

{{\stackrel {w_{{k}}\ldots w_{{|w|}}}{\longrightarrow }}}

12: paluu ( m , i ,..., );

\gamma

\gamma _{{|\gamma |}}

13: end if 14: end while 15: return ( n , i ,..., );

\gamma

\gamma _{{|\gamma |}}

Puun rakentaminen lineaarisessa ajassa. ukk- algoritmi . (Ukkosen algoritmi)

Algoritmi, jonka Esko Ukkonen keksi suffiksipuun rakentamiseen lineaarisessa ajassa, on luultavasti yksinkertaisin näistä algoritmeista. Yksinkertaisuus johtuu siitä, että algoritmia voidaan alun perin ajatella yksinkertaisena, mutta tehottomana menetelmänä, joka muutamalla "terveen järjen" toteutuksella saavuttaa parhaiden algoritmien tason suoritusajan suhteen pahimmissakin olosuhteissa. Sama asia tehdään PDF - muodossa kuvien kanssa .

Yksityiskohtainen selitys algoritmista ja toteutuksesta C++ :ssa: cs.mipt.ru (venäjäksi) ja marknelson.us (englanniksi)

Tarvitsemme Ukkosen-algoritmille

1) Implisiittiset suffiksipuut 2) Algoritmin yleinen kuvaus 3) Algoritmin optimointi

Implisiittiset suffiksipuut.

Ukkosen algoritmi rakentaa sekvenssin implisiittisiä suffiksipuita, joista viimeinen muunnetaan todelliseksi merkkijonoliitepuuksi S .

Неявное суффиксное дерево строки S — это дерево, полученное из суффиксного дерева S$ удалением всех вхождений терминального символа $ из меток дуг дерева, удалением после этого дуг без меток и удалением затем вершин, имеющих меньше двух детей. Неявное суффиксное дерево префикса S[l..i] строки S аналогично получается из суффиксного дерева для S[l..i]$ удалением символов $, дуг и вершин, как описано выше.

Minkä tahansa merkkijonon S implisiittisessä suffiksipuussa on vähemmän lehtiä kuin merkkijonon S$ suffiksipuussa, jos ainakin yksi S:n jälkiliitteistä on toisen päätteen etuliite. Terminaali $ lisättiin S:n loppuun vain tämän tilanteen välttämiseksi. Tämä on erittäin tärkeä seikka määritettäessä todellista suffiksipuuta. Jos S kuitenkin päättyy merkkiin, joka ei esiinny missään muualla S:ssä, S:n implisiittisessä suffiksipuussa on lehti jokaiselle päätteelle ja se on siksi todellinen suffiksipuu.

Vaikka implisiittisessä suffiksipuussa ei välttämättä ole lehtiä kaikille päätteille, se koodaa kaikki suffiksit S - jokainen lausutaan jonkin polun merkeillä tämän implisiittisen suffiksipuun juuresta. Jos tämä polku ei kuitenkaan pääty lehtiin, polun loppua osoittavaa merkkiä ei ole. Siten implisiittiset suffiksipuut itsessään ovat hieman vähemmän informatiivisia kuin todelliset. Käytämme niitä vain apuvälineenä Ukkosen algoritmille, jotta saadaan oikea suffiksipuu S:lle.

Algoritmin yleinen kuvaus.

Построить дерево T1 for i from 1 to m - 1 do begin {фаза i + 1} for j from 1 to i + 1 begin {продолжение j} найти в текущем дереве конец пути из корня с меткой S[j..i]. Если нужно, продолжить путь, добавив символ S(i + 1), обеспечив появление строки S[j..i + 1] в дереве, end; end;

Ukkosen algoritmi rakentaa implisiittisen suffiksipuun T i jokaiselle merkkijonon S etuliitteelle S[l..i] alkaen T 1 :stä ja kasvattaen i:tä yhdellä, kunnes rakennetaan T m . S:n todellinen suffiksipuu tulee T m :stä ja koko työ vie O(m) aikaa. Selitämme Ukkosen algoritmin esittämällä ensin menetelmän, jolla kaikki puut rakennetaan O(m³) ajassa ja sitten optimoidaan tämän menetelmän toteutus niin, että ilmoitettu nopeus saavutetaan.

Kolme sääntöä päätteen jatkamiselle.

Muuttaaksemme tämän yleisen kuvauksen algoritmiksi, meidän on määritettävä tarkasti, kuinka päätteen jatkaminen suoritetaan. Olkoon S[j..i] = β S[1..i]:n pääte. Jatkossa j, kun algoritmi löytää pään β nykyisestä puusta, se jatkaa β:ta varmistaakseen, että suffiksi βS(i + 1) on puussa. Algoritmi toimii yhden seuraavista kolmesta säännöstä mukaan.

Sääntö 1. Nykyisessä puussa polku β päättyy lehtiin. Tämä tarkoittaa, että polku β:lla merkitystä juuresta menee jonkin "lehti" kaaren loppuun (lehteen sisältyvä kaari). Kun vaihdat puuta, lisää symboli S(i + 1) tämän lehtikaaren etiketin loppuun.

Sääntö 2. Mikään polku merkkijonon β lopusta ei ala S(i + 1), mutta sieltä alkaa ainakin yksi polku. Tässä tapauksessa on luotava uusi lehtikaari, joka alkaa β:n lopusta ja merkitään symbolilla S(i + 1). Tässä tapauksessa, jos β päättyy kaaren sisään, on luotava uusi kärki. Uuden lehtikaaren lopussa olevalle lehdelle annetaan numero j. Siten säännössä 2 kaksi tapausta on mahdollista.

Sääntö 3. Jokin polku merkkijonon β lopusta alkaa symbolilla S(i + 1). Tässä tapauksessa merkkijono βS(i + 1) on jo nykyisessä puussa, joten mitään ei tarvitse tehdä (implisiittisessä suffiksipuussa loppuliitteen loppua ei tarvitse merkitä eksplisiittisesti).

Hae päätepuusta

Anna tekstin antaa ja syötteeseen tulee joukko kuvioita. Kun tekstistä on rakennettu Ukkosen-algoritmilla suffiksipuu, jokaista kuviota voi hakea seuraavasti:

Saapuvien kuvioiden symbolien mukaan läpikulku suoritetaan rakennetussa suffiksipuussa, kunnes joko kuvion symbolit ovat loppuneet tai seuraava vastaavuus tulee mahdottomaksi.
1. Anna kuviosymbolien loppua.
  1. Tällöin jokaisen alipuun lehden numerona viimeisimmän osuman pisteestä alkaen on kuvion alkusijainti tekstissä.
  2. Nyt on mahdollista löytää kuvion k aloituskohtaa kulkemalla alipuun poikki täsmäytyspolun lopusta lineaarisessa läpikäymisessä, kuten syvyys- tai leveyshaku, ja huomioimalla havaitut lehtien numerot.
  3. Tämä toimii viivalle asemien lukumäärästä, koska jokaisessa sisäisessä kärjessä on vähintään kaksi lasta ja lehtien lukumäärä polulla on verrannollinen kuljetettujen kaarien määrään.
2. Toisessa tapauksessa, kun uutta vastaavuutta ei ole, tekstissä ei ole kuviota.
3. Jos haluat löytää vain yhden esiintymän, sinun on muutettava esikäsittelyä kirjoittamalla jokaiseen kärkeen alipuun pienimmän lehden numero.

Yleistetty suffiksipuu

Suffiksipuu voidaan rakentaa merkkijonojoukolle merkkijonojen ketjutuksella tai ilman. ${\displaystyle S_{1},S_{2},\dots ,S_{n))$

Merkkijonojen ketjutus

Lisäämme jokaisen rivin loppuun erilaisia vartijamerkkejä (aakkosten ulkopuolisia merkkejä).
Yhdistetään ne kaikki yhdeksi.
Rakennamme tälle riville suffiksipuun.
Tämän puun lehtien numeroissa on numeropareja, joista ensimmäinen vastaa merkkijonoa ja toinen sen aloituspaikkaa. $Si}$

Tämä lähestymistapa on ongelmallinen synteettisten päätteiden läsnäolon vuoksi, mutta tämä ratkaistaan pienentämällä suffiksiparin toinen indeksi kaarissa lehtien kärkipisteisiin.

Ilman merkkijonojen ketjutusta

Tässä algoritmissa ei ole synteettisiä jälkiliitteitä.

Suffiksipuun rakentaminen merkkijonolle . $S_{1}\$$
Etsimme sarjan ensimmäisiä osumia . $l$ ${\displaystyle S_{1},S_{2))$
Loppuliitteen puussa täytämme sanan . $S_{1}$ $S_{2}[l+1\dots n]\$$
Joten seuraaville riveille.

On otettava huomioon, että eri kaareilla tiivistetyt etiketit voivat viitata eri merkkijonoihin, joten kaarille on tallennettava kolme numeroa.

Kahden merkkijonon jälkiliitteet voivat täsmää, mutta samaan aikaan mikään jälkiliite ei ole toisen päätteen etuliite (sentinellin vuoksi). Tämän jälkeen lehti osoittaa kaikkiin tämän päätteen merkkijonoihin ja alkuasentoihin.

Vertailu avainpuihin

Kuviojoukon löytämisen ongelman ratkaisemiseksi on Aho-Korasik-algoritmi. Se etsii kaikki esiintymät: - kuvioiden kokonaispituus, T - tekstin pituus, k - esiintymien lukumäärä. ${\näyttötyyli O(P+T+k),P}$

Asymptoottisesti kaikkien esiintymien löytäminen suffiksipuusta vie yhtä paljon aikaa. Mutta tosiasia on, että Aho-Korasik käyttää muistia avainpuulle , aikaa rakentamiseen ja aikaa etsimiseen . Mutta suffiksipuu vie muistia , aikaa - rakentamista ja etsintää. $O(P)$ $O(P)$ $O(T)$ $O(T)$ $O(T)$ $O(P)$

Eli jos näytteitä on paljon ja enemmän kuin tekstiä, loppuliitepuu on pieni, mutta sen etsiminen kestää kauan. Muuten Aho-Korasik, kun kuviot ovat lyhyitä ja teksti on suurempi, vie vähemmän muistia, mutta suffiksipuuta haetaan nopeammin.

Siten valinta yhden tai toisen välillä riippuu rajaajasta tai muistista.

Katso myös

Kirjallisuus

Gasfield D. Merkkijonot, puut ja sekvenssit algoritmeissa: Informatiikka ja laskennallinen biologia / Per. englannista. I. V. Romanovski. - 2. painos - Pietari. : Nevskin murre, 2003. - 654 s.
Smith B. Methods and algoritms for computing on strings = Computing Patterns in Strings. - M .: Williams, 2006. - 496 s. - ISBN 5-8459-1081-1 , 0-201-39839-7.
Okulov S. M. Algoritmit merkkijonojen käsittelyyn. - M. : Binom, 2013. - 255 s. - ISBN 978-5-9963016-2-1 .

Linkit

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