Suffix automat

engelsk suffix
automat riktad acyklisk ordgraf

Suffix automat för abcbc

Sorts

Substring index

Uppfinningens år

1983

Författare

Anselm Bloomer, Janet Bloomer, Andrzej Ehrenvecht , David Haussler , Ross McConnell

Komplexitet i O-symboler

	Som värst
Byggnad	$O(\vert S\vert \log \vert \Sigma \vert )$
Minnesförbrukning	$O(\vert S\vert )$

Mediafiler på Wikimedia Commons

Suffix automaton ( engelska suffixet automaton , riktad acyklisk ordgraf ) är en datastruktur som låter dig lagra i komprimerad form och bearbeta information associerad med delsträngar av en given sträng. Representerar en deterministisk finit automat som accepterar alla suffix av ett ord och endast dem, och har minsta möjliga antal tillstånd bland alla sådana automater. Mindre formellt är en suffixautomat en riktad acyklisk graf med en distingerad initial någonsymbolernaär märkta medbågaroch en uppsättning "slutliga" hörn,vertex sammanfogas , bildar ett givet suffix. Av alla grafer som uppfyller denna beskrivning är suffixet automat den som har minsta möjliga antal hörn . ${\displaystyle S=s_{1}s_{2}\dots s_{n))$ $S$

Suffixet automat beskrevs först av en grupp forskare från University of Denver och Colorado 1983, de visade också att storleken på automaten beror linjärt på längden och föreslog också en onlinealgoritm för att bygga den med en linjär gångtid . I ytterligare arbeten om detta ämne upptäcktes en nära koppling mellan suffixautomaten och suffixträden , och konceptet med suffixautomaten fick olika generaliseringar. Således introducerades en komprimerad suffixautomat, erhållen från den ursprungliga genom en procedur liknande den som tillämpades på ett suffix bor för att få ett suffixträd, samt en generaliserad suffixautomat, som är byggd för en uppsättning ord och accepterar ord som är suffix till minst en av uppgifterna . $S$ ${\displaystyle S_{1},S_{2},\dots ,S_{k))$

Med hjälp av en suffixautomat kan du effektivt lösa sådana problem som att söka efter en delsträng i en sträng , bestämma den största gemensamma delsträngen av två eller flera strängar och andra .

Historik

Konceptet med en suffixautomat introducerades av en grupp forskare från University of Denver och Colorado Anselm Blumer, Andrzej Ehrenvecht , David Haussler , Ross McConnell och Janet Bloomer 1983, även om strukturer relaterade till det påträffades tidigare i arbetet av Peter Weiner [1] , Vaughn Pratt [2] och Anatoly Olesevich Slisenko [3] ägnade sig åt algoritmer för att konstruera suffixträd . I samma arbete visade Bloomer och andra att en automat konstruerad av ett ord som är längre än det inte innehåller fler tillstånd och inga fler övergångar, och presenterade även en linjär algoritm för att konstruera en automat [4] . $S$ $ett$ $2|S|-1$ $3|S|-4$

1983 utvecklade Mu Tian Chen och Joel Seiferas oberoende en algoritm för att konstruera en suffixautomat som visar att Weiners algoritm [1] som föreslogs 1973 för att konstruera ett ordsuffixträd också konstruerar en suffixautomat för det omvända ordet som en hjälpstruktur [5] . 1987 beskrev Bloomer och andra, i analogi med ett suffixträd, en komprimerad suffixautomat [6] erhållen från en suffixautomat genom att ta bort icke-slutliga tillstånd med ett utfallshalvgrad lika med ett, och 1997 Maxime Crochemore och Renaud Verin utvecklade en linjär algoritm för dess direkta konstruktion [7] . År 2001 utvecklade Shunsuke Inenaga och andra en linjär onlinealgoritm för att konstruera en komprimerad suffixautomat [8] , såväl som en linjär algoritm för att konstruera en komprimerad suffixautomat för en uppsättning ord som ges av ett prefixträd [9] . $S$ ${\textstyle S^{R}}$

I sin ursprungliga artikel definierade Bloomer och kollegor strukturen de beskrev som en minimal automat som känner igen alla delsträngar (inte suffix) för ett givet ord. De kallade denna struktur en riktad acyklisk ordgraf [ 4 ] . Därefter användes detta namn också som en synonym för en deterministisk acyklisk finit automat - en minimal automat som känner igen en godtycklig finit uppsättning ord (som inte nödvändigtvis utgör en uppsättning av suffix eller delsträngar av en viss sträng) [10] [ 11] .

Notation

När man beskriver suffixautomater och relaterade fakta och satser används ofta notationer från teorin om formella språk i allmänhet och automatteori i synnerhet [12] :

Ett alfabet är en ändlig uppsättning ord som kan bestå av. Dess element kallas symboler ; $\Sigma$
Ett ord är en ändlig sekvens av alfabetiska tecken. Ordlängd betecknassom; ${\displaystyle \omega =\omega _{1}\omega _{2}\dots \omega _{n))$ $\omega$ $|\omega |=n$
Ett formellt språk är en uppsättning ord över ett givet alfabet;
Språket för alla ord betecknas som (här bär symbolen "*" innebörden av Kleene-stjärnan ), ett tomt ord (ett ord med noll längd) - med symbolen ; $\Sigma ^{*}$ $\varepsilon$
Sammansättningen (produkten) av ord ochbetecknas somelleroch är lika med ordet som erhålls genom att tillskrivatillhöger, det vill säga; ${\displaystyle \alpha =\alpha _{1}\alpha _{2}\dots \alpha _{n))$ ${\displaystyle \beta =\beta _{1}\beta _{2}\dots \beta _{m))$ $\alpha \cdot \beta$ $\alfa \beta$ $\beta$ $\alfa$ ${\displaystyle \alpha \beta =\alpha _{1}\alpha _{2}\dots \alpha _{n}\beta _{1}\beta _{2}\dots \beta _{m))$
Sammansättningen av språk och betecknas som eller och är lika med uppsättningen av parvisa sammanlänningar ; $A$ $B$ $A\cdot B$ $AB$ ${\displaystyle AB=\{\alpha \beta :\alpha \in A,\beta \in B\))$
Om ett ord kan representeras som , där , så kallas orden , och prefixet , suffixet och underordet (delsträngen) av ordet ; $\omega \in \Sigma ^{*}$ $\omega =\alpha \gamma \beta$ $\alpha ,\beta ,\gamma \in \Sigma ^{*}$ $\alfa$ $\beta$ $\gamma$ $\omega$
Om , då säger vi att ordet ingår (förekommer) i som ett underord. I det här fallet kallas och den vänstra och högra positionen för förekomst i, respektive. $T_{l}T_{l+1}\dots T_{r}=S$ $S$ $T$ $l$ $r$ $S$ $T$

Automatisk struktur

Formellt definieras en deterministisk finit automat av en uppsättning av fem element där: ${\mathcal {A}}=(\Sigma ,Q,q_{0},F,\delta )$

$\Sigma$ - alfabetet , som består av ord som känns igen av maskinen,
$F$ är uppsättningen av automattillstånd,
$q_{0}\in Q$ är maskinens initiala tillstånd,
$F\subset Q$ är uppsättningen av automatens sluttillstånd ,
$\delta :Q\times \Sigma \mapsto Q$ är en delvis definierad övergångsfunktion för automaten, så att för och antingen inte är definierad eller indikerar ett tillstånd till vilket en övergång kan göras från till . $\delta (q,\sigma )$ $q\in Q$ $\sigma \in \Sigma$ $q$ $\sigma$

