Utótag automata

angol utótag
automata irányított aciklikus szógráf

Utótag automata az abcbc -hez

Típusú

Alkarakterlánc index

Feltalálás éve

1983

Szerző

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

Bonyolultság az O-szimbólumokban

	Legrosszabb esetben
Épület	$O(\vert S\vert \log \vert \Sigma \vert )$
Memória fogyasztás	$O(\vert S\vert )$

Médiafájlok a Wikimedia Commons oldalon

Suffix automaton ( angol suffix automaton , irányított aciklikus szógrafikon ) egy olyan adatstruktúra , amely lehetővé teszi egy adott karakterlánc részkarakterláncaihoz kapcsolódó információk tömörített formában történő tárolását és feldolgozását . Egy determinisztikus véges automatát képvisel, amely elfogadja a szó összes utótagját, és csak azokat, és az összes ilyen automata közül a lehető legkisebb számú állapottal rendelkezik. Kevésbé formálisan az utótag automata egy irányított aciklikus gráf , amelynek megkülönböztetett kezdeti szimbólumokkalmegíveivannakés „végső” csúcsaicsúcsa összefűzve egy adott utótagot alkotnak. Az összes gráf közül, amely megfelel ennek a leírásnak, az utótag-automata az, amelyiknek a lehető legkisebb számú csúcsa van . ${\displaystyle S=s_{1}s_{2}\dots s_{n))$ $S$

Az utótag-automatát először a Denveri és Colorado Egyetem tudósainak egy csoportja írta le 1983-ban, és azt is kimutatták, hogy az automata mérete lineárisan függ a hosszától , és egy online algoritmust is javasoltak a felépítéséhez. lineáris futási idő . A témával kapcsolatos további munkák során az utótag-automaták és az utótagfák [⇨] között szoros összefüggést fedeztek , és az utótag-automata fogalma különféle általánosításokat kapott. Így bevezettek egy tömörített utótag-automatát, amelyet az utótag-bórhoz hasonló eljárással kaptunk az eredetiből, hogy utótagfát kapjunk, valamint egy általánosított utótag-automatát, amely szavak halmazára épül fel, és szavakat fogad el . amelyek az adatok legalább egyikének utótagjai . $S$ ${\displaystyle S_{1},S_{2},\dots ,S_{k))$

Az utótag-automaták segítségével hatékonyan megoldhat olyan problémákat, mint egy részkarakterlánc keresése egy karakterláncban , két vagy több karakterlánc legnagyobb közös részkarakterláncának meghatározása és egyebek .

Történelem

Az utótag-automata fogalmát a Denveri és Colorado Egyetem tudósainak egy csoportja vezette be Anselm Blumer, Andrzej Ehrenvecht , David Haussler , Ross McConnell és Janet Bloomer 1983-ban, bár találkoztak vele rokon szerkezetekkel. korábban Peter Weiner [1] , Vaughn Pratt [2] és Anatolij Olesevich Slisenko [3] utótagfák felépítésének algoritmusaival foglalkozott . Ugyanebben a munkában Bloomer és mások kimutatták, hogy egy ennél hosszabb szóból felépített automata nem tartalmaz több állapotot és nincs több átmenet, és bemutattak egy lineáris algoritmust is az automata felépítésére [4] . $S$ $egy$ $2|S|-1$ $3|S|-4$

1983-ban Mu Tian Chen és Joel Seiferas egymástól függetlenül kidolgozott egy utótag-automata felépítésére szolgáló algoritmust, amely kimutatta, hogy a Weiner-féle algoritmus [1] , amelyet 1973-ban javasoltak egy szóutótagfa felépítésére, egy utótag-automatát is készít a fordított szóhoz segédstruktúraként [ 5 ]. . 1987-ben Bloomer és mások egy utótagfával analógiával egy tömörített utótag-automatát [6] írtak le, amelyet egy utótag -automatából kaptak a nem végső állapotok törlésével , és 1997-ben Maxime Crochemore és Renaud Verin kifejlesztett egy lineáris algoritmust a közvetlen felépítéséhez [7] . 2001-ben Shunsuke Inenaga és mások kifejlesztettek egy lineáris online algoritmust tömörített utótag-automaták létrehozására [8] , valamint egy lineáris algoritmust egy előtagfa által adott szókészletre [9] tömörített utótag- automaták létrehozására . $S$ ${\textstyle S^{R}}$

Eredeti cikkükben Bloomer és munkatársai az általuk leírt szerkezetet egy minimális automataként határozták meg, amely felismeri egy adott szó összes részkarakterláncát (nem utótagját). Ezt a struktúrát irányított aciklikus szógráfnak nevezték [ 4 ] . Később ezt a nevet egy determinisztikus aciklikus véges automata szinonimájaként is használták - egy minimális automatát, amely felismer egy tetszőleges véges szavak halmazt (amely nem feltétlenül egy bizonyos karakterlánc utótagjainak vagy részkarakterláncainak halmazát alkotja) [10] [ 11] .

Jelölés

Az utótag-automaták és a kapcsolódó tények és tételek leírásakor gyakran használják a formális nyelvek elméletéből általában és különösen az automataelméletből származó jelöléseket [12] :

Az ábécé egy véges halmaz , amelyből szavakat lehet összeállítani. Elemeit szimbólumoknak nevezzük; $\Sigma$
A szó alfabetikus karakterek véges sorozata. A szó hosszának jelölése; ${\displaystyle \omega =\omega _{1}\omega _{2}\dots \omega _{n))$ $\omega$ $|\omega |=n$
A formális nyelv bizonyos szavak halmaza egy adott ábécé felett;
Az összes szó nyelvét úgy jelöljük (itt a "*" szimbólum a Kleene csillag jelentését hordozza ), üres szó (nulla hosszúságú szó) - a szimbólum ; $\Sigma ^{*}$ $\varepsilon$
A és a szavak összefűzését (szorzatát) vagyésként jelöljük,és egyenlő azzal a szóval, amelyetjobb oldali -hoz tulajdonítunk,azaz; ${\displaystyle \alpha =\alpha _{1}\alpha _{2}\dots \alpha _{n))$ ${\displaystyle \beta =\beta _{1}\beta _{2}\dots \beta _{m))$ $\alpha \cdot \beta$ $\alpha \beta$ $\beta$ $\alpha$ ${\displaystyle \alpha \beta =\alpha _{1}\alpha _{2}\dots \alpha _{n}\beta _{1}\beta _{2}\dots \beta _{m))$
A és a nyelvek összefűzését vagy vagy és egyenlő a páronkénti összefűzések halmazával ; $A$ $B$ $A\cdot B$ $AB$ ${\displaystyle AB=\{\alpha \beta :\alpha \in A,\beta \in B\))$
Ha egy szót úgy lehet ábrázolni, mint , ahol , akkor a , és szavakat rendre a szó előtagjának , utótagjának és alszavajának (alsztringjének) nevezzük ; $\omega \in \Sigma ^{*}$ $\omega =\alpha \gamma \beta$ $\alpha ,\beta ,\gamma \in \Sigma ^{*}$ $\alpha$ $\beta$ $\gamma$ $\omega$
Ha , akkor azt mondjuk, hogy a szó alszóként szerepel (előfordul) . Ebben az esetben , és az előfordulás bal és jobb helyzetének nevezzük , ill. $T_{l}T_{l+1}\dots T_{r}=S$ $S$ $T$ $l$ $r$ $S$ $T$

