Autómata de sufijo

Autómata de sufijo
Tipo	Índice de subcadena
Inventado	1983
Inventado por	Anselmo Blumer; Janet Blumer; Andrzej Ehrenfeucht ; David Haussler ; Ross McConnell
Complejidad temporal en notación O grande Operación Promedio Peor de los casos Complejidad espacial Espacio ${\displaystyle O(n)}$ ${\displaystyle O(n)}$

En informática , un autómata de sufijo es una estructura de datos eficiente para representar el índice de subcadena de una cadena dada que permite el almacenamiento, procesamiento y recuperación de información comprimida sobre todas sus subcadenas . El autómata de sufijo de una cadena es el grafo acíclico dirigido más pequeño con un vértice inicial dedicado y un conjunto de vértices "finales", de modo que las rutas desde el vértice inicial hasta los vértices finales representan los sufijos de la cadena.${\estilo de visualización S}$

En términos de la teoría de autómatas , un autómata de sufijo es el autómata finito determinista parcial mínimo que reconoce el conjunto de sufijos de una cadena dada . El gráfico de estados de un autómata de sufijo se denomina gráfico de palabras acíclico dirigido (DAWG), un término que también se utiliza a veces para cualquier autómata de estado finito acíclico determinista . ${\displaystyle S=s_{1}s_{2}\puntos s_{n}}$

Los autómatas de sufijo fueron introducidos en 1983 por un grupo de científicos de la Universidad de Denver y la Universidad de Colorado en Boulder . Sugirieron un algoritmo en línea de tiempo lineal para su construcción y demostraron que el autómata de sufijo de una cadena con una longitud de al menos dos caracteres tiene como máximo estados y como máximo transiciones. Trabajos posteriores han demostrado una estrecha conexión entre los autómatas de sufijo y los árboles de sufijo , y han esbozado varias generalizaciones de los autómatas de sufijo, como el autómata de sufijo compactado obtenido por compresión de nodos con un único arco saliente.${\estilo de visualización S}$${\textstyle 2|S|-1}$${\textstyle 3|S|-4}$

Los autómatas de sufijo proporcionan soluciones eficientes a problemas como la búsqueda de subcadenas y el cálculo de la subcadena común más grande de dos o más cadenas.

El concepto de autómata de sufijo fue introducido en 1983 ^[1] por un grupo de científicos de la Universidad de Denver y la Universidad de Colorado en Boulder formado por Anselm Blumer, Janet Blumer, Andrzej Ehrenfeucht , David Haussler y Ross McConnell, aunque conceptos similares se habían estudiado anteriormente junto con árboles de sufijos en los trabajos de Peter Weiner, ^[2] Vaughan Pratt ^[3] y Anatol Slissenko . ^[4] En su trabajo inicial, Blumer et al . mostraron un autómata de sufijo construido para la cadena de longitud mayor que tiene en la mayoría de los estados y en la mayoría de las transiciones, y sugirieron un algoritmo lineal para la construcción de autómatas. ^[5]${\estilo de visualización S}$${\estilo de visualización 1}$${\displaystyle 2|S|-1}$${\displaystyle 3|S|-4}$

En 1983, Mu-Tian Chen y Joel Seiferas demostraron de forma independiente que el algoritmo de construcción de árboles de sufijos de Weiner de 1973 ^[2], al construir un árbol de sufijos de la cadena, construye un autómata de sufijos de la cadena invertida como estructura auxiliar. ^[6] En 1987, Blumer et al . aplicaron la técnica de compresión utilizada en árboles de sufijos a un autómata de sufijos e inventaron el autómata de sufijos compactado, que también se denomina gráfico de palabras acíclico dirigido compactado (CDAWG). ^[7] En 1997, Maxime Crochemore y Renaud Vérin desarrollaron un algoritmo lineal para la construcción directa de CDAWG. ^[1] En 2001, Shunsuke Inenaga et al . desarrollaron un algoritmo para la construcción de CDAWG para un conjunto de palabras dado por un trie . ^[8]${\estilo de visualización S}$${\textstyle S^{R}}$

Generalmente, cuando se habla de autómatas sufijos y conceptos relacionados, se utilizan algunas nociones de la teoría del lenguaje formal y de la teoría de autómatas , en particular: ^[9]

