Saltar a contenido

Re-Pair

Re-Pair, propuesto por Larsson y Moffat en el año 1999, es un algoritmo de compresión sin pérdida basado en gramáticas. Su nombre proviene de Recursive Pairing, debido a que su funcionamiento se basa en agrupar el par de símbolos adyacentes más frecuente de manera recursiva, reemplazándolo por un nuevo símbolo que no existe en el alfabeto inicial. Como resultado, se obtiene una gramática libre de contexto, donde todo par de símbolos adyacentes, aparece a lo más una vez.

Definición

Dado \(S[1..n]\), un texto de tamaño \(n\), sobre un alfabeto \(\Sigma\), de tamaño \(\sigma\); Re-Pair construirá una gramática libre de contexto a partir de S, siguiendo estos tres pasos:

  1. Escanear todos los pares de símbolos adyacentes de \(S\).
  2. Elegir el par que más se repite y reemplazarlo por un símbolo nuevo, que no pertenezca a \(\Sigma\), generando \(S'\). Si todos los pares aparecen a lo más una vez, termina.
  3. Volver a paso 1 con el nuevo texto \(S'\).

Por ejemplo, si tenemos el texto \(S = aaaabbcbbcbaab\), con \(n = 12\) y \(\Sigma = {a,b,c}\), como \(aa\) aparece la mayoría de veces, la reemplazamos por \(R_1 \rightarrow aa\) y obtenemos \(S' = R_1R_1bbcbbcbR_1b\). Repetimos este paso, obteniendo \(S'' = R_1R_2bcbbcbR_2\), luego de reemplazar \(R_2 \rightarrow R_1b\). Seguimos con \(S''' = R_1R_2R_3bR_3bR_2\), con la regla \(R_3 \rightarrow bc\). Y finalmente se obtiene \(S'''' = R_1R_2R_4R_4R_2\), con la regla \(R_4 \rightarrow R_3b\). En el ejemplo, la gramática obtenida es la siguiente:

  1. \(S \rightarrow R_1R_2R_4R_4R_2\)
  2. \(R_1 \rightarrow aa\)
  3. \(R_2 \rightarrow R_1b\)
  4. \(R_3 \rightarrow bc\)
  5. \(R_4 \rightarrow R_3b\)

Cabe notar que el resultado puede variar si existen empates en los pares de símbolos que más se repiten.

Para descomprimir, basta con procesar la regla principal (\(S\)) y cada vez que se encuentre una regla, reemplazarla por la correspondiente. Si llega a haber una regla que lleve a otra regla (como \(R\_2\)), hay que continuar con los reemplazos hasta que solo existan símbolos que son parte de \(\Sigma\).

Implementación

Una implementación eficiente propuesta escrita por Raymond Wan se encuentra disponible aquí. Para utilizarla, deben realizar los siguientes comandos (probado en Ubuntu 22.04 corriendo en WSL, con git versión 2.34.1, gcc versión 11.4.0 y cmake versión 3.22.1 para poder realizar el primer apartado).

git clone https://github.com/rwanwork/Re-Pair
cd Re-Pair
mkdir build
cd build
cmake ..
make

Con esto tendrás listo para utilizar el compresor y descompresor (ubicados en Re-Pair/build/src/). Ahora para comprimir, seguimos los siguientes pasos desde la caperta build:

cd src
./repair \-i \<filename\>

Esto creará dos archivos en Re-Pair/build/src/ llamados <filename>.prel y <filename>.seq los cuales poseen la jerarquía de la gramática y como separarla. Ambos archivos vienen codificados.

Para descomprimir, desde la carpeta build realizamos lo siguiente:

cd src
./despair \-i \<filename\>

Esto creará el archivo en Re-Pair/build/src/ llamado <filename>.u el cual es el archivo original que se comprimió.

Referencias

  1. N. J. Larsson and A. Moffat, "Offline Dictionary-Based Compression". Proc. IEEE, 88(11)1722-1732, November 2000.
  2. R. Wan. "Browsing and Searching Compressed Documents". PhD thesis, University of Melbourne, Australia, December 2003.