Sufix automat

Engleză sufix
automat grafic de cuvinte aciclice direcționate

Sufix automat pentru abcbc

Tip de

Index de subșiruri

Anul inventiei

1983

Autor

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

Complexitatea în simbolurile O

	În cel mai rău caz
Clădire	$O(\vert S\vert \log \vert \Sigma \vert )$
Consumul de memorie	$O(\vert S\vert )$

Fișiere media la Wikimedia Commons

Suffix automaton ( în engleză suffix automaton , directioned acyclic word graph ) este o structură de date care vă permite să stocați sub formă comprimată și să procesați informații asociate cu subșirurile unui șir dat. Reprezintă un automat finit determinist care acceptă toate sufixele unui cuvânt și numai ele și are cel mai mic număr posibil de stări dintre toate astfel de automate. Mai puțin formal, un automat sufix este un graf aciclic direcționat cu un vârf inițial distins unsimbolurilesunt etichetate cuarceși un set de vârfuri „finale”, concatenate , formează un sufix dat. Dintre toate graficele care satisfac această descriere, automatul sufix este cel care are cel mai mic număr posibil de vârfuri . $S=s_{1}s_{2}\dots s_{n)$ $S$

Automatul sufix a fost descris pentru prima dată de un grup de oameni de știință de la Universitatea din Denver și Colorado în 1983, ei au arătat, de asemenea, că dimensiunea automatului depinde liniar de lungime și au propus, de asemenea, un algoritm online pentru construirea acestuia cu un timp de rulare liniar . În lucrările ulterioare pe această temă, a fost descoperită o legătură strânsă între automatul sufix și arborele sufix , iar conceptul de automat sufix a primit diverse generalizări. Astfel, a fost introdus un automat sufix comprimat, obținut din cel original printr-o procedură similară cu cea aplicată unui sufix bor pentru a obține un arbore de sufix, precum și un automat sufix generalizat, care este construit pentru un set de cuvinte și acceptă cuvinte. care sunt sufixe ale cel puțin uneia dintre datele . $S$ $S_{1},S_{2},\dots,S_{k)$

Cu ajutorul unui automat sufix, puteți rezolva în mod eficient probleme precum căutarea unui subșir într-un șir , determinarea celui mai mare subșir comun de două sau mai multe șiruri și altele .

Istorie

Conceptul de automat sufix a fost introdus de un grup de oameni de știință de la Universitatea Denver și Colorado Anselm Blumer, Andrzej Ehrenvecht , David Haussler , Ross McConnell și Janet Bloomer în 1983, deși au fost întâlnite structuri legate de acesta. mai devreme în lucrarea lui Peter Weiner [1] , Vaughn Pratt [2] și Anatoly Olesevich Slisenko [3] s-au dedicat algoritmilor pentru construirea arborilor sufixi . În aceeași lucrare, Bloomer și alții au arătat că un automat construit dintr-un cuvânt de lungime mai mare decât acesta nu conține mai multe stări și nu mai multe tranziții și au prezentat, de asemenea, un algoritm liniar pentru construirea unui automat [4] . $S$ $unu$ $2|S|-1$ $3|S|-4$

În 1983, Mu Tian Chen și Joel Seiferas au dezvoltat în mod independent un algoritm pentru construirea unui automat sufix care arată că algoritmul lui Weiner [1] propus în 1973 pentru construirea unui arbore sufix de cuvânt construiește și un automat sufix pentru cuvântul inversat ca structură auxiliară [5] . În 1987, Bloomer și alții, prin analogie cu un arbore de sufixe, au descris un automat sufix comprimat [6] obținut dintr-un automat sufix prin ștergerea stărilor non-finale cu un semigrad de rezultat egal cu unu, iar în 1997 Maxime Crochemore și Renaud Verin a dezvoltat un algoritm liniar pentru construcția lui directă [7] . În 2001, Shunsuke Inenaga și alții au dezvoltat un algoritm liniar online pentru construirea unui automat sufix comprimat [8] , precum și un algoritm liniar pentru construirea unui automat sufix comprimat pentru un set de cuvinte date de un arbore de prefix [9] . $S$ ${\textstyle S^{R}}$

În lucrarea lor originală, Bloomer și colegii au definit structura pe care au descris-o ca un automat minim care recunoaște toate subșirurile (nu sufixele) unui cuvânt dat. Ei au numit această structură un grafic de cuvinte aciclice direcționate [ 4 ] . Ulterior, acest nume a fost folosit și ca sinonim pentru un automat finit aciclic determinist - un automat minim care recunoaște un set finit arbitrar de cuvinte (nu constituie neapărat un set de sufixe sau subșiruri ale unui anumit șir) [10] [ 11] .

Notație

Când se descriu automate sufixe și fapte și teoreme înrudite, sunt adesea folosite notații din teoria limbajelor formale în general și teoria automatelor în special [12] :

Un alfabet este un set finitdin care pot fi compuse cuvinte. Elementele sale sunt numite simboluri ; $\Sigma$
Un cuvânt este o secvență finită de caractere alfabetice. Lungimea cuvântuluise notează ca; $\omega =\omega _{1}\omega _{2}\dots \omega _{n)$ $\omega$ $|\omega |=n$
Un limbaj formal este un set de cuvinte pe un anumit alfabet;
Limbajul tuturor cuvintelor este notat ca (aici simbolul "*" poartă semnificația stelei Kleene ), un cuvânt gol (un cuvânt de lungime zero) - prin simbolul ; $\Sigma ^{*}$ $\varepsilon$
Concatenarea (produsul) cuvintelor șise notează casauși este egală cu cuvântul obținut prin atribuirealadreapta, adică; $\alpha =\alpha _{1}\alpha _{2}\dots \alpha _{n)$ $\beta =\beta _{1}\beta _{2}\dots \beta _{m)$ $\alpha \cdot \beta$ $\alpha \beta$ $\beta$ $\alfa$ $\alpha \beta =\alpha _{1}\alpha _{2}\dots \alpha _{n}\beta _{1}\beta _{2}\dots \beta _{m)$
Concatenarea limbilor și este desemnată ca sau și este egală cu setul de concatenări în perechi ; $A$ $B$ $A\cdot B$ $AB$ $AB=\{\alpha \beta:\alpha \in A,\beta \in B\)$
Dacă un cuvânt poate fi reprezentat ca , unde , atunci cuvintele , și sunt numite prefixul , sufixul și respectiv subcuvântul (subșirul) cuvântului ; $\omega \in \Sigma ^{*}$ $\omega =\alpha \gamma \beta$ $\alpha ,\beta ,\gamma \in \Sigma ^{*}$ $\alfa$ $\beta$ $\gamma$ $\omega$
Dacă , atunci spunem că cuvântul este inclus (apare) în ca subcuvânt. În acest caz , și sunt numite pozițiile de apariție din stânga și, respectiv, din dreapta. $T_{l}T_{l+1}\dots T_{r}=S$ $S$ $T$ $l$ $r$ $S$ $T$

