Suffiks træ

Et suffikstræ er et bor , der indeholder alle suffikserne af en eller anden streng (og kun dem). Giver dig mulighed for at finde ud af, om strengen w er inkluderet i den oprindelige streng t i O (|w|) tid , hvor |w| er længden af strengen w .

Grundlæggende definitioner og beskrivelse af strukturen

$\Sigma$ er et ikke-tomt, endeligt sæt af symboler, kaldet alfabetet. En sekvens af tegn (evt. tomme) fra alfabetet er angivet med bogstaverne r , s og t . er en omvendt streng. Individuelle tegn er angivet med bogstaverne x, y eller z. - tom linje. $t^{{-1}}$ $\varepsilon$
Symbolerne fra alfabetet er bogstaverne a, b, … . Mens størrelsen af alfabetet tages konstant. |t| angiver længden af strengen t . er alle strenge af længden m, og . $\Sigma ^{m}$ $\Sigma ^{*}=\bigcup \limits _{{i=0}}^({\infty }}\Sigma ^{i}$ $\Sigma ^{+}=\Sigma ^{*}\backslash \{\varepsilon \}$

Præfikset w for strengen t er en streng sådan, at wv = t for en eller anden (muligvis tom) streng v . Et præfiks kaldes egentlig, hvis |v| 0. $\neq$

W -suffikset af strengen t er en streng sådan, at vw = t for en eller anden (muligvis tom) streng v . Et suffiks kaldes egentlig, hvis |v| 0. For eksempel, for strengen "understreng", er understrengen "sub" sit eget præfiks, "ring" er sit eget suffiks. $\neq$

En delstreng w af en streng t kaldes en højre gren , hvis t kan repræsenteres som for nogle strenge og såvel som bogstaver x y . Den venstre gren er defineret på samme måde. For eksempel, for "eabceeabcd", er understrengen "abc" den højre gren, da der i begge dens forekomster i t er forskellige tegn til højre for den, men den samme understreng er ikke en venstre gren, fordi det samme tegn " e". $uwxv$ $u'wyv'$ $u,v,u'$ $v'$ $\neq$

$\Sigma ^{+}$ - træ T er et rodfæstet træ med kanter mærket med sekvenser fra . For hvert tegn a fra alfabetet har hver node i træet T højst én kant, hvis etiket starter med tegnet a . En kant fra t til s med etiket v vil blive betegnet med . $\Sigma ^{+}$ $t\longrightarrow _{v}s$

Lad k være en node af -træet T , så er sti(k) en streng, der er sammenkædningen af alle kantetiketter fra roden til k . Vi kalder stedet w for hvilken sti( ) = w . $\Sigma ^{+}$ $\overline {w}$ $\overline {w}$

Da hver gren er unik, hvis path( t ) = w , kan vi udpege node t som . Undertræet af en node er betegnet med . De ord, der er repræsenteret i -træet T , er givet ved en mængde, som er betegnet med ord( T ). Ordet w er inkluderet i mængdeordene( T ), hvis og kun hvis der eksisterer en streng v (muligvis tom), sådan som er en node i træet T . $\overline {w}$ $\overline {w}$ $T_{{\overline {w))}$ $\Sigma ^{+}$ $\overline {wv}$

Hvis strengen w er inkluderet i ord( T ), w = uv , er en knude på træet T , vil parret blive kaldt et linkpar w i forhold til træet T . Hvis u er det længste præfiks, som er et linkpar, vil vi kalde det et kanonisk linkpar . Så skriver vi . En placering siges at være eksplicit, hvis |v| = 0, og implicit ellers. $\overline {u}$ $(\overline {u},v)$ $(\overline {u},v)$ $(\overline {u},v)$ $\widehat {w}=(\overline {u},v)$ $\widehat {w}=(\overline {u},v)$