• El "alfabeto" es un conjunto finito que se utiliza para construir palabras. Sus elementos se denominan "caracteres";${\estilo de visualización \Sigma}$
• "Palabra" es una secuencia finita de caracteres . La "longitud" de la palabra se denota como ;${\displaystyle \omega =\omega _{1}\omega _{2}\puntos \omega _{n}}$${\estilo de visualización \omega}$${\displaystyle |\omega |=n}$
• " Lenguaje formal " es un conjunto de palabras sobre un alfabeto determinado;
• "El lenguaje de todas las palabras" se denota con el carácter (donde el carácter "*" representa la estrella de Kleene ), "palabra vacía" (la palabra de longitud cero) se denota con el carácter ;${\displaystyle \Sigma ^{*}}$${\displaystyle \varepsilon }$
• " Concatenación de palabras" y se denota como o y corresponde a la palabra que se obtiene al escribir a la derecha de , es decir, ;${\displaystyle \alpha =\alpha _{1}\alpha _{2}\dots \alpha _{n}}$${\displaystyle \beta =\beta _{1}\beta _{2}\dots \beta _{m}}$${\displaystyle \alpha \cdot \beta }$${\displaystyle \alpha \beta }$${\displaystyle \beta }$${\displaystyle \alpha }$${\displaystyle \alpha \beta =\alpha _{1}\alpha _{2}\dots \alpha _{n}\beta _{1}\beta _{2}\dots \beta _{m}}$
• "Concatenación de idiomas" y se denota como o y corresponde al conjunto de concatenaciones por pares ;${\displaystyle A}$${\displaystyle B}$${\displaystyle A\cdot B}$${\displaystyle AB}$${\displaystyle AB=\{\alpha \beta :\alpha \in A,\beta \in B\}}$
• Si la palabra puede representarse como , donde , entonces las palabras , y se denominan "prefijo", "sufijo" y " subpalabra " (subcadena) de la palabra correspondientemente;${\displaystyle \omega \in \Sigma ^{*}}$${\displaystyle \omega =\alpha \gamma \beta }$${\displaystyle \alpha ,\beta ,\gamma \in \Sigma ^{*}}$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle \gamma }$${\displaystyle \omega }$
• Si y (con ) entonces se dice que "ocurre" en como subpalabra. Aquí y se denominan posiciones izquierda y derecha de ocurrencia de en correspondientemente.${\displaystyle T=T_{1}\dots T_{n}}$${\displaystyle T_{l}T_{l+1}\dots T_{r}=S}$${\displaystyle 1\leq l\leq r\leq n}$${\displaystyle S}$${\displaystyle T}$${\displaystyle l}$${\displaystyle r}$${\displaystyle S}$${\displaystyle T}$

Formalmente, el autómata finito determinista está determinado por 5-tuplas , donde: ^[10]${\displaystyle {\mathcal {A}}=(\Sigma ,Q,q_{0},F,\delta )}$

• ${\displaystyle \Sigma }$es un "alfabeto" que se utiliza para construir palabras,
• ${\displaystyle Q}$es un conjunto de " estados " del autómata,
• ${\displaystyle q_{0}\in Q}$es un estado "inicial" del autómata,
• ${\displaystyle F\subset Q}$es un conjunto de estados "finales" del autómata,
• ${\displaystyle \delta :Q\times \Sigma \mapsto Q}$es una función de "transición" parcial del autómata, de modo que para y no está definido o define una transición desde sobre el carácter .${\displaystyle \delta (q,\sigma )}$${\displaystyle q\in Q}$${\displaystyle \sigma \in \Sigma }$${\displaystyle q}$${\displaystyle \sigma }$

Lo más común es que el autómata finito determinista se represente como un gráfico dirigido ("diagrama") tal que: ^[10]

• El conjunto de vértices del gráfico corresponde al estado de estados ,${\displaystyle Q}$
• El gráfico tiene un vértice marcado específico correspondiente al estado inicial ,${\displaystyle q_{0}}$
• El gráfico tiene varios vértices marcados correspondientes al conjunto de estados finales ,${\displaystyle F}$
• El conjunto de arcos del gráfico corresponde al conjunto de transiciones ,${\displaystyle \delta }$
• En concreto, cada transición se representa mediante un arco que va desde hasta marcado con el carácter . Esta transición también puede denotarse como .${\textstyle \delta (q_{1},\sigma )=q_{2}}$${\displaystyle q_{1}}$${\displaystyle q_{2}}$${\displaystyle \sigma }$${\textstyle q_{1}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}q_{2}}$

En términos de su diagrama, el autómata reconoce la palabra sólo si existe un camino desde el vértice inicial hasta algún vértice final tal que la concatenación de caracteres en este camino forme . El conjunto de palabras reconocidas por un autómata forma un lenguaje que está configurado para ser reconocido por el autómata. En estos términos, el lenguaje reconocido por un autómata de sufijo es el lenguaje de sus sufijos (posiblemente vacíos). ^[9]${\displaystyle \omega =\omega _{1}\omega _{2}\dots \omega _{m}}$${\displaystyle q_{0}}$${\displaystyle q\in F}$${\displaystyle \omega }$${\displaystyle S}$

El "contexto correcto" de la palabra con respecto al lenguaje es un conjunto que es un conjunto de palabras tales que su concatenación con forma una palabra de . Los contextos correctos inducen una relación de equivalencia natural en el conjunto de todas las palabras. Si el lenguaje es reconocido por algún autómata finito determinista, existe un autómata único hasta el isomorfismo que reconoce el mismo lenguaje y tiene el mínimo número posible de estados. Tal autómata se llama autómata mínimo para el lenguaje dado . El teorema de Myhill-Nerode permite definirlo explícitamente en términos de contextos correctos: ^{[11] [12]}${\displaystyle \omega }$${\displaystyle L}$${\displaystyle [\omega ]_{R}=\{\alpha :\omega \alpha \in L\}}$${\displaystyle \alpha }$${\displaystyle \omega }$${\displaystyle L}$ ${\displaystyle [\alpha ]_{R}=[\beta ]_{R}}$${\displaystyle L}$${\displaystyle L}$

