Sufijo autómata

sufijo autómata

inglés sufijo
autómata gráfica de palabras acíclica dirigida

Sufijo autómata para abcbc

Tipo de

Índice de subcadena

año de invención

1983

Autor

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

Complejidad en los símbolos O

	Lo peor
Edificio	$O(\vert S\vert \log \vert \Sigma \vert )$
Consumo de memoria	${\ estilo de visualización O (\ vert S \ vert)}$

Archivos multimedia en Wikimedia Commons

Sufijo autómata ( inglés sufijo autómata , gráfico de palabra acíclica dirigida ) es una estructura de datos que le permite almacenar en forma comprimida y procesar información asociada con subcadenas de una cadena dada. Representa un autómata finito determinista que acepta todos los sufijos de una palabra y solo ellos, y tiene el menor número posible de estados entre todos esos autómatas. Menos formalmente, un sufijo autómata es un gráfico acíclico dirigido con un vértice inicial distinguido símboloslosestán etiquetados conarcosy un conjunto de vértices "finales", concatenan , forman un sufijo dado. De todos los grafos que satisfacen esta descripción, el sufijo autómata es el que tiene el menor número posible de vértices . ${\displaystyle S=s_{1}s_{2}\puntos s_{n))$ $S$

El sufijo autómata fue descrito por primera vez por un grupo de científicos de la Universidad de Denver y Colorado en 1983, también demostraron que el tamaño del autómata depende linealmente de la longitud y también propusieron un algoritmo en línea para construirlo con un tiempo de ejecución lineal . En trabajos posteriores sobre este tema, se descubrió una estrecha conexión entre el autómata de sufijos y los árboles de sufijos , y el concepto de autómata de sufijos recibió varias generalizaciones. Así, se introdujo un autómata de sufijos comprimidos, obtenido del original por un procedimiento similar al que se aplica a un sufijo boro para obtener un árbol de sufijos, así como un autómata de sufijos generalizado, que se construye para un conjunto de palabras y acepta palabras que son sufijos de al menos uno de los datos . $S$ ${\displaystyle S_{1},S_{2},\puntos,S_{k))$

Con la ayuda de un autómata de sufijos, puede resolver eficazmente problemas tales como buscar una subcadena en una cadena , determinar la subcadena común más grande de dos o más cadenas y otros .

Historia

El concepto de sufijo autómata fue introducido por un grupo de científicos de la Universidad de Denver y Colorado Anselm Blumer, Andrzej Ehrenvecht , David Haussler , Ross McConnell y Janet Bloomer en 1983, aunque se encontraron estructuras relacionadas con él. anteriormente en el trabajo de Peter Weiner [1] , Vaughn Pratt [2] y Anatoly Olesevich Slisenko [3] dedicado a los algoritmos para construir árboles de sufijos . En el mismo trabajo, Bloomer y otros demostraron que un autómata construido a partir de una palabra de mayor longitud no contiene más estados ni más transiciones, y también presentó un algoritmo lineal para construir un autómata [4] . $S$ $una$ ${\ estilo de visualización 2 | S | -1}$ ${\ estilo de visualización 3 | S | -4}$

En 1983, Mu Tian Chen y Joel Seiferas desarrollaron de forma independiente un algoritmo para construir un autómata de sufijos que muestra que el algoritmo de Weiner [1] propuesto en 1973 para construir un árbol de sufijos de palabras también construye un autómata de sufijos para la palabra invertida como estructura auxiliar [5] . En 1987, Bloomer y otros, por analogía con un árbol de sufijos, describieron un autómata de sufijos comprimido [6] obtenido a partir de un autómata de sufijos eliminando estados no finales con un resultado semigrado igual a uno, y en 1997 Maxime Crochemore y Renaud Verin desarrolló un algoritmo lineal para su construcción directa [7] . En 2001, Shunsuke Inenaga y otros desarrollaron un algoritmo lineal en línea para construir un autómata de sufijos comprimidos [8] , así como un algoritmo lineal para construir un autómata de sufijos comprimidos para un conjunto de palabras dadas por un árbol de prefijos [9] . $S$ ${\ estilo de texto S^{R}}$

En su artículo original, Bloomer y sus colegas definieron la estructura que describieron como un autómata mínimo que reconoce todas las subcadenas (no los sufijos) de una palabra determinada. Llamaron a esta estructura un gráfico de palabras acíclicas dirigidas [ 4 ] . Posteriormente, este nombre también se usó como sinónimo de un autómata finito acíclico determinista : un autómata mínimo que reconoce un conjunto finito arbitrario de palabras (que no constituyen necesariamente un conjunto de sufijos o subcadenas de una determinada cadena) [10] [ 11] .

Notación

Cuando se describen autómatas con sufijos y hechos y teoremas relacionados, a menudo se utilizan notaciones de la teoría de los lenguajes formales en general y de la teoría de los autómatas en particular [12] :

Un alfabeto es un conjunto finitodel cual se pueden componer palabras. Sus elementos se llaman símbolos ; $\Sigma$
Una palabra es una secuencia finita de caracteres alfabéticos. La longitud de la palabrase denota como; ${\ estilo de visualización \ omega = \ omega _ {1} \ omega _ {2} \ puntos \ omega _ {n}}$ $\omega$ ${\ estilo de visualización | \ omega | = n}$
Un lenguaje formal es un conjunto de palabras sobre un alfabeto dado;
El lenguaje de todas las palabras se denota como (aquí el símbolo "*" lleva el significado de la estrella Kleene ), una palabra vacía (una palabra de longitud cero) - por el símbolo ; $\Sigma^{*}$ $\varepsilon$
La concatenación (producto) de palabras yse denota comooy es igual a la palabra obtenida al atribuiraderecha, es decir,; ${\ estilo de visualización \ alfa = \ alfa _ {1} \ alfa _ {2} \ puntos \ alfa _ {n}}$ ${\ estilo de visualización \ beta = \ beta _ {1} \ beta _ {2} \ puntos \ beta _ {m}}$ $\alpha \cdot \beta$ $\Alfa Beta$ $\beta$ $\alfa$ ${\ estilo de visualización \ alfa \ beta = \ alfa _ {1} \ alfa _ {2} \ puntos \ alfa _ {n} \ beta _ {1} \ beta _ {2} \ puntos \ beta _ {m}}$
La concatenación de lenguas y se denota como o y es igual al conjunto de concatenaciones por pares ; $A$ $B$ $A\cdot B$ $AB$ ${\displaystyle AB=\{\alpha \beta :\alpha \in A,\beta \in B\))$
Si una palabra se puede representar como , donde , entonces las palabras , y se denominan prefijo , sufijo y subpalabra (subcadena) de la palabra , respectivamente; ${\ estilo de visualización \ omega \ en \ Sigma ^ {*}}$ ${\ estilo de visualización \ omega = \ alfa \ gamma \ beta}$ ${\ estilo de visualización \ alfa, \ beta, \ gamma \ en \ Sigma ^ {*}}$ $\alfa$ $\beta$ $\gama$ $\omega$
Si , entonces decimos que la palabra está incluida (ocurre) en como una subpalabra. En este caso , y se denominan posiciones izquierda y derecha de aparición , respectivamente. $T_{l}T_{l+1}\puntos T_{r}=S$ $S$ $T$ $yo$ $r$ $S$ $T$