Oftast, i praktiken, representeras ändliga automater som en riktad graf ( diagram ) så att [13] :

Uppsättningen av grafens hörn motsvarar uppsättningen av tillstånd , $F$
En viss vertex väljs i grafen, motsvarande initialtillståndet , $q_{0}$
Grafen har en uppsättning hörn som motsvarar uppsättningen av sluttillstånd , $F$
Uppsättningen av bågar i grafen motsvarar uppsättningen av övergångar , $\delta$
I det här fallet motsvarar övergången en båge från till , markerad med alfabetssymbolen . Denna övergång kallas också . ${\textstil \delta (q_{1},\sigma )=q_{2}}$ $q_{1}$ $q_{2}$ $\sigma$ ${\textstyle q_{1}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}q_{2}}$

I en sådan graf identifieras hörn och bågar med tillstånd respektive övergångar för automaten. Automaten accepterar ett ord om och endast om det finns en väg från det initiala tillståndet till något slutligt tillstånd , så att om vi sammanfogar symbolerna som påträffas på denna väg får vi ordet . Den uppsättning ord som en automat accepterar utgör språket för denna automat [12] . ${\displaystyle \omega =\omega _{1}\omega _{2}\dots \omega _{m))$ $q_{0}$ $q\in F$ $\omega$

Automaten tillstånd

Den rätta kontexten för ett ord i förhållande till språket kallas mängden . Det vill säga, detta är en uppsättning ord , som tillskriver som till ordet till höger resulterar i ett ord från språket . Rätt sammanhang inducerar en naturlig ekvivalensrelation på mängden av alla ord. Om ett språk kan definieras av någon deterministisk finit automat, så finns det för det en unik, upp till isomorfism , automat, som samtidigt har minsta möjliga antal tillstånd. En sådan automat kallas minimal för ett givet språk , Myhill-Nerode-satsen tillåter oss att specificera det explicit [14] [15] : $\omega$ $L$ ${\displaystyle [\omega ]_{R}=\{\alpha :\omega \alpha \in L\))$ $\alfa$ $\omega$ $L$ ${\displaystyle [\alpha ]_{R}=[\beta ]_{R))$ $L$ $L$

En minimal automat som känner igen ett språk över ett alfabet kan ges enligt följande: $L$ $\Sigma$

Alfabetet förblir oförändrat $\Sigma$
Tillstånden motsvarar de rätta sammanhangen för alla ord , $F$ ${\displaystyle [\omega ]_{R))$ $\omega \in \Sigma ^{*}$
Det initiala tillståndet motsvarar den rätta kontexten för det tomma ordet , $q_{0}$ ${\displaystyle [\varepsilon ]_{R))$
Sluttillstånden motsvarar de rätta sammanhangen av ord från språket , $F$ ${\displaystyle [\omega ]_{R))$ $\omega \in L$
Övergångarna har formen , var och . $\delta$ $[\omega ]_{R}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}[\omega \sigma ]_{R}$ $\omega \in \Sigma ^{*}$ $\sigma \in \Sigma$

I en sådan notation är en suffixautomat en minimal DFA som accepterar ordet suffixspråk . Rätt sammanhang för ett ord relativt ett givet språk består av ord som - suffix . Detta tillåter oss att formulera följande lemma, som definierar en en-till-en-överensstämmelse mellan rätt kontext för ett ord och uppsättningen positioner för dess förekomster i som ett underord [16] [17] : ${\displaystyle S=s_{1}s_{2}\dots s_{n))$ $\omega$ $\alfa$ $\omega \alpha$ $S$ $S$

Låta vara uppsättningen av rätt positioner av förekomster i . $endpos(\omega )=\{r:\omega =s_{l}\dots s_{r}\}$ $\omega$ $S$

Mellan elementen i uppsättningarna och det finns följande en-till-en-korrespondens: $endpos(\omega )$ ${\displaystyle [\omega ]_{R))$

Om , då ; $x\in endpos(\omega )$ ${\displaystyle s_{x+1}s_{x+2}\dots s_{n}\i [\omega ]_{R))$
Om , då . ${\displaystyle \alpha \in [\omega ]_{R))$ $n-\vert \alpha \vert \in endpos(\omega )$

Till exempel för ett ord och dess underord och . Informellt består det av ord som följer förekomster till slutet av ordet, och - från positionerna för dessa förekomster. I det här exemplet matchar elementet ordet . Samtidigt motsvarar elementet ordet . $S=abacaba$ $\omega =ab$ $endpos(ab)=\{2,6\}$ $[ab]_{R}=\{a,acaba\}$ ${\displaystyle [ab]_{R))$ $ab$ $endpos(ab)$ $x=2\in endpos(ab)$ ${\displaystyle s_{3}s_{4}s_{5}s_{6}s_{7}=acaba\in [ab]_{R))$ ${\displaystyle a\in [ab]_{R))$ $7-|a|=6\in endpos(ab)$

Av detta följer ett antal strukturella egenskaper hos tillstånden för suffixautomaten och orden som de accepterar. Låt , sedan [17] : $|\alpha |\leq |\beta |$

Om och har minst ett gemensamt element , så har det gemensamma elementet också och . Detta betyder i sin tur att det är ett suffix och därför och . I exemplet ovan är och, som en konsekvens, ett suffix , samt och ; ${\displaystyle [\alpha ]_{R))$ ${\displaystyle [\beta ]_{R))$ $x$ $endpos(\alpha )$ $endpos(\beta )$ $\alfa$ $\beta$ $endpos(\beta )\subset endpos(\alpha )$ ${\displaystyle [\beta ]_{R}\subset [\alpha ]_{R))$ ${\displaystyle a\in[ab]_{R}\cap[cab]_{R))$ $ab$ $cab$ ${\displaystyle [cab]_{R}=\{a\}\subset \{a,acaba\}=[ab]_{R))$ $endpos(cab)=\{6\}\subset \{2,6\}=endpos(ab)$
Om alltså , det vill säga förekommer i endast som ett suffix . Detta kan ses i exemplet med orden och , för vilka och ; ${\displaystyle [\alpha ]_{R}=[\beta ]_{R))$ $endpos(\alpha )=endpos(\beta )$ $\alfa$ $S$ $\beta$ $\alpha =b$ $\beta =ab$ ${\displaystyle [b]_{R}=[ab]_{R}=\{a,acaba\))$ $endpos(b)=endpos(ab)=\{2,6\}$
Om och är ett suffix så att , då . I exemplet ovan är , och "mellanliggande" suffixet . Och verkligen ,. ${\displaystyle [\alpha ]_{R}=[\beta ]_{R))$ $\gamma$ $\beta$ $|\alpha |\leq |\gamma |\leq |\beta |$ ${\displaystyle [\alpha ]_{R}=[\gamma ]_{R}=[\beta ]_{R))$ $[c]_{R}=[bac]_{R}=\{aba\}$ $\gamma =ac$ $[ac]_{R}=\{aba\}$

Således accepterar vilket tillstånd som helst av suffixautomaten någon kontinuerlig kedja av kapslade suffix av den största strängen från detta tillstånd [17] . ${\displaystyle q=[\alpha ]_{R))$