En estos términos, un "autómata de sufijos" es el autómata finito determinista mínimo que reconoce el lenguaje de los sufijos de la palabra . El contexto correcto de la palabra con respecto a este lenguaje está formado por palabras , tales que es un sufijo de . Esto permite formular el siguiente lema que define una biyección entre el contexto correcto de la palabra y el conjunto de posiciones correctas de sus ocurrencias en : ^{[13] [14]}${\displaystyle S=s_{1}s_{2}\dots s_{n}}$${\displaystyle \omega }$${\displaystyle \alpha }$${\displaystyle \omega \alpha }$${\displaystyle S}$${\displaystyle S}$

Por ejemplo, para la palabra y su subpalabra , se cumple y . De manera informal, se forma con palabras que siguen a las ocurrencias de hasta el final de y se forma con las posiciones correctas de esas ocurrencias. En este ejemplo, el elemento se corresponde con la palabra mientras que la palabra se corresponde con el elemento .${\displaystyle S=abacaba}$${\displaystyle \omega =ab}$${\displaystyle endpos(ab)=\{2,6\}}$${\displaystyle [ab]_{R}=\{a,acaba\}}$${\displaystyle [ab]_{R}}$${\displaystyle ab}$${\displaystyle S}$${\displaystyle endpos(ab)}$${\displaystyle 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}}$${\displaystyle 7-|a|=6\in endpos(ab)}$

Esto implica varias propiedades estructurales de los estados del autómata sufijo. Sea , entonces: ^[14]${\displaystyle |\alpha |\leq |\beta |}$

• Si y tienen al menos un elemento común , entonces y también tienen un elemento común. Esto implica que es un sufijo de y por lo tanto y . En el ejemplo mencionado anteriormente, , entonces es un sufijo de y por lo tanto y ;${\displaystyle [\alpha ]_{R}}$${\displaystyle [\beta ]_{R}}$${\displaystyle x}$${\displaystyle endpos(\alpha )}$${\displaystyle endpos(\beta )}$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle endpos(\beta )\subset endpos(\alpha )}$${\displaystyle [\beta ]_{R}\subset [\alpha ]_{R}}$${\displaystyle a\in [ab]_{R}\cap [cab]_{R}}$${\displaystyle ab}$${\displaystyle cab}$${\displaystyle [cab]_{R}=\{a\}\subset \{a,acaba\}=[ab]_{R}}$${\displaystyle endpos(cab)=\{6\}\subset \{2,6\}=endpos(ab)}$
• Si , entonces , por lo tanto, aparece en sólo como sufijo de . Por ejemplo, para y se cumple que y ;${\displaystyle [\alpha ]_{R}=[\beta ]_{R}}$${\displaystyle endpos(\alpha )=endpos(\beta )}$${\displaystyle \alpha }$${\displaystyle S}$${\displaystyle \beta }$${\displaystyle \alpha =b}$${\displaystyle \beta =ab}$${\displaystyle [b]_{R}=[ab]_{R}=\{a,acaba\}}$${\displaystyle endpos(b)=endpos(ab)=\{2,6\}}$
• Si y es un sufijo de tal que , entonces . En el ejemplo anterior y se cumple para el sufijo "intermedio" que .${\displaystyle [\alpha ]_{R}=[\beta ]_{R}}$${\displaystyle \gamma }$${\displaystyle \beta }$${\displaystyle |\alpha |\leq |\gamma |\leq |\beta |}$${\displaystyle [\alpha ]_{R}=[\gamma ]_{R}=[\beta ]_{R}}$${\displaystyle [c]_{R}=[bac]_{R}=\{aba\}}$${\displaystyle \gamma =ac}$${\displaystyle [ac]_{R}=\{aba\}}$

Cualquier estado del autómata de sufijos reconoce una cadena continua de sufijos anidados de la palabra más larga reconocida por este estado. ^[14]${\displaystyle q=[\alpha ]_{R}}$

La "extensión izquierda" de la cadena es la cadena más larga que tiene el mismo contexto derecho que . La longitud de la cadena más larga reconocida por se denota por . Se cumple: ^[15]${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\gamma }}}$${\displaystyle \gamma }$${\displaystyle \omega }$${\displaystyle \gamma }$${\displaystyle |{\overset {\scriptstyle {\leftarrow }}{\gamma }}|}$${\displaystyle q=[\gamma ]_{R}}$${\displaystyle len(q)}$

El "enlace de sufijo" del estado es el puntero al estado que contiene el sufijo más grande que no es reconocido por .${\displaystyle link(q)}$${\displaystyle q=[\alpha ]_{R}}$${\displaystyle p}$${\displaystyle \alpha }$${\displaystyle q}$

En estos términos se puede decir que reconoce exactamente todos los sufijos de que son más largos que y no más largos que . También se cumple: ^[15]${\displaystyle q=[\alpha ]_{R}}$${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\alpha }}}$${\displaystyle len(link(q))}$${\displaystyle len(q)}$