$\Sigma ^{+}$ -træ T , hvor hver kant er mærket med et enkelt symbol, kaldes atomisk (for det er hver placering eksplicit). -træ T , hvor hver knude er enten en rod eller en blad- eller grenknude, kaldes kompakt . $\Sigma ^{+}$

Et atomtræ kaldes også en (bjælke). Et atom- og et kompakt- træ er unikt defineret af de ord, de indeholder. $\Sigma ^{+}$ $prøve$ $\Sigma ^{+}$

Suffikstræet for streng t er et -træ således, at ord( T ) = { w | w er et underord til t }. For en streng t betegnes atomsuffikstræet ast( t ), det kompakte suffikstræ betegnes cst( t ). $\Sigma ^{+}$

Det omvendte præfikstræ for strengen t er suffikstræet for strengen . $t^{{-1}}$

Et indlejret suffiks er et suffiks, der er inkluderet i strengen t et andet sted. Det længste indlejrede suffiks kaldes det aktive suffiks af strengen t .

Egenskaber for suffikstræer

Lemma. Placeringen af w er eksplicit i et kompakt suffikstræ, hvis og kun hvis w er et ikke-indlejret suffiks af t eller w er en højre gren.

Bevis. . Hvis det er eksplicit, så kan det enten være et blad eller et grenspids eller en rod (i dette tilfælde er w også et indlejret suffiks af t ). $\Højre pil$ $\overline {w}$ $w=\varepsilon$

Hvis er et blad, så er det også et suffiks t . Så det må ikke være et indlejret suffiks, for ellers ville det optræde et andet sted i strengen t : v er et suffiks af t sådan at w er et præfiks til v . Denne node kan ikke være et blad. $\overline {w}$ $\eksisterer$

Hvis er en grenknude, så skal der være mindst to udgående kanter fra med forskellige etiketter. Det betyder, at der er to forskellige suffikser u , v , at w er et præfiks for u og w er et præfiks til v , hvor v = wxs , u = , x . Derfor er w en højre gren. $\overline {w}$ $\overline {w}$ $wx'$ $\neq x'$

$\Venstre pil$ . Hvis w er et ikke-indlejret suffiks af t , skal det være et blad. Hvis w er en højre gren, så er der to suffikser u og v , u = wxs , v = , x , så er w en grenknude. Lemmaet er bevist . $wx'$ $\neq x'$

Nu er det let at se, hvorfor svaret på spørgsmålet om ordet w er i strengen t kan findes i O(|w|) tid : man behøver kun at tjekke om w er en placering (eksplicit eller implicit) i cst( t ).

Kantetiketterne skal være pointere til positionen i strengen, så suffikstræet bruger O(n) -hukommelse . Kantetiketten (p, q) betyder en understreng eller den tomme streng, hvis p > q. $t_{p}\ldots t_{q}$

Ukkonen introducerer navnet åbne kanter for kanter, der ender med blade. Åbne kantetiketter skrives som (p, ) $\infty$ i stedet for (p, |t|) , hvor er længden, altid større end |t| . $\infty$

Lad T være et -træ. Lad være et knudepunkt T , v være det længste suffiks w sådan som også er en knude T . En umærket kant fra til kaldes et suffikslink . Hvis v = w , kaldes det atomare . $\Sigma ^{+}$ $\overline {aw}$ $\overline {v}$ $\overline {aw}$ $\overline {v}$

Udmelding. I ast( t ) og cst( t$ ), hvor $ t , er alle suffikslinks atomare. $\ikke i$

Bevis. $ -symbolet kaldes vagtsymbolet . Den første del (for ast( t )) følger af definitionen, da placeringerne er eksplicitte. For at bevise den anden del (tilfælde cst( t )) skal vi vise, at for hver knude er også en knude cst( t ). Hvis er en knude cst( t ), så er det enten et blad eller en grenknude. Hvis er et blad, så er aw ikke et indlejret suffiks af t . Takket være vagtsymbolet følger det af lemmaet, at alle suffikser (inklusive roden, det tomme suffiks) er eksplicitte, da kun roden er et indlejret suffiks. Derfor er w et blad eller en rod. Hvis er en grenknude, så er aw en højre gren, ligesom w er det . Derfor er placeringen eksplicit ved lemmaet. Påstanden er blevet bevist. $\overline {aw}$ $\overline {w}$ $\overline {aw}$ $\overline {aw}$ $\overline {w}$