Den vänstra förlängningen av en sträng är den längsta strängen som har samma högra kontext som . Längden på den längsta strängen som accepteras av staten betecknas som . Det är sant för honom att [18] : ${\overset {\scriptstyle {\leftarrow }}{\gamma }}$ $\gamma$ $\omega$ $\gamma$ $|{\overset {\scriptstyle {\leftarrow }}{\gamma }}|$ ${\displaystyle q=[\gamma ]_{R))$ $len(q)$

Den vänstra förlängningen av en sträng kan representeras som , där är det längsta ordet så att varje förekomst av ett ord i föregås av ordet . $\gamma$ ${\overleftarrow {\gamma }}=\beta \gamma$ $\beta$ $\gamma$ $S$ $\beta$

En suffixlänk från ett tillstånd är en pekare till det tillstånd som innehåller det största suffixet som inte accepteras av staten . $länk(q)$ ${\displaystyle q=[\alpha ]_{R))$ $sid$ $\alfa$ $q$

I denna notation kan vi säga att staten tar exakt alla suffix som är längre än och inte längre än . Dessutom är följande sant [18] : ${\displaystyle q=[\alpha ]_{R))$ ${\overset {\scriptstyle {\leftarrow }}{\alpha }}$ $len(länk(q))$ $len(q)$

Suffixlänkar bildar ett träd , som kan anges uttryckligen enligt följande: ${\mathcal {T}}(V,E)$

Hörnena motsvarar de vänstra expansionerna av alla delsträngar , $V$ ${\overleftarrow {\omega ))$ $S$
Kanter förbinder hörn så att och . $E$ $({\overleftarrow {\omega )),{\overleftarrow {\alpha \omega )))$ $\alpha \in \Sigma$ ${\overleftarrow {\omega }}\neq {\overleftarrow {\alpha \omega }}$

Anslutning till suffixträdet

Ett prefixträd (eller borrning ) är ett rotorienterat träd , vars bågar är markerade med symboler på ett sådant sätt attinte mer än en båge kommer ut från någon vertex av detta träd , märkt med en given symbol. Vissa hörn i prefixträdet är märkta. Ett prefixträd sägs definiera en uppsättning ord som definieras av vägar från trädets rot till märkta hörn. Prefixträd är alltså en speciell sorts finita automater, om vi betraktar roten som initialtillståndet och de märkta hörnen som sluttillstånden [19] . Suffixet bor för ett ordär ett prefixträd som definierar språket för suffixen för detta ord. Ett suffixträd är ett träd som erhålls från ett suffixhål genom en kompressionsprocedur, där successiva kanter limmas ihop om det finns en icke-slutlig vertex mellan dem, vars grad är 2 [18] . $v$ $S$

Per definition kan en suffixautomat erhållas genom att minimera ett suffixhål. Dessutom kan en komprimerad suffixautomat erhållas både genom att minimera ett suffixträd (förutsatt att alfabetets symboler är ord på trädets kanter), och genom att komprimera en konventionell automat [8] . Men förutom det uppenbara sambandet mellan suffixautomaten och suffixträdet i samma sträng, kan man också etablera viss överensstämmelse mellan suffixautomaten för en sträng och suffixträdet för en omvänd sträng [20] . ${\displaystyle S=s_{1}s_{2}\dots s_{n))$ ${\displaystyle S^{R}=s_{n}s_{n-1}\dots s_{1))$

På samma sätt som högerkontexter kan man introducera vänsterkontexter och högerförlängningar som motsvarar de längsta strängarna som har en given vänsterkontext, såväl som en ekvivalensrelation . Om vi överväger rätt tillägg med avseende på strängprefixet språk , då kan vi få det [18] : ${\displaystyle [\omega ]_{L}=\{\beta \in \Sigma ^{*}:\beta \omega \in L\))$ ${\overset {\scriptstyle {\rightarrow }}{\omega ~}}$ ${\displaystyle [\alpha ]_{L}=[\beta ]_{L))$ $L$ $S$

Suffixträdet för en sträng kan anges uttryckligen enligt följande: $S$

Hörnena motsvarar de högra förlängningarna av alla delsträngar , $V$ ${\overrightarrow {\omega ))$ $S$
Kanterna motsvarar trippel så att och . $E$ $({\overrightarrow {\omega )),x\alpha ,{\overrightarrow {\omega x)))$ $x\in \Sigma$ ${\overrightarrow {\omega x}}={\overrightarrow {\omega }}x\alpha$

Här betyder trippeln att strängen från till skrivs på kanten . $(v_{1},\omega ,v_{2})\in E$ $v_{1}$ $v_{2}$ $\omega$

Av vilket det följer att trädet med suffixlänkar för en strängautomat och suffixträdet för en sträng är isomorfa [20] : $S$ $S^{R}$

Suffixstrukturer för orden abbcbc och cbcbba
Suffix automat för ordet abcbc Suffix bor, suffixträd och komprimerad suffixautomat för ordet abbcbc . Hönsnumren motsvarar tillstånden de går in i när de minimerar eller krymper. Suffixträd för ordet cbcbba (träd med suffixlänkar för automaten för ordet abbcbc )

På samma sätt som vänster förlängningar kan ett strukturellt lemma [18] också formuleras för höger förlängningar :

Den högra förlängningen av en sträng kan representeras som , där är det längsta ordet så att varje förekomst av in omedelbart följs av ordet . $\gamma$ ${\overrightarrow {\gamma }}=\gamma \alpha$ $\alfa$ $\gamma$ $S$ $\beta$

Storlek

I en suffixautomat är längdsträngar inte mer än tillstånd och inte mer än övergångar, och dessa uppskattningar uppnås på strängar respektive [16 ] . Det är också möjligt att formulera ett starkare uttalande om sambandet mellan antalet tillstånd och övergångar i en automat: , där och är antalet övergångar respektive tillstånd [17] . $S$ $n>1$ $2n-1$ $3n-4$ ${\displaystyle abb\dots bb=ab^{n-1))$ $abb\dots bc=ab^{n-2}c$ $|\delta |\leq |Q|+n-2$ $|\delta |$ $|Q|$

Maximalt suffix automata
Suffix automat för $ab^{n-1}$ Suffix automat för $ab^{n-2}c$

Byggnad

Suffixautomaten för en sträng byggs upp genom att successivt bygga upp ordet som den är byggd för. Inledningsvis finns det en trivial automat byggd för ett tomt ord, och sedan läggs en symbol till det aktuella ordet vid varje steg, vilket innebär en omarrangering av tillstånd och övergångar för automaten [21] . ${\displaystyle S=s_{1}s_{2}\dots s_{n))$

Ändra stater

Efter att ha tilldelat ett nytt tecken till ett ord kommer vissa ekvivalensklasser att ändras. Låt vara det rätta sammanhanget för ordet med avseende på suffixspråket för ordet . Sedan beskrivs övergången från till när man tilldelar en symbol till ett ord med följande lemma [17] : $[\alpha ]_{R_{\omega ))$ $\alfa$ $\omega$ $[\alpha ]_{R_{\omega ))$ $[\alpha ]_{R_{\omega x))$ $x$ $\omega$

Låt vara några ord över ett alfabet och vara någon symbol för detta alfabet. Sedan mellan de rätta sammanhangen och orden med avseende på språken för ordens suffix respektive följande förhållande äger rum: $\alpha ,\omega \in \Sigma ^{*}$ $\Sigma$ $x\in \Sigma$ $[\alpha ]_{R_{\omega ))$ $[\alpha ]_{R_{\omega x))$ $\alfa$ $\omega$ $\omega x$