Structura automată

Formal, un automat finit determinist este definit de un set de cinci elemente în care: ${\mathcal {A}}=(\Sigma,Q,q_{0},F,\delta)$

$\Sigma$ - alfabet , care constă din cuvinte recunoscute de mașină,
$Q$ este setul de stări automate,
$q_{0}\in Q$ este starea inițială a mașinii,
$F\subset Q$ este setul de stări finale ale automatului,
$\delta:Q\times \Sigma \mapsto Q$ este o funcție de tranziție parțial definită a automatului, astfel încât pentru și fie nu este definită, fie indică o stare în care se poate face o tranziție de la la . $\delta (q,\sigma)$ $q\in Q$ $\sigma \in \Sigma$ $q$ $\sigma$

Cel mai adesea, în practică, automatele finite sunt reprezentate ca un grafic dirijat ( diagramă ) astfel încât [13] :

Mulțimea vârfurilor graficului corespunde setului de stări , $Q$
Un anumit vârf este selectat în grafic, corespunzător stării inițiale , $q_{0}$
Graficul are un set de vârfuri corespunzătoare setului de stări finale , $F$
Setul de arce din grafic corespunde setului de tranziții , $\delta$
În acest caz, tranziția corespunde unui arc de la la , marcat cu simbolul alfabetic . Această tranziție este denumită și . ${\textstyle \delta (q_{1},\sigma )=q_{2}}$ $q_{1}$ $q_{2}$ $\sigma$ ${\textstyle q_{1}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}q_{2}}$

Într-un astfel de grafic, vârfurile și arcurile sunt identificate cu stări și, respectiv, tranziții ale automatului. Automatul acceptă un cuvânt dacă și numai dacă există o cale de la starea inițială la o stare finală , astfel încât dacă concatenăm simbolurile întâlnite pe această cale, obținem cuvântul . Setul de cuvinte pe care le acceptă un automat formează limbajul acestui automat [12] . $\omega =\omega _{1}\omega _{2}\dots \omega _{m)$ $q_{0}$ $q\in F$ $\omega$

Stări automate

Contextul corect al unui cuvânt relativ la limbă se numește mulțime . Adică, acesta este un set de cuvinte , atribuindu-le cuvântului din dreapta, rezultă un cuvânt din limbă . Contextele corecte induc o relație naturală de echivalență pe mulțimea tuturor cuvintelor. Dacă un limbaj poate fi definit de un automat finit determinist, atunci pentru el există un automat unic, până la izomorfism , care are în același timp cel mai mic număr posibil de stări. Un astfel de automat este numit minim pentru un limbaj dat , teorema Myhill-Nerode ne permite să-l specificăm în mod explicit [14] [15] : $\omega$ $L$ $[\omega]_{R}=\{\alpha:\omega \alpha \in L\)$ $\alfa$ $\omega$ $L$ ${\displaystyle [\alpha ]_{R}=[\beta ]_{R))$ $L$ $L$

Un automat minim care recunoaște o limbă peste un alfabet poate fi dat după cum urmează: $L$ $\Sigma$

Alfabetul rămâne neschimbat $\Sigma$
Stările corespund contextelor corecte ale tuturor cuvintelor , $Q$ $[\omega]_{R)$ $\omega \in \Sigma ^{*}$
Starea inițială corespunde contextului corect al cuvântului gol , $q_{0}$ $[\varepsilon]_{R)$
Stările finale corespund contextelor corecte ale cuvintelor din limbă , $F$ $[\omega]_{R)$ $\omega \in L$
Tranzițiile au forma , unde și . $\delta$ $[\omega ]_{R}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}[\omega \sigma ]_{R}$ $\omega \in \Sigma ^{*}$ $\sigma \in \Sigma$

Într-o astfel de notație, un automat sufix este un DFA minim care acceptă cuvântul sufix language . Contextul corect al unui cuvânt în raport cu o limbă dată constă din cuvinte astfel încât - sufix . Acest lucru ne permite să formulăm următoarea lemă, care definește o corespondență unu-la-unu între contextul corect al unui cuvânt și setul de poziții ale aparițiilor sale în subcuvânt [16] [17] : $S=s_{1}s_{2}\dots s_{n)$ $\omega$ $\alfa$ $\omega \alpha$ $S$ $S$

Fie setul de poziții corecte ale aparițiilor în . $endpos(\omega)=\{r:\omega =s_{l}\dots s_{r}\}$ $\omega$ $S$

Între elementele seturilor și există următoarea corespondență unu-la-unu: $endpos(\omega )$ $[\omega]_{R)$

Dacă , atunci ; $x\in endpos(\omega )$ $s_{x+1}s_{x+2}\dots s_{n}\in [\omega ]_{R)$
Dacă , atunci . $\alpha \in [\omega]_{R)$ $n-\vert \alpha \vert \in endpos(\omega)$

De exemplu, pentru un cuvânt și subcuvântul său și . În mod informal, constă din cuvinte care urmează aparițiile până la sfârșitul cuvântului și - de la pozițiile acestor apariții. În acest exemplu, elementul se potrivește cu cuvântul . În același timp, elementul corespunde cuvântului . $S=abacaba$ $\omega =ab$ $endpos(ab)=\{2,6\}$ $[ab]_{R}=\{a,acaba\)$ $[ab]_{R)$ $ab$ $endpos(ab)$ $x=2\in endpos(ab)$ $s_{3}s_{4}s_{5}s_{6}s_{7}=acaba\in [ab]_{R)$ $a\in [ab]_{R)$ $7-|a|=6\in endpos(ab)$

Din aceasta rezultă o serie de proprietăți structurale ale stărilor automatului sufix și cuvintele pe care le acceptă. Fie , atunci [17] : $|\alpha |\leq |\beta |$