Estructura del autómata

Formalmente, un autómata finito determinista se define por un conjunto de cinco elementos donde: ${\mathcal {A}}=(\Sigma,Q,q_{0},F,\delta)$

$\Sigma$ - alfabeto , que consiste en palabras reconocidas por la máquina,
$q$ es el conjunto de estados del autómata,
$q_{0}\en Q$ es el estado inicial de la máquina,
${\ estilo de visualización F \ subconjunto Q}$ es el conjunto de estados finales del autómata,
$\delta :Q\times \Sigma \mapsto Q$ es una función de transición parcialmente definida del autómata, de modo que para y no está definida o indica un estado en el que se puede realizar una transición de a . ${\ estilo de visualización \ delta (q, \ sigma)}$ ${\ estilo de visualización q \ en Q}$ $\sigma \en \Sigma$ $q$ $\sigma$

Muy a menudo, en la práctica, los autómatas finitos se representan como un gráfico dirigido ( diagrama ) tal que [13] :

El conjunto de vértices del gráfico corresponde al conjunto de estados , $q$
Se selecciona un cierto vértice en el gráfico, correspondiente al estado inicial , $q_{0}$
El gráfico tiene un conjunto de vértices correspondientes al conjunto de estados finales , $F$
El conjunto de arcos en el gráfico corresponde al conjunto de transiciones , $\delta$
En este caso, la transición corresponde a un arco de a , marcado con el símbolo alfabético . Esta transición también se conoce como . ${\estilo de texto\delta (q_{1},\sigma)=q_{2}}$ $q_{1}$ $q_{2}$ $\sigma$ ${\textstyle q_{1}{\begin{pequeña matriz}{\sigma }\\[-5pt]{\longrightarrow }\end{pequeña matriz}}q_{2}}$

En dicho gráfico, los vértices y arcos se identifican con estados y transiciones del autómata, respectivamente. El autómata acepta una palabra si y sólo si hay un camino desde el estado inicial hasta algún estado final , de modo que si concatenamos los símbolos que se encuentran en este camino, obtenemos la palabra . El conjunto de palabras que un autómata acepta del lenguaje de este autómata [12] . ${\ estilo de visualización \ omega = \ omega _ {1} \ omega _ {2} \ puntos \ omega _ {m}}$ $q_{0}$ ${\ estilo de visualización q \ en F}$ $\omega$

Estados autómatas

El contexto correcto de una palabra en relación con el idioma se llama el conjunto . Es decir, se trata de un conjunto de palabras , atribuyéndolas a la palabra de la derecha resulta una palabra del idioma . Los contextos correctos inducen una relación de equivalencia natural en el conjunto de todas las palabras. Si un lenguaje puede ser definido por algún autómata finito determinista, entonces para él existe un único, hasta el isomorfismo , autómata, que al mismo tiempo tiene el menor número posible de estados. Tal autómata se llama mínimo para un lenguaje dado , el teorema de Myhill-Nerode nos permite especificarlo explícitamente [14] [15] : $\omega$ $L$ ${\displaystyle [\omega ]_{R}=\{\alpha :\omega \alpha \in L\))$ $\alfa$ $\omega$ $L$ ${\ estilo de visualización [\ alfa]_{R}=[\beta]_{R))$ $L$ $L$

Un autómata mínimo que reconoce un idioma sobre un alfabeto se puede dar de la siguiente manera: $L$ $\Sigma$

El alfabeto permanece sin cambios. $\Sigma$
Los estados corresponden a los contextos correctos de todas las palabras , $q$ ${\ estilo de visualización [\ omega] _ {R})$ ${\ estilo de visualización \ omega \ en \ Sigma ^ {*}}$
El estado inicial corresponde al contexto derecho de la palabra vacía , $q_{0}$ ${\ estilo de visualización [\ varepsilon] _ {R})$
Los estados finales corresponden a los contextos correctos de las palabras del idioma , $F$ ${\ estilo de visualización [\ omega] _ {R})$ ${\ estilo de visualización \ omega \ en L}$
Las transiciones tienen la forma , donde y . $\delta$ $[\omega ]_{R}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}[\omega \sigma ]_{R}$ ${\ estilo de visualización \ omega \ en \ Sigma ^ {*}}$ $\sigma \en \Sigma$

En tal notación, un sufijo autómata es un DFA mínimo que acepta la palabra sufijo lenguaje . El contexto correcto de una palabra relativo a un idioma dado consiste en palabras tales que - sufijo . Esto nos permite formular el siguiente lema, que define una correspondencia biunívoca entre el contexto correcto de una palabra y el conjunto de posiciones de sus ocurrencias en una subpalabra [16] [17] : ${\displaystyle S=s_{1}s_{2}\puntos s_{n))$ $\omega$ $\alfa$ ${\ estilo de visualización \ omega \ alfa}$ $S$ $S$

Sea el conjunto de posiciones correctas de ocurrencias en . $endpos(\omega )=\{r:\omega =s_{l}\dots s_{r}\}$ $\omega$ $S$

Entre los elementos de los conjuntos y existe la siguiente correspondencia biunívoca: $endpos(\omega )$ ${\ estilo de visualización [\ omega] _ {R})$

Si , entonces ; $x\in endpos(\omega )$ ${\displaystyle s_{x+1}s_{x+2}\dots s_{n}\in [\omega]_{R))$
Si , entonces . ${\ estilo de visualización \ alfa \ en [\ omega] _ {R})$ $n-\vert \alpha \vert \in endpos(\omega )$

Por ejemplo, para una palabra y su subpalabra , y . Informalmente, consta de palabras que siguen a las ocurrencias hasta el final de la palabra, y - desde las posiciones de estas ocurrencias. En este ejemplo, el elemento coincide con la palabra . Al mismo tiempo, el elemento corresponde a la palabra . $S=abacaba$ ${\ estilo de visualización \ omega = ab}$ $endpos(ab)=\{2,6\}$ $[ab]_{R}=\{a,acaba\}$ ${\ estilo de visualización [ab] _ {R})$ $abdominales$ $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)$

De aquí se sigue una serie de propiedades estructurales de los estados del sufijo autómata y las palabras que aceptan. Sea , entonces [17] : ${\ estilo de visualización | \ alfa | \ leq | \ beta |}$

