Árbol palíndromo

árbol palíndromo

inglés árbol

árbol palíndromo para cuerda eertree

Tipo de

estructura de datos

año de invención

2015

Autor

Mijaíl Rubinchik [d]

Complejidad en los símbolos O

	Lo peor
Edificio	${\ estilo de visualización O (n \ registro \ sigma)}$
Consumo de memoria	$En)$

Archivos multimedia en Wikimedia Commons

Un árbol palindrómico ( eng. palindromic tree , también overtree [1] , ing. eertree ) es una estructura de datos diseñada para almacenar y procesar subcadenas palindrómicas de una cadena . Fue propuesto por científicos de la Universidad Federal de los Urales Mikhail Rubinchik y Arseny Shur en 2015. Representa dos árboles de prefijos , ensamblados a partir de las "mitades" derechas de subcadenas palindrómicas de longitud par e impar, respectivamente. La estructura ocupa memoria y se puede construir en tiempo , donde es la longitud de la cadena y es el número de caracteres diferentes en ella. Con la ayuda de un árbol de palíndromos, se pueden resolver eficazmente problemas tales como contar el número de subcadenas palindrómicas diferentes, encontrar la división de una cadena en el menor número de palíndromos, verificar si una subcadena es un palíndromo y otros. $En)$ ${\ estilo de visualización O (n \ registro \ sigma)}$ $norte$ $\sigma$

Notación

Sea alguna cadena y sea la cadena invertida . Al describir el árbol palíndromo de una cadena , se usa la siguiente notación [2] : ${\displaystyle S=s_{1}s_{2}\puntos s_{n))$ ${\displaystyle S^{R}=s_{n}s_{n-1}\puntos s_{1))$ $S$ $S$

Una cadena se llama palíndromo si se lee igual de izquierda a derecha y de derecha a izquierda, es decir, si . $S$ ${\ Displaystyle S = S ^ {R}}$

Una subcadena es una subsecuencia continua de una cadena y se denota por . $S$ ${\displaystyle S_{l,r}=s_{l}s_{l+1}\dots s_{r))$

En particular, la subcadena que tiene se denomina prefijo de cadena y la subcadena que tiene se denomina sufijo de cadena . $l=1$ $S$ ${\ estilo de visualización r = n}$ $S$

Una subcadena palindrómica ( subpalindrome ) es una subcadena que es un palíndromo. Si esta subcadena también es un prefijo o un sufijo de la cadena , entonces se llama palíndromo de prefijo o sufijo , respectivamente . $S$ $S$

Un árbol de prefijos es un árbol orientado a la raíz, cuyos arcos están etiquetados con símbolos de tal manera que no más de un borde etiquetado con un símbolo dado proviene de cualquier vértice deeste árbol . $v$

Cada vértice del árbol de prefijos corresponde a una cadena igual a la concatenación de caracteres en el camino desde la raíz del árbol hasta este vértice.

Estructura de árbol

En la notación anterior, el árbol palíndromo de una cadena es un grafo dirigido , cada vértice del cual corresponde y se identifica con algún subpalíndromo único de la cadena. Si la cadena tiene subpalíndromos y , donde es algún carácter alfabético , entonces el árbol de palíndromos tiene un arco marcado con el símbolo , desde el vértice correspondiente a , hasta el vértice correspondiente a . En tal gráfico, cualquier vértice puede tener solo un arco entrante. Por conveniencia, también se introducen dos vértices auxiliares, que corresponden a palíndromos de longitud ( cadena vacía ) y cadena ("imaginaria"), respectivamente. Los arcos de la cadena vacía conducen a vértices correspondientes a palíndromos de la forma , y de la “cadena imaginaria” a vértices correspondientes a palíndromos de la forma (es decir, que consisten en un solo carácter). Un vértice se llama incluso si tiene un palíndromo de longitud par, e impar en caso contrario. De la definición se sigue que los arcos en un árbol palíndromo pasan solo entre vértices con la misma paridad. Desde el punto de vista de los árboles de prefijos, esta estructura se puede describir de la siguiente manera [3] : $S$ $t$ ${\ estilo de visualización ctc}$ $C$ $C$ $t$ ${\ estilo de visualización ctc}$ ${\ estilo de visualización 0}$ $-una$ ${\ estilo de visualización cc}$ $C$

Los vértices y arcos del árbol palíndromo forman dos árboles de prefijos cuyas raíces se ubican en los vértices que definen las cadenas vacías e "imaginarias", respectivamente. En este caso, el primer árbol de prefijos está compuesto por las mitades derechas de subpalíndromos de longitud par, y la segunda de impares.

El número de vértices en el árbol palíndromo no excede , lo que es consecuencia directa del siguiente lema [4] : $n+2$