Som det følger af dette bevis, garanterer vagtsymbolet eksistensen af blade for alle suffikser. Med et sådant tegn kan der ikke være andre indlejrede suffikser end tomme. Hvis vi udelader guard-karakteren, kan nogle suffikser blive indlejrede, og deres placeringer bliver implicitte.

Suffikstræhukommelseskrav

Udmelding. Et kompakt suffikstræ kan repræsenteres i en form, der kræver O(n) -hukommelse.

Bevis. Endelsestræet indeholder højst et blad pr. endelse (nøjagtig et med vogterkarakter). Hver intern node skal være en grenknude, så en intern node har mindst to børn. Hver gren øger antallet af blade med mindst én, så vi har højst n interne noder og højst n blade.

For at repræsentere strenge, der er kantetiketter, bruger vi indeksering på kildestrengen, som beskrevet ovenfor. Hver node har højst én forælder, og det samlede antal kanter overstiger derfor ikke 2n .

På samme måde har hver node højst et suffikslink, så er det samlede antal suffikslinks også begrænset til 2n . Påstanden er blevet bevist.

Som et eksempel på et suffikstræ med 2n-1 noder kan du overveje træet for ordet . Størrelsen af det atomare suffikstræ for streng t er O( ) . $a^{n}\$$ $n^{2}$