$[\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x\cup \{\varepsilon \}$ if - suffix ; $\alfa$ $\omega x$
$[\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x$ annat.

Det vill säga när ett tecken läggs till i det aktuella ordet kan ordets rätta kontext bara ändras om det är ett ordsuffix . Av detta följer att uppdelningen av alla ord i ekvivalensklasser med avseende på är en förfining av uppdelningen i ekvivalensklasser med avseende på . Med andra ord, om , då . Dessutom, när nästa symbol läggs till i ordet, kommer delning att ske i högst två tillstånd. Först och främst kommer tillståndet som motsvarar den tomma högra kontexten (det vill säga den som tar språket för ord som inte ingår som ett underord) att delas. Från detta tillstånd kommer ett nytt tillstånd att extraheras som innehåller hela ordet , samt alla dess suffix som förekommer i men inte förekom i . Följaktligen kommer den rätta kontexten för dessa ord, som tidigare var tom, nu endast att bestå av det tomma ordet [17] . $x$ $\omega$ $\alfa$ $\alfa$ $\omega x$ $\equiv _{R_{\omega x))$ $\equiv _{R_{\omega ))$ $[\alpha ]_{R_{\omega x))=[\beta ]_{R_{\omega x))$ $[\alpha ]_{R_{\omega }}=[\beta ]_{R_{\omega }}$ $\omega$ $\omega x$ $\omega x$ $\omega$

Med hänsyn till kopplingen mellan tillstånden för suffixautomaten och suffixträdets hörn, kan vi också spåra det andra tillståndet, som kan delas när nästa symbol läggs till. Eftersom en ord -till- övergång motsvarar en till- till -övergång för en omvänd sträng, motsvarar att tilldela ett tecken till en sträng att lägga till ett nytt (längsta) suffix till strängens suffixträd . I det här fallet visas inte mer än två hörn: en av dem kommer att motsvara hela ordet och den andra kan visas på den plats där grenen från trädet förekommer. Således motsvarar ett nytt tillstånd den rätta kontexten för hela strängen , och den andra (om någon) kan endast motsvara det tillståndets suffixreferens. Dessa observationer kan generaliseras med satsen [17] : $\omega$ $\omega x$ $\omega ^{R}$ $x\omega ^{R}$ $x$ $\omega$ $x\omega ^{R}$ $\omega ^{R}$ $x\omega ^{R}$ $\omega x$

Låt och . Låt också vara det längsta suffixet som förekommer i , och låt vara dess vänstra förlängning med avseende på , Det vill säga det längsta underordet i ordet sådan att . Då gäller följande för alla underord till ordet : $\omega \in \Sigma ^{*}$ $x\in \Sigma$ $\alfa$ $\omega x$ $\omega$ $\beta ={\overset {\scriptstyle {\leftarrow }}{\alpha }}$ $\omega$ $\omega$ $[\alpha ]_{R_{\omega }}=[\beta ]_{R_{\omega }}$ $u, v$ $\omega$

Om och , då ; $[u]_{R_{\omega }}=[v]_{R_{\omega }}$ $[u]_{R_{\omega }}\neq [\alpha ]_{R_{\omega }}$ $[u]_{R_{\omega x}}=[v]_{R_{\omega x}}$
Om och , då ; $[u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}$ $\vert u\vert \leq \vert \alpha \vert$ $[u]_{R_{\omega x}}=[\alpha ]_{R_{\omega x}}$
Om och , då . $[u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}$ $\vert u\vert >\vert \alpha \vert$ $[u]_{R_{\omega x))=[\beta ]_{R_{\omega x))$

I synnerhet om (till exempel när det inte inträffar alls i och ), uppdelning av det andra tillståndet inte inträffar [17] . $\alpha =\beta$ $x$ $\omega$ $\alpha =\beta =\varepsilon$

Förutom suffixlänkar måste även sluttillstånden definieras i den nya automaten. Det följer av automatens strukturella egenskaper att suffixen för ett ord är placerade på ett sådant sätt att om , då suffixen vars längd överstiger , ligger i , suffix vars längd är större än , men inte större än , ligger i , och så vidare. Med andra ord, för alla suffix finns det en vertex i suffixets tillståndsväg , som ges av sekvensen . Följaktligen, om vi anger det tillstånd som för närvarande accepterar hela strängen som , så kommer terminaltillstånden (accepterar suffix ) att vara de och endast de tillstånd som ingår i suffixsökvägen [21] . $\alfa$ ${\displaystyle q=[\alpha ]_{R))$ $\alfa$ $len(länk(q))$ $q$ $len(länk(länk(q))$ $len(länk(q))$ $länk(q)$ $\alfa$ $q$ $(q,länk(q),länk^{2}(q),\dots )$ $\omega$ $sist$ $\omega$ $(sista,länk(sista),länk^{2}(sista),\dots )$

Ändra hopp och suffixlänkar

Eventuella ändringar när du lägger till nästa tecken påverkar inte mer än två nya tillstånd, så ändringar i automatens övergångar kommer också att påverka endast dessa tillstånd. Efter tillskrivning till ordet bildas ett nytt tillstånd , och eventuellt även ett tillstånd . Suffixlänken från kommer att leda till , och från - till . Ord från förekommer endast i som suffix, så det bör inte finnas några övergångar från, och övergångar som leder till det måste leda med tecken från suffix med en längd på minst . Tillståndet är delat från , så övergångar från detta tillstånd kommer att duplicera de för . Och övergångar som leder till det kommer att leda med symbol från stater som motsvarar suffix av längd mindre än och inte mindre än , eftersom tidigare dessa övergångar ledde till och motsvarade den separerade delen av staten. De tillstånd som accepterar dessa ord kan identifieras av tillståndssuffixets sökväg [21] . $x$ $\omega$ $[\omega x]_{R_{\omega x))$ $[\alpha ]_{R_{\omega x))$ $[\omega x]_{R_{\omega x))$ $[\alpha ]_{R_{\omega x))$ $[\alpha ]_{R_{\omega x))$ $link([\alpha ]_{R_{\omega )))$ $[\omega x]_{R_{\omega x))$ $\omega x$ $[\omega x]_{R_{\omega x))$ $x$ $\omega$ $|\alfa |$ $[\alpha ]_{R_{\omega x))$ $[\alpha ]_{R_{\omega ))$ $[\alpha ]_{R_{\omega ))$ $x$ $\omega$ $|\alfa |$ $len(länk([\alpha ]_{R_{\omega ))))$ $[\alpha ]_{R_{\omega ))$ $[\omega ]_{R_{\omega ))$

Bygga en suffixautomat för ordet abcbc

∅ → a


När den första symbolen läggs till skapas ett enda nytt tillstånd i automaten.	På samma sätt läggs ett enda blad till suffixträdet.

a→ab


Nya övergångar dras från alla sluttillstånd, eftersom den nya symbolen inte har påträffats tidigare.	Av samma anledning, i ett träd med suffixlänkar, är den nya noden suspenderad från roten.

ab → abb


Tillstånd 2 tar orden ab och b , men endast b blir ett suffix, så det ordet allokeras till tillstånd 4.	I suffixträdet för det utökade ordet motsvarar detta uppdelningen av kanten som leder till vertex 2.

abb → abbc


Den nya symbolen har inte setts tidigare, övergångar till den utförs från alla de sista.	Ett nytt blad läggs till i trädet med suffixlänkar som hänger upp från roten.

abbc → abbcb


I tillstånd 4 finns bara ordet b och det är ett suffix, så ingen splittring sker.	Följaktligen, i trädet med suffixlänkar, är ett nytt blad upphängt från vertex 4.

abbcb → abbcbc


Tillstånd 5 accepterar orden abbc , bbc , bc och c , men bara de två sista är suffix till det nya ordet, så de separeras i ett separat tillstånd 8.	Följaktligen, i trädet av suffixlänkar, är kanten som leder till vertex 5 delad.

Algoritm för att konstruera en automat

De teoretiska resultaten ovan leder till följande algoritm, som tar en symbol och ordnar om ett ordsuffixautomat till en ordsuffixautomat [21] : $x$ $\omega$ $\omega x$

Ett tillståndsnummer som motsvarar hela linjen stöds ; $sist$ $\omega$
När en symbol läggs till lagras numret i variabeln och numret på det nya tillståndet som motsvarar ordet skrivs till ; $x$ $sist$ $sid$ $sist$ $\omega x$
Från de tillstånd som motsvarar suffixen anbringas övergångar till . För att göra detta förbigås suffixvägen tills ett tillstånd påträffas från vilket det redan finns en övergång längs ; $\omega$ $sist$ $p,länk(p),länk^{2}(p),\dots$ $x$
Ytterligare åtgärder motsvarar ett av tre fall:
1. Om det på hela suffixvägen inte finns någon övergång från något tillstånd till , så har det inte påträffats tidigare i och suffixlänken från leder till ; $x$ $x$ $\omega$ $sist$ $q_{0}$
2. Om övergången av hittades och leder från tillstånd till tillstånd så att , så finns det inget behov av att dela upp och det räcker med att dra en suffixlänk från till ; $x$ $sid$ $q$ $len(p)+1=len(q)$ $q$ $sist$ $q$
3. Om , då måste ord från staten vars längd inte överstiger separeras i ett separat tillstånd ; $len(q)>len(p)+1$ $q$ $len(p)+1$ $cl$
Om ett separat tillstånd valdes i föregående steg , bör övergångarna och suffixlänken från den duplicera dem i , medan det kommer att bli en gemensam suffixlänk för tillstånden och ; $cl$ $q$ $cl$ $q$ $sist$
Hopp som ledde till men matchade ord med en längd som inte är större än , omdirigeras till . För att göra detta kan du fortsätta att följa suffixvägen tills du hittar ett tillstånd, vars övergång inte leder till . $q$ $len(p)+1$ $cl$ $sid$ $q$

Proceduren som implementerar denna algoritm kan beskrivas med följande pseudokod:

funktion add_letter(x) : definiera p = senast tilldela sist = new_state() tilldela len(senast) = len(p) + 1 tills δ(p, x) är definierad: tilldela δ(p, x) = sist, p = länk(p) definiera q = δ(p, x) om q = sista : tilldela länk(sista) = q 0 annars om len(q) = len(p) + 1 : tilldela länk(sista) = q annat : definiera cl = new_state() tilldela len(cl) = len(p) + 1 tilldela δ(cl) = δ(q), länk(cl) = länk(q) tilldela länk(senaste) = länk(q) = cl medan δ(p, x) = q : tilldela δ(p, x) = cl, p = länk(p)

Här är det initiala tillståndet för automaten, och är en funktion som lägger till ett nytt tillstånd till automaten. Det antas att , , och lagras som globala variabler. $q_{0}$ $new\_state()$ $sist$ $len$ $länk$ $\delta$

Beräkningskomplexitet

Beroende på de strukturer som används kan en deterministisk version av algoritmen som beskrivs ovan implementeras i minnestid eller i minnestid , förutsatt att minnesallokering sker i . Samtidigt, för att få en sådan uppskattning av körtiden, är det nödvändigt att utföra en amorteringsanalys av algoritmens inre cykler. Om vi överväger hur parametern ändras efter den första iterationen av den första slingan, kan vi se att den strikt minskar med varje iteration av slingan. Dessutom, om vid den sista iterationen av föregående steg detta värde var lika med , då vid den andra iterationen i nästa steg kommer detta värde att vara lika med . Att den inte överskrider vid något ögonblick av tid, och att mellan cyklerna denna kvantitet ökar med endast en, ger det erforderliga påståendet. En liknande analys kan visa linjäriteten för den totala exekveringstiden för den andra cykeln av algoritmen [21] . $O(n\log |\Sigma |)$ $På)$ $På)$ $O(n|\Sigma |)$ $O(1)$ $len(p)$ $k$ $k+1$ $len(p)$ $n$

Variationer och generaliseringar

Suffixautomaten är nära relaterad till andra suffixstrukturer och delsträngsindex . Med en suffixautomat av någon sträng är det möjligt att konstruera ett suffixträd av denna sträng i linjär tid genom komprimering och rekursiv traversering av denna automat [22] . Liknande transformationer i båda riktningarna är möjliga mellan en strängsuffixautomat och ett omvänt strängsuffixträd [20] . Dessutom har ett antal algoritmmodifieringar utvecklats som gör det möjligt att bygga en automat för en uppsättning strängar som ges av ett prefixträd [9] , applicera komprimering på det [6] , bibehålla dess struktur i ett glidande fönsterläge [23] , och även bygga om när du lägger till tecken både från slutet och från början av strängen [24] . $S$ $S^{R}$

Komprimerat suffix automaton

Som nämnts ovan kan en komprimerad suffixautomat erhållas från en vanlig suffixautomat genom komprimering (ta bort tillstånd som inte är slutgiltiga och från vilka exakt en övergång leder), samt genom att minimera suffixträdet, om vi antar att alfabetet är bildas av ord skrivna på kanterna trädet. Dessutom kan tillstånden för en komprimerad automat beskrivas explicit, på samma sätt som hur det gjordes för en okomprimerad automat. En tvåvägsordförlängning är det längsta ordet , så att varje förekomst i föregås av ett ord och omedelbart följt av ett ord . När det gäller vänster och höger förlängning betyder detta att tvåvägsförlängningen är vänster förlängning av höger förlängning eller, motsvarande, höger förlängning av vänster förlängning: . När det gäller bilaterala förlängningar kan en automat med komprimerat suffix beskrivas enligt följande [18] : ${\overset {\scriptstyle {\longleftrightarrow }}{\gamma }}$ $\gamma$ $\omega =\beta \gamma \alpha$ $\gamma$ $S$ $\beta$ $\alfa$ ${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\gamma }}={\overset {\scriptstyle \leftarrow }{\overset {\rightarrow }{\gamma }}}={\overset {\rightarrow }{\ översätt {\scriptstyle \leftarrow }{\gamma ))))$