Automata szerkezet

Formálisan egy determinisztikus véges automatát öt elemből álló halmaz definiál, ahol: ${\mathcal {A}}=(\Sigma ,Q,q_{0},F,\delta )$

$\Sigma$ - ábécé , amely a gép által felismert szavakból áll,
$K$ az automata állapotok halmaza ,
$q_{0}\in Q$ a gép kezdeti állapota,
$F\subset Q$ az automata végállapotainak halmaza ,
$\delta :Q\times \Sigma \mapsto Q$ az automata részlegesen definiált átmeneti függvénye , így a for és vagy nincs definiálva, vagy olyan állapotot jelöl, amelybe át lehet lépni a -ból -be . $\delta (q,\sigma )$ $q\in Q$ $\sigma \in \Sigma$ $q$ $\sigma$

A gyakorlatban leggyakrabban a véges automatákat irányított gráfként ( diagramként ) ábrázolják úgy, hogy [13] :

A gráf csúcsok halmaza megfelel az állapotok halmazának , $K$
A gráfban kiválasztunk egy bizonyos csúcsot, amely megfelel a kezdeti állapotnak , $q_{0}$
A gráfnak van egy csúcskészlete, amely megfelel a végső állapotok halmazának , $F$
A gráf íveinek halmaza megfelel az átmenetek halmazának , $\delta$
Ebben az esetben az átmenet egy ívnek felel meg -tól -ig , amelyet az ábécé szimbóluma jelöl . Ezt az átmenetet más néven . ${\textstyle \delta (q_{1},\sigma )=q_{2}}$ $q_{1}$ $q_{2}$ $\sigma$ ${\textstyle q_{1}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}q_{2}}$

Egy ilyen gráfban a csúcsokat és az íveket az automata állapotaival, illetve átmeneteivel azonosítjuk. Az automata akkor és csak akkor fogad el egy szót , ha van egy út a kezdeti állapotból valamilyen végső állapotba , így ha összefűzzük az ezen az úton talált szimbólumokat, akkor a szót kapjuk . Az automata által elfogadott szavak halmaza ennek az automatának a nyelvét alkotja [12] . ${\displaystyle \omega =\omega _{1}\omega _{2}\dots \omega _{m))$ $q_{0}$ $q\in F$ $\omega$

Az automata állapotok

Egy szónak a nyelvhez viszonyított megfelelő kontextusát halmaznak nevezzük . Vagyis ez egy olyan szókészlet , amelyet a jobb oldali szóhoz rendelve egy szót kapunk a nyelvből . A helyes szövegkörnyezet természetes ekvivalencia-relációt indukál az összes szó halmazán. Ha egy nyelv definiálható valamilyen determinisztikus véges automatával, akkor számára létezik egy egyedi, egészen izomorfizmusig terjedő automata, amelynek egyidejűleg a lehető legkisebb állapota van. Egy ilyen automatát minimálisnak nevezünk egy adott nyelvhez , a Myhill-Nerode tétel lehetővé teszi, hogy kifejezetten megadjuk [14] [15] : $\omega$ $L$ ${\displaystyle [\omega ]_{R}=\{\alpha :\omega \alpha \in L\))$ $\alpha$ $\omega$ $L$ ${\displaystyle [\alpha ]_{R}=[\beta ]_{R))$ $L$ $L$

Egy nyelvet ábécén keresztül felismerő minimális automata a következőképpen adható meg: $L$ $\Sigma$

Az ábécé változatlan marad $\Sigma$
Az állapotok megfelelnek minden szó megfelelő kontextusának , $K$ ${\displaystyle [\omega ]_{R))$ $\omega \in \Sigma ^{*}$
A kezdeti állapot az üres szó megfelelő kontextusának felel meg , $q_{0}$ ${\displaystyle [\varepsilon ]_{R))$
A végső állapotok megfelelnek a nyelvből származó szavak megfelelő kontextusának , $F$ ${\displaystyle [\omega ]_{R))$ $\omega \in L$
Az átmenetek alakja , hol és . $\delta$ $[\omega ]_{R}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}[\omega \sigma ]_{R}$ $\omega \in \Sigma ^{*}$ $\sigma \in \Sigma$

Ebben a jelölésben az utótag automata egy minimális DFA, amely elfogadja az utótag nyelv szót . Egy szó megfelelő szövegkörnyezete egy adott nyelvhez viszonyítva olyan szavakból áll , hogy - utótag . Ez lehetővé teszi a következő lemma megfogalmazását, amely egy az egyben megfeleltetést definiál egy szó megfelelő kontextusa és az alszóban előforduló helyeinek halmaza között [16] [17] : ${\displaystyle S=s_{1}s_{2}\dots s_{n))$ $\omega$ $\alpha$ $\omega \alpha$ $S$ $S$

Legyen az előfordulások helyes pozícióinak halmaza -ben . $endpos(\omega )=\{r:\omega =s_{l}\dots s_{r}\}$ $\omega$ $S$

A halmazok és a halmazok elemei között a következő egy az egyhez megfeleltetés van: $endpos(\omega )$ ${\displaystyle [\omega ]_{R))$

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

Például egy szó és annak alszava esetén , és . Informálisan olyan szavakból áll, amelyek az előfordulásokat a szó végéig követik, és - ezen előfordulások pozícióiból. Ebben a példában az elem megegyezik a szóval . Ugyanakkor az elem megfelel a szónak . $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)$

Ebből következik az utótag automata állapotainak és az általuk elfogadott szavaknak számos szerkezeti tulajdonsága. Legyen , akkor [17] : $|\alpha |\leq |\beta |$

Ha és van legalább egy közös eleme , akkor a közös elemnek is van és . Ez viszont azt jelenti, hogy egy utótag , ezért és . A fenti példában és ennek következtében egy utótag , valamint az és ; ${\displaystyle [\alpha ]_{R))$ ${\displaystyle [\beta ]_{R))$ $x$ $endpos(\alpha )$ $endpos(\beta )$ $\alpha$ $\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)$
Ha , akkor , azaz a -ban csak utótagként fordul elő . Ez látható az és szavak példáján , amelyekre és ; ${\displaystyle [\alpha ]_{R}=[\beta ]_{R))$ $endpos(\alpha )=endpos(\beta )$ $\alpha$ $S$ $\beta$ $\alpha =b$ $\beta =ab$ ${\displaystyle [b]_{R}=[ab]_{R}=\{a,acaba\))$ $endpos(b)=endpos(ab)=\{2,6\}$
Ha és olyan utótag , hogy , akkor . A fenti példában , és a "köztes" utótag a . És valóban ,. ${\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\}$