Un " árbol de prefijos " (o "trie") es un árbol dirigido con raíz en el que los arcos están marcados por caracteres de tal manera que ningún vértice de dicho árbol tiene dos arcos salientes marcados con el mismo carácter. Algunos vértices en trie están marcados como finales. Se dice que Trie reconoce un conjunto de palabras definidas por caminos desde su raíz hasta los vértices finales. De esta manera, los árboles de prefijos son un tipo especial de autómatas finitos deterministas si percibe su raíz como un vértice inicial. ^[16] El "trie de sufijos" de la palabra es un árbol de prefijos que reconoce un conjunto de sus sufijos. "Un árbol de sufijos " es un árbol obtenido a partir de un trie de sufijos mediante el procedimiento de compactación, durante el cual se fusionan los bordes consecuentes si el grado del vértice entre ellos es igual a dos. ^[15]${\displaystyle v}$${\displaystyle S}$

Por definición, un autómata de sufijo puede obtenerse mediante la minimización del trie de sufijo. Puede demostrarse que un autómata de sufijo compactado se obtiene mediante la minimización del árbol de sufijo (si se supone que cada cadena en el borde del árbol de sufijo es un carácter sólido del alfabeto) y la compactación del autómata de sufijo. ^[17] Además de esta conexión entre el árbol de sufijo y el autómata de sufijo de la misma cadena, también existe una conexión entre el autómata de sufijo de la cadena y el árbol de sufijo de la cadena invertida . ^[18]${\displaystyle S=s_{1}s_{2}\dots s_{n}}$${\displaystyle S^{R}=s_{n}s_{n-1}\dots s_{1}}$

De manera similar a los contextos derechos, se pueden introducir "contextos izquierdos" , "extensiones derechas" correspondientes a la cadena más larga que tenga el mismo contexto izquierdo que y la relación de equivalencia . Si se consideran las extensiones derechas con respecto al lenguaje de los "prefijos" de la cadena, se puede obtener: ^[15]${\displaystyle [\omega ]_{L}=\{\beta \in \Sigma ^{*}:\beta \omega \in L\}}$${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\omega ~}}}$${\displaystyle \omega }$${\displaystyle [\alpha ]_{L}=[\beta ]_{L}}$${\displaystyle L}$${\displaystyle S}$

, lo que implica que el árbol de enlace de sufijos de la cadena y el árbol de sufijos de la cadena son isomorfos: ^[18]${\displaystyle S}$${\displaystyle S^{R}}$

De manera similar al caso de las extensiones izquierdas, el siguiente lema se aplica a las extensiones derechas: ^[15]

Un autómata sufijo de la cadena de longitud tiene como máximo estados y como máximo transiciones. Estos límites se alcanzan en las cadenas y correspondientemente. ^[13] Esto se puede formular de una manera más estricta como donde y son los números de transiciones y estados en el autómata correspondientemente. ^[14]${\displaystyle S}$${\displaystyle n>1}$${\displaystyle 2n-1}$${\displaystyle 3n-4}$${\displaystyle abb\dots bb=ab^{n-1}}$${\displaystyle abb\dots bc=ab^{n-2}c}$${\displaystyle |\delta |\leq |Q|+n-2}$${\displaystyle |\delta |}$${\displaystyle |Q|}$

Inicialmente el autómata sólo consta de un único estado correspondiente a la palabra vacía, luego se van añadiendo los caracteres de la cadena uno a uno y el autómata se reconstruye en cada paso de forma incremental. ^[19]

Después de que se añade un nuevo carácter a la cadena, se modifican algunas clases de equivalencia. Sea el contexto correcto de con respecto al lenguaje de los sufijos. Entonces, la transición de a después de que se añade a se define mediante el lema: ^[14]${\displaystyle [\alpha ]_{R_{\omega }}}$${\displaystyle \alpha }$${\displaystyle \omega }$${\displaystyle [\alpha ]_{R_{\omega }}}$${\displaystyle [\alpha ]_{R_{\omega x}}}$${\displaystyle x}$${\displaystyle \omega }$

Después de añadir a la palabra actual el contexto correcto de puede cambiar significativamente solo si es un sufijo de . Esto implica que la relación de equivalencia es un refinamiento de . En otras palabras, si , entonces . Después de la adición de un nuevo carácter , se dividirán como máximo dos clases de equivalencia de y cada una de ellas puede dividirse como máximo en dos nuevas clases. Primero, la clase de equivalencia correspondiente al contexto correcto vacío siempre se divide en dos clases de equivalencia, una de ellas correspondiente a sí misma y que tiene como contexto correcto. Esta nueva clase de equivalencia contiene exactamente y todos sus sufijos que no ocurrieron en , ya que el contexto correcto de tales palabras estaba vacío antes y ahora solo contiene palabras vacías. ^[14]${\displaystyle x}$${\displaystyle \omega }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \omega x}$${\displaystyle \equiv _{R_{\omega x}}}$${\displaystyle \equiv _{R_{\omega }}}$${\displaystyle [\alpha ]_{R_{\omega x}}=[\beta ]_{R_{\omega x}}}$${\displaystyle [\alpha ]_{R_{\omega }}=[\beta ]_{R_{\omega }}}$${\displaystyle \equiv _{R_{\omega }}}$${\displaystyle \omega x}$${\displaystyle \{\varepsilon \}}$${\displaystyle \omega x}$${\displaystyle \omega }$