Den komprimerade suffixautomaten för ett ord kan ges av paret , där: $S$ $(V, E)$

$V=\{{\overleftrightarrow {\omega }}:\omega \in \Sigma ^{*}\}$ är uppsättningen av automattillstånd;
$E=\{({\overleftrightarrow {\omega )),x\alpha ,{\overleftrightarrow {\omega x))):x\in \Sigma ,\alpha \in \Sigma ^{*},{ \overleftrightarrow {\omega x}}={\overleftrightarrow {\omega }}x\alpha \}$ - en uppsättning övergångar av automaten.

Tvåvägsförlängningar genererar en ekvivalensrelation som beskriver orden som accepteras av samma tillstånd hos den komprimerade automaten. Denna relation är en transitiv stängning av relationen , vilket understryker det faktum att tillstånd för en komprimerad suffixautomat kan erhållas både genom att limma suffixträdets hörn som är likvärdiga vad gäller (suffixträdminimering) och genom att limma tillstånd för en suffixautomat som är likvärdiga när det gäller (komprimerande suffix automat) [25] . Om orden och har samma högra förlängningar, och orden och har de vänstra förlängningarna, då sammanlagt orden , och har samma bilaterala förlängning. I det här fallet kan det visa sig att orden och inte har samma vänster- eller högertillägg. I fallet med , och vänster och höger tillägg är: , men och . I fallet med envägskontexter och tillägg bildade ord från samma ekvivalensklass en kontinuerlig kedja av kapslade prefix eller suffix och kunde unikt bestämmas av längden på de kortaste och längsta orden i klassen. Vid tvåvägsutvidgningar kan man bara säga säkert att ord från samma klass är underord till det längsta ordet från denna klass, och annars kan klasserna ha en ganska komplex struktur. Det totala antalet sådana ekvivalensklasser överstiger inte , vilket innebär att en komprimerad suffixautomat med en längdsträng som mest kommer att ha tillstånd. Antalet övergångar i en sådan automat överstiger inte [18] . ${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\alpha }}={\overset {\scriptstyle \longleftrightarrow }{\beta }}}$ ${\textstyle ({\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}})\vee ({\overset {\ scriptstyle {\leftarrow }}{\alpha }}={\overset {\scriptstyle {\leftarrow }}{\beta }})}$ ${\overset {\scriptstyle {\leftarrow }}{\alpha }}={\overset {\scriptstyle {\leftarrow }}{\beta }}$ ${\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}$ $\alfa$ $\beta$ $\beta$ $\gamma$ $\alfa$ $\beta$ $\gamma$ $\alfa$ $\gamma$ $S=\beta =ab$ $\alpha =a$ $\gamma =b$ ${\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}=ab={\overset {\scriptstyle { \leftarrow }}{\beta }}={\overset {\scriptstyle {\leftarrow }}{\gamma }}$ ${\overset {\scriptstyle {\rightarrow }}{\gamma \,}}=b$ ${\overset {\scriptstyle {\leftarrow }}{\alpha }}=a$ $n+1$ $n$ $n+1$ $2n-2$