Így az utótag-automata bármely állapota elfogadja ebből az állapotból a legnagyobb karakterlánc beágyazott utótagjainak valamilyen folytonos láncát [17] . ${\displaystyle q=[\alpha ]_{R))$

A karakterlánc bal oldali kiterjesztése az a leghosszabb karakterlánc , amelynek a jobb oldali kontextusa megegyezik a . Az állam által elfogadott leghosszabb karakterlánc hosszát a következővel jelöljük . Igaz rá, hogy [18] : ${\overset {\scriptstyle {\leftarrow }}{\gamma }}$ $\gamma$ $\omega$ $\gamma$ $|{\overset {\scriptstyle {\leftarrow }}{\gamma }}|$ ${\displaystyle q=[\gamma ]_{R))$ $len(q)$

A karakterlánc bal oldali kiterjesztése a következőképpen ábrázolható: ahol a leghosszabb szó, amelyben a szó bármely előfordulását megelőzi a szó . $\gamma$ ${\overleftarrow {\gamma }}=\beta \gamma$ $\beta$ $\gamma$ $S$ $\beta$

Az állapotból származó utótag hivatkozás egy olyan állapotra mutató mutató, amely a legnagyobb utótagot tartalmazza , amelyet az állapot nem fogad el . $link(q)$ ${\displaystyle q=[\alpha ]_{R))$ $p$ $\alpha$ $q$

Ebben a jelölésben azt mondhatjuk, hogy az állapot pontosan minden olyan toldalékot vesz fel, amely hosszabb, mint és nem hosszabb, mint . Ezenkívül igaz a következő [18] : ${\displaystyle q=[\alpha ]_{R))$ ${\overset {\scriptstyle {\leftarrow }}{\alpha }}$ $len(link(q))$ $len(q)$

Az utótag-hivatkozások egy fát alkotnak , amelyet a következőképpen lehet kifejezetten megadni: ${\mathcal {T}}(V,E)$

A csúcsok megfelelnek az összes részkarakterlánc bal oldali kiterjesztésének , $V$ ${\overleftarrow {\omega ))$ $S$
Az élek olyan csúcsokat kötnek össze , hogy és . $E$ $({\overleftarrow {\omega )),{\overleftarrow {\alpha \omega )))$ $\alpha \in \Sigma$ ${\overleftarrow {\omega }}\neq {\overleftarrow {\alpha \omega }}$

Kapcsolat az utótagfával

Az előtagfa (vagy furat ) egy gyökérorientált fa , amelynek ívei szimbólumokkal vannak megjelölve oly módon, hogyegy adott szimbólummal megjelölt csúcsából legfeljebb egy ív jön ki. Az előtagfa egyes csúcsai fel vannak címkézve. Az előtagfáról azt mondják, hogy a fa gyökerétől a címkézett csúcsokig tartó útvonalak által meghatározott szavak halmazát határozza meg. Így az előtagfák a véges automaták egy speciális fajtája, ha a gyökért tekintjük kiindulási állapotnak, a címkézett csúcsokat pedig végső állapotnak [19] . A szó utótagja bór egy előtag fa, amely meghatározza a szó utótagjainak nyelvét. Az utótagfa az utótag furatából tömörítési eljárással kapott fa, amelyben az egymást követő éleket összeragasztják, ha van közöttük egy nem végső csúcs, amelynek foka 2 [18] . $v$ $S$

Definíció szerint utótag-automatát kaphatunk egy utótag furatának minimalizálásával . Ezenkívül tömörített utótag-automatát kaphatunk egy utótagfa minimalizálásával (feltételezve, hogy az ábécé szimbólumai a fa szélein lévő szavak), és egy hagyományos automata tömörítésével [8] . Azonban amellett, hogy nyilvánvaló kapcsolat van az utótag-automata és ugyanazon karakterlánc utótagfája között, egy karakterlánc utótag-automata és egy fordított karakterlánc utótagfája között is megállapítható némi megfelelés [ 20 ] . ${\displaystyle S=s_{1}s_{2}\dots s_{n))$ ${\displaystyle S^{R}=s_{n}s_{n-1}\dots s_{1))$

A jobb oldali kontextusokhoz hasonlóan bevezethetünk bal oldali kontextusokat és jobb oldali kiterjesztéseket , amelyek megfelelnek az adott bal kontextussal rendelkező leghosszabb karakterláncoknak, valamint egy ekvivalencia relációt . Ha figyelembe vesszük a megfelelő kiterjesztéseket a karakterlánc előtag nyelvéhez képest , akkor azt kapjuk, hogy [18] : ${\displaystyle [\omega ]_{L}=\{\beta \in \Sigma ^{*}:\beta \omega \in L\))$ ${\overset {\scriptstyle {\rightarrow }}{\omega ~}}$ ${\displaystyle [\alpha ]_{L}=[\beta ]_{L))$ $L$ $S$

Egy karakterlánc utótag fája kifejezetten a következőképpen adható meg: $S$

A csúcsok megfelelnek az összes részsztring megfelelő kiterjesztésének , $V$ ${\overrightarrow {\omega ))$ $S$
Az élek olyan hármasoknak felelnek meg , hogy és . $E$ $({\overrightarrow {\omega )),x\alpha ,{\overrightarrow {\omega x)))$ $x\in \Sigma$ ${\overrightarrow {\omega x}}={\overrightarrow {\omega }}x\alpha$

Itt a hármas azt jelenti, hogy a -tól -ig karakterlánc a szélére van írva . $(v_{1},\omega ,v_{2})\in E$ $v_{1}$ $v_{2}$ $\omega$

Amiből az következik, hogy egy karakterlánc-automata utótag-hivatkozásainak fája és egy karakterlánc utótagfája izomorf [20] : $S$ $S^{R}$

Az abbcbc és cbcbba szavak utótag szerkezetei
Utótag automata az abcbc szóhoz Bór utótag, utótag fa és tömörített utótag automata az abbcbc szóhoz . A csúcsszámok azoknak az állapotoknak felelnek meg, amelyekbe minimalizáláskor vagy zsugorításkor kerülnek. Utótag fa a cbcbba szóhoz (utótag hivatkozások fája az abbcbc szó automatájához )

A bal oldali kiterjesztésekhez hasonlóan a jobb oldali kiterjesztésekhez is megfogalmazható egy szerkezeti lemma [18] :