Dada la correspondencia entre los estados del autómata de sufijos y los vértices del árbol de sufijos, es posible averiguar el segundo estado que puede dividirse después de que se añada un nuevo carácter. La transición de a corresponde a la transición de a en la cadena invertida. En términos de árboles de sufijos, corresponde a la inserción del nuevo sufijo más largo en el árbol de sufijos de . Como máximo, se pueden formar dos nuevos vértices después de esta inserción: uno de ellos correspondiente a , mientras que el otro corresponde a su antecesor directo si hubo una ramificación. Volviendo a los autómatas de sufijos, significa que el primer nuevo estado reconoce y el segundo (si hay un segundo nuevo estado) es su enlace de sufijo. Puede enunciarse como un lema: ^[14]${\displaystyle \omega }$${\displaystyle \omega x}$${\displaystyle \omega ^{R}}$${\displaystyle x\omega ^{R}}$${\displaystyle x\omega ^{R}}$${\displaystyle \omega ^{R}}$${\displaystyle x\omega ^{R}}$${\displaystyle \omega x}$

Esto implica que si (por ejemplo, cuando no ocurrió en absoluto y ), entonces solo se divide la clase de equivalencia correspondiente al contexto derecho vacío. ^[14]${\displaystyle \alpha =\beta }$${\displaystyle x}$${\displaystyle \omega }$${\displaystyle \alpha =\beta =\varepsilon }$

