Resumen Técnico: Coincidencia de Diccionario Interno Casi Óptima

Definición del Problema

El artículo aborda el problema de la Coincidencia de Diccionario Interno (IDM, por sus siglas en inglés). En este escenario, se da de antemano un texto grande $T$ de longitud $n$ sobre un alfabeto linealmente ordenable. Un diccionario $D$ consiste en $d$ subcadenas de $T$. El objetivo es preprocesar $T$ y $D$ para responder eficientemente a consultas sobre las ocurrencias de patrones de $D$ dentro de subcadenas arbitrarias $T[l, r]$ de $T$.

El artículo se centra en cinco tipos específicos de consultas:

1. Exists($l, r$): Determinar si al menos un patrón de $D$ ocurre en $T[l, r]$.
2. Report($l, r$): Reportar todas las ocurrencias de todos los patrones de $D$ en $T[l, r]$.
3. ReportDistinct($l, r$): Reportar todos los patrones distintos de $D$ que ocurren en $T[l, r]$.
4. Count($l, r$): Contar el número total de ocurrencias de todos los patrones de $D$ en $T[l, r]$.
5. CountDistinct($l, r$): Contar el número de patrones distintos de $D$ que ocurren en $T[l, r]$.

Este problema generaliza la coincidencia de diccionario clásica y la coincidencia de patrones internos (IPM). Es particularmente relevante para diccionarios "internos" donde la longitud total de los patrones $L$ es mucho mayor que el número de patrones $d$ (por ejemplo, diccionarios de todos los palíndromos, cuadrados o subcadenas no primitivas), ya que la complejidad de la solución debe depender de $n$ y $d$, no de $L$.

Metodología: Estructura de Subcadena Básica (BASS)

La contribución central del artículo es la propuesta de una novedosa estructura de datos de tamaño $O(n)$ llamada Estructura de Subcadena Básica (BASS). BASS organiza las subcadenas de $T$ utilizando una cuadrícula bidimensional y clases de equivalencia.

1. La Cuadrícula y las Clases de Equivalencia

La estructura mapea cada subcadena $T[l, r]$ a un punto $(l, r)$ en una cuadrícula 2D.

• Clases de Equivalencia: Dos subcadenas son equivalentes si sus "extensiones" son idénticas. La extensión de una subcadena $t$, denotada como $ext(t)$, es la cadena más larga $s$ tal que $t$ es una subcadena de $s$ y $|occ(t)| = |occ(s)|$. Este concepto corresponde a los nodos en el Grafo Acíclico Compacto de Palabras (CDAWG).
• Bloques: En la cuadrícula, cada clase de equivalencia forma un "bloque" con una forma de escalera. Un bloque $B$ se define por parámetros: un rango de filas $[left_B, right_B]$, un límite superior $top_B$, y una secuencia no decreciente de límites inferiores $b_{left_B}, \dots, b_{right_B}$.
• Propiedades: El artículo demuestra que todos los bloques dentro de la misma clase de equivalencia comparten la misma forma (salvo tras una traslación). Además, la suma de las longitudes de los límites izquierdo y superior de todos los bloques distintos es $O(n)$.

2. Mapeos de Árboles

BASS integra dos árboles de sufijos modificados para formalizar las relaciones entre bloques:

• PreTree($T$): Un árbol de sufijos de $T$. Captura las relaciones entre bloques que comparten una columna (relaciones ancestro-descendiente).
• SufTree($T$): Un árbol de sufijos de la cadena invertida $rev(T)$. Captura las relaciones entre bloques que comparten una fila.
  Estos árboles permiten a la estructura mapear las coordenadas de la cuadrícula a los nodos de manera eficiente, permitiendo la localización en tiempo $O(1)$ de la clase de equivalencia de una subcadena y su posición dentro de un bloque.

3. Estrategias de Procesamiento de Consultas

