Resumen Técnico: Coincidencia de Permutaciones bajo Presupuestos de Parikh

1. Definición del Problema

El artículo aborda el problema de la Coincidencia de Patrones de Permutación (Jumbled/Abelian) sobre un alfabeto general $\Sigma$. Dado un patrón $P$ de longitud $m$ y un texto $T$ de longitud $n$, la tarea clásica es determinar si $T$ contiene una subcadena de longitud $m$ cuyo multiconjunto de símbolos coincida con el de $P$. Esto es equivalente a verificar si el vector de Parikh (vector de frecuencia) de una ventana en $T$ es igual al vector de Parikh de $P$.

Más allá de la mera detección, los autores extienden el alcance a dos variantes de optimización:

1. Subcadena Máxima Factible bajo Suministro de Patrón (MFSP): Tratando los conteos de símbolos de $P$ como un presupuesto de recursos (vector de suministro), el objetivo es encontrar la subcadena más larga $S$ de $T$ tal que los conteos de símbolos de $S$ estén acotados componente a componente por los de $P$ (es decir, $freq(S) \preceq freq(P)$).
2. Selección No Solapada: Dado un conjunto de todas las coincidencias de permutación en $T$, seleccionar el subconjunto de máxima cardinalidad de estas coincidencias de modo que ninguna de las coincidencias seleccionadas se solape. Dado que todas las coincidencias tienen longitud $m$, esto se modela como un problema de empaquetamiento de intervalos.

2. Metodología y Algoritmos

El artículo propone un marco unificado basado en algoritmos de ventana deslizante y mantenimiento de la diferencia del vector de Parikh.

2.1 Coincidencia de Permutación en Tiempo Lineal (Línea Base)

Los autores presentan un algoritmo para detectar ocurrencias de permutación en $O(n + \sigma)$ de tiempo y $O(\sigma)$ de espacio, donde $\sigma = |\Sigma|$.

• Mecanismo: En lugar de recalcular los vectores de frecuencia para cada ventana, el algoritmo mantiene un vector de diferencia $\Delta_i(c) = freq(W_i)(c) - freq(P)(c)$ para la ventana actual $W_i$.
• Optimización: Un único contador entero, $nz_i$, rastrea el número de entradas distintas de cero en $\Delta_i$. Una ventana es una coincidencia si y solo si $nz_i = 0$.
• Actualizaciones: Cuando la ventana se desliza, solo dos coordenadas de $\Delta$ cambian (un carácter sale y uno entra). El algoritmo actualiza $nz$ en tiempo constante basándose en si una coordenada cruza el cero.

2.2 MFSP: Subcadena Máxima Factible

Para resolver la variante de empaquetamiento, los autores introducen un algoritmo de dos punteros (ventana deslizante) que también se ejecuta en $O(n + \sigma)$ de tiempo.

• Mecanismo: El algoritmo mantiene una ventana $T[\ell..r]$ y un arreglo de conteo cnt para la ventana actual. Un contador de violaciones viol rastrea cuántos símbolos exceden su presupuesto definido por $freq(P)$.
• Lógica: El puntero derecho $r$ expande la ventana. Si añadir un carácter causa una violación (es decir, cnt excede sup), el puntero izquierdo $\ell$ avanza hasta que se restaura la factibilidad.
• Corrección: El algoritmo se basa en la monotonicidad de la factibilidad: reducir una ventana desde la izquierda nunca aumenta los conteos de símbolos. La prueba establece que para cada extremo derecho $r$, el algoritmo encuentra la subcadena factible más larga que termina en $r$, garantizando la optimalidad global.

2.3 Selección No Solapada mediante Empaquetamiento de Intervalos

Una vez enumeradas todas las coincidencias de permutación (usando el algoritmo de línea base), el problema de selección se resuelve mediante una estrategia voraz (greedy).

• Mecanismo: Dado que todas las coincidencias corresponden a intervalos de igual longitud $m$, el problema se reduce a seleccionar el máximo número de intervalos disjuntos.
• Estrategia: El algoritmo escanea el texto de izquierda a derecha, seleccionando la primera coincidencia disponible y luego saltando hacia adelante $m$ posiciones hacia la siguiente coincidencia potencial no solapada.
• Prueba: Un argumento de intercambio demuestra que esta regla voraz de "finalización temprana" (o inicio temprano, dado que las longitudes son iguales) produce un conjunto de máxima cardinalidad.

3. Contribuciones Clave

1. Marco Unificado: Un enfoque conciso de ventana deslizante que maneja la detección, la optimización (MFSP) y la selección utilizando el mantenimiento de la diferencia de Parikh.
2. Complejidad Óptima: Todos los algoritmos propuestos logran $O(n + \sigma)$ de tiempo y $O(\sigma)$ de espacio. Esto coincide con el límite inferior para leer la entrada y es óptimo para alfabetos generales.
3. Formulación de MFSP: La introducción del problema MFSP, que redefine la coincidencia jumbled como un problema de empaquetamiento restringido por recursos, resuelto con un algoritmo de dos punteros provablemente correcto en tiempo lineal.
4. Optimalidad Voraz: Una prueba formal de que un simple escaneo voraz es óptimo para seleccionar coincidencias de permutación no solapadas cuando todas las coincidencias tienen la misma longitud.

4. Resultados y Observaciones Experimentales

Los autores reportan observaciones experimentales ligeras para corroborar sus límites teóricos:

• Escalabilidad: Tanto la coincidencia de permutaciones como el MFSP exhiben un escalado lineal con la longitud del texto $n$, consistente con el análisis $O(n + \sigma)$.
• Factores de Rendimiento: El tiempo de ejecución está dominado por los patrones de acceso a memoria de los arreglos de conteo/mapas y la densidad de las coincidencias (que afecta el volumen de salida pero no la lógica de escaneo).
• Manejo de Alfabetos: Para alfabetos grandes, la compresión de alfabeto (mapear los símbolos que aparecen en $P$ y $T$ a enteros $1 \dots \sigma'$) reduce significamente la huella de memoria y mejora la localidad de caché, manteniendo la eficiencia incluso cuando $\sigma$ es grande pero $\sigma'$ es pequeño.
• Eficiencia de MFSP: El mecanismo del contador de violaciones en MFSP evita comprobaciones completas de factibilidad, asegurando que cada carácter sea añadido o eliminado como máximo una vez, adhiriéndose a la amortización estándar de dos punteros.

5. Significación y Alcance

El artículo posiciona la coincidencia de cadenas basada en frecuencias no solo como una tarea de detección, sino como una base para primitivas de optimización combinatoria.

• Contribución Teórica: Conecta el problema clásico de coincidencia jumbled con la optimización de tipo empaquetamiento, proporcionando límites ajustados y algoritmos concisos.
• Utilidad Práctica: Los algoritmos están diseñados para el escaneo de un solo paso, lo que los hace adecuados para aplicaciones que requieren procesamiento en tiempo real o optimización bajo restricciones de recursos (por ejemplo, presupuestos de tokens en el procesamiento de texto).
• Modestia: Los autores declaran explícitamente que su enfoque está en las primitivas de detección y optimización más que en la construcción de índices para múltiples consultas. Reconocen que trabajos futuros podrían explorar extensiones ponderadas o aproximadas de MFSP, pero su contribución actual se limita estrictamente a soluciones exactas de tiempo lineal para los problemas definidos.

El trabajo concluye que, mediante el mantenimiento de las diferencias del vector de Parikh y el uso de estrategias simples de dos punteros o voraces, se pueden resolver variantes complejas de la coincidencia de permutaciones con una corrección demostrable y una complejidad de tiempo lineal óptima.