Además de los enlaces de sufijos, también es necesario definir estados finales del autómata. De las propiedades de estructura se deduce que todos los sufijos de una palabra reconocidos por son reconocidos por algún vértice en la ruta de sufijos de . Es decir, los sufijos con una longitud mayor que se encuentran en , los sufijos con una longitud mayor que pero no mayor que se encuentran en , y así sucesivamente. Por lo tanto, si el estado que reconoce se denota por , entonces todos los estados finales (es decir, los sufijos que reconocen de ) forman la secuencia . ^[19]${\displaystyle \alpha }$${\displaystyle q=[\alpha ]_{R}}$ ${\displaystyle (q,link(q),link^{2}(q),\dots )}$${\displaystyle q}$${\displaystyle len(link(q))}$${\displaystyle q}$${\displaystyle len(link(link(q))}$${\displaystyle len(link(q))}$${\displaystyle link(q)}$${\displaystyle \omega }$${\displaystyle last}$${\displaystyle \omega }$${\displaystyle (last,link(last),link^{2}(last),\dots )}$

Después de que el carácter se añade a los posibles nuevos estados del autómata de sufijo son y . El enlace de sufijo de va a y de va a . Las palabras de aparecen en solo como sus sufijos, por lo tanto, no debería haber transiciones en absoluto desde mientras que las transiciones a deben ir desde sufijos de que tengan una longitud de al menos y estar marcadas con el carácter . El estado está formado por un subconjunto de , por lo tanto, las transiciones de deben ser las mismas que las de . Mientras tanto, las transiciones que conducen a deben ir desde sufijos de que tengan una longitud menor que y al menos , ya que dichas transiciones han conducido a antes y correspondieron a una parte separada de este estado. Los estados correspondientes a estos sufijos se pueden determinar mediante el recorrido de la ruta de enlace de sufijo para . ^[19]${\displaystyle x}$${\displaystyle \omega }$${\displaystyle [\omega x]_{R_{\omega x}}}$${\displaystyle [\alpha ]_{R_{\omega x}}}$${\displaystyle [\omega x]_{R_{\omega x}}}$${\displaystyle [\alpha ]_{R_{\omega x}}}$${\displaystyle [\alpha ]_{R_{\omega x}}}$${\displaystyle link([\alpha ]_{R_{\omega }})}$${\displaystyle [\omega x]_{R_{\omega x}}}$${\displaystyle \omega x}$${\displaystyle [\omega x]_{R_{\omega x}}}$${\displaystyle \omega }$${\displaystyle \alpha }$${\displaystyle x}$${\displaystyle [\alpha ]_{R_{\omega x}}}$${\displaystyle [\alpha ]_{R_{\omega }}}$${\displaystyle [\alpha ]_{R_{\omega x}}}$${\displaystyle [\alpha ]_{R_{\omega }}}$${\displaystyle [\alpha ]_{R_{\omega x}}}$${\displaystyle \omega }$${\displaystyle |\alpha |}$${\displaystyle len(link([\alpha ]_{R_{\omega }}))}$${\displaystyle [\alpha ]_{R_{\omega }}}$${\displaystyle [\omega ]_{R_{\omega }}}$

Construcción del autómata sufijo para la palabra abbcbc
∅ → un Después de agregar el primer carácter, solo se crea un estado en el autómata de sufijo. De manera similar, solo se agrega una hoja al árbol de sufijos.	a → ab Se extraen nuevas transiciones de todos los estados finales anteriores, ya que b no aparecía antes. Por la misma razón se añade otra hoja a la raíz del sufijo árbol.
ab → abb El estado 2 reconoce las palabras ab y b , pero solo b es el nuevo sufijo, por lo tanto, esta palabra se separa en el estado 4. En el árbol de sufijos corresponde a la división de la arista que conduce al vértice 2.	abb → abbc El carácter c aparece por primera vez, por lo que las transiciones se extraen de todos los estados finales anteriores. El árbol de sufijos de la cadena inversa tiene otra hoja agregada a la raíz.
abbc → abbcb El estado 4 consta de la única palabra b , que es sufijo, por lo tanto el estado no está dividido. En consecuencia, la nueva hoja se cuelga en el vértice 4 del árbol de sufijos.	abbcb → abbcbc El estado 5 reconoce las palabras abbc , bbc , bc y c , pero solo las dos últimas son sufijos de la nueva palabra, por lo que se separan en el nuevo estado 8. En consecuencia, la arista que conduce al vértice 5 se divide y el vértice 8 se coloca en el medio de la arista.

Los resultados teóricos anteriores conducen al siguiente algoritmo que toma el carácter y reconstruye el autómata de sufijo de en el autómata de sufijo de : ^[19]${\displaystyle x}$${\displaystyle \omega }$${\displaystyle \omega x}$

1. El estado correspondiente a la palabra se mantiene como ;${\displaystyle \omega }$${\displaystyle last}$
2. Después de agregarlo, el valor anterior de se almacena en la variable y se reasigna al nuevo estado correspondiente a ;${\displaystyle x}$${\displaystyle last}$${\displaystyle p}$${\displaystyle last}$${\displaystyle \omega x}$
3. Los estados correspondientes a los sufijos de se actualizan con transiciones a . Para ello se debe recorrer , hasta que exista un estado que ya tenga una transición de ;${\displaystyle \omega }$${\displaystyle last}$${\displaystyle p,link(p),link^{2}(p),\dots }$${\displaystyle x}$
4. Una vez finalizado el bucle mencionado anteriormente, se dan 3 casos:
   1. Si ninguno de los estados en la ruta del sufijo tuvo una transición por , entonces nunca ocurrió en antes y el enlace del sufijo de debe conducir a ;${\displaystyle x}$${\displaystyle x}$${\displaystyle \omega }$${\displaystyle last}$${\displaystyle q_{0}}$
   2. Si se encuentra la transición por y conduce del estado al estado , tal que , entonces no tiene que dividirse y es un enlace de sufijo de ;${\displaystyle x}$${\displaystyle p}$${\displaystyle q}$${\displaystyle len(p)+1=len(q)}$${\displaystyle q}$${\displaystyle last}$
   3. Si se encuentra la transición pero , entonces las palabras que tienen una longitud máxima deben segregarse en un nuevo estado "clon" ;${\displaystyle len(q)>len(p)+1}$${\displaystyle q}$${\displaystyle len(p)+1}$${\displaystyle cl}$
5. Si el paso anterior concluyó con la creación de , las transiciones de éste y su sufijo enlace deben copiar las de , al mismo tiempo se asigna como enlace de sufijo común de ambos y ;${\displaystyle cl}$${\displaystyle q}$${\displaystyle cl}$${\displaystyle q}$${\displaystyle last}$
6. Las transiciones que han llevado a antes pero que corresponden a palabras de longitud máxima se redirigen a . Para ello, se continúa recorriendo la ruta del sufijo de hasta que se encuentre el estado tal que la transición de desde no lleve a .${\displaystyle q}$${\displaystyle len(p)+1}$${\displaystyle cl}$${\displaystyle p}$${\displaystyle x}$${\displaystyle q}$

Todo el procedimiento se describe mediante el siguiente pseudocódigo: ^[19]

función  add_letter(x) : define  p = last  asigna  last = new_state()  asigna  len(last) = len(p) + 1  mientras  δ(p, x) no está definido: asigna  δ(p, x) = last, p = link(p)  define  q = δ(p, x)  si  q = last : asigna  link(last) = q 0  de lo contrario si  len(q) = len(p) + 1 : asigna  link(last) = q  de lo contrario : define  cl = new_state()  asigna  len(cl) = len(p) + 1  asigna  δ(cl) = δ(q), link(cl) = link(q)  asigna  link(last) = link(q) = cl  mientras  δ(p, x) = q : asigna  δ(p, x) = cl, p = link(p)

Aquí se encuentra el estado inicial del autómata y es una función que crea un nuevo estado para él. Se supone que , , y se almacenan como variables globales. ^[19]${\displaystyle q_{0}}$${\displaystyle new\_state()}$${\displaystyle last}$${\displaystyle len}$${\displaystyle link}$${\displaystyle \delta }$

La complejidad del algoritmo puede variar dependiendo de la estructura subyacente utilizada para almacenar las transiciones del autómata. Puede implementarse en con sobrecarga de memoria o en con sobrecarga de memoria si se supone que la asignación de memoria se realiza en . Para obtener dicha complejidad, uno tiene que utilizar los métodos de análisis amortizado . El valor de se reduce estrictamente con cada iteración del ciclo, mientras que solo puede aumentar hasta en uno después de la primera iteración del ciclo en la siguiente llamada add_letter . El valor general de nunca excede y solo aumenta en uno entre iteraciones de adición de nuevas letras que sugieren que la complejidad total también es lineal como máximo. La linealidad del segundo ciclo se muestra de manera similar. ^[19]${\displaystyle O(n\log |\Sigma |)}$${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle O(n|\Sigma |)}$${\displaystyle O(1)}$${\displaystyle len(p)}$${\displaystyle len(p)}$${\displaystyle n}$

El autómata de sufijo está estrechamente relacionado con otras estructuras de sufijo e índices de subcadenas . Dado un autómata de sufijo de una cadena específica, se puede construir su árbol de sufijos mediante compactación y recorrido recursivo en tiempo lineal. ^[20] Se pueden realizar transformaciones similares en ambas direcciones para cambiar entre el autómata de sufijo de y el árbol de sufijo de cadena invertida . ^[18] Además de esto, se desarrollaron varias generalizaciones para construir un autómata para el conjunto de cadenas dado por trie, ^[8] automatización de sufijo compactada (CDAWG), ^[7] para mantener la estructura del autómata en la ventana deslizante, ^[21] y para construirlo de manera bidireccional, admitiendo la inserción de caracteres tanto al principio como al final de la cadena. ^[22]${\displaystyle S}$${\displaystyle S^{R}}$

Como ya se mencionó anteriormente, un autómata de sufijo compactado se obtiene mediante la compactación de un autómata de sufijo regular (eliminando estados que no son finales y tienen exactamente un arco saliente) y la minimización de un árbol de sufijos. De manera similar al autómata de sufijo regular, los estados del autómata de sufijo compactado se pueden definir de manera explícita. Una extensión bidireccional de una palabra es la palabra más larga , de modo que cada ocurrencia de en es precedida y sucedida por . En términos de extensiones izquierda y derecha significa que la extensión bidireccional es la extensión izquierda de la extensión derecha o, lo que es equivalente, la extensión derecha de la extensión izquierda, es decir . En términos de extensiones bidireccionales, el autómata compactado se define de la siguiente manera: ^[15]${\displaystyle {\overset {\scriptstyle {\longleftrightarrow }}{\gamma }}}$${\displaystyle \gamma }$${\displaystyle \omega =\beta \gamma \alpha }$${\displaystyle \gamma }$${\displaystyle S}$${\displaystyle \beta }$${\displaystyle \alpha }$${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\gamma }}={\overset {\scriptstyle \leftarrow }{\overset {\rightarrow }{\gamma }}}={\overset {\rightarrow }{\overset {\scriptstyle \leftarrow }{\gamma }}}}$

