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 $Σ$ , de tamaño $σ$ ; Re-Pair construirá una gramática libre de contexto a partir de S, siguiendo estos tres pasos:

Escanear todos los pares de símbolos adyacentes de $S$ .
Elegir el par que más se repite y reemplazarlo por un símbolo nuevo, que no pertenezca a $Σ$ , generando $S^{'}$ . Si todos los pares aparecen a lo más una vez, termina.
Volver a paso 1 con el nuevo texto $S^{'}$ .

Por ejemplo, si tenemos el texto $S = a a a a b b c b b c b a a b$ , con $n = 12$ y $Σ = a, b, c$ , como $a a$ aparece la mayoría de veces, la reemplazamos por $R_{1} \to a a$ y obtenemos $S^{'} = R_{1} R_{1} b b c b b c b R_{1} b$ . Repetimos este paso, obteniendo $S^{″} = R_{1} R_{2} b c b b c b R_{2}$ , luego de reemplazar $R_{2} \to R_{1} b$ . Seguimos con $S^{‴} = R_{1} R_{2} R_{3} b R_{3} b R_{2}$ , con la regla $R_{3} \to b c$ . Y finalmente se obtiene $S^{⁗} = R_{1} R_{2} R_{4} R_{4} R_{2}$ , con la regla $R_{4} \to R_{3} b$ . En el ejemplo, la gramática obtenida es la siguiente:

$S \to R_{1} R_{2} R_{4} R_{4} R_{2}$
$R_{1} \to a a$
$R_{2} \to R_{1} b$
$R_{3} \to b c$
$R_{4} \to R_{3} b$

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 $Σ$ .

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ó.

Experimentación

Se realizaron pruebas con textos obtenidos de PizzaChili, del Corpus no repetitivo (dna.100MB y sources.100MB) y del Corpus repetitivo (world_leaders y einstein.de). La siguiente tabla muestra el ratio de compresión de los textos con diferentes estrategias. Queda claro que RePair aprovecha la repetitividad del texto para obtener una mejor compresión (menor es mejor) comparado con gzip y bzip, pero obtiene peores resultados en textos no repetitivos.

*Texto*	*gzip*	*bzip*	*PizzaChili_RePair*	*RaymondWan_RePair*
dna.100MB	28.53%	22.84%	No reportado	29.49%
sources.100MB	32.51%	27.05%	No reportado	43.98%
world_leaders	17.78%	7.11%	1.78%	1.78%
einstein.de	31.46%	4.38%	0.16%	0.15%

Referencias

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