Este artículo explora los algoritmos de compresión de datos, motivado por la implementación de un broker de Kafka personalizado (MonKafka). La compresión es crucial para optimizar el almacenamiento y la transmisión de datos, ya que reduce el espacio requerido y el tiempo de procesamiento. Existen dos tipos principales: compresión sin pérdida, donde los datos se pueden reconstruir perfectamente, y compresión con pérdida, donde se sacrifica cierta precisión por una mayor reducción de tamaño (como en JPEG). El artículo se centra en la compresión sin pérdida y describe varias técnicas, incluyendo la codificación de longitud de ejecución (RLE), el algoritmo Lempel-Ziv (LZ) – el ancestro de DEFLATE y Snappy – y la codificación de Huffman.
La codificación de Huffman asigna códigos más cortos a los símbolos más frecuentes, ahorrando espacio. El artículo profundiza en el algoritmo GZIP, que utiliza DEFLATE, una combinación de LZ77 (o LZSS) y codificación de Huffman. DEFLATE es ampliamente utilizado en formatos como ZIP, DOCX y PNG. LZ77 funciona mediante referencias hacia atrás a secuencias previamente encontradas en un 'ventana deslizante', mientras que la codificación de Huffman optimiza la representación de símbolos basándose en su frecuencia. DEFLATE utiliza bloques de diferentes tipos: sin comprimir (Tipo 0), con códigos de Huffman fijos (Tipo 1) y con códigos de Huffman dinámicos (Tipo 2), estos últimos adaptándose a la frecuencia de los símbolos en cada bloque. La elección del tipo de bloque impacta en la eficiencia de la compresión.
Los algoritmos de compresión buscan optimizar tres métricas: la relación de compresión, la velocidad de compresión y la velocidad de descompresión. GZIP, al ser un formato de archivo, incluye un encabezado y un pie de página, además del bloque comprimido. El artículo también menciona la complejidad de la implementación de DEFLATE, ilustrada por una anécdota sobre los desarrolladores que, tras meses de trabajo, parecían estar al borde de la locura debido a las intrincadas manipulaciones a nivel de bits. En resumen, la comprensión de estos algoritmos es fundamental para optimizar el rendimiento de sistemas que manejan grandes volúmenes de datos.