Este artículo explora el algoritmo de compresión bzip, a menudo pasado por alto en favor de alternativas más populares como zstd o xz, pero que ofrece ventajas significativas en ciertos escenarios, particularmente cuando se trata de comprimir código fuente. El autor, enfrentando la necesidad de reducir el tamaño de archivos de código Lua dentro de un entorno de programación Minecraft (ComputerCraft), investigó diferentes algoritmos de compresión y descubrió que bzip superaba a los demás en términos de ratio de compresión, incluso superando a lzip.
La clave de la superioridad de bzip radica en su enfoque fundamentalmente diferente. Mientras que la mayoría de los algoritmos de compresión (gzip, zstd, xz, brotli, lzip) se basan en LZ77, un método que busca y reemplaza patrones repetidos en los datos, bzip utiliza la Transformada de Burrows-Wheeler (BWT). BWT reordena los caracteres de los datos para agrupar los que ocurren en contextos similares, lo que facilita la identificación y compresión de secuencias repetidas. Esto es especialmente efectivo con datos de tipo texto, como el código fuente, donde patrones y palabras clave se repiten con frecuencia. Por ejemplo, en lugar de buscar referencias a la palabra 'hello' dispersas, BWT agrupa todas las 'o's consecutivas que siguen a 'hell', simplificando la compresión.
El artículo también aborda la implementación práctica de bzip, destacando que bzip2 y bzip3 difieren principalmente en la forma en que comprimen la salida de BWT. Además, señala que los niveles de compresión (como -9 en bzip2) tienen un impacto limitado debido a la naturaleza determinista del algoritmo BWT, a diferencia de los algoritmos basados en LZ77 que utilizan heurísticas para optimizar la búsqueda de patrones. El autor incluso creó un codificador bzip2 ad-hoc para demostrar el potencial de mejora.
Finalmente, el artículo analiza el tamaño del decodificador. Los algoritmos basados en LZ77 tienden a tener decodificadores más grandes debido a la complejidad de la búsqueda de patrones. bzip, al evitar esta búsqueda, ofrece un decodificador más pequeño, aunque ligeramente más complejo. El autor estima el tamaño de los decodificadores de varios algoritmos, mostrando que bzip se sitúa en un punto intermedio, pero con el potencial de optimización para reducir aún más su tamaño. En resumen, bzip ofrece una excelente combinación de ratio de compresión y tamaño de decodificador, lo que lo convierte en una opción valiosa para la compresión de código fuente y otros datos de tipo texto.