Suffixautomat för en uppsättning strängar

Låt en uppsättning ord ges . På samma sätt som en automat byggd på ett enda ord kan vi överväga en generaliserad suffixautomat som accepterar språket för ord som är suffixet till minst ett ord från . I det här fallet, för antalet tillstånd och övergångar för denna automat, kommer alla samma begränsningar som angavs ovan att vara uppfyllda om vi sätter [25] . Själva konstruktionsalgoritmen liknar i huvudsak algoritmen för att konstruera en automat för en rad, men istället för en pekare till det tillstånd som motsvarar ordet , kommer add_letter- funktionen att ta en pekare till det tillstånd som accepterar ordet . ord , vilket antyder att övergången sker från den nuvarande uppsättningen ord till uppsättningen . Utöver huvudåtgärderna som redan ingår i algoritmen kommer det att vara nödvändigt att separat analysera fallet när strängen redan finns i maskinen - i det här fallet kan du behöva dela upp det tillstånd som accepterar det, liknande hur det gick till när man bildade en suffixlänk i algoritmen för ett enda ord [26] [27] . $T=\{S_{1},S_{2},\dots ,S_{k}}\}$ $S$ $T$ $n=|S_{1}|+|S_{2}|+\dots +|S_{k}|$ $sist$ $\omega$ $\omega x$ $\omega _{i}$ ${\displaystyle \{\omega _{1},\dots ,\omega _{i},\dots ,\omega _{k))\))$ ${\displaystyle \{\omega _{1},\dots ,\omega _{i}x,\dots ,\omega _{k}\))$ $\omega _{i}x$

En vidareutveckling av denna idé var konstruktionen av en suffixautomat för fallet när uppsättningen inte anges i en explicit form, utan som ett prefixträd på hörnen. Mohry och andra har visat att en sådan automat innehåller på de flesta tillstånd och kan byggas i tid linjär i sin storlek. Samtidigt kan antalet övergångar i en sådan automat nå - till exempel, om vi betraktar en uppsättning ord över alfabetet , kommer den totala längden av ord från denna uppsättning att vara i storleksordningen , antalet hörn i motsvarande prefixträd kommer att vara lika med , och i suffixautomaten kommer det att finnas en ordning av tillstånd och övergångar. Själva algoritmen, föreslagen av Mohri, upprepar till stor del den allmänna algoritmen för att konstruera en automat från en uppsättning strängar, men istället för att varje gång lägga till tecknen i ett ord från uppsättningen från början till slut, korsar algoritmen prefixträdet i genomgångsordningen i bredd och tilldelar nästa tecken i den ordningen , i vilken den möter dem under genomgången, vilket garanterar en amorterad linjär körtid för algoritmen [28] . $T$ $F$ $2Q-2$ $O(Q|\Sigma |)$ $T=\{\sigma _{1},a\sigma _{1},a^{2}\sigma _{1},\dots ,a^{n}\sigma _{1},a ^{n}\sigma _{2},\dots ,a^{n}\sigma _{k}\}$ ${\displaystyle \Sigma =\{a,\sigma _{1},\dots ,\sigma _{k}\))$ ${\textstyle O(n^{2}+nk)}$ $O(n+k)$ $O(n+k)$ $O(nk)$

Skjutfönster

I vissa komprimeringsalgoritmer som LZ77 och RLE kan det vara användbart att lagra en suffixautomat eller liknande struktur inte för hela det lästa ordet, utan bara för de sista tecknen. Först och främst uppstår ett sådant behov på grund av detaljerna i datakomprimeringsuppgifter, där de komprimerade strängarna vanligtvis är ganska stora och minnesanvändning är oönskad. År 1985 utvecklade Janet Bloomer en algoritm som stöder en suffixautomat på ett fönster med glidande storlek och körs i värsta fall och genomsnitt, förutsatt att tecknen i ordet som ska komprimeras är oberoende och enhetligt fördelade . I samma arbete visades det att uppskattningen är oförbättrbar - om vi anser att ord erhållna genom formensammanlänkning av flera ord av för en suffixautomat är omöjligt [29] . $k$ $På)$ $k$ $O(nk)$ $O(n\log k)$ $O(nk)$ $(ab)^{m}c(ab)^{m}d$ $k=6m+2$ $k$ $m$ $O(nk)$

Det verkar som om detsamma borde vara sant för suffixträdet , eftersom suffixträdets hörn motsvarar tillstånden för suffixautomaten för den utvikta strängen. Men om en separat vertex för varje suffix inte tilldelas i suffixträdet, kommer det inte att finnas några sådana skarpa hopp och det är möjligt att bygga en amorterad algoritm som stöder suffixträdet på ett glidfönster. En motsvarande algoritm för ett suffixträd, baserad på McCraiths algoritm och stöder att lägga till ett nytt tecken till höger och ta bort ett tecken till vänster, föreslogs 1989 av Edward Fiala och Daniel Green [30] och förklarades 1996 i termer av Ukkonens algoritm av Jesper Larsson [31] [32] . I detta avseende förblev frågan om det är möjligt att upprätthålla ett snabbt glidande fönster för en komprimerad automat, som kombinerar vissa egenskaper hos både en vanlig suffixautomat och ett suffixträd, öppen under lång tid. Ett negativt svar på denna fråga erhölls 2008 av Martin Senft och Tomasz Dvorak, som visade att om alfabetet består av två eller flera tecken, så är den amorterade tiden som krävs för att flytta fönstret med ett tecken i värsta fall av storleken av [33] . $Ok)$