Una cadena de longitud puede tener como máximo distintas subcadenas palindrómicas no vacías. Además, después de asignar un determinado carácter al final de una cadena, el número de subpalíndromos diferentes de esta cadena no puede aumentar más de . $S$ $norte$ $norte$ $C$ $una$

Prueba

Esta afirmación se deriva de los siguientes hechos:

Si un palíndromo es un sufijo de un palíndromo , entonces también es su prefijo; $tu$ $v$
Si los palíndromos y son sufijos de la cadena y , entonces aparece al menos dos veces (como prefijo y como sufijo ); $tu$ $v$ $w$ ${\ estilo de visualización |u|<|v|}$ $tu$ $w$ $v$
Cualquier cadena puede tener como máximo un sufijo palíndromo único (que se presenta solo una vez). $w$ $w$

La última propiedad es esencialmente equivalente al lema, ya que todas las nuevas subcadenas que aparecen al agregar el siguiente carácter a la cadena deben ser sus sufijos [5] . ■

Además de los arcos habituales que sirven como transiciones para el árbol de prefijos, para cada vértice del árbol de palíndromos se define un enlace de sufijos que conduce del vértice al vértice correspondiente al sufijo propio más grande (no igual a toda la cadena ). palíndromo _ Al mismo tiempo, el enlace del sufijo desde el vértice "imaginario" no está definido, pero por definición conduce de un vértice vacío al "imaginario". Los enlaces de sufijos forman un árbol con raíz en un vértice "imaginario" y juegan un papel importante en la construcción de un árbol palíndromo [3] . $v$ $tu$ $v$ $v$

Edificio

Como muchas otras estructuras de cuerdas, un árbol palíndromo se construye iterativamente . Inicialmente, consta solo de vértices correspondientes a las cadenas vacías e imaginarias. Luego, la estructura se reconstruye gradualmente a medida que la cadena crece un carácter a la vez. Dado que, como mucho, aparece un nuevo palíndromo en una cadena al agregar un carácter, reconstruir el árbol en el peor de los casos requerirá agregar un nuevo nodo y un enlace de sufijo. Para determinar un posible nuevo nodo durante la construcción del árbol, se mantiene un último puntero al nodo correspondiente al mayor de los sufijos palíndromo actuales [3] .

Todos los palíndromos de sufijo de la cadena son accesibles mediante enlaces de sufijo desde last , por lo que para determinar un nuevo palíndromo de sufijo (corresponderá al nuevo vértice, si lo hay) es necesario seguir los enlaces de sufijo de last hasta que se encuentre que el carácter que precede al sufijo-palindrome actual coincide con el carácter que se asignó a la cadena. Más formalmente, sea el sufijo palíndromo máximo de la cadena , luego , o , donde es algún sufijo palíndromo . Por lo tanto, iterando entre los enlaces de sufijo de last , se puede determinar si se puede expandir comparando los caracteres y . Cuando se haya encontrado el sufijo del palíndromo correspondiente , debe verificar si el árbol del palíndromo contiene una transición desde el vértice correspondiente mediante el símbolo [3] . $PAGS$ ${\displaystyle S_{1,k}=s_{1}s_{2}\puntos s_{k))$ ${\ Displaystyle PAG = s_ {k}}$ $P=s_{k}Qs_{k}$ $q$ ${\ estilo de visualización S_ {1, k-1}}$ $q$ $PAGS$ $s_{k-|Q|-1}$ ${\ Displaystyle s_ {k}}$ $q$ ${\ Displaystyle s_ {k}}$

Si existe tal transición, entonces ya se ha encontrado en la línea anterior y corresponde al vértice al que conduce esta transición. De lo contrario, debe crear un nuevo vértice para él y hacer una transición desde . A continuación, defina un enlace de sufijo para que coincida con el segundo sufijo de palíndromo más largo . Para encontrarlo, uno debe continuar pasando por alto los últimos enlaces de sufijos hasta que se encuentre el segundo vértice , tal que ; es este vértice el que será el enlace del sufijo . Si denotamos la transición desde arriba con el símbolo , todo el proceso se puede describir con el siguiente pseudocódigo [3] : $PAGS$ ${\ Displaystyle s_ {k}}$ $q$ $PAGS$ ${\ Displaystyle S_ {1, k}}$ $q$ ${\displaystyle s_{k-|Q|-1}=s_{k))$ $PAGS$ $v$ $C$ ${\ estilo de visualización \ delta (v, c)}$

función find_link(v): while s k -len(v)-1 ≠ s k : asignar v = link(v) devolver v función agregar_letra(c): asignar k = k + 1 definir s k = c definir q = encontrar_enlace(último) si δ(q, c) no está definido: definir p = nuevo_vértice() definir len(p) = len(q ) + 2 definir enlace(p) = δ(buscar_enlace(enlace(q)), c) definir δ(q, c) = p asignar último = δ(q, c)