Si y tiene al menos un elemento común , entonces el elemento común también tiene y . Esto, a su vez, significa que es un sufijo y por lo tanto y . En el ejemplo anterior, y, como consecuencia, es un sufijo , así como y ; ${\ estilo de visualización [\ alfa] _ {R))$ ${\ estilo de visualización [\ beta] _ {R))$ $X$ $endpos(\alpha )$ $endpos(\beta)$ $\alfa$ $\beta$ $endpos(\beta)\subset endpos(\alpha)$ ${\displaystyle [\beta ]_{R}\subconjunto [\alpha ]_{R))$ ${\displaystyle a\in[ab]_{R}\cap[taxi]_{R))$ $abdominales$ ${\ cabina de estilo de pantalla}$ ${\displaystyle [taxi]_{R}=\{a\}\subset \{a,acaba\}=[ab]_{R))$ $endpos(taxi)=\{6\}\subset \{2,6\}=endpos(ab)$
Si , entonces , es decir, aparece en solo como sufijo . Esto se puede ver en el ejemplo de las palabras y , para las cuales y ; ${\ estilo de visualización [\ alfa]_{R}=[\beta]_{R))$ $endpos(\alpha)=endpos(\beta)$ $\alfa$ $S$ $\beta$ ${\ estilo de visualización \ alfa = b}$ ${\ estilo de visualización \ beta = ab}$ ${\displaystyle [b]_{R}=[ab]_{R}=\{a,acaba\))$ $endpos(b)=endpos(ab)=\{2,6\}$
Si y es un sufijo tal que , entonces . En el ejemplo anterior, , y el sufijo "intermedio" es . Y de hecho, . ${\ estilo de visualización [\ alfa]_{R}=[\beta]_{R))$ $\gama$ $\beta$ $|\alpha |\leq |\gamma |\leq |\beta |$ ${\displaystyle [\alpha ]_{R}=[\gamma ]_{R}=[\beta ]_{R))$ $[c]_{R}=[bac]_{R}=\{aba\}$ ${\ estilo de visualización \ gamma = ac}$ $[ac]_{R}=\{aba\}$

Por lo tanto, cualquier estado del autómata de sufijos acepta alguna cadena continua de sufijos anidados de la cadena más grande de este estado [17] . ${\ estilo de visualización q = [\ alfa] _ {R))$

La extensión izquierda de una cadena es la cadena más larga que tiene el mismo contexto derecho que . La longitud de la cadena más larga aceptada por el estado se indica como . Es verdad para él que [18] : ${\overset {\scriptstyle {\leftarrow }}{\gamma }}$ $\gama$ $\omega$ $\gama$ $|{\overset {\scriptstyle {\leftarrow }}{\gamma }}|$ ${\displaystyle q=[\gamma]_{R))$ ${\ Displaystyle len (q)}$

La extensión izquierda de una cadena se puede representar como , donde es la palabra más larga tal que cualquier aparición de una palabra en está precedida por la palabra . $\gama$ ${\overleftarrow {\gamma }}=\beta \gamma$ $\beta$ $\gama$ $S$ $\beta$

Un enlace de sufijo de un estado es un puntero al estado que contiene el sufijo más grande que no es aceptado por el estado . ${\ enlace de estilo de pantalla (q)}$ ${\ estilo de visualización q = [\ alfa] _ {R))$ $pags$ $\alfa$ $q$

En esta notación, podemos decir que el estado toma exactamente todos los sufijos que son más largos que y no más largos que . Además, lo siguiente es cierto [18] : ${\ estilo de visualización q = [\ alfa] _ {R))$ ${\overset {\scriptstyle {\leftarrow }}{\alpha }}$ $len(enlace(q))$ ${\ Displaystyle len (q)}$

Los enlaces de sufijo forman un árbol , que se puede especificar explícitamente de la siguiente manera: ${\mathcal {T}}(V,E)$

Los vértices corresponden a las expansiones izquierdas de todas las subcadenas , $V$ ${\overleftarrow {\omega ))$ $S$
Los bordes conectan vértices tales que y . $mi$ $({\overleftarrow {\omega )),{\overleftarrow {\alpha \omega )))$ ${\ estilo de visualización \ alfa \ en \ Sigma}$ ${\overleftarrow {\omega }}\neq {\overleftarrow {\alpha \omega }}$

Conexión con el árbol de sufijos

Un árbol de prefijos (o taladro ) es un árbol orientado a la raíz, cuyos arcos están marcados con símbolos de tal manera queno sale más de un arco de cualquier vértice de este árbol , etiquetado con un símbolo dado. Algunos vértices del árbol de prefijos están etiquetados. Se dice que un árbol de prefijos define un conjunto de palabras definidas por caminos desde la raíz del árbol hasta los vértices etiquetados. Por lo tanto, los árboles de prefijos son un tipo especial de autómatas finitos, si consideramos la raíz como el estado inicial y los vértices etiquetados como los estados finales [19] . El sufijo boro de una palabraes un árbol de prefijos que define el idioma de los sufijos de esta palabra. Un árbol de sufijos es un árbol obtenido a partir de un taladro de sufijos mediante un procedimiento de compresión, en el que las aristas sucesivas se pegan entre sí si hay un vértice no final entre ellas, cuyo grado es 2 [18] . $v$ $S$

Por definición, se puede obtener un autómata de sufijo minimizando un orificio de sufijo. Además, se puede obtener un autómata de sufijos comprimidos tanto minimizando un árbol de sufijos (asumiendo que los símbolos del alfabeto son palabras en los bordes del árbol) como comprimiendo un autómata convencional [8] . Sin embargo, además de la conexión obvia entre el autómata de sufijos y el árbol de sufijos de la misma cadena, también se puede establecer alguna correspondencia entre el autómata de sufijos de una cadena y el árbol de sufijos de una cadena invertida [20] . ${\displaystyle S=s_{1}s_{2}\puntos s_{n))$ ${\displaystyle S^{R}=s_{n}s_{n-1}\puntos s_{1))$

De manera similar a los contextos de la derecha, se pueden introducir contextos de la izquierda y extensiones de la derecha correspondientes a las cadenas más largas que tienen un contexto de la izquierda dado, así como una relación de equivalencia . Si consideramos las extensiones correctas con respecto al idioma del prefijo de cadena , entonces podemos obtener eso [18] : ${\displaystyle [\omega ]_{L}=\{\beta \in \Sigma ^{*}:\beta \omega \in L\))$ ${\overset {\scriptstyle {\rightarrow }}{\omega ~}}$ ${\ estilo de visualización [\ alfa]_{L}=[\beta]_{L))$ $L$ $S$

El árbol de sufijos de una cadena se puede especificar explícitamente de la siguiente manera: $S$

Los vértices corresponden a las extensiones derechas de todas las subcadenas , $V$ ${\overrightarrow {\omega ))$ $S$
Las aristas corresponden a ternas tales que y . $mi$ $({\overrightarrow {\omega )),x\alpha ,{\overrightarrow {\omega x)))$ ${\ estilo de visualización x \ en \ Sigma}$ ${\overrightarrow {\omega x}}={\overrightarrow {\omega }}x\alpha$

Aquí, el triple significa que la cadena de a está escrita en el borde . $(v_{1},\omega ,v_{2})\en E$ $v_{1}$ $v_{2}$ $\omega$

De lo cual se deduce que el árbol de enlaces de sufijos para un autómata de cadenas y el árbol de sufijos de una cadena son isomorfos [20] : $S$ ${\ estilo de visualización S^{R}}$

Estructuras de sufijos de las palabras abbcbc y cbcbba
Sufijo autómata para la palabra abcbc Sufijo boro, árbol de sufijos y sufijo autómata comprimido para la palabra abbcbc . Los números de vértice corresponden a los estados en los que entran cuando se minimizan o reducen. Árbol de sufijos para la palabra cbcbba (árbol de enlaces de sufijos para el autómata de la palabra abbcbc )