A karakterlánc jobb oldali kiterjesztése a következőképpen ábrázolható: ahol a leghosszabb szó, így az in előfordulását közvetlenül a szó követi . $\gamma$ ${\overrightarrow {\gamma }}=\gamma \alpha$ $\alpha$ $\gamma$ $S$ $\beta$

Méret

Az utótag-automatákban a karakterláncok hossza nem több állapotnál és nem több átmenetnél, és ezeket a becsléseket karakterláncokon , illetve [16] értjük el . Az állapotok és az átmenetek száma közötti összefüggésre egy automatában erősebb állítás is megfogalmazható: , ahol és az átmenetek, illetve állapotok száma [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|$

Maximum utótag automaták
Utótag automata for $ab^{n-1}$ Utótag automata for $ab^{n-2}c$

Épület

Egy karakterlánc utótag-automatája úgy épül fel, hogy egymás után felépítjük a szót, amelyre épül. Kezdetben egy üres szóra épül egy triviális automata, majd minden lépésben egy szimbólumot adunk az aktuális szóhoz, ami az automata állapotainak és átmeneteinek átrendezését vonja maga után [21] . ${\displaystyle S=s_{1}s_{2}\dots s_{n))$

Változó államok

Miután új karaktert rendel egy szóhoz, néhány ekvivalenciaosztály megváltozik. Legyen a szó megfelelő szövegkörnyezete a szó utótagnyelvéhez képest . Ekkor a szimbólumnak egy szóhoz való hozzárendelésekor az átmenetet a -ról a következőre a következő lemma írja le [17] : $[\alpha ]_{R_{\omega ))$ $\alpha$ $\omega$ $[\alpha ]_{R_{\omega ))$ $[\alpha ]_{R_{\omega x))$ $x$ $\omega$

Legyen néhány szó egy ábécé fölött, és legyen ennek az ábécé valamilyen szimbóluma. Ezután a megfelelő kontextusok és a szavak között a szavak utótagjainak nyelvei tekintetében a következő kapcsolat jön létre: $\alpha ,\omega \in \Sigma ^{*}$ $\Sigma$ $x\in \Sigma$ $[\alpha ]_{R_{\omega ))$ $[\alpha ]_{R_{\omega x))$ $\alpha$ $\omega$ $\omega x$

$[\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x\cup \{\varepszilon \}$ if - utótag ; $\alpha$ $\omega x$
$[\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x$ másképp.

Ez azt jelenti, hogy ha az aktuális szóhoz egy karaktert adunk , a szó megfelelő kontextusa csak akkor változhat meg, ha az egy szóutótag . Ebből az következik, hogy az összes szó felosztása ekvivalenciaosztályokba a tekintetében az ekvivalenciaosztályokba való felosztás finomítása a tekintetében . Más szóval, ha , akkor . Ezen túlmenően, amikor a következő szimbólumot adjuk a szóhoz, a felosztás legfeljebb két állapotban történik. Mindenekelőtt az üres jobb kontextusnak megfelelő állapot (vagyis annak, amelyik alszóként nem szereplő szavak nyelvét veszi fel) felosztásra kerül. Ebből az állapotból egy új állapot kerül kinyerésre, amely tartalmazza a teljes szót , valamint minden olyan utótagját, amely előfordul, de nem fordult elő -ban . Ennek megfelelően e szavak megfelelő szövegkörnyezete, amely korábban üres volt, most csak az üres szóból fog állni [17] . $x$ $\omega$ $\alpha$ $\alpha$ $\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$

Figyelembe véve az utótag-automata állapotai és az utótagfa csúcsai közötti kapcsolatot, nyomon követhetjük a második állapotot is, amely a következő szimbólum hozzáadásakor kettéválhat. Mivel a szó - to átmenet egy fordított karakterlánc to-to átmenetének felel meg, egy karakter hozzárendelése egy karakterlánchoz egy új (leghosszabb) utótag hozzáadásának felel meg a karakterlánc utótagfájához . Ebben az esetben legfeljebb két csúcs jelenik meg: az egyik a teljes szónak felel meg , a másik pedig ott jelenhet meg, ahol a fa ága található. Így az egyik új állapot a teljes karakterlánc megfelelő kontextusának felel meg , a másik pedig (ha van) csak az adott állapot utótag-hivatkozásának felelhet meg. Ezek a megfigyelések a [17] tétellel általánosíthatók : $\omega$ $\omega x$ $\omega ^{R}$ $x\omega ^{R}$ $x$ $\omega$ $x\omega ^{R}$ $\omega ^{R}$ $x\omega ^{R}$ $\omega x$

Hagyjuk és . Legyen a leghosszabb utótag is , amely -ben előfordul , és legyen a bal oldali kiterjesztése a -hoz képest, vagyis a szó leghosszabb részszava , hogy . Ekkor a következő igaz a szó bármely részszavaira : $\omega \in \Sigma ^{*}$ $x\in \Sigma$ $\alpha$ $\omega x$ $\omega$ $\beta ={\overset {\scriptstyle {\leftarrow }}{\alpha }}$ $\omega$ $\omega$ $[\alpha ]_{R_{\omega }}=[\beta ]_{R_{\omega }}$ $u,v$ $\omega$

Ha és , akkor ; $[u]_{R_{\omega }}=[v]_{R_{\omega }}$ $[u]_{R_{\omega }}\neq [\alpha ]_{R_{\omega }}$ $[u]_{R_{\omega x}}=[v]_{R_{\omega x}}$
Ha és , akkor ; $[u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}$ $\vert u\vert \leq \vert \alpha \vert$ $[u]_{R_{\omega x}}=[\alpha ]_{R_{\omega x}}$
Ha és , akkor . $[u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}$ $\vert u\vert >\vert \alpha \vert$ $[u]_{R_{\omega x))=[\beta ]_{R_{\omega x))$

Különösen, ha (például amikor egyáltalán nem fordul elő és -ben ), a második állapot felosztása nem következik be [17] . $\alpha =\beta$ $x$ $\omega$ $\alpha =\beta =\varepsilon$

Az utótag hivatkozások mellett a végállapotokat is meg kell határozni az új automatában. Az automata szerkezeti tulajdonságaiból következik, hogy bármely szó utótagjai úgy helyezkednek el, hogy ha , akkor azok az utótagok , amelyek hossza meghaladja a -t , benne vannak , azok az utótagok, amelyek hossza nagyobb, mint , de nem nagyobb -ban , és hamar. Más szóval, bármely utótagnak van egy csúcsa az utótag állapotútjában , amelyet a sorozat ad meg . Ennek megfelelően, ha azt az állapotot, amely jelenleg a teljes karakterláncot elfogadja -nak jelöljük , akkor a terminális (utótagokat elfogadó ) állapotok azok és csak azok lesznek, amelyek az utótag elérési útjában szerepelnek [21] . $\alpha$ ${\displaystyle q=[\alpha ]_{R))$ $\alpha$ $len(link(q))$ $q$ $len(link(link(q))$ $len(link(q))$ $link(q)$ $\alpha$ $q$ $(q,link(q),link^{2}(q),\pontok )$ $\omega$ $last$ $\omega$ $(utolsó,link(utolsó),link^{2}(utolsó),\pontok )$

Ugrás és utótag hivatkozások módosítása

A következő karakter hozzáadásakor végzett változtatások legfeljebb két új állapotot érintenek, így az automata átmeneteinek változásai is csak ezeket az állapotokat érintik. A szóhoz való hozzárendelés után egy új állapot jön létre , és esetleg egy állapot is . A from utótag hivatkozás ide vezet , és innen - hova . A -ból származó szavak csak utótagként fordulnak elő , ezért ne legyenek átmenetek, és a hozzá vezető átmeneteknek karakterenként kell vezetniük a legalább hosszúságú utótagokból . Az állapot el van választva a -tól , így az ebből az állapotból való átmenetek megduplázzák az állapotot . A hozzá vezető átmenetek pedig szimbólummal fognak elvezetni a -nál kisebb és nem kisebb utótagoknak megfelelő állapotokból , mivel korábban ezek az átmenetek az állapot elválasztott részéhez vezettek és annak feleltek meg. Azokat az állapotokat, amelyek elfogadják ezeket a szavakat, az állapotutótag elérési útjával azonosíthatjuk [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 ))$

Utótag -automata felépítése az abcbc szóhoz

∅ → a


Az első szimbólum hozzáadásakor egyetlen új állapot jön létre az automatában.	Hasonlóképpen egyetlen levél kerül hozzáadásra az utótagfához.

a→ab


Minden végső állapotból új átmenetek rajzolódnak ki, mivel az új szimbólummal korábban nem találkoztunk.	Ugyanezen okból az utótaghivatkozások fájában az új csomópont felfüggesztésre kerül a gyökérből.

ab → abb


A 2. állapot felveszi az ab és b szavakat , de csak a b lesz utótag, így ez a szó a 4. állapothoz lesz hozzárendelve.	A bővített szó utótagfájában ez a 2. csúcshoz vezető él felhasadásának felel meg.

abb → abbc


Az új szimbólumot még nem látták, az összes véglegesről áttérnek rá.	Egy új levél kerül a gyökérre felfüggesztett utótag hivatkozások fájába.

abbc → abbcb


A 4. állapotban csak a b szó van, és ez egy utótag, így nem történik hasadás.	Ennek megfelelően az utótaghivatkozások fájában egy új levél felfüggesztésre kerül a 4. csúcsról.

abbcb → abbcbc


Az 5. állapot elfogadja az abbc , bbc , bc és c szavakat , de csak az utolsó kettő utótagja az új szónak, ezért külön 8-as állapotba különülnek el.	Ennek megfelelően az utótaghivatkozások fájában az 5. csúcshoz vezető él felhasad.

Automata felépítésének algoritmusa

A fenti elméleti eredmények a következő algoritmushoz vezetnek, amely egy szimbólumot vesz és egy szóutótag-automatát szóutótag - automatává rendez át [21] : $x$ $\omega$ $\omega x$

A teljes sornak megfelelő állapotszám támogatott ; $last$ $\omega$
Amikor egy szimbólumot adunk hozzá , a szám a változóban tárolódik , és a szónak megfelelő új állapot számát írjuk be ; $x$ $last$ $p$ $last$ $\omega x$
Az utótagoknak megfelelő állapotokból a -be átmenetek rögzítésre kerülnek . Ehhez az utótag elérési útját a rendszer kihagyja mindaddig, amíg nem találkozik olyan állapottal, amelyből már van átmenet . $\omega$ $last$ $p,link(p),link^{2}(p),\dots$ $x$
A további műveletek a három eset egyikének felelnek meg:
1. Ha a teljes utótag útvonalon nincs átmenet egyik állapotból sem , akkor korábban nem találkoztunk vele, és az utótag hivatkozása az utótagból ide vezet ; $x$ $x$ $\omega$ $last$ $q_{0}$
2. Ha az átmenetet megtaláltuk, és állapotból állapotba úgy vezet, hogy , akkor nem kell felosztani , elég egy utótag hivatkozást húzni -ból -be ; $x$ $p$ $q$ $len(p)+1=len(q)$ $q$ $last$ $q$
3. Ha , akkor az állapotból származó szavakat , amelyek hossza nem haladja meg , külön állapotba kell választani ; $len(q)>len(p)+1$ $q$ $len(p)+1$ $cl$
Ha az előző lépésben külön állapotot választottunk , akkor az átmeneteknek és az abból származó utótag hivatkozásnak meg kell duplikálnia azokat -ban , miközben az és állapotok közös utótag hivatkozásává válik ; $cl$ $q$ $cl$ $q$ $last$
Azok az ugrások, amelyek a szóhoz vezettek, de egyező szavakkal nem hosszabbak, mint , a következőre kerülnek átirányításra . Ehhez továbbra is követheti az utótag útvonalát , amíg nem talál egy állapotot, amelyből az átmenet nem vezet a -hoz . $q$ $len(p)+1$ $cl$ $p$ $q$

Az ezt az algoritmust megvalósító eljárás a következő pszeudokóddal írható le:

függvény add_letter(x) : define p = utolsó hozzárendelés utolsó = új_állapot() hozzárendelés len(utolsó) = len(p) + 1 , amíg δ(p, x) meg nem határozzuk: hozzárendelés δ(p, x) = utolsó, p = link(p) define q = δ(p, x) if q = utolsó : link(utolsó) = q 0 else if len(q) = len(p) + 1 : link (utolsó) = q hozzárendelése else : define cl = új_állapot() hozzárendelés len(cl) = len(p) + 1 hozzárendelés δ(cl) = δ(q), link(cl) = link(q) hozzárendelni link(utolsó) = link(q) = cl míg δ(p, x) = q : δ(p, x) hozzárendelése = cl, p = link(p)

Itt látható az automata kezdeti állapota, és egy olyan függvény, amely új állapotot ad az automatához. Feltételezzük, hogy , , és globális változóként tárolódnak. $q_{0}$ $new\_state()$ $last$ $len$ $link$ $\delta$

Számítási összetettség

A használt struktúráktól függően a fent leírt algoritmus determinisztikus változata megvalósítható memóriaidőben vagy memóriaidőben , feltéve, hogy a memóriafoglalás a -ben történik . Ugyanakkor a futási idő ilyen becsléséhez el kell végezni az algoritmus belső ciklusainak amortizációs elemzését . Ha figyelembe vesszük, hogy a paraméter hogyan változik az első ciklus első iterációja után , akkor láthatjuk, hogy szigorúan csökken a ciklus minden iterációjával. Sőt, ha az előző lépés utolsó iterációjában ez az érték egyenlő volt -vel , akkor a következő lépés második iterációjában ez az érték egyenlő lesz . Az, hogy egyetlen pillanatban sem haladja meg, és a ciklusok között ez a mennyiség csak eggyel nő, megadja a szükséges állítást. Hasonló elemzéssel kimutatható az algoritmus második ciklusának teljes végrehajtási idejének linearitása [21] . $O(n\log |\Sigma |)$ $Tovább)$ $Tovább)$ $O(n|\Sigma |)$ $O(1)$ $len(p)$ $k$ $k+1$ $len(p)$ $n$

Változatok és általánosítások

Az utótag-automata szorosan kapcsolódik más utótag-struktúrákhoz és részstringindexekhez . Valamelyik karakterlánc utótag-automatájával lehetséges ennek a karakterláncnak az utótagfáját lineáris időben megszerkeszteni az automata tömörítésével és rekurzív bejárásával [22] . Hasonló transzformációk mindkét irányban lehetségesek egy karakterlánc utótag automata és egy fordított sztring utótag fa között [20] . Ezen kívül számos algoritmus-módosítást fejlesztettek ki, amelyek lehetővé teszik automata felépítését egy előtag fa által megadott karakterláncok halmazához [9] , tömörítést alkalmaznak rá [6] , struktúráját csúszóablak módban tartják [23] , és újraépítsd is, amikor karaktereket adsz hozzá mind a végétől, mind az elejétől [24] . $S$ $S^{R}$

Tömörített utótag automata

Mint fentebb említettük, egy közönséges utótag automatából tömörítéssel (a nem végleges állapotok eltávolításával, amelyekből pontosan egy átmenet vezet), valamint az utótagfa minimalizálásával kaphatunk tömörített utótag-automatát, ha feltételezzük, hogy az ábécé az élek fára írt szavak alkotják. Ezenkívül egy tömörített automata állapotai explicit módon leírhatók, hasonlóan ahhoz, ahogyan azt egy tömörítetlen automatánál tették. A kétirányú szókiterjesztés a leghosszabb szó , így minden előfordulást egy szó előz meg, és közvetlenül egy szó követi . A bal és a jobb oldali kiterjesztések szempontjából ez azt jelenti, hogy a kétirányú kiterjesztés a jobb oldali kiterjesztés bal oldali, vagy ennek megfelelően a bal oldali kiterjesztés jobb oldali kiterjesztése: . A kétoldali kiterjesztések tekintetében egy tömörített utótag-automatát a következőképpen írhatunk le [18] : ${\overset {\scriptstyle {\longleftrightarrow }}{\gamma }}$ $\gamma$ $\omega =\beta \gamma \alpha$ $\gamma$ $S$ $\beta$ $\alpha$ ${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\gamma }}={\overset {\scriptstyle \leftarrow }{\overset {\rightarrow }{\gamma }}}={\overset {\rightarrow }{\ overset {\scriptstyle \leftarrow }{\gamma ))))$

