Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings

1. Planteamiento del Problema

La mayoría de los algoritmos tradicionales de descomposición de cadenas (por ejemplo, Lempel-Ziv, Transformada de Burrows-Wheeler, Codificación de Longitud de Ejecución) procesan las cadenas de manera lineal y unidireccional (de izquierda a derecha o mediante permutación). Aunque son efectivos para la compresión o el agrupamiento, estos métodos a menudo oscurecen la simetría estructural de fuera hacia adentro de una cadena. Específicamente, no capturan explícitamente cómo las ejecuciones (runs) de los límites de una cadena pueden ser peladas capa por capa para revelar un núcleo interno.

El artículo aborda la necesidad de un método de descomposición que:

1. Procesa las cadenas desde ambos extremos simultáneamente (bilateral).
2. Opera a nivel de ejecuciones máximas (caracteres idénticos consecutivos) en lugar de caracteres individuales.
3. Es exactamente reversible y computacionalmente eficiente.
4. Proporciona conocimientos estructurales sobre la simetría de cadenas, los palíndromos y la localidad de edición.

2. Metodología: El Algoritmo Flashback

Los autores proponen Flashback, un algoritmo determinista que descompone una cadena en una secuencia de "tokens bilaterales".

Mecanismo Central

1. Envoltura con Centinelas: La cadena de entrada $s$ se envuelve en dos caracteres centinela únicos, @ y $, que no forman parte del alfabeto original $\Sigma$. Esto asegura que las ejecuciones iniciales y finales en el primer paso sean distintas y de longitud 1.
2. Pelado Bilateral:
   • En cada paso, el algoritmo identifica la ejecución máxima inicial y la ejecución máxima final del rango activo actual.
   • Estas dos ejecuciones se concatenan en una única cadena de símbolos $\sigma$.
   • Se registra una posición de división $p$, que representa la longitud de la ejecución inicial.
   • El par $(\sigma, p)$ forma un token bilateral.
   • El algoritmo se recursa sobre el "subcadena del medio" restante (la parte entre las ejecuciones peladas).
3. Terminación: El proceso se detiene cuando el medio está vacío o consiste en una sola ejecución (o dos ejecuciones adyacentes que cubren el rango), emitiendo un token terminal donde la posición de división $p=0$.

Reconstrucción ($F^{-1}$)

La reconstrucción es el proceso inverso, trabajando de adentro hacia afuera:

• Toma la secuencia de tokens y asigna un búfer.
• Procesa los tokens desde el último (más interno) hasta el primero (más externo).
• Para cada token, escribe la parte frontal de la cadena, llena recursivamente el hueco interno y luego escribe la parte trasera.
• Finalmente, se eliminan los caracteres centinela para recuperar la cadena original.

3. Contribuciones Clave y Resultados Teóricos

A. El Teorema de Emparejamiento de Ejecuciones (Núcleo Teórico)

El resultado central del artículo establece que Flashback es matemáticamente equivalente a emparejar las ejecuciones de la Codificación de Longitud de Ejecución (RLE) de fuera hacia adentro.

• Si una cadena tiene $r$ ejecuciones máximas, Flashback empareja la 1ª ejecución con la $r$-ésima, la 2ª con la $(r-1)$-ésima, y así sucesivamente.
• Conteo de Tokens: El número exacto de tokens $k$ viene dado por:
  $$k = 1 + \lceil r/2 \rceil$$
  (El $+1$ cuenta por el token centinela inicial).
• Optimalidad: Los autores demuestran que este enfoque "codicioso" (pelar ejecuciones completas) es óptimo. Ningún otro esquema de pelado bilateral de ejecuciones admisible puede producir menos tokens. Si $r$ es par, Flashback es el esquema único de tokens mínimos.

B. Propiedades Estructurales

1. Núcleo Irreducible: El token terminal (el "núcleo" de la descomposición) contiene como máximo dos símbolos distintos.
   • Si $r$ es impar, el núcleo es una sola ejecución.
   • Si $r$ es par, el núcleo son dos ejecuciones adyacentes.