Samtidigt, om den exakta bredden på fönstret inte är viktig och målet endast är att behålla ett fönster vars bredd inte överstiger , i storleksordning, kan detta göras med den ungefärliga algoritm som föreslås av Inenaga et al. 2004. En egenskap hos algoritmen är att "fönstret" som rör sig längs ordet har en variabel längd, som vid något tillfälle varken är mindre eller mer än , medan den totala körtiden förblir linjär [34] . $Ok)$ $k$ $2k+1$

Applikationer

Strängsuffixautomaten kan användas för att lösa problem som [35] [36] : $S$

Räknar antalet distinkta delsträngar över tid online, $S$ $O(|S|)$
Att hitta den längsta delsträngen som ingår i den minst två gånger i tiden , $S$ $O(|S|)$
Hitta den största gemensamma delsträngen av strängar och i tid , $S$ $T$ $O(|T|)$
Räknar antalet förekomster av en sträng som en delsträng i tid , $T$ $S$ $O(|T|)$
Sök efter alla förekomster i tiden , där är antalet förekomster. $T$ $S$ $O(|T|+k)$ $k$

Här är det värt att tänka på att någon sträng matas in när automaten redan är byggd och klar att användas. $T$

Suffixautomater har också hittat sin väg in i applikationer som datakomprimering [37] , musikidentifiering från inspelade fragment [38] [39] och genomisk sekvensmatchning [40] .

Anteckningar

↑ 1 2 Weiner, 1973
↑ Pratt, 1973
↑ Slisenko, 1983
↑ 1 2 Blumer et al., 1984 , sid. 109-110
↑ Chen, Seiferas, 1985 , sid. 97
↑ 12 Blumer et al., 1987 , sid. 578
↑ Crochemore, Verin, 1997 , sid. 192
↑ 1 2 Inenaga et al., 2005 , s. 156-158
↑ 1 2 Inenaga et al., 2001 , sid. ett
↑ Perrin, 1990 , sid. tio
↑ Sgarbas et al., 2003 , sid. 2
↑ 1 2 Crochemore, Hancart, 1997 , s. 3-6
↑ Serebryakov et al., 2006 , sid. 50-54
↑ Rubtsov, 2019 , sid. 89-94
↑ Hopcroft, Ullman, 1979 , s. 65-68
↑ 12 Blumer et al., 1984 , sid. 111-114
↑ 1 2 3 4 5 6 7 8 Crochemore, Hancart, 1997 , s. 27-31
↑ 1 2 3 4 5 6 7 Inenaga et al., 2005 , s. 159-162
↑ Rubinchik, Shur, 2018 , s. 1-2
↑ 1 2 3 Fujishige et al., 2016 , s. 1-3
↑ 1 2 3 4 5 Crochemore, Hancart, 1997 , s. 31-36
↑ Parasjtjenko, 2007 , sid. 19-22
↑ Blumer, 1987 , sid. 451
↑ Inenaga, 2003 , sid. ett
↑ 1 2 Blumer et al., 1987 , sid. 585-588
↑ Blumer et al., 1987 , sid. 588-589
↑ Blumer et al., 1987 , sid. 593
↑ Mohri et al., 2009 , s. 3558-3560
↑ Blumer, 1987 , s. 461-465
↑ Fiala, Greene, 1989 , sid. 490
↑ Larsson, 1996
↑ Brodnik, Jekovec, 2018 , sid. ett
↑ Senft, Dvorak, 2008 , sid. 109
↑ Inenaga et al., 2004
↑ Crochemore, Hancart, 1997 , s. 39-41
↑ Crochemore, Hancart, 1997 , s. 36-39
↑ Yamamoto et al., 2014 , sid. 675
↑ Crochemore et al., 2003 , sid. 211
↑ Mohri et al., 2009 , sid. 3553
↑ Faro, 2016 , sid. 145

Litteratur