De manera similar a las extensiones por la izquierda, también se puede formular un lema estructural [18] para las extensiones por la derecha :

La extensión derecha de una cadena se puede representar como , donde es la palabra más larga tal que cualquier aparición de in va seguida inmediatamente por la palabra . $\gama$ ${\overrightarrow {\gamma}}=\gamma \alpha$ $\alfa$ $\gama$ $S$ $\beta$

Tamaño

En un autómata de sufijos, las cadenas de longitud no son más que estados y no más que transiciones, y estas estimaciones se logran en cadenas y, respectivamente [16] . También es posible formular una declaración más fuerte sobre la relación entre el número de estados y transiciones en un autómata: , donde y son el número de transiciones y estados, respectivamente [17] . $S$ $n>1$ $2n-1$ ${\ estilo de visualización 3n-4}$ ${\displaystyle abb\dots bb=ab^{n-1))$ $abb\puntos bc=ab^{n-2}c$ ${\ estilo de visualización | \ delta | \ leq | Q | + n-2}$ ${\ estilo de visualización | \ delta |}$ ${\ estilo de visualización | Q |}$

Autómatas de sufijo máximo
Sufijo autómata para $ab^{n-1}$ Sufijo autómata para $ab^{n-2}c$

Edificio

El sufijo autómata de una cadena se construye construyendo sucesivamente la palabra para la que se construye. Inicialmente, se construye un autómata trivial para una palabra vacía, y luego en cada paso se agrega un símbolo a la palabra actual, lo que implica un reordenamiento de estados y transiciones del autómata [21] . ${\displaystyle S=s_{1}s_{2}\puntos s_{n))$

Cambio de estados

Después de asignar un nuevo carácter a una palabra, algunas clases de equivalencia cambiarán. Sea el contexto correcto de la palabra con respecto al sufijo idioma de la palabra . Luego, la transición de a cuando se asigna un símbolo a una palabra se describe mediante el siguiente lema [17] : ${\ estilo de visualización [\ alfa] _ {R_ {\ omega}}}$ $\alfa$ $\omega$ ${\ estilo de visualización [\ alfa] _ {R_ {\ omega}}}$ ${\ estilo de visualización [\ alfa] _ {R_ {\ omega x}}}$ $X$ $\omega$

Sean algunas palabras sobre un alfabeto y sean algún símbolo de este alfabeto. Entonces entre los contextos correctos y las palabras con respecto a los idiomas de los sufijos de las palabras y, respectivamente, se da la siguiente relación: ${\ estilo de visualización \ alfa, \ omega \ en \ Sigma ^ {*}}$ $\Sigma$ ${\ estilo de visualización x \ en \ Sigma}$ ${\ estilo de visualización [\ alfa] _ {R_ {\ omega}}}$ ${\ estilo de visualización [\ alfa] _ {R_ {\ omega x}}}$ $\alfa$ $\omega$ ${\ estilo de visualización \ omega x}$