2. Caracterización de Palíndromos: Una cadena es un palíndromo si y solo si:
   • Su RLE tiene un número impar de ejecuciones ($r$ es impar).
   • Su RLE es simétrico (la $i$-ésima ejecución coincide con la $(r+1-i)$-ésima ejecución tanto en símbolo como en longitud).
   • En términos de Flashback, esto significa que el núcleo es una sola ejecución, y cada token no terminal tiene símbolos frontal/trasero coincidentes con longitudes iguales.
3. Caracterización de Imágenes: Los autores proporcionan una caracterización de estado finito de las secuencias de tokens válidas. Una secuencia es una salida válida de Flashback si y solo si satisface restricciones locales específicas respecto a las posiciones de división, la alternancia de ejecuciones y las formas terminales.

C. Localidad de Edición

La descomposición exhibe una fuerte localidad de edición:

• Cambios en la Longitud de Ejecución: Cambiar la longitud de una sola ejecución $m_i$ (sin cambiar el símbolo) afecta exactamente un token de contenido. Específicamente, reescribe el token en la profundidad $\min(i, r+1-i)$.
• Ediciones de Caracteres: Las inserciones, eliminaciones o sustituciones cambian como máximo dos límites de ejecución, alterando el conteo de tokens en como máximo 1 y desplazando potencialmente el contenido en un número acotado de tokens.

4. Análisis de Complejidad

• Complejidad Temporal: Tanto la descomposición ($F$) como la reconstrucción ($F^{-1}$) se ejecutan en tiempo $O(n)$.
  • La descomposición escanea cada carácter un número constante de veces (una vez para identificar ejecuciones, una vez para emitir tokens).
  • La reconstrucción escribe cada carácter directamente en su posición final en el búfer de salida.
• Complejidad Espacial: El algoritmo utiliza espacio $O(n)$.
  • La descomposición puede implementarse de forma iterativa (eliminación de recursión de cola) para usar $O(1)$ espacio auxiliar más allá de los búferes de entrada/salida.

5. Significado y Aplicaciones

• Herramienta Estructural vs. Compresión: Los autores declaran explícitamente que Flashback no es un esquema de compresión. El recuento total de caracteres en los tokens es igual a $n+2$ (la longitud original más los centinelas). En su lugar, es una herramienta estructural para razonar sobre la simetría de cadenas y las propiedades a nivel de ejecución.
• Complementariedad: A diferencia de Lempel-Ziv (que encuentra subcadenas repetidas) o BWT (que agrupa caracteres idénticos), Flashback captura el anidamiento bilateral. Revela la estructura "como una cebolla" de una cadena.
• Conocimiento Teórico: El artículo cierra la brecha entre la codificación simple de longitud de ejecución y la descomposición estructural compleja, mostrando que una estrategia simple de emparejamiento "de fuera hacia adentro" produce una representación única, óptima y altamente local de la simetría de cadenas.
• Palíndromos y Núcleos: Ofrece una nueva perspectiva algorítmica sobre los palíndromos y el "núcleo" de una cadena, definiéndolos a través de las propiedades del núcleo de pelado.

Resumen

Flashback es una descomposición de cadenas novedosa y reversible que pella ejecuciones máximas desde ambos extremos de una cadena simultáneamente. Su contribución teórica principal es el Teorema de Emparejamiento de Ejecuciones, que demuestra que la descomposición es equivalente a emparejar ejecuciones de RLE de fuera hacia adentro, resultando en un conteo de tokens de $1 + \lceil r/2 \rceil$. El método se ejecuta en tiempo lineal, ofrece una localidad de edición precisa y proporciona un marco riguroso para analizar la simetría de cadenas y los palíndromos, distinguiéndose de los algoritmos de compresión tradicionales al priorizar el conocimiento estructural sobre la reducción de datos.