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

8

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 Sde 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.nO(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 .O(n2)

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 ?O(n)O(n)O(n2)

Eff
fuente
Deberías hacer una pregunta más específica. Reiterar un artículo en diferentes palabras parece ser amplio para este sitio. ¿En qué parte del periódico te pierden los autores?
adrianN
@adrianN He escrito un poco más sobre lo que específicamente estoy confundido.
Eff
El documento asumió que usará la tabla hash y lo contó como O(n), que en este caso podría ser reemplazado por wlog por árbol de sufijos para ser O(n). Acabo de leer el texto, tu pregunta sigue siendo muy exigente, pero realmente no entiendo por qué gastaríasO(n2)Solo por un artículo.
Mal
@ Mal Entonces estás diciendo que uno podría construir un árbol de sufijos de S en Θ(n) tiempo (por cierto, todavía no entiendo cuándo es posible construir un árbol de sufijos en tiempo lineal y cuándo se necesita O(nlogn)) Luego encontramos la subcadena más frecuente en el árbol de sufijos enΘ(n)hora. ¿Correcto?
Eff
¿Yo? No. Pero Ukkonen dijo algunas palabras al respecto.O(n) para alfabeto de tamaño constante y O(nlogn)en general. Entonces podemos ordenar por frecuencias enO(nlogn)o incluso explotar pequeños números naturales para contar. No estoy seguro si algo 1 ~ n esΘ(n), lo siento, no hay respuesta para esa parte.
Mal

Respuestas:

1

Verifiqué el código, volví a leer el documento y parece que el algoritmo no funciona O(n)en la forma que has descrito.
Las llamadas recursivas de encontrar pares funcionan enO(nlogn)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 enO(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. 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: hayn personajes entonces n2 pares, entonces n4, n8, n16... Ves el patrón, hay 2n pares, pero de acuerdo con la descripción del algoritmo, este resultado O(nlogn+n) toma tiempo solo atravesar entradas.

Mal
fuente