Dacă și are cel puțin un element comun , atunci elementul comun are și . Aceasta, la rândul său, înseamnă că este un sufix și, prin urmare, și . În exemplul de mai sus, și, ca o consecință, este un sufix , precum și și ; $[\alpha ]_{R)$ $[\beta]_{R)$ $X$ $endpos(\alpha )$ $endpos(\beta)$ $\alfa$ $\beta$ $endpos(\beta)\subset endpos(\alpha)$ $[\beta]_{R}\subset [\alpha ]_{R)$ $a\in[ab]_{R}\cap[cab]_{R)$ $ab$ $cabin$ $[cab]_{R}=\{a\}\subset \{a,acaba\}=[ab]_{R)$ $endpos(cab)=\{6\}\subset \{2,6\}=endpos(ab)$
Dacă , atunci , adică apare în doar ca sufix . Acest lucru poate fi văzut în exemplul cuvintelor și , pentru care și ; ${\displaystyle [\alpha ]_{R}=[\beta ]_{R))$ $endpos(\alpha)=endpos(\beta)$ $\alfa$ $S$ $\beta$ $\alpha =b$ $\beta =ab$ $[b]_{R}=[ab]_{R}=\{a,acaba\)$ $endpos(b)=endpos(ab)=\{2,6\}$
Dacă și este un sufix astfel încât , atunci . În exemplul de mai sus, , iar sufixul „intermediar” este . Și într-adevăr, . ${\displaystyle [\alpha ]_{R}=[\beta ]_{R))$ $\gamma$ $\beta$ $|\alpha |\leq |\gamma |\leq |\beta |$ $[\alpha ]_{R}=[\gamma ]_{R}=[\beta ]_{R)$ $[c]_{R}=[bac]_{R}=\{aba\)$ $\gamma =ac$ $[ac]_{R}=\{aba\)$

Astfel, orice stare a automatului sufix acceptă un lanț continuu de sufixe imbricate ale celui mai mare șir din această stare [17] . $q=[\alpha ]_{R)$

Extensia din stânga a unui șir este cel mai lung șir care are același context drept ca și . Lungimea celui mai lung șir acceptat de stat este notată ca . Este adevărat pentru el că [18] : ${\overset {\scriptstyle {\leftarrow }}{\gamma }}$ $\gamma$ $\omega$ $\gamma$ $|{\overset {\scriptstyle {\leftarrow }}{\gamma }}|$ $q=[\gamma]_{R)$ $len(q)$

Extensia din stânga a unui șir poate fi reprezentată ca , unde este cel mai lung cuvânt, astfel încât orice apariție a unui cuvânt în este precedată de cuvânt . $\gamma$ ${\overleftarrow {\gamma }}=\beta \gamma$ $\beta$ $\gamma$ $S$ $\beta$

O legătură de sufix de la o stare este un pointer către starea care conține cel mai mare sufix care nu este acceptat de stat . $link(q)$ $q=[\alpha ]_{R)$ $p$ $\alfa$ $q$

În această notație, putem spune că statul ia exact toate sufixele care sunt mai lungi decât și nu mai lungi decât . În plus, următoarele sunt adevărate [18] : $q=[\alpha ]_{R)$ ${\overset {\scriptstyle {\leftarrow }}{\alpha }}$ $len(link(q))$ $len(q)$

Legăturile sufixelor formează un arbore , care poate fi specificat în mod explicit după cum urmează: ${\mathcal {T}}(V,E)$

Vârfurile corespund expansiunilor din stânga tuturor subșirurilor , $V$ ${\overleftarrow {\omega ))$ $S$
Muchiile conectează vârfuri astfel încât și . $E$ $({\overleftarrow {\omega )),{\overleftarrow {\alpha \omega )))$ $\alpha \in \Sigma$ ${\overleftarrow {\omega }}\neq {\overleftarrow {\alpha \omega }}$

Legătura cu arborele sufixului

Un arbore de prefix (sau un alezaj ) este un arbore orientat spre rădăcină, ale cărui arcuri sunt marcate cu simboluri astfel încât sănu iasă mai mult de un arc din orice vârf al acestui arbore , etichetat cu un simbol dat. Unele vârfuri din arborele de prefix sunt etichetate. Se spune că un arbore de prefix definește un set de cuvinte definite de căi de la rădăcina arborelui până la vârfurile etichetate. Astfel, arborii de prefix sunt un tip special de automată finită, dacă considerăm rădăcina ca stare inițială, iar vârfurile etichetate ca stări finale [19] . Sufixul bor al unui cuvânteste un arbore de prefix care definește limba sufixelor acestui cuvânt. Un arbore de sufix este un arbore obținut dintr-un orificiu de sufix printr-o procedură de compresie, în care muchiile succesive sunt lipite între ele dacă între ele există un vârf nefinal, al cărui grad este 2 [18] . $v$ $S$

Prin definiție, un automat sufix poate fi obținut prin minimizarea unui alezaj sufix. În plus, un automat sufix comprimat poate fi obținut atât prin minimizarea unui arbore sufix (presupunând că simbolurile alfabetului sunt cuvinte de pe marginile arborelui), cât și prin comprimarea unui automat convențional [8] . Totuși, pe lângă legătura evidentă dintre automatul sufix și arborele sufix al aceluiași șir, se poate stabili și o oarecare corespondență între automatul sufix al unui șir și arborele sufix al unui șir inversat [20] . $S=s_{1}s_{2}\dots s_{n)$ $S^{R}=s_{n}s_{n-1}\dots s_{1)$

Similar contextelor din dreapta, se pot introduce contexte din stânga și extensii din dreapta corespunzătoare celor mai lungi șiruri având un context din stânga dat, precum și o relație de echivalență . Dacă luăm în considerare extensiile corecte cu privire la limbajul prefixului șirului , atunci putem obține că [18] : $[\omega ]_{L}=\{\beta \in \Sigma ^{*}:\beta \omega \in L\)$ ${\overset {\scriptstyle {\rightarrow }}{\omega ~}}$ $[\alpha ]_{L}=[\beta ]_{L)$ $L$ $S$

Arborele sufixului unui șir poate fi specificat în mod explicit după cum urmează: $S$

