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 sufijo autómata de una cuerdaes 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.
Autómata de sufijo | |||||||||
---|---|---|---|---|---|---|---|---|---|
Tipo | Índice de subcadena | ||||||||
Inventado | 1983 | ||||||||
Inventado por | Anselm Blumer; Janet Blumer; Andrzej Ehrenfeucht ; David Haussler ; Ross McConnell | ||||||||
Complejidad del tiempo en notación O grande | |||||||||
|
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 estado de un autómata de sufijo se denomina gráfico de palabra acíclico dirigido (DAWG), un término que a veces también se utiliza para cualquier autómata de estado finito acíclico determinista .
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 Boulder . Sugirieron un algoritmo de tiempo lineal en línea para su construcción y mostraron que el sufijo autómata de una cadena tener una longitud de al menos dos caracteres tiene como máximo estados y como máximo transiciones. Otros trabajos han mostrado una estrecha conexión entre autómatas de sufijos y árboles de sufijos , y han delineado varias generalizaciones de autómatas de sufijos, como el autómata de sufijos compactado obtenido por compresión de nodos con un solo arco saliente.
Los autómatas de sufijo brindan 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.
Historia
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 Boulder, formado por Anselm Blumer, Janet Blumer, Andrzej Ehrenfeucht , David Haussler y Ross McConnell, aunque se habían estudiado conceptos similares anteriormente. junto a árboles de sufijo en las obras de Peter Weiner, [2] Vaughan Pratt [3] y Anatol Slissenko . [4] En su trabajo inicial, Blumer et al . mostró un sufijo autómata construido para la cuerda de longitud mayor que tiene como máximo estados y como máximo transiciones, y sugirió un algoritmo lineal para la construcción de autómatas. [5]
En 1983, Mu-Tian Chen y Joel Seiferas demostraron de forma independiente que el algoritmo de construcción de árbol de sufijos de Weiner de 1973 [2] mientras construía un árbol de sufijos de la cadena construye un sufijo autómata de la cadena invertida como estructura auxiliar. [6] En 1987, Blumer et al . aplicó la técnica de compresión utilizada en árboles de sufijos a un autómata de sufijo e inventó el autómata de sufijo compactado, que también se denomina gráfico de palabra acíclica dirigida compactada (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 . desarrolló un algoritmo para la construcción de CDAWG para un conjunto de palabras dadas por un trie . [8]
Definiciones
Por lo general, cuando se habla de autómatas de sufijo y conceptos relacionados, se utilizan algunas nociones de la teoría del lenguaje formal y la teoría de autómatas , en particular: [9]
- "Alfabeto" es un conjunto finito que se usa para construir palabras. Sus elementos se denominan "personajes";
- "Palabra" es una secuencia finita de caracteres. "Longitud" de la palabra se denota como ;
- " Lenguaje formal " es un conjunto de palabras sobre un alfabeto dado;
- "El idioma de todas las palabras" se indica como (donde el carácter "*" representa la estrella de Kleene ), "palabra vacía" (la palabra de longitud cero) se indica mediante el carácter;
- " Concatenación de palabras" y se denota como o y corresponde a la palabra obtenida escribiendo a la derecha de , es decir, ;
- "Concatenación de idiomas" y se denota como o y corresponde al conjunto de concatenaciones por pares ;
- Si la palabra puede representarse como , dónde , luego palabras , y se denominan "prefijo", "sufijo" y " subpalabra " (subcadena) de la palabra correspondientemente;
- Si luego se dice que "ocurre" en como una subpalabra. Aquí y se llaman posiciones izquierda y derecha de ocurrencia de en correspondientemente.
Estructura de autómata
Formalmente, el autómata finito determinista está determinado por 5-tupla , donde: [10]
- es un "alfabeto" que se utiliza para construir palabras,
- es un conjunto de " estados " de autómatas ,
- es un estado "inicial" de autómata,
- es un conjunto de estados "finales" de autómata,
- es una función de "transición" parcial del autómata, tal que por y no está definido o define una transición de sobre el personaje .
Más comúnmente, el autómata finito determinista se representa como un gráfico dirigido ("diagrama") tal que: [10]
- El conjunto de vértices del gráfico corresponde al estado de los estados,
- El gráfico tiene un vértice marcado específico correspondiente al estado inicial ,
- El gráfico tiene varios vértices marcados que corresponden al conjunto de estados finales ,
- El conjunto de arcos del gráfico corresponde al conjunto de transiciones,
- Específicamente, cada transición está representado por un arco desde a marcado con el personaje . Esta transición también se puede denotar como.
En términos de su diagrama, el autómata reconoce la palabra solo si hay un camino desde el vértice inicial a algún vértice final tal que la concatenación de caracteres en este camino forma . 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 sufijo autómata dees el idioma de sus sufijos (posiblemente vacíos). [9]
Estados de autómata
"Contexto correcto" de la palabra con respecto al lenguaje es un conjunto eso es un conjunto de palabras tal 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 idiomaes reconocido por algún autómata finito determinista, existe un autómata único hasta 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 le permite definirlo explícitamente en términos de contextos correctos: [11] [12]
Teorema : autómata mínimo que reconoce el lenguaje sobre el alfabeto puede definirse explícitamente de la siguiente manera:
- Alfabeto Se mantiene igual,
- Estados corresponder a contextos correctos de todas las palabras posibles ,
- Estado inicial corresponde al contexto correcto de la palabra vacía ,
- Estados finales corresponder a contextos correctos de palabras de ,
- Transiciones son dadas por , dónde y .
En estos términos, un "autómata de sufijo" 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 idioma consta de palabras , tal que es un sufijo de . Permite formular el siguiente lema definiendo una biyección entre el contexto correcto de la palabra y el conjunto de posiciones correctas de sus ocurrencias en: [13] [14]
Teorema - Sea ser el conjunto de posiciones correctas de ocurrencias de en .
Hay una biyección siguiente entre y :
- Si , luego ;
- Si , luego .
Por ejemplo, para la palabra y su subpalabra , se mantiene y . Informalmente está formado por palabras que siguen a apariciones de hasta el final de y está formado por las posiciones correctas de esas ocurrencias. En este ejemplo, el elemento se corresponde con la palabra mientras la palabra se corresponde con el elemento .
Implica varias propiedades estructurales de los estados de autómatas sufijos. Dejar, luego: [14]
- Si y tener al menos un elemento común , luego y tienen un elemento común también. Eso implica es un sufijo de y por lo tanto y . En el ejemplo mencionado anteriormente,, entonces es un sufijo de y por lo tanto y ;
- Si , luego , por lo tanto ocurre en solo como un sufijo de . Por ejemplo, para y sostiene eso y ;
- Si y es un sufijo de tal que , luego . En el ejemplo anterior y es válido para el sufijo "intermedio" que .
Cualquier estado del sufijo autómata reconoce una cadena continua de sufijos anidados de la palabra más larga reconocida por este estado. [14]
"Extensión izquierda" de la cuerda es la cuerda más larga que tiene el mismo contexto correcto que . Largo de la cuerda más larga reconocida por se denota por . Tiene: [15]
Teorema - Extensión izquierda de puede representarse como , dónde es la palabra más larga tal que cualquier ocurrencia de en está precedido por .
"Enlace de sufijo" del Estado es el puntero al estado que contiene el sufijo más grande de que no es reconocido por .
En estos términos se puede decir reconoce exactamente todos los sufijos de eso es más largo que y no más de . También contiene: [15]
Teorema : los enlaces de sufijo forman un árbol que se puede definir explícitamente de la siguiente manera:
- Vértices del árbol corresponden a las extensiones izquierdas de todo subcadenas,
- Bordes del árbol conectan pares de vértices , tal que y .
Conexión con árboles de sufijos
Un " árbol de prefijos " (o "trie") es un árbol dirigido enraizado en el que los arcos están marcados por caracteres de tal manera que no hay vérticesde tal á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 "sufijo trie" de la palabraes un árbol de prefijos que reconoce un conjunto de sus sufijos. "Un árbol de sufijos " es un árbol obtenido a partir de un sufijo trie mediante el procedimiento de compactación, durante el cual los bordes consecuentes se fusionan si el grado del vértice entre ellos es igual a dos. [15]
Por su definición, un autómata de sufijo se puede obtener mediante la minimización del sufijo trie. Se puede demostrar 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 sufijos 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 sufijos de la cadena invertida . [18]
De manera similar a los contextos correctos, uno puede introducir "contextos izquierdos" , "extensiones derechas" correspondiente a la cadena más larga que tiene el mismo contexto izquierdo que y la relación de equivalencia . Si uno considera extensiones correctas con respecto al idioma de "prefijos" de la cadena se puede obtener: [15]
Teorema - Sufijo árbol de la cuerda puede definirse explícitamente de la siguiente manera:
- Vértices del árbol corresponden a las extensiones derechas de todo subcadenas,
- Bordes corresponden a trillizos tal que y .
Aquí triplete significa que hay una ventaja de a con la cuerda escrito en él
, que implica el árbol de enlaces de sufijo de la cadena y el árbol del sufijo de la cuerda son isomorfos: [18]
Estructuras de sufijo de las palabras "abbcbc" y "cbcbba" |
---|
|
De manera similar al caso de las extensiones izquierdas, el siguiente lema es válido para las extensiones derechas: [15]
Teorema : extensión derecha de la cuerda puede representarse como , dónde es la palabra más larga, de modo que cada aparición de en es sucedido por .
Tamaño
Un autómata sufijo de la cuerda de longitud tiene como máximo estados y como máximo transiciones. Estos límites se alcanzan en cadenas y correspondientemente. [13] Esto puede formularse de una manera más estricta como dónde y son los números de transiciones y estados en el autómata correspondientemente. [14]
Autómatas de sufijo máximo |
---|
|
Construcción
Inicialmente, el autómata solo consta de un solo estado correspondiente a la palabra vacía, luego los caracteres de la cadena se agregan uno por uno y el autómata se reconstruye en cada paso de forma incremental. [19]
Actualizaciones de estado
Después de agregar un nuevo carácter a la cadena, se modifican algunas clases de equivalencia. Dejar ser el contexto correcto de con respecto a la lengua de sufijos. Entonces la transición de a después se adjunta a está definido por el lema: [14]
Teorema - Sea se acaben algunas palabras y ser algún personaje de este alfabeto. Entonces hay una siguiente correspondencia entre y :
- Si es un sufijo de ;
- de lo contrario.
Después de agregar a la palabra actual el contexto correcto de puede cambiar significativamente solo si es un sufijo de . Implica relación de equivalenciaes un refinamiento de. En otras palabras, si, luego . Después de la adición de un nuevo carácter como máximo dos clases de equivalencia dese dividirán y cada uno de ellos podrá dividirse en dos clases nuevas como máximo. Primero, la clase de equivalencia correspondiente al contexto derecho vacío siempre se divide en dos clases de equivalencia, una de ellas correspondiente a sí mismo y teniendo como un contexto adecuado. 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]
Dada la correspondencia entre los estados del sufijo autómata y los vértices del árbol de sufijos, es posible descubrir el segundo estado que posiblemente se puede dividir después de agregar un nuevo carácter. La transición de a corresponde a la transición de a en la cuerda invertida. En términos de árboles de sufijos, corresponde a la inserción del nuevo sufijo más largo en el árbol del sufijo 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 antepasado directo si hubo ramificación. Volviendo al sufijo autómata, significa que el primer estado nuevo reconocey el segundo (si hay un segundo estado nuevo) es su enlace de sufijo. Puede enunciarse como un lema: [14]
Teorema - Sea, ser algo de palabra y carácter . También deja ser el sufijo más largo de , que ocurre en , y deja . Luego, para cualquier subcadena de se mantiene:
- Si y , luego ;
- Si y , luego ;
- Si y , luego .
Implica que si (por ejemplo, cuando no ocurrió en en absoluto y ), solo se divide la clase de equivalencia correspondiente al contexto derecho vacío. [14]
Además de los enlaces de sufijos, también es necesario definir los estados finales del autómata. De las propiedades de la estructura se deduce que todos los sufijos de una palabra reconocido por son reconocidos por algún vértice en la ruta del sufijo de . Es decir, sufijos con una longitud mayor que quedarse en cama , sufijos con una longitud mayor que pero no mayor que quedarse en cama y así. Por tanto, si el Estado reconociendo se denota por , entonces todos los estados finales (es decir, reconociendo sufijos de ) forman la secuencia . [19]
Actualizaciones de enlaces de transiciones y sufijos
Después del personaje se adjunta a posibles nuevos estados del sufijo autómata son y . Vínculo de sufijo de va a y de va a . Palabras de ocurre en sólo como sus sufijos, por lo tanto, no debería haber transiciones en absoluto de mientras que las transiciones deben ir de sufijos de tener longitud al menos y estar marcado con el personaje . Expresar está formado por un subconjunto de , por lo tanto, las transiciones de debe ser igual que desde . Mientras tanto, las transiciones que conducen a debe ir de sufijos de tener una longitud menor que y al menos , ya que tales transiciones han llevado a antes y correspondía a la parte secesionada de este estado. Los estados correspondientes a estos sufijos pueden determinarse mediante el recorrido de la ruta de enlace del sufijo para. [19]
Construcción del sufijo autómata para la palabra abbcbc | |||||||||
---|---|---|---|---|---|---|---|---|---|
|
| ||||||||
|
| ||||||||
|
|
Algoritmo de construcción
Los resultados teóricos anteriores conducen al siguiente algoritmo que toma carácter y reconstruye el sufijo autómata de en el sufijo autómata de : [19]
- El estado correspondiente a la palabra se mantiene como ;
- Después se adjunta, valor anterior de se almacena en la variable y se reasigna al nuevo estado correspondiente a ;
- Estados correspondientes a sufijos de se actualizan con transiciones a . Para hacer esto, uno debe pasar por, hasta que haya un estado que ya tenga una transición por ;
- Una vez finalizado el ciclo antes mencionado, existen 3 casos:
- Si ninguno de los estados en la ruta del sufijo tuvo una transición por , luego nunca ocurrió en antes y el enlace de sufijo de debería conducir a ;
- Si la transición por se encuentra y conduce desde el estado al Estado , tal que , luego no tiene que dividirse y es un enlace de sufijo de ;
- Si se encuentra la transición pero , luego palabras de tener longitud como máximo debe segregarse en un nuevo estado "clon" ;
- Si el paso anterior se concluyó con la creación de , las transiciones de él y su enlace de sufijo deben copiar las de , al mismo tiempo se asigna como enlace de sufijo común de ambos y ;
- Transiciones que han llevado a antes, pero correspondía a palabras de la longitud como máximo son redirigidos a . Para hacer esto, se continúa recorriendo el camino del sufijo de hasta que se encuentre el estado tal que la transición por de eso no conduce a .
Todo el procedimiento se describe mediante el siguiente pseudocódigo: [19]
función add_letter (x) : definir p = último asignar último = new_state () asignar len (último) = len (p) + 1 mientras que δ (p, x) no está definido: asignar δ (p, x) = último, p = enlace (p) definir q = δ (p, x) si q = último : asignar enlace (último) = q 0 más si len (q) = len (p) + 1 : asignar enlace (último) = q más : definir cl = new_state () asignar len (cl) = len (p) + 1 asignar δ (cl) = δ (q), enlace (cl) = enlace (q) asignar enlace (último) = enlace (q) = cl mientras δ (p, x) = q : asignar δ (p, x) = cl, p = enlace (p)
Aquí es el estado inicial del autómata y es una función que le crea un nuevo estado. Es asumido, , y se almacenan como variables globales. [19]
Complejidad
La complejidad del algoritmo puede variar según 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 tal complejidad, hay que utilizar los métodos de análisis amortizado . El valor dese 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 . Valor global de nunca excede y solo se incrementa en uno entre iteraciones de agregar nuevas letras que sugieren que la complejidad total es, como mucho, también lineal. La linealidad del segundo ciclo se muestra de manera similar. [19]
Generalizaciones
El sufijo autómata está estrechamente relacionado con otras estructuras de sufijos e índices de subcadenas . Dado un autómata de sufijo de una cadena específica, uno puede construir su árbol de sufijos a través de compactación y recorrido recursivo en tiempo lineal. [20] Transformaciones similares son posibles en ambas direcciones para cambiar entre el sufijo autómata de y el árbol del sufijo de la cuerda invertida . [18] Aparte de esto, se desarrollaron varias generalizaciones para construir un autómata para el conjunto de cadenas dado por trie, [8] automatización de sufijo compactado (CDAWG), [7] para mantener la estructura del autómata en la ventana deslizante, [21 ] y construirlo de forma bidireccional, apoyando la inserción de caracteres tanto al principio como al final de la cadena. [22]
Autómata sufijo compactado
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 pueden definirse de manera explícita. Una extensión bidireccional de una palabra es la palabra mas larga , de modo que cada aparición de en está precedido por y sucedido 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]
Teorema - sufijo autómata compactado de la palabra está definido por un par , dónde:
- es un conjunto de estados autómatas;
- es un conjunto de transiciones de autómatas.
Las extensiones bidireccionales inducen una relación de equivalencia que define el conjunto de palabras reconocidas por el mismo estado de autómata compactado. Esta relación de equivalencia es un cierre transitivo de la relación definida por, que destaca el hecho de que un autómata compactado puede obtenerse pegando ambos vértices de árbol de sufijo equivalentes a través de relación (minimización del árbol de sufijos) y pegar estados de autómatas de sufijos equivalentes a través de relación (compactación del sufijo autómata). [23] Si palabras y tienen las mismas extensiones correctas y palabras y tienen las mismas extensiones izquierdas, luego acumulativamente todas las cadenas , y tienen las mismas extensiones bidireccionales. Al mismo tiempo, puede suceder que ni las extensiones izquierda ni derecha de y coincidir. Como ejemplo, uno puede tomar, y , cuyas extensiones izquierda y derecha son las siguientes: , pero y . Dicho esto, mientras que las relaciones de equivalencia de las extensiones unidireccionales se formaron mediante una cadena continua de prefijos o sufijos anidados, las relaciones de equivalencia de las extensiones bidireccionales son más complejas y lo único que se puede concluir con certeza es que las cadenas con la misma extensión bidireccional son subcadenas de la cadena más larga que tienen 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 sufijo autómata compactado de la cuerda tiene una longitud tiene como máximo estados. La cantidad de transiciones en tal autómata es como máximo. [15]
Sufijo autómata de varias cadenas
Considere un conjunto de palabras . Es posible construir una generalización del sufijo autómata que reconozca el lenguaje formado por sufijos de todas las palabras del conjunto. Las restricciones para el número de estados y transiciones en dicho autómata seguirían siendo las mismas que para un autómata de una sola palabra si pones. [23] El algoritmo es similar a la construcción de un autómata de una sola palabra, excepto que en lugar deestado, la función add_letter funcionaría con el estado correspondiente a la palabra asumiendo la transición del conjunto de palabras al set . [24] [25]
Esta idea se generaliza aún más al caso cuando no se da explícitamente sino que se da mediante un árbol de prefijos convértices. Mohri y col . demostró que tal autómata tendría como muchoy 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 workds es igual a , el número de vértices en el sufijo correspondiente trie es igual a y el sufijo autómata correspondiente está formado por estados y transiciones. El algoritmo sugerido por Mohri repite principalmente el algoritmo genérico para la construcción de autómatas de varias cadenas, pero en lugar de hacer crecer las palabras una por una, atraviesa el trie en un orden de búsqueda de amplitud primero y agrega nuevos caracteres a medida que los encuentra en el recorrido, lo que garantiza amortizaciones complejidad lineal. [26]
Ventana deslizante
Algunos algoritmos de compresión , como LZ77 y RLE, pueden beneficiarse del almacenamiento de autómatas de sufijo o una estructura similar no para toda la cadena, sino solo para elsus caracteres mientras se actualiza la cadena. Esto se debe a que la compresión de datos suele ser expresivamente grande yla memoria es indeseable. 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 manera independiente y uniforme . Ella también mostró La complejidad no puede mejorarse: si se consideran las palabras construidas como una concatenación de varios palabras, donde , luego el número de estados para la ventana de tamaño cambiaría frecuentemente con saltos de orden , que hace que incluso una mejora teórica de para autómatas de sufijo regular imposible. [27]
Lo mismo debería ser cierto para el árbol de sufijos porque sus vértices corresponden a los estados del sufijo autómata de la cadena invertida, pero este problema puede resolverse al no almacenar explícitamente cada vértice correspondiente al sufijo de toda la cadena, por lo que solo se almacenan los vértices con en al menos dos bordes salientes. Edward Fiala y Daniel Greene sugirieron una variación del algoritmo de construcción de árboles de sufijos de McCreight para esta tarea en 1989; [28] varios años más tarde se obtuvo un resultado similar con la variación del algoritmo de Ukkonen por Jesper Larsson. [29] [30] La existencia de tal algoritmo, para autómatas de sufijos compactados que absorben algunas propiedades tanto de árboles de sufijos como de autómatas de sufijos, fue una cuestión abierta durante mucho tiempo hasta que fue descubierto por Martin Senft y Tomasz Dvorak en 2008, que es imposible si el tamaño del alfabeto es de al menos dos. [31]
Una forma de superar este obstáculo es permitir que el ancho de la ventana varíe un poco mientras permanece . Puede lograrse 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 sea de longitud pero se garantiza que al menos y como mucho al tiempo que proporciona una complejidad general lineal del algoritmo. [32]
Aplicaciones
Sufijo autómata de la cuerda puede utilizarse para resolver problemas como: [33] [34]
- Contando el número de subcadenas distintas de en en línea,
- Encontrar la subcadena más larga de ocurriendo al menos dos veces en ,
- Encontrar la subcadena común más larga de y en ,
- Contando el número de apariciones de en en ,
- Encontrar todas las apariciones de en en , dónde es el número de ocurrencias.
Se asume aquí que se da en la entrada después del sufijo autómata de esta construido. [33]
Los autómatas de sufijo también se utilizan en la compresión de datos, [35] recuperación de música [36] [37] y emparejamiento en secuencias del genoma. [38]
Referencias
- ↑ a b Crochemore, Vérin (1997) , p. 192
- ↑ a b Weiner (1973)
- ↑ Pratt (1973)
- ^ Slisenko (1983)
- ^ Blumer y col. (1984) , pág. 109
- ^ Chen, Seiferas (1985) , p. 97
- ^ a b Blumer y col. (1987) , pág. 578
- ^ a b Inenaga y col. (2001) , pág. 1
- ↑ a b Crochemore, Hancart (1997) , págs. 3-6
- ^ a b Серебряков и др. (2006) , págs. 50 a 54
- ^ Рубцов (2019) , págs. 89-94
- ^ Hopcroft, Ullman (1979) , págs. 65-68
- ^ a b Blumer y col. (1984) , págs. 111-114
- ↑ a b c d e f g h Crochemore, Hancart (1997) , págs. 27-31
- ^ a b c d e f g Inenaga et al. (2005) , págs. 159-162
- ^ Rubinchik, Shur (2018) , págs. 1-2
- ^ Inenaga y col. (2005) , págs. 156-158
- ^ a b c Fujishige y col. (2016) , págs. 1-3
- ↑ a b c d e f g Crochemore, Hancart (1997) , págs. 31-36
- ^ Паращенко (2007) , págs. 19-22
- ^ Blumer (1987) , p. 451
- ^ Inenaga (2003) , p. 1
- ^ a b Blumer y col. (1987) , págs. 585-588
- ^ Blumer y col. (1987) , págs. 588-589
- ^ Blumer y col. (1987) , pág. 593
- ^ Mohri y col. (2009) , págs. 3558—3560
- ^ Blumer (1987) , págs. 461-465
- ^ Fiala, Greene (1989) , p. 490
- ^ Larsson (1996)
- ↑ Brodnik, Jekovec (2018) , p. 1
- ↑ Senft, Dvořák (2008) , p. 109
- ^ Inenaga y col. (2004)
- ↑ a b Crochemore, Hancart (1997) , págs. 36-39
- ^ Crochemore, Hancart (1997) , págs. 39-41
- ^ Yamamoto y col. (2014) , pág. 675
- ^ Crochemore y col. (2003) , pág. 211
- ^ Mohri y col. (2009) , pág. 3553
- ↑ Faro (2016) , p. 145
Bibliografía
- Anselm Cyril Blumer; Janet Blumer; Andrzej Ehrenfeucht ; David Haussler ; Ross McConnell (1984). Construyendo el DFA mínimo para el conjunto de todas las subpalabras de una palabra en línea en tiempo lineal . Coloquio Internacional sobre Autómatas, Lenguajes y Programación . págs. 109-118. doi : 10.1007 / 3-540-13345-3_9 . ISBN 978-3-540-13345-2. Wikidata Q90309073 .
- Anselm Cyril Blumer; Janet Blumer; Andrzej Ehrenfeucht ; David Haussler ; Ross McConnell (julio de 1987). "Archivos completos invertidos para una recuperación y un análisis de texto eficaces" . Revista de la ACM . 34 (3): 578–595. CiteSeerX 10.1.1.87.6824 . doi : 10.1145 / 28869.28873 . ISSN 0004-5411 . Wikidata Q90311855 .
- Janet Blumer (diciembre de 1987). "¿Cuánto es ese DAWG en la ventana? Un algoritmo de ventana móvil para el gráfico de palabras acíclicas dirigidas" . Revista de algoritmos . 8 (4): 451–469. doi : 10.1016 / 0196-6774 (87) 90045-9 . ISSN 0196-6774 . Wikidata Q90327976 .
- Andrej Brodnik; Matevž Jekovec (3 de agosto de 2018). "Árbol de sufijo deslizante" . Algoritmos . 11 (8): 118. doi : 10.3390 / A11080118 . ISSN 1999-4893 . Wikidata Q90431196 .
- Mu-Tian Chen; Joel Seiferas (1985). Construcción de árbol de subpalabras eficiente y elegante . Algoritmos combinatorios sobre palabras . págs. 97-107. CiteSeerX 10.1.1.632.4 . doi : 10.1007 / 978-3-642-82456-2_7 . ISBN 978-3-642-82456-2. Wikidata Q90329833 .
- Maxime Crochemore ; Christophe Hancart (1997). Autómatas para patrones coincidentes . Manual de lenguajes formales . 2 . págs. 399–462. CiteSeerX 10.1.1.392.8637 . doi : 10.1007 / 978-3-662-07675-0_9 . ISBN 978-3-642-59136-5. Wikidata Q90413384 .
- Maxime Crochemore ; Renaud Vérin (1997). En gráficos de palabras acíclicos dirigidos compactos . Estructuras en lógica e informática . Apuntes de conferencias en Ciencias de la Computación . págs. 192–211. CiteSeerX 10.1.1.13.6892 . doi : 10.1007 / 3-540-63246-8_12 . ISBN 978-3-540-69242-3. Wikidata Q90413885 .
- Maxime Crochemore ; Costas S. Iliopoulos; Gonzalo Navarro ; Yoan J. Pinzón (2003). Un enfoque de autómata de sufijo de bits paralelos para (δ, γ) -Matching en la recuperación de música . Simposio internacional sobre procesamiento de cadenas y recuperación de información . págs. 211-223. CiteSeerX 10.1.1.8.533 . doi : 10.1007 / 978-3-540-39984-1_16 . ISBN 978-3-540-39984-1. Wikidata Q90414195 .
- Vladimir Serebryakov; Maksim Pavlovich Galochkin; Meran Gabibullaevich Furugian; Dmitriy Ruslanovich Gonchar (2006). Теория и реализация языков программирования (PDF) (en ruso). Moscú: MZ Press. ISBN 5-94073-094-9. Wikidata Q90432456 .
- Simone Faro (2016). Evaluación y mejora de algoritmos rápidos para el emparejamiento exacto en las secuencias del genoma . Congreso Internacional de Algoritmos para Biología Computacional . Apuntes de conferencias en Ciencias de la Computación . págs. 145-157. doi : 10.1007 / 978-3-319-38827-4_12 . ISBN 978-3-319-38827-4. Wikidata Q90412338 .
- Edward R. Fiala; Daniel H. Greene (abril de 1989). "Compresión de datos con ventanas finitas" . Comunicaciones de la ACM . 32 (4): 490–505. doi : 10.1145 / 63334.63341 . ISSN 0001-0782 . Wikidata Q90425560 .
- Yuta Fujishige; Yuki Tsujimaru; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda (2016). Computación DAWG y palabras mínimas ausentes en tiempo lineal para alfabetos enteros (PDF) . Simposio Internacional sobre Fundamentos Matemáticos de la Informática . 58 . págs. 38: 1–38: 14. doi : 10.4230 / LIPICS.MFCS.2016.38 . ISBN 978-3-95977-016-3. ISSN 1868-8969 . Wikidata Q90410044 .
- John Edward Hopcroft ; Jeffrey David Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas (1ª ed.). Massachusetts: Addison-Wesley . ISBN 978-81-7808-347-6. OL 9082218M . Wikidata Q90418603 .
- Shunsuke Inenaga (marzo de 2003). "Construcción bidireccional de árboles de sufijo" (PDF) . Revista Nórdica de Computación . 10 (1): 52–67. CiteSeerX 10.1.1.100.8726 . ISSN 1236-6064 . Wikidata Q90335534 .
- Shunsuke Inenaga; Hiromasa Hoshino; Ayumi Shinohara; Masayuki Takeda; Setsuo Arikawa; Giancarlo Mauri; Giulio Pavesi (marzo de 2005). "Construcción en línea de gráficos compactos de palabras acíclicas dirigidas" . Matemáticas aplicadas discretas . 146 (2): 156-179. CiteSeerX 10.1.1.1039.6992 . doi : 10.1016 / J.DAM.2004.04.012 . ISSN 0166-218X . Wikidata Q57518591 .
- Shunsuke Inenaga; Hiromasa Hoshino; Ayumi Shinohara; Masayuki Takeda; Setsuo Arikawa (2001). "Construcción del CDAWG para un trie" (PDF) . Conferencia de Cuerda de Praga. Actas : 37–48. CiteSeerX 10.1.1.24.2637 . Wikidata Q90341606 .
- Shunsuke Inenaga; Ayumi Shinohara; Masayuki Takeda; Setsuo Arikawa (marzo de 2004). "Gráficos compactos de palabras acíclicas dirigidas para una ventana deslizante" . Diario de algoritmos discretos . 2 (1): 33–51. CiteSeerX 10.1.1.101.358 . doi : 10.1016 / S1570-8667 (03) 00064-9 . ISSN 1570-8667 . Wikidata Q90345535 .
- N. Jesper Larsson (1996). "Aplicación ampliada de árboles de sufijos a la compresión de datos" . Actas. Conferencia de compresión de datos : 190-199. CiteSeerX 10.1.1.12.8623 . doi : 10.1109 / DCC.1996.488324 . ISSN 2375-0383 . Wikidata Q90427112 .
- Mehryar Mohri; Pedro Moreno; Eugene Weinstein (septiembre de 2009). "Algoritmo de construcción de autómatas de sufijo general y límites de espacio" . Informática Teórica . 410 (37): 3553–3562. CiteSeerX 10.1.1.157.7443 . doi : 10.1016 / J.TCS.2009.03.034 . ISSN 0304-3975 . Wikidata Q90410808 .
- Дмитрий А. Паращенко (2007), Обработка строк на основе суффиксных автоматов (PDF) (en ruso), San Petersburgo: ITMO University , Wikidata Q90436837
- Vaughan Ronald Pratt (1973), Mejoras y aplicaciones para el buscador de repetición Weiner , OCLC 726598262 , Wikidata Q90300966
- Александр Александрович Рубцов (2019). Заметки и задачи о регулярных языках и конечных автоматах (PDF) (en ruso). Moscú: Instituto de Física y Tecnología de Moscú . ISBN 978-5-7417-0702-9. Wikidata Q90435728 .
- Mikhail Rubinchik; Arseny M. Shur (febrero de 2018). "Eertree" (PDF) . Revista europea de combinatoria . 68 : 249-265. arXiv : 1506.04862 . doi : 10.1016 / J.EJC.2017.07.021 . ISSN 0195-6698 . Wikidata Q90726647 .
- Martin Senft; Tomáš Dvořák (2008). Perfección deslizante CDAWG . Simposio internacional sobre procesamiento de cadenas y recuperación de información . págs. 109-120. doi : 10.1007 / 978-3-540-89097-3_12 . ISBN 978-3-540-89097-3. Wikidata Q90426624 .
- Anatoly Olesievich Slisenko (1983). "Detección de periodicidades y emparejamiento de cadenas en tiempo real" . Revista de Ciencias Matemáticas . 22 (3): 1316-1387. doi : 10.1007 / BF01084395 . ISSN 1072-3374 . Wikidata Q90305414 .
- Peter Weiner (octubre de 1973). "Algoritmos de coincidencia de patrones lineales" . Simposio sobre los fundamentos de la informática : 1–11. CiteSeerX 10.1.1.474.9582 . doi : 10.1109 / SWAT.1973.13 . Wikidata Q29541479 .
- Jun'ichi Yamamoto; Tomohiro I; Hideo Bannai; Shunsuke Inenaga; Masayuki Takeda (2014). Factorización Lempel-Ziv en línea compacta más rápida (PDF) . Simposio sobre Aspectos Teóricos de la Informática . Actas internacionales de Leibniz en informática. 25 . págs. 675–686. CiteSeerX 10.1.1.742.6691 . doi : 10.4230 / LIPICS.STACS.2014.675 . ISBN 978-3-939897-65-1. ISSN 1868-8969 . Wikidata Q90348192 .
enlaces externos
- Medios relacionados con el autómata de sufijo en Wikimedia Commons
- Artículo de autómata de sufijo sobre algoritmos E-Maxx en inglés