$[\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x\cup \{\varepsilon \}$ si - sufijo ; $\alfa$ ${\ estilo de visualización \ omega x}$
$[\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x$ de lo contrario.

Es decir, cuando se agrega un carácter a la palabra actual, el contexto correcto de la palabra solo puede cambiar si es un sufijo de palabra . De esto se sigue que la partición de todas las palabras en clases de equivalencia con respecto a es un refinamiento de la partición en clases de equivalencia con respecto a . En otras palabras, si , entonces . Además, al agregar el siguiente símbolo a la palabra, la división se producirá en no más de dos estados. En primer lugar, se dividirá el estado que corresponde al contexto derecho vacío (es decir, el que toma el idioma de las palabras que no se incluyen como subpalabra). De este estado, se extraerá un nuevo estado que contiene la palabra completa , así como todos sus sufijos que ocurren pero no ocurrieron en . En consecuencia, el contexto correcto de estas palabras, que antes estaba vacío, ahora consistirá solo en la palabra vacía [17] . $X$ $\omega$ $\alfa$ $\alfa$ ${\ estilo de visualización \ omega x}$ ${\ Displaystyle \ equiv _ {R_ {\ omega x}}}$ ${\ estilo de visualización \ equiv _ {R_ {\ omega}}}$ $[\alfa]_{R_{\omega x))=[\beta]_{R_{\omega x))$ $[\alpha ]_{R_{\omega }}=[\beta ]_{R_{\omega }}$ $\omega$ ${\ estilo de visualización \ omega x}$ ${\ estilo de visualización \ omega x}$ $\omega$

Teniendo en cuenta la conexión entre los estados del autómata de sufijos y los vértices del árbol de sufijos, también podemos rastrear el segundo estado, que puede dividirse cuando se agrega el siguiente símbolo. Dado que una transición de palabra -to corresponde a una transición a-to para una cadena invertida, asignar un carácter a una cadena corresponde a agregar un sufijo nuevo (el más largo) al árbol de sufijos de la cadena . En este caso, no aparecerán más de dos vértices: uno de ellos corresponderá a la palabra entera , y el otro podrá aparecer en el lugar donde se encuentra la rama del árbol. Por lo tanto, un nuevo estado corresponde al contexto correcto de toda la cadena y el otro (si lo hay) solo puede corresponder a la referencia del sufijo de ese estado. Estas observaciones pueden generalizarse mediante el teorema [17] : $\omega$ ${\ estilo de visualización \ omega x}$ ${\ estilo de visualización \ omega ^ {R}}$ $x\omega ^{R}$ $X$ $\omega$ $x\omega ^{R}$ ${\ estilo de visualización \ omega ^ {R}}$ $x\omega ^{R}$ ${\ estilo de visualización \ omega x}$

Sea y . Sea también el sufijo más largo que ocurre en , y sea su extensión izquierda con respecto a , es decir, la subpalabra más larga de la palabra tal que . Entonces lo siguiente es cierto para cualquier subpalabra de la palabra : ${\ estilo de visualización \ omega \ en \ Sigma ^ {*}}$ ${\ estilo de visualización x \ en \ Sigma}$ $\alfa$ ${\ estilo de visualización \ omega x}$ $\omega$ $\beta ={\overset {\scriptstyle {\leftarrow }}{\alpha }}$ $\omega$ $\omega$ $[\alpha ]_{R_{\omega }}=[\beta ]_{R_{\omega }}$ $tú, v$ $\omega$

Si y , entonces ; $[u]_{R_{\omega }}=[v]_{R_{\omega }}$ $[u]_{R_{\omega }}\neq [\alfa]_{R_{\omega }}$ $[u]_{R_{\omega x}}=[v]_{R_{\omega x}}$
Si y , entonces ; $[u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}$ ${\ estilo de visualización \ vert u \ vert \ leq \ vert \ alpha \ vert}$ $[u]_{R_{\omega x}}=[\alpha ]_{R_{\omega x}}$
Si y , entonces . $[u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}$ $\vert u\vert >\vert \alpha \vert$ $[u]_{R_{\omega x))=[\beta]_{R_{\omega x))$

En particular, si (por ejemplo, cuando no ocurre en absoluto en y ), no ocurre la división del segundo estado [17] . ${\ estilo de visualización \ alfa = \ beta}$ $X$ $\omega$ ${\ estilo de visualización \ alfa = \ beta = \ varepsilon}$

Además de los enlaces de sufijos, los estados finales también deben definirse en el nuevo autómata. De las propiedades estructurales del autómata se sigue que los sufijos de cualquier palabra están ubicados de tal manera que si , entonces los sufijos cuya longitud excede , se encuentran en , los sufijos cuya longitud es mayor que , pero no mayor que , se encuentran en , y pronto. En otras palabras, para cualquier sufijo hay un vértice en el estado del sufijo path , que viene dado por la secuencia . En consecuencia, si designamos el estado que actualmente acepta toda la cadena como , entonces los estados del terminal (que aceptan sufijos ) serán aquellos y solo aquellos estados que están incluidos en la ruta del sufijo [21] . $\alfa$ ${\ estilo de visualización q = [\ alfa] _ {R))$ $\alfa$ $len(enlace(q))$ $q$ $len(enlace(enlace(q))$ $len(enlace(q))$ ${\ enlace de estilo de pantalla (q)}$ $\alfa$ $q$ $(q,enlace(q),enlace^{2}(q),\puntos)$ $\omega$ ${\ estilo de visualización último}$ $\omega$ $(último,enlace(último),enlace^{2}(último),\puntos)$

Cambio de saltos y enlaces de sufijos

Cualquier cambio al agregar el siguiente carácter no afecta a más de dos nuevos estados, por lo que los cambios en las transiciones del autómata también afectarán solo a estos estados. Después de la atribución a la palabra , se forma un nuevo estado y también, posiblemente, un estado . El sufijo link from conducirá a , y from -to . Las palabras from ocurren solo como sufijos, por lo que no debe haber transiciones from, y las transiciones que conducen a ella deben comenzar por carácter de sufijos con una longitud de al menos . El estado se separa de , por lo que las transiciones desde este estado duplicarán las de . Y las transiciones que conducen a él conducirán por símbolo de estados correspondientes a sufijos de longitud menor que y no menor que , ya que antes estas transiciones conducían y correspondían a la parte separada del estado. Los estados que aceptan estas palabras se pueden identificar mediante la ruta del sufijo de estado [21] . $X$ $\omega$ $[\omega x]_{R_{\omega x))$ ${\ estilo de visualización [\ alfa] _ {R_ {\ omega x}}}$ $[\omega x]_{R_{\omega x))$ ${\ estilo de visualización [\ alfa] _ {R_ {\ omega x}}}$ ${\ estilo de visualización [\ alfa] _ {R_ {\ omega x}}}$ ${\ enlace de estilo de visualización ([\ alfa] _ {R_ {\ omega}})}$ $[\omega x]_{R_{\omega x))$ ${\ estilo de visualización \ omega x}$ $[\omega x]_{R_{\omega x))$ $X$ $\omega$ $|\alfa |$ ${\ estilo de visualización [\ alfa] _ {R_ {\ omega x}}}$ ${\ estilo de visualización [\ alfa] _ {R_ {\ omega}}}$ ${\ estilo de visualización [\ alfa] _ {R_ {\ omega}}}$ $X$ $\omega$ $|\alfa |$ $len(enlace([\alpha ]_{R_{\omega ))))$ ${\ estilo de visualización [\ alfa] _ {R_ {\ omega}}}$ $[\omega ]_{R_{\omega ))$

Construyendo un sufijo autómata para la palabra abcbc

∅ → un


Cuando se agrega el primer símbolo, se crea un único estado nuevo en el autómata.	De manera similar, se agrega una sola hoja al árbol de sufijos.

a→ab


Se extraen nuevas transiciones de todos los estados finales, ya que el nuevo símbolo no se ha encontrado antes.	Por la misma razón, en un árbol de enlaces de sufijos, el nuevo nodo se suspende desde la raíz.

ab → abb


El estado 2 toma las palabras ab y b , pero solo b se convertirá en un sufijo, por lo que esa palabra se asigna al estado 4.	En el árbol de sufijos de la palabra expandida, esto corresponde a la división del borde que conduce al vértice 2.

abb → abbc


El nuevo símbolo no se ha visto antes, las transiciones se llevan a cabo desde todos los finales.	Se agrega una nueva hoja al árbol de enlaces de sufijos suspendidos de la raíz.

abbc → abbcb


En el estado 4, solo existe la palabra b y es un sufijo, por lo que no se produce división.	En consecuencia, en el árbol de enlaces de sufijos, una nueva hoja se suspende del vértice 4.

abbcb → abbcbc


El estado 5 acepta las palabras abbc , bbc , bc y c , pero solo las dos últimas son sufijos de la nueva palabra, por lo que se separan en un estado 8 separado.	En consecuencia, en el árbol de enlaces de sufijos, el borde que conduce al vértice 5 se divide.

Algoritmo para la construcción de un autómata

Los resultados teóricos anteriores conducen al siguiente algoritmo, que toma un símbolo y reorganiza un autómata de sufijo de palabra en un autómata de sufijo de palabra [21] : $X$ $\omega$ ${\ estilo de visualización \ omega x}$

Se admite un número de estado correspondiente a toda la línea ; ${\ estilo de visualización último}$ $\omega$
Cuando se agrega un símbolo , el número se almacena en la variable , y se escribe el número del nuevo estado correspondiente a la palabra ; $X$ ${\ estilo de visualización último}$ $pags$ ${\ estilo de visualización último}$ ${\ estilo de visualización \ omega x}$
De los estados correspondientes a los sufijos , se añaden transiciones a . Para hacer esto, se pasa por alto la ruta del sufijo hasta que se encuentra un estado desde el cual ya hay una transición a lo largo de ; $\omega$ ${\ estilo de visualización último}$ $p,enlace(p),enlace^{2}(p),\puntos$ $X$
Otras acciones corresponden a uno de los tres casos:
1. Si en toda la ruta del sufijo no hay transición de ningún estado a , entonces no se ha encontrado previamente en y el enlace del sufijo de conduce a ; $X$ $X$ $\omega$ ${\ estilo de visualización último}$ $q_{0}$
2. Si se encontró la transición por y conduce de estado a estado tal que , entonces no hay necesidad de dividir y es suficiente dibujar un enlace de sufijo de a ; $X$ $pags$ $q$ $len(p)+1=len(q)$ $q$ ${\ estilo de visualización último}$ $q$
3. Si , entonces las palabras del estado cuya longitud no exceda deben separarse en un estado separado ; $len(q)>len(p)+1$ $q$ $len(p)+1$ ${\ estilo de visualización cl}$
Si se seleccionó un estado separado en el paso anterior , entonces las transiciones y el enlace de sufijo deberían duplicarse en , mientras que se convertirá en un enlace de sufijo común de los estados y ; ${\ estilo de visualización cl}$ $q$ ${\ estilo de visualización cl}$ $q$ ${\ estilo de visualización último}$
Los saltos que conducen a palabras coincidentes de longitud no superior a , se redirigen a . Para hacer esto, puede continuar siguiendo la ruta del sufijo hasta que encuentre un estado, cuya transición no conduzca a . $q$ $len(p)+1$ ${\ estilo de visualización cl}$ $pags$ $q$

El procedimiento que implementa este algoritmo se puede describir mediante el siguiente pseudocódigo:

función add_letter(x) : definir p = último asignar último = nuevo_estado() asignar len(último) = len(p) + 1 hasta que se defina δ(p , x) : asignar δ(p, x) = último, p = link(p) define q = δ(p, x) if q = last : asigna link(last) = q 0 else if len(q) = len(p) + 1 : asigna link(last) = q else : define cl = nuevo_estado() asignar len(cl) = len(p) + 1 asignar δ(cl) = δ(q), enlace(cl) = enlace(q) asignar enlace(último) = enlace(q) = cl while δ(p, x) = q : asignar δ(p, x) = cl, p = enlace(p)

Aquí , es el estado inicial del autómata, y es una función que agrega un nuevo estado al autómata. Se supone que , y se almacenan como variables globales. $q_{0}$ $nuevo\_estado()$ ${\ estilo de visualización último}$ ${\ estilo de visualización largo}$ ${\ enlace de estilo de visualización}$ $\delta$

Complejidad computacional

Según las estructuras utilizadas, se puede implementar una versión determinista del algoritmo descrito anteriormente en tiempo de memoria o en tiempo de memoria , suponiendo que la asignación de memoria se produzca en . Al mismo tiempo, para obtener tal estimación del tiempo de ejecución, es necesario realizar un análisis de amortización de los ciclos internos del algoritmo. Si consideramos cómo cambia el parámetro después de la primera iteración del primer ciclo, podemos ver que disminuye estrictamente con cada iteración del ciclo. Además, si en la última iteración del paso anterior este valor era igual a , entonces en la segunda iteración del siguiente paso este valor será igual a . Que no exceda en ningún instante de tiempo, y que entre ciclos esta cantidad aumente en uno solo, da la afirmación requerida. Un análisis similar puede mostrar la linealidad del tiempo total de ejecución del segundo ciclo del algoritmo [21] . $O(n\log |\Sigma |)$ $En)$ $En)$ ${\ estilo de visualización O (n | \ Sigma |)}$ $O(1)$ $len(p)$ $k$ $k+1$ $len(p)$ $norte$

Variaciones y generalizaciones

El autómata de sufijos está estrechamente relacionado con otras estructuras de sufijos e índices de subcadenas . Teniendo un autómata de sufijos de alguna cadena, es posible construir un árbol de sufijos de esta cadena en tiempo lineal mediante compresión y recorrido recursivo de este autómata [22] . Son posibles transformaciones similares en ambas direcciones entre un autómata de sufijo de cadena y un árbol de sufijo de cadena invertido [20] . Además, se han desarrollado una serie de modificaciones del algoritmo que permiten construir un autómata para un conjunto de cadenas dadas por un árbol de prefijos [9] , aplicarle compresión [6] , mantener su estructura en modo ventana deslizante [23] , y también reconstruir al agregar caracteres tanto desde el final como desde el comienzo de la cadena [24] . $S$ ${\ estilo de visualización S^{R}}$

Autómata de sufijo comprimido

Como se mencionó anteriormente, se puede obtener un autómata de sufijo comprimido a partir de un autómata de sufijo ordinario mediante compresión (eliminando estados que no son finales y de los que conduce exactamente una transición), así como minimizando el árbol de sufijos, si asumimos que el alfabeto es formado por palabras escritas en los bordes del árbol. Además, los estados de un autómata comprimido se pueden describir explícitamente, de forma similar a como se hizo para un autómata sin comprimir. Una extensión de palabra bidireccional es la palabra más larga , de modo que cualquier ocurrencia en está precedida por una palabra e inmediatamente seguida por una palabra . En términos de extensiones izquierda y derecha, esto significa que la extensión bidireccional es la extensión izquierda de la extensión derecha o, de manera equivalente, la extensión derecha de la extensión izquierda: . En términos de extensiones bilaterales, un autómata de sufijo comprimido se puede describir de la siguiente manera [18] : ${\overset {\scriptstyle {\longleftrightarrow}}{\gamma}}$ $\gama$ $\omega =\beta \gamma \alpha$ $\gama$ $S$ $\beta$ $\alfa$ ${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\gamma }}={\overset {\scriptstyle \leftarrow }{\overset {\rightarrow }{\gamma }}}={\overset {\rightarrow }{\ overset {\scriptstyle \leftarrow }{\gamma ))))$