Vârfurile corespund extensiilor drepte ale tuturor subșirurilor , $V$ ${\overrightarrow {\omega ))$ $S$
Muchiile corespund unor triple astfel încât și . $E$ $({\overrightarrow {\omega )),x\alpha ,{\overrightarrow {\omega x}))$ $x\in \Sigma$ ${\overrightarrow {\omega x}}={\overrightarrow {\omega }}x\alpha$

Aici, triplul înseamnă că șirul de la la este scris pe margine . $(v_{1},\omega,v_{2})\in E$ $v_{1}$ $v_{2}$ $\omega$

Din care rezultă că arborele legăturilor sufixelor pentru un automat cu șir și arborele sufixului unui șir sunt izomorfe [20] : $S$ $S^{R}$

Structuri de sufixe ale cuvintelor abbcbc și cbcbba
Sufix automat pentru cuvântul abcbc Sufixul bor, sufixul arborelui și sufixul comprimat automat pentru cuvântul abbcbc . Numerele vârfurilor corespund stărilor în care intră la minimizare sau micșorare. Arborele de sufixe pentru cuvântul cbcbba (arborele de legături de sufixe pentru automatul cuvântului abbcbc )

Similar extensiilor din stânga, o lemă structurală [18] poate fi formulată și pentru extensiile din dreapta :

Extensia dreaptă a unui șir poate fi reprezentată ca , unde este cel mai lung cuvânt, astfel încât orice apariție a lui în este imediat urmată de cuvânt . $\gamma$ ${\overrightarrow {\gamma }}=\gamma \alpha$ $\alfa$ $\gamma$ $S$ $\beta$

Dimensiune

Într-un automat sufix, șirurile de lungime nu sunt mai mult decât stări și nu mai mult decât tranziții, iar aceste estimări sunt realizate pe șiruri și, respectiv , [16] . De asemenea, este posibil să se formuleze o afirmație mai puternică despre relația dintre numărul de stări și tranziții dintr-un automat: , unde și sunt numărul de tranziții și, respectiv, de stări [17] . $S$ $n>1$ $2n-1$ $3n-4$ $abb\dots bb=ab^{n-1)$ $abb\dots bc=ab^{n-2}c$ $|\delta |\leq |Q|+n-2$ $|\delta |$ $|Q|$

Sufix maxim automate
Sufix automat pentru $ab^{n-1}$ Sufix automat pentru $ab^{n-2}c$

Clădire

Automatul sufix al unui șir se construiește prin construirea succesivă a cuvântului pentru care este construit. Inițial, există un automat banal construit pentru un cuvânt gol, iar apoi la fiecare pas se adaugă un simbol cuvântului curent, ceea ce presupune o rearanjare a stărilor și tranzițiilor automatului [21] . $S=s_{1}s_{2}\dots s_{n)$

Schimbarea statelor

După atribuirea unui nou caracter unui cuvânt, unele clase de echivalență se vor schimba. Fie contextul corect al cuvântului în raport cu limba sufixului cuvântului . Apoi trecerea de la la la atribuirea unui simbol unui cuvânt este descrisă de următoarea lemă [17] : $[\alpha ]_{R_{\omega ))$ $\alfa$ $\omega$ $[\alpha ]_{R_{\omega ))$ $[\alpha ]_{R_{\omega x))$ $X$ $\omega$