At bygge et træ i lineær tid. mcc algoritme . (McCreight's Algorithm)

Mcc - algoritmen starter med et tomt træ og tilføjer suffikser startende fra det længste. Mcc - algoritmen er ikke en online-algoritme, det vil sige, at hele linjen er nødvendig for dens drift. Korrekt betjening kræver, at strengen afsluttes med et specialtegn, der adskiller sig fra de andre, således at intet suffiks er et præfiks til et andet suffiks. Hvert suffiks i træet svarer til et blad. For algoritmen definerer vi - det aktuelle suffiks (i trin ), ( head ) - det største præfiks for suffikset , som også er præfikset for et andet suffiks , hvor . ( hale ) definere som . $suf_{i}$ $jeg$ $hoved_{i}$ $suf_{i}$ $suf_{j}$ $j<i$ $hale_{i}$ $suf_{i}-head_{i}$

Nøgleideen med mcc- algoritmen er forholdet mellem og . $hoved_{i}$ $hoved_{{i-1}}$

Lemma. Hvis hvor er et bogstav i alfabetet, er en streng (kan være tom), så er et præfiks . $head_{{i-1}}=aw$ $-en$ $w$ $w$ $hoved_{i}$

Bevis. Lad . Så findes der , , sådan som både er et præfiks på og et præfiks på . Så er et præfiks og er derfor et præfiks for hovedet . Lemmaet er bevist. $head_{{i-1}}=aw$ $j$ $j<i$ $aw$ $suf_{{i-1}}$ $suf_{{j-1}}$ $w$ $suf_{i}$ $suf_{j}$ $w$ $hoved_{i}$

Vi kender placeringen af , og hvis vi har et suffikslink, kan vi hurtigt hoppe til placeringen af hovedpræfikset uden at skulle finde stien fra træets rod. Men placeringen er muligvis ikke eksplicit (hvis placeringen ikke var eksplicit i det forrige trin), og suffikslinket er muligvis endnu ikke indstillet til node . McCrays løsning finder en node i to trin: "genscanning" og "scanning". Vi krydser træet op fra knudepunktet , indtil vi finder et suffikslink, følger det og scanner derefter stien til placeringen igen (hvilket er enkelt, fordi vi ved, at længden og placeringen eksisterer, så vi ikke behøver at læse hele kanten etiketter, der bevæger sig ned på træet, kan vi bare kontrollere kun begyndelsesbogstaverne og længden af ordene). $head_{{i-1}}=aw$ $w$ $hoved_{i}$ $\overline {w}$ $\overline {head_{{i-1}}}$ $\overline {head_{{i-1}}}$ $\overline {hoved_{i}}$ $\overline {head_{{i-1}}}$ $w$ $w$

Figuren viser denne idé. I stedet for at forsøge at finde en sti fra roden til knudepunktet , springer algoritmen til , følger suffikset til , genscanner stien til den (muligvis implicitte) placering og forbliver for at finde stien til , krydsende tegn for tegn. $f$ $-en$ $d$ $e$ $f$

Algoritmen består af tre dele.

1. Først bestemmer den strukturen af det forrige hoved, finder det næste tilgængelige suffikslink og følger det.

2. Den scanner derefter den del af det forrige hoved, som længden er kendt for (denne del hedder ). $\beta$

3. Til sidst sætter algoritmen suffikslinket for , scanner resten (navngivet ) og tilføjer et nyt blad for . $hoved_{{i-1}}$ $hoved_{i}$ $\gamma$ $hale_{i}$

En grenknude oprettes i anden fase af genscanningen, hvis der ikke findes en lokation . I dette tilfælde er scanningen ikke nødvendig, for hvis den var længere end , så ville det være en højre gren, men ved lemmaet er det også en højre gren, så noden skal allerede eksistere. Noden oprettes i tredje fase, hvis placeringen ikke allerede er eksplicit. $w$ $hoved_{i}$ $\alfa \beta$ $\alfa \beta \gamma$ $\alfa \beta$ $\overline {\alpha \beta }$ $\overline {hoved_{i}}$

Algoritme 1 (mcc, McCreight) Input: streng t 1: T : = tomt træ; 2: hoved 0 := ;

\epsilon

3: n := længde(t) ; 4: for i := 1 til n gør 5: find , , sådan at

\chi

\alfa

\beta

en. hoved i-1 = ,

\chi \alfa \beta

b. hvis forfaderen til nodehovedet i -1 ikke er roden ( rod ), angiv den , ellers c. og ( | hoved i-1 |=0)

\overline {\chi \alpha }

|\alpha |=0

|\chi |\leq 1

|\chi |=0\venstrehøjrepil

6: hvis ( >0) så 7: følg suffikslinket fra node til ;

|\alfa |

\overline {\chi \alpha }

\overline {\alpha }

8: end if 9: := Rescan( ) ;

\overline {\alpha \beta }

\overline {\alpha },\beta

10: sæt suffikslink fra til 11: ( , hale i ) := Scan ( , suf i - );

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

\overline {\alpha \beta }

\overline {hoved_{{i}}}

\overline {\alpha \beta }

\alfa \beta

12: tilføj et blad svarende til hale i ; 13: slut for

Bemærk, at hvis derefter og genkendes lige så hurtigt, som at følge suffikslinket i henhold til linje 7 i algoritmen. $|\alpha |=0$ $\overline {\alpha }=rod$

Genscanningsproceduren leder efter en placering . Hvis placeringen endnu ikke er eksplicit, tilføjes en ny node. Dette tilfælde opstår, når hovedet ( ) ses i sin helhed: hvis hovedet er længere (og noden allerede er defineret), skal det være et præfiks med mere end to suffikser og er også en venstre gren af . En placering kan kun være eksplicit, hvis den knude allerede er en grenknude, og hvis der ikke var nogen venstre gren , må den have været længere, fordi der blev fundet et længere præfiks. $\alfa \beta$ $\overline {\alpha \beta }$ $hoved$ $\alfa \beta$ $t$ $\overline {\alpha \beta }$ $\alfa \beta$ $hoved_{{i-1}}$

Scanningsproceduren søger i træets dybde og returnerer positionen.

Procedure 1 Rescan(n, ) Input : node n , linie 1: i :=1;

\beta

\beta

2: mens jeg | | gør 3: find kant e=n n' , w 1 = 1 ;

\leq

\beta

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

\beta

4: hvis jeg +| w |>| |+1 derefter 5: k :=| | -i +1;

\beta

\beta

6: delt kant e med ny knude m og kanter n m og m n' ;

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

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

7: retur m ; 8: slut hvis 9: i := i +| w |; 10: n := n' ; 11: ende mens 12: returnere n' ; Procedure 2 Scan(n, ) Input : node n , linie 1: i :=1;

\gamma

\gamma

2: mens der er en kant e = n n' , w 1 = i do 3: k :=1;

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

\gamma

4: mens w k = i og k | w | til 5: k := k +1;

\gamma

\leq

6: i := i +1; 7: slut mens 8: hvis k >| w | derefter 9: n := n' ; 10: andet 11: delt kant e med ny node m og kanter n m og m n' ;

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

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

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

\gamma

\gamma _{{|\gamma |}}

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

\gamma

\gamma _{{|\gamma |}}

At bygge et træ i lineær tid. ukk algoritme . (Ukkonens algoritme)

Algoritmen, som Esko Ukkonen opfandt til at bygge et suffikstræ i lineær tid, er sandsynligvis den enkleste af disse algoritmer. Enkelheden kommer af, at algoritmen indledningsvis kan opfattes som en simpel, men ineffektiv metode, der med nogle få "common-sense"-implementeringer når niveauet af de bedste algoritmer i form af køretid under værst tænkelige forhold. Det samme gøres i PDF med figurer .

Detaljeret forklaring af algoritmen og implementeringen i C++ : cs.mipt.ru (på russisk) og marknelson.us (på engelsk)

Til Ukkonen-algoritmen har vi brug for

1) Implicitte suffikstræer 2) Generel beskrivelse af algoritmen 3) Algoritmeoptimering