• Consultas de Conteo (Count): El algoritmo reduce el problema de conteo a un problema de conteo de rangos 2D. Al almacenar sumas parciales de las ocurrencias de patrones a lo largo de los límites de los bloques y utilizar una estructura de datos de conteo de rangos 2D estática (basada en el trabajo de Chan y Pătraşcu), se optimiza el tiempo de consulta.
• Consultas de Conteo de Distintos (CountDistinct): Esta es la consulta más compleja. Los autores descomponen el problema en dos partes:
  1. Calcular las ocurrencias totales ($A_1$) menos las ocurrencias en un rango de sufijo específico determinado por una "posición clave" (el sufijo más corto de $T[l, r]$ que aparece exactamente una vez).
  2. Restar los patrones sobrecontados ($A_2$) basados en la estructura del trie de sufijos.
     Para manejar esto eficientmente, el artículo introduce conjuntos de eventos derivados de Árboles Link-Cut para rastrear los cambios en los conteos de ocurrencias a medida que el rango de la consulta se desplaza, permitiendo el cálculo de $A_2$ mediante estructuras de datos persistentes.

Resultados Clave y Contribuciones

El artículo presenta algoritmos que logran tiempos de consulta y preprocesamiento casi óptimos para los cinco tipos de consulta. Los resultados se resumen a continuación (donde $\tilde{O}$ suprime factores polilogarítmicos):

Tipo de Consulta	Tiempo de Preprocesamiento	Tiempo de Consulta	Espacio
Exists	$O(n + d)$	$O(1)$	$O(n + d)$
Report	$O(n + d)$	$O(1 + x)$	$O(n + d)$
Count	$O(n + d\sqrt{\log n})$	$O(\frac{\log n}{\log \log n})$	$O(n + d)$
ReportDistinct	$O(n \log n + d)$	$O(1 + x)$	$O(n + d)$
CountDistinct	$O(n \log^2 n + d\sqrt{\log n})$	$O(\log n)$	$O(n \log^2 n + d)$

Nota: $x$ denota la longitud de la salida.

Mejoras Específicas

1. CountDistinct: El artículo resuelve una pregunta abierta de un trabajo previo [16] proporcionando el primer algoritmo que responde a consultas CountDistinct en tiempo $\tilde{O}(1)$ (específicamente $O(\log n)$) con preprocesamiento de $\tilde{O}(n+d)$. Los mejores resultados previos requerían un tiempo de consulta $\tilde{O}(m)$ con un preprocesamiento de $\tilde{O}(n^2/m + d)$.
2. Count: El tiempo de consulta se mejora de $O(\frac{\log^2 n}{\log \log n})$ a $O(\frac{\log n}{\log \log n})$, lo cual los autores demuestran que es óptimo para estructuras de datos de tamaño $\tilde{O}(n)$ basadas en cotas inferiores para el conteo de rangos 2D.
3. ReportDistinct: El tiempo de consulta se mejora de $O(\log n + x)$ a $O(1 + x)$.
4. Aplicabilidad General: Los autores demuestran que BASS puede aplicarse a otros problemas de consulta interna, como el problema de la Subcadena Común Más Larga de Rango (RLCS), logrando un tiempo de consulta de $O(1)$ y un preprocesamiento de $O(n)$, mejorando el tiempo de consulta previo de $O(\log n)$.

Significado y Reivindicaciones

El artículo afirma que BASS es la primera estructura de datos capaz de manejar todos los tipos de consultas de IDM con tiempos de consulta y preprocesamiento casi óptimos. A diferencia de trabajos anteriores que trataban diferentes tipos de consultas con enfoques especializados y disjuntos, BASS proporciona un marco unificado.

La importancia del trabajo radica en:

• Optimidad: Igualar las cotas inferiores condicionales conocidas para la coincidencia de diccionarios dinámica (hasta factores subpolinomiales) y demostrar la optimalidad incondicional para la consulta Count.
• Marco Unificado: Organizar exitosamente las clases de equivalencia en una estructura de cuadrícula 2D que cierra la brecha entre los conceptos de CDAWG y la consulta eficiente de subcadenas, una conexión no explorada completamente en la literatura previa.
• Manejo de Diccionarios Grandes: Proporcionar soluciones donde la complejidad depende del número de patrones $d$ en lugar de la longitud total de los patrones $L$, lo que las hace adecuadas para diccionarios internos complejos (por ejemplo, todos los palíndromos o cuadrados).

Los autores señalan que para diccionarios dinámicos (donde los patrones pueden añadirse o eliminarse), pueden construir algoritmos que procesan actualizaciones en tiempo $\tilde{O}(n^\alpha)$ y responden a consultas CountDistinct en $\tilde{O}(n^{1-\alpha})$ tiempo, igualando las cotas inferiores condicionales conocidas para este entorno.