Reparar
Re-Pair (abreviatura de Recursive Pairing) es un algoritmo de compresión basado en la gramática que, dado un texto de entrada, construye un programa de línea recta , es decir, una gramática libre de contexto que genera una sola cadena: el texto de entrada. La gramática se construye reemplazando de forma recursiva el par de caracteres más frecuentes que aparecen en el texto. Una vez que no hay un par de caracteres que se produzcan dos veces, la cadena resultante se utiliza como axioma de la gramática. Por lo tanto, la gramática de salida es tal que todas las reglas excepto el axioma tienen dos símbolos en el lado derecho.
En su artículo, el algoritmo se presenta 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 altas relaciones de compresión y ofrece un buen rendimiento para la descompresión. Sin embargo, el mayor inconveniente del algoritmo es su consumo de memoria, que es aproximadamente 5 veces el tamaño de la entrada. Este uso de memoria es necesario para realizar la compresión en tiempo lineal, pero hace que el algoritmo no sea práctico para comprimir archivos grandes.
La imagen de la derecha muestra cómo funciona el algoritmo comprime la cadena .