Implicitte suffikstræer.

Ukkonens algoritme bygger en sekvens af implicitte suffikstræer, hvoraf det sidste konverteres til et ægte strengsuffikstræ S .

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

Det implicitte suffikstræ for enhver streng S vil have færre blade end suffikstræet for streng S$, hvis og kun hvis mindst et af suffikserne af S er et præfiks for et andet suffiks. Terminalen $ blev tilføjet til slutningen af S bare for at undgå denne situation. Ved at definere et rigtigt suffikstræ er dette et meget vigtigt punkt. Men hvis S slutter med et tegn, der ikke optræder andre steder i S, så vil det implicitte suffikstræ for S have et blad for hvert suffiks og er derfor et sandt suffikstræ.

Selvom det implicitte suffikstræ måske ikke har blade for alle suffikser, koder det alle suffikserne S - hver udtales af tegnene på en sti fra roden af dette implicitte suffikstræ. Men hvis denne sti ikke ender med et blad, vil der ikke være nogen markør, der angiver slutningen af stien. Således er implicitte suffikstræer i sig selv noget mindre informative end rigtige. Vi vil kun bruge dem som en hjælp til Ukkonens algoritme for at få et sandt suffikstræ for S.

Generel beskrivelse af algoritmen.

Построить дерево 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;

Ukkonens algoritme bygger et implicit suffikstræ T i for hvert præfiks S[l..i] af streng S, startende ved T 1 og inkrementering i med én, indtil T m er bygget . Det rigtige suffikstræ for S kommer fra T m , og hele jobbet tager O(m) tid. Vi vil forklare Ukkonens algoritme ved først at præsentere en metode, hvorved alle træer bygges i O(m³) tid, og derefter vil vi optimere implementeringen af denne metode, så den deklarerede hastighed opnås.