El sufijo comprimido autómata de una palabra puede estar dado por el par , donde: $S$ $(V,E)$

$V=\{{\overleftrightarrow {\omega }}:\omega \in \Sigma ^{*}\}$ es el conjunto de estados del autómata;
$E=\{({\overleftrightarrow {\omega )),x\alpha ,{\overleftrightarrow {\omega x))):x\in \Sigma ,\alpha \in \Sigma ^{*},{ \overleftrightarrow {\omega x}}={\overleftrightarrow {\omega }}x\alpha \}$ - un conjunto de transiciones del autómata.

Las extensiones bidireccionales generan una relación de equivalencia que describe las palabras aceptadas por el mismo estado del autómata comprimido. Esta relación es un cierre transitivo de la relación , que enfatiza el hecho de que los estados de un autómata de sufijo comprimido se pueden obtener pegando vértices de árboles de sufijos que son equivalentes en términos de (minimización del árbol de sufijos) y pegando estados de un autómata de sufijos que son equivalentes en términos de (comprimir sufijo autómata) [25 ] . Si las palabras y tienen las mismas extensiones a la derecha, y las palabras y tienen las extensiones a la izquierda, entonces en conjunto las palabras , y tienen la misma extensión bilateral. En este caso, puede resultar que las palabras y no tengan las mismas extensiones izquierda o derecha. En el caso de , y las extensiones izquierda y derecha son: , pero y . En el caso de contextos y extensiones unidireccionales, las palabras de la misma clase de equivalencia formaban una cadena continua de prefijos o sufijos anidados y podían determinarse únicamente por la longitud de las palabras más cortas y más largas de la clase. En el caso de las extensiones bidireccionales, solo se puede decir con certeza que las palabras de la misma clase son subpalabras de la palabra más larga de esta clase y, de lo contrario, las clases pueden tener una estructura bastante compleja. El número total de tales clases de equivalencia no excede , lo que implica que un autómata de sufijo comprimido de una cadena de longitud tendrá como máximo estados. El número de transiciones en tal autómata no excede [18] . ${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\alpha }}={\overset {\scriptstyle \longleftrightarrow }{\beta }}}$ ${\textstyle ({\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}})\vee ({\overset {\ estilo de script {\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$ $\gama$ $\alfa$ $\beta$ $\gama$ $\alfa$ $\gama$ ${\ estilo de visualización S = \ beta = ab}$ ${\ estilo de visualización \ alfa = a}$ ${\ estilo de visualización \ 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$ $norte$ $n+1$ $2n-2$

Sufijo autómata para un conjunto de cadenas

Deje que se dé un conjunto de palabras . De manera similar a un autómata construido sobre una sola palabra , podemos considerar un autómata de sufijo generalizado que acepta el lenguaje de las palabras que son el sufijo de al menos una palabra de . En este caso, para el número de estados y transiciones de este autómata, se cumplirán todas las mismas restricciones que se indicaron anteriormente si ponemos [25] . El algoritmo de construcción en sí es esencialmente similar al algoritmo para construir un autómata para una línea, pero en lugar de un puntero al estado correspondiente a la palabra , al pasar a la palabra , la función agregar_letra tomará un puntero al estado que acepta el word , lo que implica que la transición se produce desde el conjunto actual de palabras al conjunto . Además de las acciones principales que ya están incluidas en el algoritmo, será necesario analizar por separado el caso cuando la cadena ya esté presente en la máquina; en este caso, es posible que deba dividir el estado que la acepta, similar a cómo sucedió al formar un enlace de sufijo en el algoritmo para una sola palabra [26] [27] . $T=\{S_{1},S_{2},\puntos,S_{k}}\}$ $S$ $T$ $n=|S_{1}|+|S_{2}|+\puntos +|S_{k}|$ ${\ estilo de visualización último}$ $\omega$ ${\ estilo de visualización \ omega x}$ $\ omega _ {i}$ ${\displaystyle \{\omega _{1},\puntos,\omega _{i},\puntos,\omega _{k))\))$ ${\displaystyle \{\omega _{1},\puntos,\omega _{i}x,\puntos,\omega _{k}\))$ ${\ estilo de visualización \ omega _ {i} x}$

Un desarrollo posterior de esta idea fue la construcción de un autómata de sufijos para el caso en que el conjunto no se especifica de forma explícita, sino como un árbol de prefijos en los vértices. Mohry y otros han demostrado que tal autómata contiene en la mayoría de los estados y puede construirse en el tiempo lineal en su tamaño. Al mismo tiempo, la cantidad de transiciones en dicho autómata puede alcanzar ; por ejemplo, si consideramos un conjunto de palabras sobre el alfabeto , entonces la longitud total de las palabras de este conjunto será del orden de , la cantidad de vértices en el árbol de prefijos correspondiente será igual a , y en el sufijo autómata habrá un orden de estados y transiciones. El algoritmo en sí, propuesto por Mohri, repite en gran medida el algoritmo general para construir un autómata a partir de un conjunto de cadenas, pero en lugar de agregar cada vez los caracteres de una palabra del conjunto de principio a fin, el algoritmo atraviesa el árbol de prefijos en el orden de recorrido en ancho y asigna los siguientes caracteres en ese orden, en el que los encuentra durante el recorrido, lo que garantiza un tiempo de ejecución lineal amortizado del algoritmo [28] . $T$ $q$ ${\ estilo de visualización 2Q-2}$ ${\ estilo de visualización O (Q | \ Sigma |)}$ $T=\{\sigma_{1},a\sigma_{1},a^{2}\sigma_{1},\dots,a^{n}\sigma_{1},a ^{n}\sigma_{2},\puntos,a^{n}\sigma_{k}\}$ ${\displaystyle \Sigma =\{a,\sigma _{1},\puntos,\sigma _{k}\))$ ${\textstyle O(n^{2}+nk)}$ $O(n+k)$ $O(n+k)$ $O (nk)$

Ventana corrediza

En algunos algoritmos de compresión , como LZ77 y RLE , puede ser útil almacenar un autómata de sufijo o una estructura similar no para la palabra de lectura completa, sino solo para los últimos caracteres. En primer lugar, surge tal necesidad debido a las características específicas de las tareas de compresión de datos, donde las cadenas comprimidas suelen ser bastante grandes y el uso de la memoria no es deseable. En 1985, Janet Bloomer desarrolló un algoritmo que admite un autómata de sufijos en una ventana de tamaño deslizante y se ejecuta en el peor de los casos y en el promedio, suponiendo que los caracteres de la palabra que se va a comprimir se distribuyen de manera independiente y uniforme . En el mismo trabajo se demostró que la estimación es inmejorable - si consideramos palabras obtenidas por formaconcatenación de varias palabras de la para un sufijo autómata es imposible [29] . $k$ $En)$ $k$ $O (nk)$ ${\ estilo de visualización O (n \ log k)}$ $O (nk)$ $(ab)^{m}c(ab)^{m}d$ $k=6m+2$ $k$ $metro$ $O (nk)$

Parecería que lo mismo debería ser cierto para el árbol de sufijos , ya que los vértices del árbol de sufijos corresponden a los estados del autómata de sufijos de la cuerda desplegada. Sin embargo, si no se asigna un vértice separado para cada sufijo en el árbol de sufijos, entonces no habrá saltos tan bruscos y es posible la construcción de un algoritmo amortizado que admita el árbol de sufijos en una ventana deslizante. Un algoritmo correspondiente para un árbol de sufijos, basado en el algoritmo de McCraith y que permite agregar un nuevo carácter a la derecha y eliminar un carácter a la izquierda, fue propuesto en 1989 por Edward Fiala y Daniel Green [30] , y en 1996 expuesto en términos del algoritmo de Ukkonen por Jesper Larsson [31] [ 32] . En este sentido, la cuestión de si es posible mantener una ventana deslizante rápida para un autómata comprimido, que combina algunas propiedades tanto de un autómata de sufijos ordinarios como de un árbol de sufijos, permaneció abierta durante mucho tiempo. Martin Senft y Tomasz Dvorak obtuvieron una respuesta negativa a esta pregunta en 2008, quienes demostraron que si el alfabeto consta de dos o más caracteres, entonces el tiempo amortizado requerido para cambiar la ventana un carácter en el peor de los casos es del orden de [33] . $OK)$

Al mismo tiempo, si el ancho exacto de la ventana no es importante y el objetivo es solo mantener una ventana cuyo ancho no exceda , en orden de magnitud, esto se puede hacer con el algoritmo aproximado propuesto por Inenaga et al. 2004. Una característica del algoritmo es que la “ventana” que se mueve a lo largo de la palabra tiene una longitud variable, que en cualquier momento no es ni menor ni mayor que , mientras que el tiempo total de ejecución sigue siendo lineal [34] . $OK)$ $k$ ${\ estilo de visualización 2k+1}$