Sgarbas K. N., Fakotakis N. D., Kokkinakis G. K. Optimal insättning i deterministiska DAWG:er // Theoretical Computer Science - Elsevier BV , 2003. - Vol . 301, Iss. 1-3. - S. 103-117. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/S0304-3975(02)00571-6
Perrin D. Finite Automata // Formella modeller och semantik : Handbook of Theoretical Computer Science / J. v . Leeuwen - Elsevier BV , 1990. - Vol. B.-P. 1-57. - ISBN 978-0-444-88074-1 - doi:10.1016/B978-0-444-88074-1.50006-8
Weiner P. Linjära mönstermatchningsalgoritmer (engelska) // Symposium on Foundations of Computer Science - 1973. - S. 1-11. — 213 sid. doi : 10.1109/SWAT.1973.13
Pratt V. R. Förbättringar och tillämpningar för Weiner upprepningsfinnare (engelska) - 1973.
Slisenko A. O. Detektion av periodiciteter och strängmatchning i realtid (engelska) // Journal of Soviet mathematics - Springer Science + Business Media , 1983. - Vol. 22, Iss. 3. - P. 1316-1387. — ISSN 1072-3374 ; 1573-8795 - doi:10.1007/BF01084395
Blumer A. C. , Blumer J. , Ehrenfeucht A. , Haussler D. , McConnell R. Bygger den minimala DFA för uppsättningen av alla underord i ett ord online i linjär tid // Automata , Languages and Programming - 1984 .- s. 109-118. — 526 sid. — ISBN 978-3-540-13345-2 — doi:10.1007/3-540-13345-3_9
Blumer A. C. , Blumer J. , Ehrenfeucht A. , Haussler D. , McConnell R. Kompletta inverterade filer för effektiv texthämtning och analys // J. ACM / D. J. Rosenkrantz - New York, NY : Association for Computing Machinery . 1987. Vol. 34, Iss. 3. - P. 578-595. - ISSN 0004-5411 - doi:10.1145/28869.28873
Blumer J. Hur mycket kostar den där DAWG i fönstret? En algoritm för rörligt fönster för den riktade acykliska ordgrafen (engelska) // Journal of Algorithms - Academic Press , 1987. - Vol. 8, Iss. 4. - s. 451-469. — ISSN 0196-6774 ; 1090-2678 - doi:10.1016/0196-6774(87)90045-9
Chen M., Seiferas J. Effektiv och elegant underordsträdkonstruktion (engelska) // Combinatorial Algorithms on Words / A. Apostolico , Z. Galil - Springer Berlin Heidelberg , 1985. - P. 97-107. - ISBN 978-3-642-82456-2 - doi:10.1007/978-3-642-82456-2_7
Inenaga S. Bidirectional Construction of Suffix Trees (engelska) // Nordic Journal of Computing - 2003. - Vol. 10, Iss. 1. - S. 52-67. — ISSN 1236-6064
Inenaga S., Hoshino H., Shinohara A., Takeda M., Arikawa S., Mauri G., Pavesi G. On-line konstruktion av kompakta riktade acykliska ordgrafer // Discrete Applied Mathematics - Elsevier BV , 2005. Vol. 146, Iss. 2. - S. 156-179. — ISSN 0166-218X ; 1872-6771 - doi:10.1016/J.DAM.2004.04.012
Inenaga S., Hoshino H., Shinohara A., Takeda M., Arikawa S. Konstruktion av CDAWG för ett försök (engelska) // Prague Stringology Conference - Tjeckiska tekniska universitetet i Prag : 2001. - S. 37-48.
Inenaga S., Shinohara A., Takeda M., Arikawa S. Kompakt riktade acykliska ordgrafer för ett glidande fönster (engelska) // Journal of Discrete Algorithms - Elsevier BV , 2004. - Vol. 2, Iss. 1. - S. 33-51. — ISSN 1570-8667 ; 1570-8675 - doi:10.1016/S1570-8667(03)00064-9
Yamamoto J., I T., Bannai H., Inenaga S., Takeda M. Faster Compact On-Line Lempel-Ziv Factorization (engelska) // Symposium on Theoretical Aspects of Computer Science / E. Mayr , N. Portier — 2014 - Vol. 25. - s. 675-686. — ISBN 978-3-939897-65-1 — ISSN 1868-8969 — doi:10.4230/LIPICS.STACS.2014.675
Fujishige Y., Tsujimaru Y., Inenaga S., Bannai H., Takeda M. Computing DAWGs and Minimal Absent Words in Linear Time for Heltal Alphabets // Mathematical Foundations of Computer Science / P. Faliszewski , A. Muscholl , R. Niedermeier - 2016. - Vol. 58—S. 38:1–38:14. — ISBN 978-3-95977-016-3 — ISSN 1868-8969 — doi:10.4230/LIPICS.MFCS.2016.38
Mohri M., Moreno P., Weinstein E. Allmänt suffix automatkonstruktionsalgoritm och rymdgränser (engelska) // Theoretical Computer Science - Elsevier BV , 2009. - Vol. 410, Iss. 37. - P. 3553-3562. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/J.TCS.2009.03.034
Faro S. Evaluation and Improvement of Fast Algorithms for Exact Matching on Genome Sequences (engelska) // Algorithms for Computational Biology / M. Botón-Fernández , C. Martín-Vide , M. A. Vega-Rodríguez - Springer International Publishing , 2016. 145-157. - ISBN 978-3-319-38827-4 - doi:10.1007/978-3-319-38827-4_12
Crochemore M. , Hancart C. Automata for Matching Patterns (engelska) // Handbook of Formal Languages / G. Rozenberg , A. Salomaa - Springer Berlin Heidelberg , 1997. - Vol. 2. - s. 399-462. - ISBN 978-3-642-59136-5 - doi:10.1007/978-3-662-07675-0_9
Crochemore M. , Vérin R. Om kompakt riktade acykliska ordgrafer (engelska) // Structures in Logic and Computer Science : A Selection of Essays in Honor of A. Ehrenfeucht / J. Mycielski , G. Rozenberg , A. Salomaa - Springer Berlin Heidelberg , 1997. - P. 192-211. — ISBN 978-3-540-69242-3 — doi:10.1007/3-540-63246-8_12
Crochemore M. , Iliopoulos C. S. , Navarro G. , Pinzon Y. J. A Bit-Parallel Suffix Automaton Approach for (δ,γ)-Matching in Music Retrieval // String Processing and Information Retrieval / M. A. Nascimento , E. S. L. Moura Berlin , A. L. Heidelberg , 2003. - S. 211-223. - ISBN 978-3-540-39984-1 - doi: 10.1007/978-3-540-39984-1_16
Hopcroft J. E. , Ullman J. D. Introduktion till automatteori, språk och beräkningar (eng.) - 1 - MA : Addison-Wesley , 1979. - 418 sid. — ISBN 978-81-7808-347-6
Fiala E. R., Greene D. H. Datakomprimering med ändliga fönster // Commun . ACM - [New York] : Association for Computing Machinery , 1989. - Vol. 32, Iss. 4. - S. 490-505. — ISSN 0001-0782 ; 1557-7317 - doi:10.1145/63334.63341
Senft M., Dvořák T. Sliding CDAWG Perfection (engelska) // String Processing and Information Retrieval / A. Turpin , A. Moffat , A. Amir - Springer Berlin Heidelberg , 2008. - S. 109-120. — ISBN 978-3-540-89097-3 — doi:10.1007/978-3-540-89097-3_12
Larsson N. J. Utökad tillämpning av suffixträd för datakomprimering // Proceedings . Datakompressionskonferens - IEEE , 1996. - P. 190-199. - ISBN 0-8186-7358-3 - ISSN 2375-0383 ; 2375-0391 ; 1068-0314 ; 2375-0359 - doi:10.1109/DCC.1996.488324
Brodnik A. , Jekovec M. Sliding Suffix Tree (engelska) // Algorithms - MDPI , 2018. - Vol. 11, Iss. 8. - P. 118. - ISSN 1999-4893 - doi:10.3390/A11080118
Rubinchik M., Shur A. M. Eertree (engelska) : En effektiv datastruktur för bearbetning av palindromer i strängar // European Journal of Combinatorics / P. O. Mendez , P. Rosentiehl , É. C. Verdière , A. Björner , F. Brenti , A. Brouwer , P. Cameron , R. Cordovil , D. Foata , P. Frankl et al. — Elsevier BV , 2018. — Vol. 68. - S. 249-265. — ISSN 0195-6698 ; 1095-9971 - doi:10.1016/J.EJC.2017.07.021 - arXiv:1506.04862
Serebryakov V. A. , Galochkin M. P. , Furugyan M. G. , Gonchar D. R. Teori och implementering av programmeringsspråk : Lärobok - M .: MZ Press , 2006. - 352 s. — ISBN 5-94073-094-9
Rubtsov A. A. Anteckningar och problem om vanliga språk och finita automater - Moskva : MIPT , 2019. - 112 sid. — ISBN 978-5-7417-0702-9
Parashchenko D. A. Strängbearbetning baserad på suffixautomater - St. Petersburg. : ITMO , 2007. - 35 sid.

Länkar

suffix automat. Bygger i O(N) och tillämpar . MAXimal . (obestämd)
Suffix automat . ITMO Wikinotes . (obestämd)

Strängar
Stränglikhetsmått	Avstånd från Damerau till Loewenstein Levenshtein avstånd Hamming avstånd Jaro-Winkler likhet
Sök efter delsträng	Boyer-Moore algoritm Boyer-Moore-Horspool-algoritm Knuth-Morris-Pratt-algoritm Rabin-Karps algoritm prefixfunktion Z-funktion Algoritm Aho - Korasik
palindromer	palindromträd Manakers algoritm
Sekvensjustering	Needleman-Wunsha algoritm Smith-Waterman algoritm
Suffixstrukturer	Suffix array Suffix automat suffixträd prefixträd
Övrig	analysera Mönstermatchning Största vanliga följden Största gemensamma delsträngen

Formella språk och formella grammatiker
Allmänna begrepp	Chomsky hierarki Alfabet Ord
Typ 0	Obegränsad grammatik Turing maskin uppräknat språk Lösbart språk
Typ 1	Sammanhangskänslig grammatik Kontextkänsligt språk Linjärt begränsad automat
Typ 2	Kontextfri grammatik Tvetydig grammatik Kontextfritt språk Pushdown-automat ( deterministisk ) Tillväxt Lemma Ogdens Lemma Cooks teorem
Typ 3	Vanlig grammatik vanligt språk Vanligt uttryck Tillståndsmaskin ( deterministisk , icke- deterministisk ) DFA-minimering Bestämning av NFA Myhill-Nerodes sats
analysera	LL analysator LR-parser Rekursiv nedstigningsmetod Kok-Yngre-Kasami-algoritm