Tre regler for suffiksfortsættelse.

For at gøre denne generelle beskrivelse til en algoritme, skal vi specificere præcis, hvordan vi udfører suffiksfortsættelse. Lad S[j..i] = β være suffikset af S[1..i]. I fortsættelse j, når algoritmen finder enden β i det aktuelle træ, fortsætter den β for at sikre, at suffikset βS(i + 1) er til stede i træet. Algoritmen fungerer efter en af følgende tre regler.

Regel 1. I det aktuelle træ ender stien β i et blad. Det betyder, at stien fra roden mærket β går til enden af en "blad"-bue (den bue, der er inkluderet i bladet). Når du skifter træ, skal du tilføje symbolet S(i + 1) til enden af etiketten på denne bladbue.

Regel 2. Ingen sti fra enden af strengen β begynder med S(i + 1), men der er mindst én sti, der starter derfra. I dette tilfælde skal der oprettes en ny bladbue, startende i slutningen af β, mærket med symbolet S(i + 1). I dette tilfælde, hvis β ender inde i buen, skal der oprettes et nyt toppunkt. Bladet for enden af den nye bladbue tildeles nummeret j. I regel 2 er der således to tilfælde mulige.

Regel 3. En sti fra enden af strengen β begynder med symbolet S(i + 1). I dette tilfælde er strengen βS(i + 1) allerede i det aktuelle træ, så der skal ikke gøres noget (i et implicit suffikstræ behøver slutningen af suffikset ikke at være markeret eksplicit).

Søg i suffikstræet

Lad teksten være givet og et sæt mønstre kommer til input. Efter at have bygget et suffikstræ fra teksten ved hjælp af Ukkonen-algoritmen, kan hvert mønster søges på følgende måde:

Ifølge symbolerne for indkommende mønstre udføres en gennemgang i det konstruerede suffikstræ, indtil enten symbolerne på mønsteret er opbrugt, eller den næste match bliver umulig.
1. Lad mønstersymbolerne løbe ud.
  1. Derefter har hvert blad i undertræet startende fra punktet for den sidste match som nummer den oprindelige position af mønsteret i teksten.
  2. Det er nu muligt at finde mønsterets k startpositioner ved at krydse undertræet fra slutningen af den matchende sti i en lineær gennemgang, som f.eks. dybde- eller bredde-først søgning, og notere bladnumrene, der er fundet.
  3. Dette fungerer for en linje fra antallet af positioner, da hvert indre toppunkt har mindst to børn, og antallet af blade langs stien er proportional med antallet af gennemkørte buer.
2. I det andet tilfælde, når der ikke er noget nyt match, så er der ikke noget mønster i teksten.
3. Hvis du kun skal finde én forekomst, skal du ændre forbehandlingen ved at skrive i hvert vertex nummeret på det mindste blad i undertræet.

Generaliseret suffikstræ

Et suffikstræ kan bygges på et sæt strenge med eller uden strengsammenkædning. ${\displaystyle S_{1},S_{2},\dots ,S_{n))$

Strengsammenkædning

Vi tilføjer forskellige vagtposter (tegn uden for alfabetet) til slutningen af hver linje.
Lad os samle dem alle til én.
Vi bygger et suffikstræ på denne linje.
Bladnumrene i dette træ har talpar, hvor det første svarer til strengen og det andet til startpositionen i den. $S_{i}$

Denne tilgang er problematisk på grund af tilstedeværelsen af syntetiske suffikser, men dette løses ved at reducere det andet indeks af suffiksparret i buerne til bladhjørnerne.

Uden strengsammenkædning

Der vil ikke være nogen syntetiske suffikser i denne algoritme.

Opbygning af et suffikstræ til strengen . $S_{1}\$$
Vi leder efter de første kampe i strengen . $l$ ${\displaystyle S_{1},S_{2))$
I suffikstræet for fuldfører vi for . $S_{1}$ $S_{2}[l+1\dots n]\$$
Så videre til de næste linjer.