Egy szó tömörített utótag-automatája megadható a párral , ahol: $S$ $(V, E)$

$V=\{{\overleftrightarrow {\omega }}:\omega \in \Sigma ^{*}\}$ az automata állapotok halmaza;
$E=\{({\overleftrightarrow {\omega )),x\alpha ,{\overleftrightarrow {\omega x))):x\in \Sigma ,\alpha \in \Sigma ^{*},{ \overleftrightarrow {\omega x}}={\overleftrightarrow {\omega }}x\alpha \}$ - az automata átmeneteinek halmaza.

A kétirányú kiterjesztések egy ekvivalencia relációt generálnak, amely leírja a tömörített automata azonos állapota által elfogadott szavakat. Ez a reláció a reláció tranzitív lezárása , ami azt a tényt hangsúlyozza, hogy a tömörített utótag-automaták állapotai megszerezhetők mind az utótagfa-csúcsok összeragasztásával, amelyek egyenértékűek (utótagfa-minimalizálás), mind pedig az utótag-automaták olyan állapotainak ragasztásával, amelyek ekvivalensek a (tömörítő utótagú automata) [25] szempontjából . Ha a és szavaknak azonos a jobb oldali kiterjesztése, a és szavaknak pedig a bal oldali kiterjesztései , akkor az és a szavak összesítésében ugyanaz a kétoldali kiterjesztése. Ebben az esetben kiderülhet, hogy a és szavak nem ugyanazokkal a bal vagy jobb oldali kiterjesztéssel rendelkeznek. , és esetén a bal és jobb oldali kiterjesztések: , de és . Egyirányú kontextusok és kiterjesztések esetén az azonos ekvivalenciaosztályból származó szavak egymásba ágyazott előtagokból vagy utótagokból álló folyamatos láncot alkottak, és egyértelműen meghatározhatóak voltak az osztály legrövidebb és leghosszabb szavainak hossza alapján. A kétirányú kiterjesztések esetében csak annyit lehet biztosan mondani, hogy az azonos osztályból származó szavak az osztály leghosszabb szavának alszavai , egyébként pedig az osztályok meglehetősen bonyolult szerkezetűek lehetnek. Az ilyen ekvivalencia osztályok száma nem haladja meg a -t, ami azt jelenti, hogy egy hosszúságú karakterlánc tömörített utótagú automatának legfeljebb állapota lehet. Az átmenetek száma egy ilyen automatában nem haladja meg a [18] -ot . ${\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 \,}}$ $\alpha$ $\beta$ $\beta$ $\gamma$ $\alpha$ $\beta$ $\gamma$ $\alpha$ $\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$