Se supone aquí que inicialmente el árbol está descrito por solo dos vértices con longitudes y, en consecuencia, con un enlace de sufijo del primer vértice al segundo. La última variable almacena el vértice correspondiente al mayor palíndromo de sufijos de la línea actual, inicialmente apunta al vértice de la línea cero. También se supone que inicialmente es igual a y se escribe algún carácter de servicio, lo que no ocurre en la cadena . ${\ estilo de visualización 0}$ $-una$ $k$ ${\ estilo de visualización 0}$ ${\ estilo de visualización s_ {0}}$ ${\displaystyle s_{1}s_{2}\puntos s_{k))$

Complejidad computacional

La complejidad del algoritmo puede variar según las estructuras de datos que almacenan la tabla de saltos en el árbol. En el caso general, cuando se usa una matriz asociativa , el tiempo empleado en acceder alcanza , donde es el tamaño del alfabeto a partir del cual se construye la cadena. Vale la pena señalar que cada iteración de la primera llamada a find_link reduce la longitud de last , y de la segunda, la longitud de link(last) , que solo puede aumentar en uno entre llamadas sucesivas a add_letter . Por lo tanto, el tiempo total de find_link no excede y el tiempo total requerido para ejecutar llamadas add_letter se puede estimar como [3] . El consumo de memoria de esta estructura es lineal en el peor de los casos, sin embargo, si consideramos el tamaño medio de la estructura sobre todas las cadenas de una determinada longitud , el consumo medio de memoria será del orden de [6] . ${\ estilo de visualización \ delta (q, c)}$ ${\ estilo de visualización O (\ registro \ sigma)}$ $\sigma$ $En)$ $norte$ ${\ estilo de visualización O (n \ registro \ sigma)}$ $norte$ $O({\sqrt {n\sigma)))$

Modificaciones

Simultáneamente con la introducción de esta estructura de datos, Rubinchik y Shur también propusieron una serie de modificaciones que permiten ampliar el alcance de las tareas resueltas por un árbol palíndromo. En particular, se propuso un método que permite construir un árbol palíndromo general para un conjunto de cadenas con las mismas asintóticas . Tal modificación nos permite resolver los mismos problemas considerados en el contexto de un conjunto de cadenas, por ejemplo, encontrar el subpalíndromo común más grande de todas las cadenas o el número de subpalíndromos diferentes de todas las cadenas en el agregado. Otra modificación propuesta fue una variante de construcción en árbol, en la que la adición de un carácter lleva tiempo en el peor de los casos (y no amortizado , como ocurre en la construcción estándar) y memoria. Este enfoque permite proporcionar persistencia parcial del árbol, en el que es posible revertir la adición del último carácter en momentos arbitrarios. Además, se propuso una versión totalmente persistente del árbol, que permite acceder y anexar un carácter a cualquiera de las versiones previamente guardadas en tiempo y memoria en el peor de los casos [7] . ${\displaystyle S_{1},S_{2},\puntos,S_{k))$ $O(\log n)$ ${\ estilo de visualización O (\ registro \ sigma)}$ $O(1)$ $O(\log n)$

En 2019, Watanabe y sus colegas desarrollaron una estructura de datos basada en un árbol palíndromo, llamado e 2 rtre 2 , para trabajar con subpalíndromos de cadenas dadas por codificación de longitud de ejecución [4] , y en 2020, el mismo equipo de autores, junto con Mieno, desarrolló dos algoritmos, que permiten mantener un árbol palíndromo en una ventana deslizante de tamaño . El primero de estos algoritmos requiere tiempo y memoria, y el segundo requiere tiempo y memoria [8] . $d$ ${\ estilo de visualización O (n \ registro \ sigma)}$ ${\ estilo de visualización O (d)}$ ${\ estilo de visualización O (n + d \ sigma)}$ ${\ estilo de visualización O (d \ sigma)}$

Aplicaciones

El árbol palíndromo ofrece muchas aplicaciones posibles para obtener algoritmos teóricamente rápidos y prácticamente fáciles de implementar para resolver una serie de problemas combinatorios en programación y cibernética matemática [9] .

Una de las tareas para las que se desarrolló esta estructura es contar diferentes subpalíndromos en una cadena en línea . Se puede configurar de la siguiente manera: un carácter a la vez se asigna un carácter a la vez a la cadena inicialmente vacía. En cada paso, debe imprimir el número de subpalíndromos diferentes en la cadena dada. Desde el punto de vista del árbol palíndromo, esto equivale a imprimir el número de vértices no triviales de la estructura en cada paso. En 2010 [10] se presentó una solución lineal para la versión fuera de línea de este problema , y en 2013 [11] se encontró la solución óptima con tiempo de ejecución para la versión en línea . La solución indicada, sin embargo, utilizó dos estructuras de datos "pesadas": un análogo del algoritmo Manaker , así como un árbol de sufijos . El árbol palíndromo, por un lado, tiene las mismas asintóticas en el peor de los casos, y por otro lado, es una estructura mucho más ligera [3] . ${\ estilo de visualización O (n \ registro \ sigma)}$