Să fie câteva cuvinte peste un alfabet și să fie un simbol al acestui alfabet. Apoi, între contextele potrivite și cuvintele cu privire la limbile sufixelor cuvintelor și, respectiv, are loc următoarea relație: $\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 \}$ dacă - sufix ; $\alfa$ $\omega x$
$[\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x$ in caz contrar.

Adică, atunci când un caracter este adăugat cuvântului curent, contextul corect al cuvântului se poate schimba numai dacă este un sufix de cuvânt . De aici rezultă că împărțirea tuturor cuvintelor în clase de echivalență cu privire la este o rafinare a împărțirii în clase de echivalență cu privire la . Cu alte cuvinte, dacă , atunci . În plus, atunci când adăugați următorul simbol la cuvânt, împărțirea va avea loc în cel mult două stări. În primul rând, starea care corespunde contextului drept gol (adică cea care ia limba cuvintelor care nu sunt incluse ca subcuvânt) va fi împărțită. Din această stare, va fi extrasă o nouă stare care conține întregul cuvânt , precum și toate sufixele acestuia care apar în dar nu au apărut în . În consecință, contextul corect al acestor cuvinte, care anterior era gol, va consta acum doar din cuvântul gol [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$

Ținând cont de legătura dintre stările automatului sufix și vârfurile arborelui sufix, putem urmări și a doua stare, care se poate diviza atunci când este adăugat următorul simbol. Deoarece o tranziție de la -la cuvântul corespunde unei tranziții la - la un șir inversat, alocarea unui caracter unui șir corespunde cu adăugarea unui nou (cel mai lung) sufix la arborele de sufixe al șirului . În acest caz, nu apar mai mult de două vârfuri: unul dintre ele va corespunde întregului cuvânt , iar celălalt poate apărea în locul în care apare ramura din copac. Astfel, o stare nouă corespunde contextului corect al întregului șir , iar cealaltă (dacă există) poate corespunde doar referinței sufixului acelei stări. Aceste observații pot fi generalizate prin teorema [17] : $\omega$ $\omega x$ $\omega ^{R}$ $x\omega ^{R}$ $X$ $\omega$ $x\omega ^{R}$ $\omega ^{R}$ $x\omega ^{R}$ $\omega x$

Lasă și . Fie, de asemenea , cel mai lung sufix care apare în , și fie extensia sa din stânga față de , adică cel mai lung subcuvânt al cuvântului astfel încât . Atunci următoarele sunt valabile pentru orice subcuvinte ale cuvântului : $\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$

Dacă și , atunci ; $[u]_{R_{\omega }}=[v]_{R_{\omega }}$ $[u]_{R_{\omega }}\neq [\alpha ]_{R_{\omega }}$ $[u]_{R_{\omega x}}=[v]_{R_{\omega x}}$
Dacă și , atunci ; $[u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}$ $\vert u\vert \leq \vert \alpha \vert$ $[u]_{R_{\omega x}}=[\alpha ]_{R_{\omega x}}$
Dacă și , atunci . $[u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}$ $\vert u\vert >\vert \alpha \vert$ $[u]_{R_{\omega x))=[\beta ]_{R_{\omega x))$

În special, dacă (de exemplu, când nu apare deloc în și ), divizarea celei de-a doua stări nu are loc [17] . $\alpha =\beta$ $X$ $\omega$ $\alpha =\beta =\varepsilon$

Pe lângă legăturile sufixe, în noul automat trebuie să se definească și stările finale. Din proprietățile structurale ale automatului rezultă că sufixele oricărui cuvânt sunt situate în așa fel încât dacă , atunci sufixele a căror lungime depășește , se află în , sufixele a căror lungime este mai mare decât , dar nu mai mare decât , se află în , și curând. Cu alte cuvinte, pentru orice sufix există un vârf în calea stării sufixului , care este dat de secvența . În consecință, dacă desemnăm starea care acceptă în prezent întregul șir ca fiind , atunci stările terminale (acceptând sufixe ) vor fi acele și numai acele stări care sunt incluse în calea sufixului [21] . $\alfa$ $q=[\alpha ]_{R)$ $\alfa$ $len(link(q))$ $q$ $len(link(link(q))$ $len(link(q))$ $link(q)$ $\alfa$ $q$ $(q,link(q),link^{2}(q),\dots )$ $\omega$ $ultimul$ $\omega$ $(ultimul,link (ultimul), link^{2}(ultimul),\dots )$

Schimbarea sărituri și legături sufixe

Orice modificare la adăugarea următorului caracter nu afectează mai mult de două stări noi, așa că modificările în tranzițiile automatului vor afecta, de asemenea, numai aceste stări. După atribuirea cuvântului , se formează o nouă stare și, eventual, o stare . Legătura sufixului de la va duce la , și de la - la . Cuvintele de la apar doar ca sufixe, deci nu ar trebui să existe tranziții de la, iar tranzițiile care conduc la acesta trebuie să conducă după caractere de la sufixe cu o lungime de cel puțin . Statul este împărțit din , așa că tranzițiile din această stare le vor duplica pe cele din . Iar tranzițiile care conduc la acesta vor conduce prin simbol din stările corespunzătoare sufixelor de lungime mai mică decât și nu mai mică decât , deoarece mai devreme aceste tranziții au condus și au corespuns la partea separată a statului. Stările care acceptă aceste cuvinte pot fi identificate prin calea sufixului de stat [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$ $|\alpha |$ $[\alpha ]_{R_{\omega x))$ $[\alpha ]_{R_{\omega ))$ $[\alpha ]_{R_{\omega ))$ $X$ $\omega$ $|\alpha |$ $len(link([\alpha ]_{R_{\omega ))))$ $[\alpha ]_{R_{\omega ))$ $[\omega]_{R_{\omega ))$

Construirea unui automat sufix pentru cuvântul abcbc

∅ → a


Când primul simbol este adăugat, o singură stare nouă este creată în automat.	În mod similar, o singură frunză este adăugată arborelui sufix.

a→ab


Sunt trase noi tranziții din toate stările finale, deoarece noul simbol nu a mai fost întâlnit înainte.	Din același motiv, într-un arbore de legături sufixe, noul nod este suspendat de la rădăcină.

ab → abb


Starea 2 ia cuvintele ab și b , dar numai b va deveni un sufix, astfel încât acel cuvânt este alocat stării 4.	În arborele sufix al cuvântului extins, aceasta corespunde împărțirii muchiei care duce la vârful 2.

abb → abbc


Noul simbol nu a mai fost văzut până acum, se efectuează tranziții către el din toate cele finale.	O nouă frunză este adăugată arborelui de legături sufixe suspendate de rădăcină.

abbc → abbcb


În starea 4, există doar cuvântul b și este un sufix, deci nu are loc nicio divizare.	În consecință, în arborele legăturilor sufixelor, o nouă frunză este suspendată de vârful 4.

abbcb → abbcbc


Starea 5 acceptă cuvintele abbc , bbc , bc și c , dar numai ultimele două sunt sufixe ale noului cuvânt, deci sunt separate într-o stare separată 8.	În consecință, în arborele legăturilor sufixe, muchia care duce la vârful 5 este împărțită.

Algoritm pentru construirea unui automat

Rezultatele teoretice de mai sus conduc la următorul algoritm, care ia un simbol și rearanjează un automat sufix de cuvânt într-un automat sufix de cuvânt [21] : $X$ $\omega$ $\omega x$

Este acceptat un număr de stare corespunzător întregii linii ; $ultimul$ $\omega$
Când se adaugă un simbol , numărul este stocat în variabilă , iar numărul noii stări corespunzător cuvântului este scris în ; $X$ $ultimul$ $p$ $ultimul$ $\omega x$
Din stările corespunzătoare sufixelor se aplică treceri la . Pentru a face acest lucru, calea sufixului este ocolită până când este întâlnită o stare din care există deja o tranziție de-a lungul ; $\omega$ $ultimul$ $p,link(p),link^{2}(p),\dots$ $X$
Acțiunile ulterioare corespund unuia dintre cele trei cazuri:
1. Dacă pe întreaga cale de sufix nu există nicio tranziție de la nicio stare la , atunci nu a fost întâlnită anterior în și legătura sufixului de la duce la ; $X$ $X$ $\omega$ $ultimul$ $q_{0}$
2. Dacă tranziția prin a fost găsită și duce de la o stare la alta astfel încât , atunci nu este nevoie să se despartă și este suficient să se tragă o legătură sufixă de la la ; $X$ $p$ $q$ $len(p)+1=len(q)$ $q$ $ultimul$ $q$
3. Dacă , atunci cuvintele din statul a căror lungime nu depăşeşte trebuie separate într - o stare separată ; $len(q)>len(p)+1$ $q$ $len(p)+1$ $cl$
Dacă la pasul anterior a fost selectată o stare separată , atunci tranzițiile și legătura sufixului de la aceasta ar trebui să le dubleze în , în timp ce va deveni o legătură sufix comună a stărilor și ; $cl$ $q$ $cl$ $q$ $ultimul$
Salturile care au condus la cuvintele potrivite cu lungimea nu mai mare de , sunt redirecționate către . Pentru a face acest lucru, puteți continua să urmați calea sufixului până când găsiți o stare, tranziția de la care nu duce la . $q$ $len(p)+1$ $cl$ $p$ $q$

Procedura care implementează acest algoritm poate fi descrisă prin următorul pseudocod:

funcția add_letter(x) : define p = last assign last = new_state() assign len(last) = len(p) + 1 până când δ(p, x) este definit: atribui δ(p, x) = last, p = link(p) define q = δ(p, x) if q = last : atribuie link(ultim) = q 0 else if len(q) = len(p) + 1 : atribui link(last) = q else : define cl = new_state() atribuiți len(cl) = len(p) + 1 atribuiți δ(cl) = δ(q), link(cl) = link(q) atribuiți link(last) = link(q) = cl while δ(p, x) = q : atribuiți δ(p, x) = cl, p = link(p)

Aici , este starea inițială a automatului și este o funcție care adaugă o nouă stare automatului. Se presupune că , , și sunt stocate ca variabile globale. $q_{0}$ $nou\_state()$ $ultimul$ $len$ $link$ $\delta$

Complexitate computațională

În funcție de structurile utilizate, o versiune deterministă a algoritmului descris mai sus poate fi implementată în timp de memorie sau în timp de memorie , presupunând că alocarea memoriei are loc în . În același timp, pentru a obține o astfel de estimare a timpului de rulare, este necesar să se efectueze o analiză de amortizare a ciclurilor interne ale algoritmului. Dacă luăm în considerare modul în care parametrul se modifică după prima iterație a primei bucle, putem vedea că scade strict cu fiecare iterație a buclei. Mai mult, dacă la ultima iterație a pasului precedent această valoare a fost egală cu , atunci la a doua iterație la pasul următor această valoare va fi egală cu . Că nu depășește în niciun moment de timp și că între cicluri această cantitate crește doar cu unul, dă afirmația necesară. O analiză similară poate arăta liniaritatea timpului total de execuție al celui de-al doilea ciclu al algoritmului [21] . $O(n\log |\Sigma |)$ $Pe)$ $Pe)$ $O(n|\Sigma |)$ $O(1)$ $len(p)$ $k$ $k+1$ $len(p)$ $n$

Variații și generalizări

Automatul sufixului este strâns legat de alte structuri de sufixe și indici de subșiruri . Având un automat sufix al unui șir, este posibil să se construiască un arbore sufix al acestui șir în timp liniar prin compresie și parcurgere recursivă a acestui automat [22] . Transformări similare în ambele direcții sunt posibile între un automat cu sufix de șir și un arbore de sufix de șir inversat [20] . În plus, au fost dezvoltate o serie de modificări ale algoritmului care permit construirea unui automat pentru un set de șiruri date de un arbore de prefix [9] , să-i aplice compresie [6] , să-și mențină structura într-un mod de fereastră glisantă [23] , și, de asemenea, reconstruiți atunci când adăugați caractere atât de la sfârșit, cât și de la începutul șirului [24] . $S$ $S^{R}$

Automat sufix comprimat

După cum am menționat mai sus, un automat sufix comprimat poate fi obținut dintr-un automat sufix obișnuit prin compresie (eliminând stările care nu sunt finale și din care duce exact o tranziție), precum și prin minimizarea arborelui sufix, dacă presupunem că alfabetul este format din cuvinte scrise pe marginile arborelui. În plus, stările unui automat comprimat pot fi descrise în mod explicit, similar modului în care a fost făcut pentru un automat necomprimat. O extensie de cuvânt cu două sensuri este cel mai lung cuvânt , astfel încât orice apariție în este precedată de un cuvânt și imediat urmată de un cuvânt . În ceea ce privește extensiile din stânga și din dreapta, aceasta înseamnă că extensia bidirecțională este extensia din stânga a extensiei din dreapta sau, echivalent, extensia din dreapta a extensiei din stânga: . În ceea ce privește extensiile bilaterale, un automat cu sufix comprimat poate fi descris după cum urmează [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 }{\ overset {\scriptstyle \leftarrow }{\gamma ))))$

