Comprender la compresión / codificación en tiempo lineal

Estoy leyendo el artículo NJ Larsson, A. Moffat: Offline Dictionary-Based Compression , que describe un algoritmo de compresión que, si lo entiendo correctamente, es bastante similar a la codificación de pares de bytes .

Dada una cuerda $S$de longitud , estoy tratando de entender cómo se puede comprimir en tiempo lineal, , con este método de compresión. ¿Cómo se hace esto exactamente? He leído el documento, pero todavía no entiendo cómo logran el tiempo lineal, por lo que tal vez lo entendería explicado de una manera diferente.$n$$\mathcal O (n)$

Mi primera confusión surge en el primer paso en el algoritmo, donde encontramos que el par más común, por ejemplo, en abcababcabcel par más común absería reemplazado por un nuevo símbolo, digamos XcXXcXc. No entiendo cómo podemos encontrar el par más común lo suficientemente rápido. Mi enfoque ingenuo sería mirar primero el primer par aby luego contar el número de ocurrencias, luego mirar el siguiente par bcy contar el número de ocurrencias, etc. Sin embargo, esto ya daría solo para encontrar el par más común una vez .$\mathcal O (n^2)$

A continuación, incluso si entendiera cómo encontrar el par más común en el tiempo . Mi siguiente problema es que, ¿no tenemos que encontrar el par más común hasta veces? ¿Y por lo tanto esto daría un tiempo total de ?$\mathcal O(n)$$\mathcal O(n)$$\mathcal O(n^2)$

Verifiqué el código, volví a leer el documento y parece que el algoritmo no funciona $\mathcal O(n)$en la forma que has descrito.
Las llamadas recursivas de encontrar pares funcionan en$\mathcal O(n \log n)$dividido por constante si desea empacarlo hasta el final. De hecho, la estructura debajo mantiene punteros a la primera aparición de pares, divide la cola de pares por eventos para que sea eficiente, pero aún loglineal. Por otro lado, analizando el código escrito por Ph.D. estudiante del autor He descubierto varios trucos: la longitud de los pares (el nombre original) se da como parámetro (el valor predeterminado es 2) y la recurrencia está limitada por el parámetro, que puede descartar más llamadas (el valor predeterminado es de aproximadamente 5 niveles), con capacidad de hacer solo un pase o empujar hasta el final. El código predeterminado se ejecuta en$\mathcal O(n)$, pero no producirá una compresión óptima. También hay un interruptor para preferir memoria, tiempo o ser neutral.

El documento y el código muestran el uso de la tabla hash, que se ejecuta solo en el tiempo constante esperado, pero la función dada funciona muy bien con los caracteres. Además, el código limita la longitud de entrada mediante codificación constante.

Cambiar la tabla hash al árbol de sufijos y reescribir la parte de la recurrencia en pares parciales de mantenimiento de libros podría arrojar mejores resultados. No estoy seguro de si esto es posible. $\mathcal O(n)$, esta sería probablemente una pregunta diferente.

También se usa un truco para evitar que el espacio vacío atraviese: el inicio de puntos de bloque vacíos al primer personaje no vacío, pero esto solo acelera el desplazamiento, aún con tiempo loglineal. La parte responsable de este comportamiento es reemplazar los pares por el nuevo personaje cada iteración: mantener solo las reglas de reescritura y operarlas sería más rápido, pero aún así el acceso para verificar si se introdujeron nuevos pares requeriría verificar las reglas de reescritura contra las nuevas. en el caso de que construyamos un árbol binario completo con pares en las hojas de tal manera que después de reemplazar el par con un nuevo carácter y concatenar con el padre tengamos nuevos pares en las hojas hasta la raíz: hay$n$ personajes entonces $\frac{n}{2}$ pares, entonces $\frac{n}{4}$, $\frac{n}{8}$, $\frac{n}{16}$... Ves el patrón, hay $2n$ pares, pero de acuerdo con la descripción del algoritmo, este resultado $\mathcal O(n\log n + n)$ toma tiempo solo atravesar entradas.