Otra posible aplicación de esta estructura es la enumeración de cadenas binarias ricas en palíndromos [12] . Anteriormente se demostró que una palabra de longitud no puede contener más que diferentes palíndromos; las palabras en las que se logra esta estimación se denominan ricas en palíndromos. Amy Glen y sus colegas introdujeron el concepto de palabras ricas en palindrómicos en 2008 [13] . Rubinchik y Shur demostraron que usando un árbol de palíndromos, uno puede detectar todas las palabras ricas en palindrómicos cuya longitud no exceda , donde es el número de tales palabras. Este resultado permitió aumentar el número de miembros conocidos de la secuencia A216264 en OEIS de 25 a 60. Los datos obtenidos mostraron que la secuencia crece mucho más lentamente de lo que se pensaba anteriormente, es decir, está acotada desde arriba como [14] . $norte$ $n+1$ $norte$ ${\ estilo de visualización O (R)}$ $R$ ${\ estilo de visualización O (1605 ^ {n})}$

Notas

↑ Rubinchik, 2016 , pág. 6-9
↑ Rubinchik, Shur, 2018 , págs. 1-2
↑ 1 2 3 4 5 6 7 Rubinchik, Shur, 2018 , págs. 2-6
↑ 1 2 Watanabe et al., 2019 , págs. 432-434
↑ Droubay et al., 2001 , págs. 542-546
↑ Rubinchik, Shur, 2016 , pág. una
↑ Rubinchik, Shur, 2018 , pág. 6-11
↑ Mieno et al., 2020
↑ Rubinchik, 2016 , pág. 75-76
↑ Groult, 2010
↑ Kosolobov et al., 2013
↑ Secuencia OEIS A216264 _
↑ Glen et al., 2009
↑ Rukavicka, 2017

Literatura

Rubinchik M. Complejidad computacional de algunas tareas de procesamiento de cadenas - Ekaterimburgo : UrFU , 2016. - 83 p.
Droubay X., Justin J., Pirillo G. Palabras episturmianas y algunas construcciones de de Luca y Rauzy (inglés) // Ciencias de la Computación Teórica - Elsevier BV , 2001. - Vol. 255, edición. 1-2. - Pág. 539-553. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/S0304-3975(99)00320-5
Groult R., Prieur É., Richomme G. Recuento de palíndromos distintos en una palabra en tiempo lineal // Informar . proceso. Letón. - Elsevier BV , 2010. - Vol. 110, edición. 20.- Pág. 908-912. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/J.IPL.2010.07.018
Kosolobov D., Rubinchik M., Shur A. M. Encontrar distintos subpalíndromos en línea (inglés) // Conferencia de Stringología de Praga - Universidad Técnica Checa en Praga : 2013. - P. 63-69. -arXiv :1305.2540
Mieno T., Watanabe K., Nakashima Y., Inenaga S., Bannai H., Takeda M., Ginsparg P. Computación de árboles palindrómicos para una ventana deslizante y sus aplicaciones (inglés) // ArXiv.org - 2020. - 14 pm. — ISSN 2331-8422 — arXiv:2006.02134
Rubinchik M., Shur A. M. The Number of Distinct Subpalindromes in Random Words (inglés) // Fund. informar. - Prensa IOS , 2016. - Vol. 145, edición. 3.- Pág. 371-384. — ISSN 0169-2968 ; 1875-8681 - doi:10.3233/FI-2016-1366 - arXiv:1505.08043
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
Watanabe K., Nakashima Y., Inenaga S., Bannai H., Takeda M. Consultas de subcadenas palindrómicas únicas más cortas en cadenas codificadas de longitud de ejecución // Lect . Nota Cómputo. ciencia / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlín , Heidelberg , Nueva York, NY , Londres [etc.] : Springer , 2019. - P. 430-441. — ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-030-25005-8_35 - arXiv:1903.06290
Glen A., Justin J., Widmer S., Zamboni L. Q. Palindromic richness (inglés) // 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 , 2009. — Vol. 30, edición. 2.- Pág. 510-531. — ISSN 0195-6698 ; 1095-9971 - doi:10.1016/J.EJC.2008.04.006 - arXiv:0801.1656
Rukavicka J. Sobre el número de palabras ricas (inglés) // Lect. Nota Cómputo. ciencia / G. Goos , J. Hartmanis , J. v. Leeuwen - Berlín , Heidelberg , Nueva York, NY , Londres [etc.] : Springer , 2017. - P. 345-352. — ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-319-62809-7_26 - arXiv:1701.07778

Enlaces

El árbol palíndromo . Resúmenes de la wiki de la 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