Automatul sufixului comprimat al unui cuvânt poate fi dat de perechea , unde: $S$ $(V, E)$

$V=\{{\overleftrightarrow {\omega }}:\omega \in \Sigma ^{*}\}$ este ansamblul stărilor automatelor;
$E=\{({\overleftrightarrow {\omega }),x\alpha ,{\overleftrightarrow {\omega x}}):x\in \Sigma,\alpha \in \Sigma ^{*},{ \overleftrightarrow {\omega x}}={\overleftrightarrow {\omega }}x\alpha \}$ - un set de tranziții ale automatului.

Extensiile în două sensuri generează o relație de echivalență care descrie cuvintele acceptate de aceeași stare a automatului comprimat. Această relație este o închidere tranzitivă a relației , care subliniază faptul că stările unui automat sufix comprimat pot fi obținute atât prin lipirea vârfurilor arborelui sufixelor care sunt echivalente din punct de vedere al (minimizarea arborelui sufixului), cât și prin lipirea stărilor unui automat sufix care sunt echivalente din punct de vedere al (comprimare sufix automat) [25 ] . Dacă cuvintele și au aceleași extensii la dreapta, iar cuvintele și au extensiile din stânga, atunci în agregat cuvintele și au aceeași extensie bilaterală. În acest caz, se poate dovedi că cuvintele și nu au aceleași extensii la stânga sau la dreapta. În cazul lui , și extensiile din stânga și din dreapta sunt: , dar și . În cazul contextelor și extensiilor unidirecționale, cuvintele din aceeași clasă de echivalență formau un lanț continuu de prefixe sau sufixe imbricate și puteau fi determinate în mod unic de lungimile celor mai scurte și mai lungi cuvinte din clasă. În cazul extensiilor în două sensuri, se poate spune doar cu siguranță că cuvintele din aceeași clasă sunt subcuvinte ale celui mai lung cuvânt din această clasă, iar în caz contrar clasele pot avea o structură destul de complexă. Numărul total de astfel de clase de echivalență nu depășește , ceea ce implică faptul că un automat sufix comprimat al unui șir de lungime va avea cel mult stări. Numărul de tranziții într-un astfel de automat nu depășește [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$

Sufix automat pentru un set de șiruri

Să fie dat un set de cuvinte . Similar unui automat construit pe un singur cuvânt , putem considera un automat sufix generalizat care acceptă limbajul cuvintelor care sunt sufixul a cel puțin unui cuvânt din . În acest caz, pentru numărul de stări și tranziții ale acestui automat, toate aceleași restricții care au fost indicate mai sus vor fi satisfăcute dacă punem [25] . Algoritmul de construcție în sine este în esență similar cu algoritmul pentru construirea unui automat pentru o linie, dar în loc de un pointer către starea corespunzătoare cuvântului , atunci când trece la cuvântul , funcția add_letter va lua un pointer către starea care acceptă cuvânt , implicând că trecerea are loc de la setul curent de cuvinte la setul . În plus față de principalele acțiuni care sunt deja incluse în algoritm, va fi necesar să analizați separat cazul în care șirul este deja prezent în mașină - în acest caz, este posibil să trebuiască să împărțiți starea care îl acceptă, similar cu cum s-a întâmplat când se formează o legătură sufixă în algoritm pentru un singur cuvânt [26] [27] . $T=\{S_{1},S_{2},\dots,S_{k}}\}$ $S$ $T$ $n=|S_{1}|+|S_{2}|+\dots +|S_{k}|$ $ultimul$ $\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$