Utótag automata karakterláncok halmazához

Legyen adott egy szókészlet . Hasonlóan az egyetlen szóra épített automatához , tekinthetünk általánosított utótag-automatának, amely elfogadja azoknak a szavaknak a nyelvét, amelyek legalább egy szó utótagja a -ból . Ebben az esetben az automata állapotainak és átmeneteinek számára ugyanazok a korlátozások teljesülnek, amelyeket a fentiekben jeleztünk, ha a [25] -t adjuk meg . Maga a szerkesztési algoritmus lényegében hasonló az egysoros automata felépítésére szolgáló algoritmushoz, de a szónak megfelelő állapotra mutató mutató helyett a szóra való átlépéskor az add_letter függvény egy mutatót visz arra az állapotra, amely elfogadja a szó , ami arra utal, hogy az átmenet az aktuális szókészletből a halmazba történik . Az algoritmusban már szereplő főbb műveletek mellett külön elemezni kell azt az esetet, amikor a karakterlánc már jelen van a gépben - ebben az esetben előfordulhat, hogy fel kell osztani az azt elfogadó állapotot, hasonlóan a hogyan történt, amikor egyetlen szóra utótag hivatkozást képeztünk az algoritmusban [26] [27] . $T=\{S_{1},S_{2},\dots ,S_{k}}\}$ $S$ $T$ $n=|S_{1}|+|S_{2}|+\dots +|S_{k}|$ $last$ $\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$