Det skal tages i betragtning, at de komprimerede etiketter på forskellige buer kan referere til forskellige strenge, så tre numre skal gemmes på buerne.

Suffikser for to strenge kan matche, men på samme tid vil intet suffiks være et præfiks for et andet suffiks (på grund af vagtpost). Bladet peger derefter på alle strenge og startpositioner for det suffiks.

Sammenligning med nøgletræer

For at løse problemet med at finde et sæt mønstre er der Aho-Korasik-algoritmen. Den finder alle forekomster for - den samlede længde af mønstrene, T - længden af teksten, k - antallet af forekomster. $O(P+T+k),P$

Asymptotisk tager det lige lang tid at finde alle forekomster i et suffikstræ. Men faktum er, at Aho-Korasik bruger hukommelse til nøgletræet , tid til at bygge og tid til at søge . Men suffikstræet optager hukommelse , tid - konstruktion og søgning. $O(P)$ $O(P)$ $O(T)$ $O(T)$ $O(T)$ $O(P)$

Det vil sige, at hvis der er mange prøver og mere end teksten, så er suffikstræet lille, men det tager lang tid at søge. Ellers tager Aho-Korasik, når mønstrene er korte og teksten er større, mindre hukommelse, men suffikstræet søges hurtigere.

Således afhænger valget mellem det ene eller det andet af grænsetiden eller hukommelsen.

Se også

Litteratur

Gasfield D. Strenge, træer og sekvenser i algoritmer: Informatik og beregningsbiologi / Pr. fra engelsk. I. V. Romanovsky. - 2. udg. - Sankt Petersborg. : Nevsky Dialect, 2003. - 654 s.
Smith B. Metoder og algoritmer til beregning på strenge = Computing Patterns in Strings. - M. : Williams, 2006. - 496 s. - ISBN 5-8459-1081-1 , 0-201-39839-7.
Okulov S. M. Algoritmer til behandling af strenge. - M. : Binom, 2013. - 255 s. - ISBN 978-5-9963016-2-1 .

Links

Træ (datastruktur)
Binært søgetræ Træ (grafteori) træstruktur
Binære træer	binært træ T-træ
Selvbalancerende binære træer	AA træ AVL træ Rød-sort træ Splay træ træ med bøder kartesisk træ Fibonacci træ B-træ T-træ
B-træer	2-3-træ B⁺-træ B*-træ B x -træ UB træ 2-3-4 træ (a,b)-træ dansende træ
præfiks træer	suffiks træ Komprimeret præfikstræ Ternært søgetræ
Binær opdeling af rummet	k-dimensionelt træ VP træ
Ikke-binære træer	Quadtree oktre Sparsom Voxel Octree eksponentielt træ PQ træ
At bryde rummet op	R-træ Hilbert R-træ R+-træ R*-træ X-træ M-træ Fenwick træ Segmenttræ
Andre træer	dynge hash træ fingertræ metrisk træ Belægning træ BK-træ Dobbeltkædet træ iDistance Linkskåret træ LSM træ
Algoritmer	Bredde først søgning Dybde første søgning DSW algoritme spanning tree protokol

Strenge
String lighedsmål	Afstand fra Damerau til Loewenstein Levenshtein afstand Hammerafstand Jaro-Winkler lighed
Understrengssøgning	Boyer-Moore algoritme Boyer-Moore-Horspool algoritme Knuth-Morris-Pratt algoritme Rabin-Karp algoritme præfiks funktion Z-funktion Algoritme Aho - Korasik
palindromer	palindrom træ Manakers algoritme
Sekvensjustering	Needleman-Wunsha algoritme Smith-Waterman algoritme
Suffiksstrukturer	Suffiks array Suffiks automat suffiks træ præfiks træ
Andet	parsing Mønster matchende Største fælles efterfølger Største fælles understreng