O dezvoltare ulterioară a acestei idei a fost construirea unui automat sufix pentru cazul în care mulțimea este specificată nu într-o formă explicită, ci ca un arbore de prefix pe vârfuri. Mohry și alții au arătat că un astfel de automat conține cel mult stări și poate fi construit în timp liniar în dimensiunea sa. În același timp, numărul de tranziții într-un astfel de automat poate ajunge - de exemplu, dacă luăm în considerare un set de cuvinte peste alfabet , atunci lungimea totală a cuvintelor din acest set va fi de ordinul , numărul de vârfuri în arborele de prefix corespunzător va fi egal cu , iar în automatul sufix va exista o ordine a stărilor și tranzițiilor. Algoritmul însuși, propus de Mohri, repetă în mare măsură algoritmul general pentru construirea unui automat dintr-un set de șiruri de caractere, dar în loc să adauge de fiecare dată caracterele unui cuvânt din mulțime de la început până la sfârșit, algoritmul străbate arborele de prefix în ordinea parcurgerii în lățime și atribuie următoarele caractere în acea ordine, în care le întâlnește în timpul parcurgerii, ceea ce garantează un timp de rulare liniar amortizat al algoritmului [28] . $T$ $Q$ $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}\}$ $\Sigma =\{a,\sigma _{1},\dots,\sigma _{k}\)$ ${\textstyle O(n^{2}+nk)}$ $O(n+k)$ $O(n+k)$ $O(nk)$

Fereastra glisantă

În unii algoritmi de compresie, cum ar fi LZ77 și RLE , poate fi util să stocați un automat sufix sau o structură similară nu pentru întregul cuvânt citit, ci doar pentru ultimele caractere. În primul rând, o astfel de nevoie apare din cauza specificului sarcinilor de comprimare a datelor, unde șirurile comprimate sunt de obicei destul de mari și utilizarea memoriei este nedorită. În 1985, Janet Bloomer a dezvoltat un algoritm care acceptă un automat sufix pe o fereastră de dimensiuni glisante și rulează pentru cel mai rău caz și medie, presupunând că caracterele din cuvântul care urmează să fie comprimat sunt distribuite independent și uniform . În aceeași lucrare s -a arătat că estimarea este de neîmbunătățit - dacă luăm în considerare cuvintele obținute prin formaconcatenarea mai multor cuvinte de pentru un sufix automat este imposibil [29] . $k$ $Pe)$ $k$ $O(nk)$ $O(n\log k)$ $O(nk)$ $(ab)^{m}c(ab)^{m}d$ $k=6m+2$ $k$ $m$ $O(nk)$

S-ar părea că același lucru ar trebui să fie valabil și pentru arborele sufix , deoarece vârfurile arborelui sufix corespund stărilor automatului sufix al șirului desfășurat. Cu toate acestea, dacă un vârf separat pentru fiecare sufix nu este alocat în arborele de sufixe, atunci nu vor exista astfel de salturi ascuțite și este posibilă construcția unui algoritm amortizat care să susțină arborele sufixului pe o fereastră glisantă. Un algoritm corespunzător pentru un arbore sufix, bazat pe algoritmul lui McCraith și care sprijină adăugarea unui nou caracter în dreapta și ștergerea unui caracter în stânga, a fost propus în 1989 de Edward Fiala și Daniel Green [30] , iar în 1996 a fost expus în termenii algoritmului lui Ukkonen de Jesper Larsson [31] [32] . În această privință, întrebarea dacă este posibil să se mențină o fereastră de alunecare rapidă pentru un automat comprimat, care combină unele proprietăți atât ale unui automat sufix obișnuit, cât și ale unui arbore de sufix, a rămas deschisă multă vreme. Un răspuns negativ la această întrebare a fost obținut în 2008 de Martin Senft și Tomasz Dvorak, care au arătat că, dacă alfabetul este format din două sau mai multe caractere, atunci timpul amortizat necesar pentru deplasarea ferestrei cu un caracter în cel mai rău caz este de ordinul din [33] . $O.K)$

În același timp, dacă lățimea exactă a ferestrei nu este importantă și scopul este doar menținerea unei ferestre a cărei lățime nu depășește , în ordinea mărimii, acest lucru se poate face cu algoritmul aproximativ propus de Inenaga și colab. 2004. O caracteristică a algoritmului este că „fereastra” care se mișcă de-a lungul cuvântului are o lungime variabilă, care în orice moment nu este nici mai mică, nici mai mare decât , în timp ce timpul total de rulare rămâne liniar [34] . $O.K)$ $k$ $2k+1$

Aplicații

Automatul sufix de șir poate fi folosit pentru a rezolva probleme precum [35] [36] : $S$

Numărarea numărului de subșiruri distincte de -a lungul timpului online, $S$ $O(|S|)$
Găsirea celui mai lung subșir care este inclus în el de cel puțin două ori, în timp , $S$ $O(|S|)$
Găsirea celui mai mare subșir comun de șiruri și în timp , $S$ $T$ $O(|T|)$
Numărarea numărului de apariții ale unui șir ca subșir în timp , $T$ $S$ $O(|T|)$
Căutați toate aparițiile în timp , unde este numărul de apariții. $T$ $S$ $O(|T|+k)$ $k$

Aici merită să luați în considerare faptul că se introduce un șir atunci când automatul a fost deja construit și este gata de utilizare. $T$

Automatele sufixelor și-au găsit drumul în aplicații precum compresia datelor [37] , identificarea muzicii din fragmente înregistrate [38] [39] și potrivirea secvenței genomice [40] .

Note

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

Literatură