Ennek az ötletnek a továbbfejlesztése volt egy utótag-automata felépítése arra az esetre, amikor a halmaz nem explicit formában, hanem előtag faként van megadva a csúcsokon. Mohry és mások kimutatták, hogy egy ilyen automata legfeljebb állapotokat tartalmaz, és méretében lineárisan építhető fel időben. Ugyanakkor egy ilyen automatában az átmenetek száma elérheti - például ha egy szókészletet tekintünk az ábécé felett , akkor ebből a halmazból a szavak teljes hossza a csúcsok számának nagyságrendje lesz. a megfelelő előtag fában egyenlő lesz -vel, az utótag-automatában pedig az állapotok és átmenetek sorrendje lesz. Maga az algoritmus, amelyet Mohri javasolt, nagyrészt megismétli az automata sztringek halmazából történő felépítésének általános algoritmusát, de ahelyett, hogy minden alkalommal hozzáfűzné egy szó karaktereit a halmazból az elejétől a végéig, az algoritmus bejárja az előtagfát a bejárási sorrendet szélességben , és abban a sorrendben rendeli hozzá a következő karaktereket, amelyben a bejárás során találkozik velük, ami garantálja az algoritmus amortizált lineáris futási idejét [28] . $T$ $K$ $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)$

Tolóablak

Egyes tömörítési algoritmusokban , például az LZ77 -ben és az RLE -ben, hasznos lehet egy utótag-automatát vagy hasonló szerkezetet nem a teljes olvasott szóhoz, hanem csak az utolsó karakterekhez tárolni. Elsősorban az adattömörítési feladatok sajátosságai miatt merül fel ilyen igény, ahol a tömörített karakterláncok általában meglehetősen nagyok, és nem kívánatos a memóriahasználat. 1985-ben Janet Bloomer kifejlesztett egy algoritmust, amely támogatja az utótag automatát egy csúszó méretű ablakon , és a legrosszabb esetre és az átlagra fut , feltételezve, hogy a tömörítendő szó karakterei egymástól függetlenül és egyenletesen vannak elosztva . Ugyanebben a munkában kimutatták , hogy a becslés nem javítható - ha figyelembe vesszük, hogy a becslés alak több szavának összefűzésével nyert szavakat egy utótag automatára nem lehetséges [29] . $k$ $Tovább)$ $k$ $O(nk)$ $O(n\log k)$ $O(nk)$ $(ab)^{m}c(ab)^{m}d$ $k=6m+2$ $k$ $m$ $O(nk)$

Úgy tűnik, ugyanez igaz az utótagfára is, mivel az utótagfa csúcsai megfelelnek a kibontott karakterlánc utótag-automatájának állapotainak. Ha azonban az utótagfában nincs külön csúcs minden utótaghoz, akkor nem lesznek ilyen éles ugrások, és lehetséges egy amortizált algoritmus felépítése, amely támogatja az utótagfát egy csúszó ablakon. Edward Fiala és Daniel Green [30] 1989-ben javasolt egy megfelelő algoritmust egy utótagfához, amely McCraith algoritmusán alapul, és támogatja egy új karakter jobb oldali hozzáadását és egy karakter törlését a bal oldalon, és 1996-ban kifejtette Ukkonen algoritmusának feltételei , Jesper Larsson [31] [32] . Ebben a tekintetben az a kérdés, hogy lehetséges-e egy tömörített automata gyors csúszóablaka fenntartani, amely egyesíti mind a közönséges utótag-automaták, mind az utótagfa egyes tulajdonságait, sokáig nyitva maradt. Erre a kérdésre 2008-ban nemleges választ kapott Martin Senft és Tomasz Dvorak, akik kimutatták, hogy ha az ábécé két vagy több karakterből áll, akkor a legrosszabb esetben az ablak egy karakterrel történő eltolásához szükséges amortizált idő a megfelelő sorrendben van. a [33] . $Rendben)$

Ugyanakkor, ha az ablak pontos szélessége nem fontos, és csak az a cél, hogy olyan ablakot tartsunk fenn, amelynek szélessége nem haladja meg a -t, nagyságrendileg ez megtehető az Inenaga és munkatársai által javasolt közelítő algoritmussal. 2004. Az algoritmus sajátossága, hogy a szó mentén mozgó „ablak” változó hosszúságú, amely bármikor sem kisebb , sem több, mint , miközben a teljes futási idő lineáris marad [34] . $Rendben)$ $k$ $2k+1$

Alkalmazások

A karakterlánc utótag automata olyan problémák megoldására használható, mint például [35] [36] : $S$

Megszámolja a különböző részkarakterláncok számát az idő múlásával online, $S$ $O(|S|)$
Keresse meg a benne lévő leghosszabb karakterláncot legalább kétszer, időben , $S$ $O(|S|)$
A karakterláncok legnagyobb közös részsorozatának megtalálása időben , $S$ $T$ $O(|T|)$
Egy karakterlánc részstringként való előfordulásai számának számolása időben , $T$ $S$ $O(|T|)$
Az összes előfordulás keresése időben , ahol az előfordulások száma. $T$ $S$ $O(|T|+k)$ $k$

Itt érdemes megfontolni, hogy valamilyen karakterláncot akkor kell bevinni, amikor az automata már fel van építve és használatra kész. $T$

Az utótag-automaták olyan alkalmazásokban is utat találtak, mint az adattömörítés [37] , a rögzített töredékekből származó zeneazonosítás [38] [39] és a genomi szekvencia-illesztés [40] .

Jegyzetek

↑ 1 2 Weiner, 1973
↑ Pratt, 1973
↑ Szliszenko, 1983
↑ 1 2 Blumer et al., 1984 , p. 109-110
↑ Chen, Seiferas, 1985 , p. 97
↑ 12 Blumer et al., 1987 , p. 578
↑ Crochemore, Verin, 1997 , p. 192
↑ 1 2 Inenaga et al., 2005 , pp. 156-158
↑ 1 2 Inenaga et al., 2001 , p. egy
↑ Perrin, 1990 , p. tíz
↑ Sgarbas et al., 2003 , p. 2
↑ 1 2 Crochemore, Hancart, 1997 , pp. 3-6
↑ Serebryakov et al., 2006 , p. 50-54
↑ Rubcov, 2019 , p. 89-94
↑ Hopcroft, Ullman, 1979 , pp. 65-68
↑ 12 Blumer et al., 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
↑ Parashchenko, 2007 , p. 19-22
↑ Blumer, 1987 , p. 451
↑ Inenaga, 2003 , p. egy
↑ 1 2 Blumer et al., 1987 , pp. 585-588
↑ Blumer et al., 1987 , pp. 588-589
↑ Blumer et al., 1987 , p. 593
↑ Mohri et al., 2009 , pp. 3558-3560
↑ Blumer, 1987 , pp. 461-465
↑ Fiala, Greene, 1989 , p. 490
↑ Larsson, 1996
↑ Brodnik, Jekovec, 2018 , p. egy
↑ 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 et al., 2003 , p. 211
↑ Mohri et al., 2009 , p. 3553
↑ Faro, 2016 , p. 145

