Reparar

Algoritmo de compresión de datos sin pérdida, pero que consume memoria

Re-Pair (abreviatura de recursive pairing ) es un algoritmo de compresión basado en gramática que, dado un texto de entrada, construye un programa lineal , es decir, una gramática libre de contexto que genera una única cadena: el texto de entrada. Para realizar la compresión en tiempo lineal, consume una cantidad de memoria que es aproximadamente cinco veces el tamaño de su entrada.

La gramática se construye reemplazando recursivamente el par de caracteres que aparece con mayor frecuencia en el texto. Si no hay ningún par de caracteres que aparezca dos veces, la cadena resultante se utiliza como axioma de la gramática. Por lo tanto, la gramática resultante es tal que todas las reglas, excepto el axioma, tienen dos símbolos en el lado derecho.

Cómo funciona

Construcción de un programa de línea recta que genera la cadena w="xabcabcy123123zabc" mediante el uso de Re-Pair

Re-Pair fue introducido por primera vez por NJ. Larsson y A. Moffat ^[1] en 1999.

En su artículo, se presenta el algoritmo junto con una descripción detallada de las estructuras de datos necesarias para implementarlo con una complejidad lineal en el tiempo y el espacio. Los experimentos demostraron que Re-Pair logra altos índices de compresión y ofrece un buen rendimiento para la descompresión. Sin embargo, el principal inconveniente del algoritmo es su consumo de memoria, que es aproximadamente 5 veces el tamaño de la entrada. Tal uso de memoria es necesario para realizar la compresión en tiempo lineal, pero hace que el algoritmo sea poco práctico para comprimir archivos grandes.

La imagen de la derecha muestra cómo funciona el algoritmo que comprime la cadena . ${\displaystyle w=xabcabcy123123zabc}$

Durante la primera iteración, el par , que aparece tres veces en , se reemplaza por un nuevo símbolo . En la segunda iteración, el par más frecuente en la cadena , que es , se reemplaza por un nuevo símbolo . Por lo tanto, al final de la segunda iteración, la cadena restante es . En las siguientes dos iteraciones, los pares y se reemplazan por los símbolos y respectivamente. Finalmente, la cadena no contiene ningún par repetido y, por lo tanto, se utiliza como axioma de la gramática de salida. ${\displaystyle ab}$ ${\displaystyle w}$ ${\displaystyle R_{1}}$ ${\displaystyle w=xR_{1}cR_{1}cy123123zR_{1}c}$ ${\displaystyle R_{1}c}$ ${\displaystyle R_{2}}$ ${\displaystyle w=xR_{2}R_{2}y123123zR_{2}}$ ${\displaystyle 12}$ ${\displaystyle R_{3}3}$ ${\displaystyle R_{3}}$ ${\displaystyle R_{4}}$ ${\displaystyle w=xR_{2}R_{2}yR_{4}R_{4}zR_{2}}$

Estructuras de datos

Para lograr una complejidad temporal lineal, Re-Pair requiere las siguientes estructuras de datos

• Una secuencia que representa la cadena de entrada. La posición de la secuencia contiene el i -ésimo símbolo de la cadena de entrada más dos referencias a otras posiciones en la secuencia. Estas referencias apuntan a las posiciones siguiente/anterior, por ejemplo y , de modo que la misma subcadena comience en , y y las tres ocurrencias sean capturadas por la misma referencia (es decir, hay una variable en la gramática que genera la cadena). ${\displaystyle i}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle w[i]}$ ${\displaystyle w[k]}$ ${\displaystyle w[m]}$
• Una cola de prioridad . Cada elemento de la cola es un par de símbolos (terminales o pares definidos previamente) que aparecen consecutivamente en la secuencia. La prioridad de un par está dada por el número de ocurrencias del par en la secuencia restante. Cada vez que se crea un nuevo par, se actualiza la cola de prioridad.
• Una tabla hash para realizar un seguimiento de los pares ya definidos. Esta tabla se actualiza cada vez que se crea o elimina un nuevo par.

Dado que la tabla hash y la cola de prioridad hacen referencia a los mismos elementos (pares), se pueden implementar mediante una estructura de datos común denominada PAIR con punteros para la tabla hash (h_next) y la cola de prioridad (p_next y p_prev). Además, cada PAIR apunta al comienzo de la primera (f_pos) y la última (b_pos) ocurrencias de la cadena representada por el PAIR en la secuencia. La siguiente imagen muestra una descripción general de esta estructura de datos.