Las extensiones bidireccionales inducen una relación de equivalencia que define el conjunto de palabras reconocidas por el mismo estado del autómata compactado. Esta relación de equivalencia es un cierre transitivo de la relación definida por , que resalta el hecho de que un autómata compactado puede obtenerse tanto pegando vértices de árboles de sufijos equivalentes mediante una relación (minimización del árbol de sufijos) como pegando estados de autómatas de sufijos equivalentes mediante una relación (compactación del autómata de sufijo). ^[23] Si las palabras y tienen las mismas extensiones derechas, y las palabras y tienen las mismas extensiones izquierdas, entonces, acumulativamente, todas las cadenas , y tienen las mismas extensiones bidireccionales. Al mismo tiempo, puede suceder que ni las extensiones izquierda ni derecha de y coincidan. Como ejemplo, se puede tomar , y , para las cuales las extensiones izquierda y derecha son las siguientes: , pero y . Dicho esto, mientras que las relaciones de equivalencia de extensiones unidireccionales se formaron mediante alguna cadena continua de prefijos o sufijos anidados, las relaciones de equivalencia de extensiones bidireccionales son más complejas y lo único que se puede concluir con seguridad es que las cadenas con la misma extensión bidireccional son subcadenas de la cadena más larga que tiene la misma extensión bidireccional, pero incluso puede suceder que no tengan ninguna subcadena no vacía en común. El número total de clases de equivalencia para esta relación no excede lo que implica que el autómata de sufijo compactado de la cadena que tiene longitud tiene como máximo estados. La cantidad de transiciones en dicho autómata es como máximo . ^[15]${\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 }})}$${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\alpha }}={\overset {\scriptstyle {\leftarrow }}{\beta }}}$${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}}$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle \beta }$${\displaystyle \gamma }$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle \gamma }$${\displaystyle \alpha }$${\displaystyle \gamma }$${\displaystyle S=\beta =ab}$${\displaystyle \alpha =a}$${\displaystyle \gamma =b}$${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}=ab={\overset {\scriptstyle {\leftarrow }}{\beta }}={\overset {\scriptstyle {\leftarrow }}{\gamma }}}$${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\gamma \,}}=b}$${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\alpha }}=a}$${\displaystyle n+1}$${\displaystyle n}$${\displaystyle n+1}$${\displaystyle 2n-2}$

Consideremos un conjunto de palabras . Es posible construir una generalización de un autómata de sufijos que reconocería el lenguaje formado por los sufijos de todas las palabras del conjunto. Las restricciones para el número de estados y transiciones en dicho autómata permanecerían iguales que para un autómata de una sola palabra si ponemos . ^[23] El algoritmo es similar a la construcción de un autómata de una sola palabra excepto que en lugar del estado, la función add_letter trabajaría con el estado correspondiente a la palabra asumiendo la transición del conjunto de palabras al conjunto . ^{[24] [25]}${\displaystyle T=\{S_{1},S_{2},\dots ,S_{k}\}}$${\displaystyle n=|S_{1}|+|S_{2}|+\dots +|S_{k}|}$${\displaystyle last}$${\displaystyle \omega _{i}}$${\displaystyle \{\omega _{1},\dots ,\omega _{i},\dots ,\omega _{k}\}}$${\displaystyle \{\omega _{1},\dots ,\omega _{i}x,\dots ,\omega _{k}\}}$