Irodalom

Sgarbas K. N., Fakotakis N. D., Kokkinakis G. K. Optimal insertion in deterministic DAWGs // Theoretical 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. Véges automaták // Formális modellek és szemantika : Az elméleti számítástechnika kézikönyve / J. v . Leeuwen - Elsevier BV , 1990. - 20. évf. B.-P. 1-57. - ISBN 978-0-444-88074-1 - doi:10.1016/B978-0-444-88074-1.50006-8
Weiner P. Lineáris mintaillesztési algoritmusok (angol) // Symposium on Foundations of Computer Science - 1973. - P. 1-11. — 213p. doi : 10.1109/SWAT.1973.13
Pratt V. R. A Weiner ismétléskereső fejlesztései és alkalmazásai (angol) - 1973.
Slisenko A. O. Periodikusok detektálása és a karakterlánc-illesztés valós időben (angol) // 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. A minimális DFA felépítése egy szó összes alszavajához online lineáris időben // Automata , Languages and 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. Teljes fordított fájlok a hatékony szövegkeresés és -elemzés érdekében // J. ACM / D. J. Rosenkrantz - New York, NY : Association for Computing Machinery . 1987. évf. 34, Iss. 3. - P. 578-595. - ISSN 0004-5411 - doi:10.1145/28869.28873
Blumer J. Mennyi az a DAWG az ablakban? Mozgóablak-algoritmus az irányított aciklikus szógráfhoz (angol) // 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 (angol) // Kombinatorikus algoritmusok szavakon / 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. Utótagfák kétirányú felépítése (angol) // 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 directed 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. CDAWG építése egy próbaverzióhoz (angol) // Prague Stringology Conference - Czech Technical University in Prague : 2001. - P. 37-48 .
Inenaga S., Shinohara A., Takeda M., Arikawa S. Kompakt irányított aciklikus szógráfok csúszó ablakhoz (angol) // 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 (angol) // Symposium 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. Számítástechnika DAWG-k és minimális hiányzó szavak lineáris időben integer Alphabets // A számítástechnika matematikai alapjai / P. Faliszewski , A. Muscholl , R. Niedermeier - 2016. - Kt. 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. Általános utótag automata építési algoritmus és térhatárok (angol) // 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 (angol) // Algorithms for Computational Biology / M. Botón-Fernández , C. Martín-Vide , M. A. Vega-Rodríguez - Springer International Publishing - P 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 (angol) // Formális nyelvek kézikönyve / G. Rozenberg , A. Salomaa - Springer Berlin Heidelberg , 1997. - 1. kötet. 2. - P. 399-462. - ISBN 978-3-642-59136-5 - doi:10.1007/978-3-662-07675-0_9
Crochemore M. , Vérin R. A kompakt irányított aciklikus szógráfokról (angol) // Struktúrák a logikában és a számítástechnikában : Válogatás a esszékből A. Ehrenfeucht tiszteletére / 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. Mourai 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. Bevezetés az automataelméletbe, nyelvekbe és számításba (ang.) - 1 - MA : Addison-Wesley , 1979. - 418 p. — ISBN 978-81-7808-347-6
Fiala E. R., Greene D. H. Adattömörítés véges ablakokkal // 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 (angol) // 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. Az utótagfák kiterjesztett alkalmazása adattömörítésre // Proceedings . Adattömörítési konferencia - IEEE , 1996. - 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 (angol) // Algorithms - MDPI , 2018. - Vol. 11, Iss. 8. - P. 118. - ISSN 1999-4893 - doi:10.3390/A11080118
Rubinchik M., Shur A. M. Eertree (angol) : Egy hatékony adatstruktúra palindromok feldolgozásához stringekben // 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 és társai. — Elsevier BV , 2018. — 1. évf. 68. - P. 249-265. — ISSN 0195-6698 ; 1095-9971 - doi:10.1016/J.EJC.2017.07.021 - arXiv:1506.04862
Szerebryakov V. A. , Galochkin M. P. , Furugyan M. G. , Gonchar D. R. Programozási nyelvek elmélete és megvalósítása : Tankönyv - M .: MZ Press , 2006. - 352 p. — ISBN 5-94073-094-9
Rubtsov A. A. Megjegyzések és problémák a reguláris nyelvekről és a véges automatákról - Moszkva : MIPT , 2019. - 112 p. — ISBN 978-5-7417-0702-9
Parashchenko D. A. String feldolgozás utótag automaták alapján - Szentpétervár. : ITMO , 2007. - 35 p.

Linkek

utótag automata. Épület O(N)-ben és alkalmazása . MAXimális . (határozatlan)
Utótag automata . ITMO Wikinotes . (határozatlan)

Húrok
Karakterlánc hasonlósági mértékek	Távolság Damerau és Loewenstein között Levenshtein távolság Hamming távolság Jaro-Winkler hasonlóságok
Substring keresés	Boyer-Moore algoritmus Boyer-Moore-Horspool algoritmus Knuth-Morris-Pratt algoritmus Rabin-Karp algoritmus előtag funkció Z-függvény Algoritmus Aho - Korasik
palindromák	palindromfa Menedzser algoritmusa
Sorozat-igazítás	Needleman-Wunsha algoritmus Smith-Waterman algoritmus
Utótag szerkezetek	Utótag tömb Utótag automata utótag fa előtag fa
Egyéb	elemzése Minta illesztés A legnagyobb közös sorozat Legnagyobb közös részkarakterlánc

Formális nyelvek és formális nyelvtanok
Általános fogalmak	Chomsky-hierarchia Ábécé Szó
Típus 0	Korlátlan nyelvtan Turing gép felsorolt nyelv Feloldható nyelv
1. típus	Környezetérzékeny nyelvtan Környezetérzékeny nyelv Lineárisan korlátos automata
2. típus	Kontextus mentes nyelvtan Kétértelmű nyelvtan Kontextus mentes nyelv Lenyomó automata ( determinisztikus ) Növekedési Lemma Ogden Lemma Cook-tétel
3. típus	Szabályos nyelvtan szabályos nyelv Reguláris kifejezés Állapotgép ( determinisztikus , nem determinisztikus ) DFA minimalizálás Az NFA meghatározása Myhill-Nerode tétel
elemzése	LL analizátor LR elemző Rekurzív süllyedés módszere Kok-Younger-Kasami algoritmus