Las siguientes dos imágenes muestran un ejemplo de cómo se ven estas estructuras de datos después de la inicialización y después de aplicar un paso del proceso de emparejamiento (no se muestran los punteros a NULL):

Codificación de la gramática

Una vez que se ha construido la gramática para una cadena de entrada dada, para lograr una compresión efectiva, esta gramática debe codificarse de manera eficiente. Uno de los métodos más simples para codificar la gramática es la codificación implícita , que consiste en invocar la función encodeCFG(X), descrita a continuación, de manera secuencial sobre todos los símbolos del axioma. Intuitivamente, las reglas se codifican a medida que se visitan en un recorrido en profundidad de la gramática. La primera vez que se visita una regla, su lado derecho se codifica de manera recursiva y se le asigna un nuevo código. A partir de ese punto, cada vez que se alcanza la regla, se escribe el valor asignado.

num_rules_encoded = 256 // De forma predeterminada, los caracteres ASCII extendidos son las terminales de la gramática.   writeSymbol ( símbolo s ) { bitslen = log ( num_rules_encoded ); // Inicialmente 8, para describir cualquier carácter ASCII extendido escribe s en binario usando bitslen bits }             void encodeCFG_rec ( símbolo s ) { if ( s no es terminal y esta es la primera vez que aparece el símbolo s ) { tomar regla s → X Y ; escribir bit 1 ; encodeCFG_rec ( X ); encodeCFG_rec ( Y ) ; asignar al símbolo s valor ++ num_rules_encoded ; } else { escribir bit 0 ; writeSymbol ( terminal / valor asignado ) } }                                           void encodeCFG ( símbolo s ) { encodeCFG_rec ( s ); escribir bit 1 ; }       

Otra posibilidad es separar las reglas de la gramática en generaciones de modo que una regla pertenezca a la generación si y solo si al menos una de o pertenece a la generación y la otra pertenece a la generación con . Luego, estas generaciones se codifican posteriormente a partir de la generación . Este fue el método propuesto originalmente cuando se introdujo Re-Pair por primera vez. Sin embargo, la mayoría de las implementaciones de Re-Pair utilizan el método de codificación implícita debido a su simplicidad y buen rendimiento. Además, permite la descompresión sobre la marcha. ${\displaystyle X\to YZ}$ ${\displaystyle i}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle i-1}$ ${\displaystyle j}$ ${\displaystyle j\leq i-1}$ ${\displaystyle 0}$

Versiones

Existen varias implementaciones diferentes de Re-Pair. Cada una de estas versiones tiene como objetivo mejorar un aspecto específico del algoritmo, como reducir el tiempo de ejecución, reducir el consumo de espacio o aumentar la tasa de compresión.

Véase también

• Codificación de pares de bytes
• Algoritmo Sequitur

Referencias

1. Larsson, NJ, y Moffat, A. (2000). Compresión basada en diccionarios fuera de línea. Actas del IEEE, 88(11), 1722–1732.
2. R. Wan. "Exploración y búsqueda de documentos comprimidos". Tesis doctoral, Universidad de Melbourne, Australia, diciembre de 2003.
3. Satoshi Yoshida y Takuya Kida, Codificación efectiva de longitud variable a longitud fija mediante un algoritmo de re-emparejamiento, en Proc. of Data Compression Conference 2013 (DCC 2013), pág. 532, Snowbird, Utah, EE. UU., marzo de 2013.
4. Bille, P., Gørtz, IL y Prezza, N. (abril de 2017). Compresión de reparación que ahorra espacio. En 2017 (DCC) (págs. 171-180). IEEE.
5. Gańczorz, M., y Jeż, A. (abril de 2017). Mejoras en el compresor gramatical Re-Pair. En la Conferencia de compresión de datos (DCC) de 2017 (pp. 181-190). IEEE.
6. Furuya, I., Takagi, T., Nakashima, Y., Inenaga, S., Bannai, H. y Kida, T. (2018). MR-RePair: compresión gramatical basada en repeticiones máximas. Preimpresión de arXiv arXiv:1811.04596.