Esta idea se generaliza aún más al caso en el que no se da explícitamente sino que se da mediante un árbol de prefijos con vértices. Mohri et al . demostraron que un autómata de este tipo tendría como máximo y puede construirse en tiempo lineal a partir de su tamaño. Al mismo tiempo, el número de transiciones en dicho autómata puede alcanzar , por ejemplo, para el conjunto de palabras sobre el alfabeto, la longitud total de las palabras es igual a , el número de vértices en el trie de sufijo correspondiente es igual a y el autómata de sufijo correspondiente está formado por estados y transiciones. El algoritmo sugerido por Mohri repite principalmente el algoritmo genérico para construir un autómata de varias cadenas, pero en lugar de hacer crecer las palabras una por una, recorre el trie en un orden de búsqueda en amplitud y agrega nuevos caracteres a medida que los encuentra en el recorrido, lo que garantiza una complejidad lineal amortizada. ^[26]${\displaystyle T}$${\displaystyle Q}$${\displaystyle 2Q-2}$${\displaystyle O(Q|\Sigma |)}$${\displaystyle 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)}$${\displaystyle O(n+k)}$${\displaystyle O(n+k)}$${\displaystyle O(nk)}$

Algunos algoritmos de compresión , como LZ77 y RLE, pueden beneficiarse de almacenar un autómata de sufijo o una estructura similar no para toda la cadena sino solo para los últimos caracteres mientras se actualiza la cadena. Esto se debe a que la compresión de datos suele ser expresivamente grande y el uso de memoria no es deseable. En 1985, Janet Blumer desarrolló un algoritmo para mantener un autómata de sufijo en una ventana deslizante de tamaño en el peor de los casos y en promedio, asumiendo que los caracteres se distribuyen de forma independiente y uniforme . También demostró que la complejidad no se puede mejorar: si se consideran palabras construidas como una concatenación de varias palabras, donde , entonces el número de estados para la ventana de tamaño cambiaría con frecuencia con saltos de orden , lo que hace imposible incluso la mejora teórica de para autómatas de sufijo regulares. ^[27]${\displaystyle k}$${\displaystyle O(n)}$${\displaystyle k}$${\displaystyle O(nk)}$${\displaystyle O(n\log k)}$${\displaystyle O(nk)}$${\displaystyle (ab)^{m}c(ab)^{m}d}$${\displaystyle k=6m+2}$${\displaystyle k}$${\displaystyle m}$${\displaystyle O(nk)}$

Lo mismo debería ser cierto para el árbol de sufijos porque sus vértices corresponden a estados del autómata de sufijos de la cadena invertida, pero este problema puede resolverse al no almacenar explícitamente cada vértice correspondiente al sufijo de toda la cadena, almacenando así solo los vértices con al menos dos aristas salientes. En 1989, Edward Fiala y Daniel Greene sugirieron una variación del algoritmo de construcción de árboles de sufijos de McCreight para esta tarea; ^[28] varios años después, Jesper Larsson obtuvo un resultado similar con la variación del algoritmo de Ukkonen . ^{[29] [30]} La existencia de un algoritmo de este tipo, para un autómata de sufijos compactado que absorba algunas propiedades tanto de los árboles de sufijos como de los autómatas de sufijos, fue una cuestión abierta durante mucho tiempo hasta que Martin Senft y Tomasz Dvorak descubrieron en 2008 que es imposible si el tamaño del alfabeto es al menos dos. ^[31]

Una forma de superar este obstáculo es permitir que el ancho de la ventana varíe un poco mientras se mantiene . Esto se puede lograr mediante un algoritmo aproximado sugerido por Inenaga et al. en 2004. No se garantiza que la ventana para la que se construye el autómata de sufijo en este algoritmo tenga una longitud, pero se garantiza que tenga al menos y como máximo, al tiempo que se proporciona una complejidad general lineal del algoritmo. ^[32]${\displaystyle O(k)}$${\displaystyle k}$${\displaystyle k}$${\displaystyle 2k+1}$

El autómata sufijo de la cadena se puede utilizar para resolver problemas como: ^{[33] [34]}${\displaystyle S}$

• Contando el número de subcadenas distintas de en línea,${\displaystyle S}$${\displaystyle O(|S|)}$
• Encontrar la subcadena más larga de que aparece al menos dos veces en ,${\displaystyle S}$${\displaystyle O(|S|)}$
• Encontrar la subcadena común más larga de y en ,${\displaystyle S}$${\displaystyle T}$${\displaystyle O(|T|)}$
• Contando el número de ocurrencias de en en ,${\displaystyle T}$${\displaystyle S}$${\displaystyle O(|T|)}$
• Encontrar todas las ocurrencias de en , donde es el número de ocurrencias.${\displaystyle T}$${\displaystyle S}$${\displaystyle O(|T|+k)}$${\displaystyle k}$

Se supone aquí que se da en la entrada después de que se construye el sufijo del autómata. ^[33]${\displaystyle T}$${\displaystyle S}$

Los autómatas de sufijo también se utilizan en la compresión de datos, ^[35] la recuperación de música ^{[36] [37]} y la coincidencia de secuencias del genoma. ^[38]

• Medios relacionados con Suffix autómata en Wikimedia Commons
• Artículo sobre autómatas sufijos en Algoritmos E-Maxx en inglés