Sgarbas K. N., Fakotakis N. D., Kokkinakis G. K. Inserție optimă în DAWG-uri deterministe // Teoretic Computer Science - Elsevier BV , 2003. - Vol . 301, Iss. 1-3. - P. 103-117. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/S0304-3975(02)00571-6
Perrin D. Finite Automata // Formal Models and Semantics : 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. Algoritmi de potrivire a modelelor lineare (engleză) // Symposium on Foundations of Computer Science - 1973. - P. 1-11. — 213p. doi : 10.1109/SWAT.1973.13
Pratt V. R. Îmbunătățiri și aplicații pentru găsitorul de repetiții Weiner (engleză) - 1973.
Slisenko A. O. Detectarea periodicităților și potrivirea șirurilor în timp real (engleză) // 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. Construirea DFA minimă pentru setul tuturor subcuvintelor unui cuvânt on-line în timp liniar // Automate , Languages y Programming - 1984 .- P. 109-118. — 526 p. — 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. Complete inverted files for efficient text retrieval and analysis // 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. Cât costă acel DAWG din fereastră? Un algoritm de fereastră în mișcare pentru graficul de cuvinte aciclice direcționate (engleză) // Journal of Algorithms - Academic Press , 1987. - Vol. 8, Iss. 4. - P. 451-469. — ISSN 0196-6774 ; 1090-2678 - doi:10.1016/0196-6774(87)90045-9
Chen M., Seiferas J. Efficient and Elegant Subword-Tree Construction (engleză) // 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. Construcția bidirecțională a arborilor sufixi (engleză) // Nordic Journal of Computing - 2003. - Vol. 10, Iss. 1. - P. 52-67. — ISSN 1236-6064
Inenaga S., Hoshino H., Shinohara A., Takeda M., Arikawa S., Mauri G., Pavesi G. On-line construction of compact directioned acyclic word graphs // Discrete Applied Mathematics - Elsevier BV , 2005. Vol. 146, Iss. 2. - P. 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. Construction of the CDAWG for a trie (engleză) // Praga Stringology Conference - Czech Technical University din Praga : 2001. - P. 37-48 .
Inenaga S., Shinohara A., Takeda M., Arikawa S. Compact directioned acyclic word graphs for a sliding window (engleză) // Journal of Discrete Algorithms - Elsevier BV , 2004. - Vol. 2, Iss. 1. - P. 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 (engleză) // Simpozion on Theoretical Aspects of Computer Science / E. Mayr , N. Portier — 2014 - Vol. 25. - P. 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 Integer Alphabets // Mathematical Foundations of Computer Science / P. Faliszewski , A. Muscholl , R. Niedermeier - 2016. - Vol. 58—P. 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. General suffix automaton construction algorithm and space bounds (engleză) // 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. Evaluare and Improvement of Fast Algorithms for Exact Matching on Genome Sequences (engleză) // Algorithms for Computational Biology / M. Botón-Fernández , C. Martín-Vide , M. A. Vega-Rodríguez - Springer International Publishing , 2016. - P 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 (engleză) // Handbook of Formal Languages / G. Rozenberg , A. Salomaa - Springer Berlin Heidelberg , 1997. - Vol. 2. - P. 399-462. - ISBN 978-3-642-59136-5 - doi:10.1007/978-3-662-07675-0_9
Crochemore M. , Vérin R. On compact directioned acyclic word graphs (english) // Structuri în 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. Moura , A. L. Oliveira - Springer Berlin Heidelberg , 2003. - P. 211-223. - ISBN 978-3-540-39984-1 - doi: 10.1007/978-3-540-39984-1_16
Hopcroft J. E. , Ullman J. D. Introduction to Automata Theory, Languages, and Computation (Eng.) - 1 - MA : Addison-Wesley , 1979. - 418 p. — ISBN 978-81-7808-347-6
Fiala E. R., Greene D. H. Comprimarea datelor cu ferestre finite // Commun . ACM - [New York] : Association for Computing Machinery , 1989. - Vol. 32, Iss. 4. - P. 490-505. — ISSN 0001-0782 ; 1557-7317 - doi:10.1145/63334.63341
Senft M., Dvořák T. Sliding CDAWG Perfection (engleză) // String Processing and Information Retrieval / A. Turpin , A. Moffat , A. Amir - Springer Berlin Heidelberg , 2008. - P. 109-120. — ISBN 978-3-540-89097-3 — doi:10.1007/978-3-540-89097-3_12
Larsson N. J. Aplicarea extinsă a arborilor de sufixe la compresia datelor // Proceedings . Data Compression Conference - 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 (engleză) // Algoritmi - MDPI , 2018. - Vol. 11, Iss. 8. - P. 118. - ISSN 1999-4893 - doi:10.3390/A11080118
Rubinchik M., Shur A. M. Eertree (engleză) : O structură de date eficientă pentru procesarea palindromilor în șiruri // 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. - P. 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. Teoria și implementarea limbajelor de programare : Manual - M .: MZ Press , 2006. - 352 p. — ISBN 5-94073-094-9
Rubtsov A. A. Note și probleme despre limbaje obișnuite și automate finite - Moscova : MIPT , 2019. - 112 p. — ISBN 978-5-7417-0702-9
Parashchenko D. A. Prelucrare șiruri bazată pe automate sufixe - Sankt Petersburg. : ITMO , 2007. - 35 p.

Link -uri

sufix automat. Construirea în O(N) și aplicarea . MAXimal . (nedefinit)
Sufix automat . Wikinote ITMO . (nedefinit)

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănarea Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun

Limbi formale și gramatici formale
Concepte generale	Ierarhia Chomsky Alfabet Cuvânt
Tip 0	Gramatică nelimitată mașină Turing limbaj enumerat Limbajul rezolvabil
Tipul 1	Gramatică sensibilă la context Limbaj sensibil la context Automat delimitat liniar
Tipul 2	Gramatică fără context Gramatică ambiguă Limbaj fără context Automat Pushdown ( determinist ) Lema de creștere Lema lui Ogden Teorema lui Cook
Tip 3	Gramatica obișnuită limbaj obișnuit Expresie uzuala Mașină de stări ( deterministă , nedeterministă ) Minimizarea DFA Determinarea NFA Teorema Myhill-Nerode
analizare	Analizor LL Analizor LR Metoda coborârii recursive Algoritmul Kok-Younger-Kasami