Aplicaciones

El autómata de sufijo de cadena se puede utilizar para resolver problemas como [35] [36] : $S$

Contar el número de subcadenas distintas a lo largo del tiempo en línea, $S$ ${\ estilo de visualización O (| S |)}$
Encontrar la subcadena más larga que se incluye en ella al menos dos veces, en el tiempo , $S$ ${\ estilo de visualización O (| S |)}$
Encontrar la subcadena común más grande de cadenas y en el tiempo , $S$ $T$ ${\ estilo de visualización O (| T |)}$
Contando el número de ocurrencias de una cadena como una subcadena en el tiempo , $T$ $S$ ${\ estilo de visualización O (| T |)}$
Busque todas las ocurrencias en el tiempo , donde es el número de ocurrencias. $T$ $S$ ${\ estilo de visualización O (| T | + k)}$ $k$

Aquí vale la pena considerar que se ingresa alguna cadena cuando el autómata ya se ha construido y está listo para usar. $T$

Los autómatas de sufijos también se han abierto paso en aplicaciones como la compresión de datos [37] , la identificación de música a partir de fragmentos grabados [38] [39] y la coincidencia de secuencias genómicas [40] .

Notas

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

Literatura

Sgarbas K. N., Fakotakis N. D., Kokkinakis G. K. Inserción óptima en DAWG deterministas // Ciencias informáticas teóricas - Elsevier BV , 2003. - Vol . 301, edición. 1-3. - Pág. 103-117. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/S0304-3975(02)00571-6
Perrin D. Autómatas finitos // Modelos formales y semántica : Manual de informática teórica / 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. Algoritmos de coincidencia de patrones lineales (inglés) // Simposio sobre fundamentos de la informática - 1973. - P. 1-11. — 213p. doi : 10.1109/SWAT.1973.13
Pratt V. R. Mejoras y aplicaciones para el buscador de repeticiones de Weiner (inglés) - 1973.
Slisenko A. O. Detección de periodicidades y coincidencia de cadenas en tiempo real (inglés) // Revista de matemáticas soviéticas - Springer Science + Business Media , 1983. - Vol. 22, edición. 3.- Pág. 1316-1387. — ISSN 1072-3374 ; 1573-8795 - doi:10.1007/BF01084395
Blumer A. C. , Blumer J. , Ehrenfeucht A. , Haussler D. , McConnell R. Building the minimal DFA for the set of all subwords of a word on-line in linear time // Automata , Languages and Programming - 1984 .- págs. 109-118. — 526 pág. — 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. Archivos invertidos completos para una recuperación y análisis de texto eficientes // J. ACM / D. J. Rosenkrantz - Nueva York, NY : Association for Computing Machinery . 1987. vol. 34, edición. 3.- Pág. 578-595. - ISSN 0004-5411 - doi:10.1145/28869.28873
Blumer J. ¿Cuánto cuesta ese DAWG en la ventana? Un algoritmo de ventana móvil para el gráfico de palabras acíclicas dirigidas (inglés) // Journal of Algorithms - Academic Press , 1987. - vol. 8, edición. 4.- Págs. 451-469. — ISSN 0196-6774 ; 1090-2678 - doi:10.1016/0196-6774(87)90045-9
Chen M., Seiferas J. Construcción de árbol de subpalabras eficiente y elegante (inglés) // Algoritmos combinatorios en palabras / 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. Construcción bidireccional de árboles de sufijos (inglés) // Nordic Journal of Computing - 2003. - vol. 10, edición. 1.- Pág. 52-67. — ISSN 1236-6064
Inenaga S., Hoshino H., Shinohara A., Takeda M., Arikawa S., Mauri G., Pavesi G. Construcción en línea de gráficos de palabras acíclicas dirigidas compactas // Matemáticas aplicadas discretas - Elsevier BV , 2005. Vol. 146, edición. 2.- Pág. 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. Construcción del CDAWG para un trie (inglés) // Conferencia de Stringología de Praga - Universidad Técnica Checa en Praga : 2001. - P. 37-48.
Inenaga S., Shinohara A., Takeda M., Arikawa S. Gráficos de palabras acíclicas dirigidas compactas para una ventana deslizante (inglés) // Journal of Discrete Algorithms - Elsevier BV , 2004. - Vol. 2, edición. 1.- Pág. 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 (inglés) // Simposio sobre aspectos teóricos de la informática / E. Mayr , N. Portier — 2014 .- vol. 25.- Pág. 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 DAWG y Minimal Absent Words in Linear Time for Integer Alphabets // Mathematical Foundations of Computer Science / P. Faliszewski , A. Muscholl , R. Niedermeier - 2016. - Vol. 58—Pág. 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. Algoritmo de construcción de autómatas de sufijos generales y límites espaciales (inglés) // Ciencias de la computación teórica - Elsevier BV , 2009. - vol. 410, edición. 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 (Inglés) // 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 (inglés) // Handbook of Formal Languages / G. Rozenberg , A. Salomaa - Springer Berlin Heidelberg , 1997. - Vol. 2.- Pág. 399-462. - ISBN 978-3-642-59136-5 - doi:10.1007/978-3-662-07675-0_9
Crochemore M. , Vérin R. Sobre gráficos de palabras acíclicos dirigidos compactos (inglés) // Estructuras en lógica e informática : una selección de ensayos en honor a A. Ehrenfeucht / J. Mycielski , G. Rozenberg , A. Salomaa - Springer Berlin Heidelberg , 1997. - Págs. 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 // Procesamiento de cadenas y recuperación de información / 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. Introducción a la teoría, los lenguajes y la computación de los autómatas (ing.) - 1 - MA : Addison-Wesley , 1979. - 418 p. — ISBN 978-81-7808-347-6
Fiala E. R., Greene D. H. Compresión de datos con ventanas finitas // Commun . ACM - [Nueva York] : Asociación de Maquinaria de Computación , 1989. - Vol. 32, edición. 4.- Pág. 490-505. — ISSN 0001-0782 ; 1557-7317 - doi:10.1145/63334.63341
Senft M., Dvořák T. Sliding CDAWG Perfection (inglés) // Procesamiento de cadenas y recuperación de información / 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. Aplicación extendida de árboles de sufijos a la compresión de datos // Procedimientos . Conferencia de Compresión de Datos - 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. Árbol de sufijos deslizantes (inglés) // Algorithms - MDPI , 2018. - Vol. 11, edición. 8. - Pág. 118. - ISSN 1999-4893 - doi:10.3390/A11080118
Rubinchik M., Shur A. M. Eertree (inglés) : una estructura de datos eficiente para procesar palíndromos en cadenas // 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ág. 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. Teoría e implementación de lenguajes de programación : Libro de texto - M .: MZ Press , 2006. - 352 p. — ISBN 5-94073-094-9
Rubtsov A. A. Notas y problemas sobre lenguajes regulares y autómatas finitos - Moscú : MIPT , 2019. - 112 p. — ISBN 978-5-7417-0702-9
Parashchenko D. A. Procesamiento de cadenas basado en autómatas de sufijo - San Petersburgo. : ITMO , 2007. - 35 págs.

Enlaces

sufijo autómata. Construyendo en O(N) y aplicando . MÁXima . (indefinido)
Sufijo autómata . Wikinotas de ITMO . (indefinido)

Instrumentos de cuerda
Medidas de similitud de cadenas	Distancia de Damerau a Loewenstein distancia Levenstein distancia de hamming Similitudes Jaro-Winkler
Búsqueda de subcadena	Algoritmo de Boyer-Moore Algoritmo de Boyer-Moore-Horspool Algoritmo de Knuth-Morris-Pratt Algoritmo de Rabin-Karp función de prefijo Función Z Algoritmo Aho - Korasik
palíndromos	árbol palíndromo Algoritmo del administrador
Alineación de secuencia	Algoritmo de Needleman-Wunsha Algoritmo de Smith-Waterman
Estructuras de sufijos	Matriz de sufijos sufijo autómata árbol de sufijos árbol de prefijos
Otro	analizando La coincidencia de patrones Mayor subsecuencia común Mayor subcadena común

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami