Saltar a contenido

Deflate

Historia de su Creación

El algoritmo Deflate fue desarrollado por Phil Katz y publicado en 1996 en el documento RFC 1951 con el nombre DEFLATE Compressed Data Format Specification version 1.3. Katz lo diseñó como una combinación de los algoritmos de compresión LZ77 y codificación de Huffman, permitiendo una compresión sin pérdida de datos. Uno de los objetivos principales de Deflate era proporcionar un método eficiente y libre de restricciones de patentes, lo cual lo hizo ampliamente adoptado en herramientas como gzip y en el formato de archivos ZIP.

Funcionamiento del Algoritmo

Deflate es un algoritmo de compresión que emplea una combinación de técnicas eficaces y clásicas, LZ77 y codificación de Huffman, para lograr una compresión sin pérdida de datos. Su operación puede entenderse a través de sus dos fases principales:

1. Compresión LZ77

  • La fase LZ77 escanea el flujo de datos en busca de secuencias repetidas dentro de una ventana de datos previamente procesados. Esta ventana es típicamente de hasta 32 KB.
  • Cuando se detecta una secuencia que ya apareció antes en el flujo, esta puede reemplazarse por una referencia que indique cuántos bytes hacia atrás se encuentra la secuencia original y cuántos bytes tiene la secuencia repetida.
  • Por ejemplo, si en una parte de los datos aparece el texto "ABABABAB", LZ77 reemplaza cada repetición de "AB" después de la primera ocurrencia con una referencia a la posición anterior. Esto reduce el número de bytes necesarios para representar el texto, ya que utiliza referencias en lugar de almacenar cada ocurrencia completa.
  • La eficiencia de LZ77 depende de la cantidad de patrones repetidos y de la capacidad del algoritmo para encontrarlos dentro de la ventana de compresión.

2. Codificación de Huffman

  • Una vez comprimidos los datos con LZ77, Deflate utiliza la codificación de Huffman para asignar códigos de longitud variable a cada símbolo resultante, basándose en la frecuencia de aparición.
  • Los símbolos más frecuentes en el flujo de datos reciben códigos más cortos, mientras que los menos frecuentes reciben códigos más largos. De este modo, los datos comunes ocupan menos espacio, logrando una compresión adicional.
  • Deflate puede utilizar dos tipos de codificación de Huffman:
  • Codificación de Huffman fija: Utiliza una tabla de códigos de longitud fija que es igual para cualquier archivo.
  • Codificación de Huffman dinámica: Calcula una tabla específica para los datos del bloque, permitiendo mayor flexibilidad y mejor compresión en datos variables.

Ejemplo Detallado

Supongamos que queremos comprimir el texto ABABABABAB con el algoritmo Deflate. A continuación se muestra cómo se desarrollaría el proceso de compresión en cada una de las dos fases:

Fase de LZ77

  • Entrada: ABABABABAB
  • Proceso:
  • Deflate procesa la primera aparición de AB y la almacena tal cual.
  • Luego, detecta que la siguiente secuencia es también AB y, en lugar de almacenar AB de nuevo, la reemplaza por una referencia a la posición de la primera aparición de AB.
  • Este proceso continúa hasta el final del texto.
  • Resultado: El flujo de datos podría representarse como AB (2,2) (2,2) (2,2), donde (2,2) indica "vuelve 2 posiciones y lee 2 bytes". Esta representación usa menos datos que repetir AB en cada posición.

Fase de Codificación de Huffman

  • En esta fase, el flujo de datos transformado, es decir, AB (2,2) (2,2) (2,2), se codifica utilizando Huffman.
  • Como hay solo dos caracteres diferentes (A y B) y referencias ((2,2)), el algoritmo de Huffman asigna códigos binarios cortos a AB y a las referencias (2,2) debido a su alta frecuencia en los datos.
  • Codificación:
  • Supongamos que el código binario asignado a A es 0, a B es 1, y a (2,2) es 10.
  • Resultado: La secuencia completa podría representarse como una serie de bits compacta, algo así como 01 10 10 10, en lugar de almacenar los datos como texto sin comprimir.

Bloques en Deflate

Para administrar la compresión de datos, el algoritmo Deflate divide la información en bloques, donde cada bloque puede adoptar uno de los tres formatos de compresión mencionados:

  • Bloque sin compresión: Útil cuando los datos son difíciles de comprimir. Almacena los datos tal cual, sin comprimir.
  • Bloque con códigos de Huffman fijos: Utiliza una tabla de códigos estándar que asigna códigos predefinidos a los caracteres.
  • Bloque con códigos de Huffman dinámicos: Genera una tabla de códigos específica para el contenido del bloque, logrando una compresión más efectiva en algunos casos.

El resultado es un archivo comprimido que reduce significativamente el tamaño original, conservando toda la información para una descompresión sin pérdida.

Pseudocódigo de deflate

A continuación se presenta un código simplificado de deflate, ya que las implementaciones completas resultan demasiado largas.

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

// Estructura para almacenar una referencia LZ77 (distancia, longitud) o un símbolo literal.
struct LZ77Token {
    bool isLiteral;
    char literal;
    int distance;
    int length;
};

// Función para encontrar la coincidencia más larga en una ventana de 32 KB.
LZ77Token findLongestMatch(const std::string& window, const std::string& data, int pos) {
    int maxDistance = 0;
    int maxLength = 0;

    for (int dist = 1; dist <= window.size() && dist <= 32768; ++dist) {
        int length = 0;
        while (length < data.size() - pos && window[window.size() - dist + length] == data[pos + length]) {
            ++length;
        }

        if (length > maxLength) {
            maxDistance = dist;
            maxLength = length;
        }
    }

    // Si encontramos una coincidencia larga, devolvemos una referencia, si no, un literal.
    if (maxLength > 1) {
        return {false, '\0', maxDistance, maxLength};
    } else {
        return {true, data[pos], 0, 0};
    }
}

// Función para comprimir datos usando una versión simplificada de LZ77.
std::vector<LZ77Token> compressLZ77(const std::string& data) {
    std::string window;
    std::vector<LZ77Token> compressedData;

    for (int pos = 0; pos < data.size();) {
        // Busca la coincidencia más larga en la ventana.
        LZ77Token token = findLongestMatch(window, data, pos);

        // Agrega el token a la salida comprimida.
        compressedData.push_back(token);

        // Si es un literal, avanzamos una posición.
        // Si es una referencia, avanzamos según la longitud de la coincidencia.
        int advance = token.isLiteral ? 1 : token.length;
        window += data.substr(pos, advance);
        if (window.size() > 32768) {
            window = window.substr(window.size() - 32768);
        }
        pos += advance;
    }

    return compressedData;
}

// Función de ejemplo de codificación simple de Huffman para mostrar el proceso.
// Usa un mapa simple para asignar códigos fijos.
std::unordered_map<char, std::string> buildFixedHuffmanTable() {
    std::unordered_map<char, std::string> huffmanTable;
    // Códigos ficticios para ejemplo.
    huffmanTable['A'] = "00";
    huffmanTable['B'] = "01";
    huffmanTable['C'] = "10";
    huffmanTable['D'] = "11";
    return huffmanTable;
}

// Función para mostrar los datos comprimidos.
void printCompressedData(const std::vector<LZ77Token>& compressedData) {
    std::cout << "Datos comprimidos:\n";
    for (const auto& token : compressedData) {
        if (token.isLiteral) {
            std::cout << "Literal: " << token.literal << "\n";
        } else {
            std::cout << "Referencia: (Distancia=" << token.distance << ", Longitud=" << token.length << ")\n";
        }
    }
}

int main() {
    std::string data = "ABABABABCDCDCDABABABAB";
    std::vector<LZ77Token> compressedData = compressLZ77(data);

    // Imprimir el resultado de la compresión LZ77
    printCompressedData(compressedData);

    // Ejemplo de codificación de Huffman fija
    auto huffmanTable = buildFixedHuffmanTable();
    std::cout << "\nTabla de Huffman fija:\n";
    for (const auto& [symbol, code] : huffmanTable) {
        std::cout << symbol << " -> " << code << "\n";
    }

    return 0;
}
Deflate es un código que requiere un código de alta extensión, por lo que solo se presenta una versión simplificada. Para ver implementaciones más a detalle, adjunto en las referencias se encuentra un repositorio de Zlib en C, el cual es un algoritmo que funciona en base a deflate.

Importancia y Aplicaciones de Deflate

Gracias a su diseño libre de patentes y su capacidad para equilibrar eficiencia y calidad de compresión, Deflate se ha convertido en un estándar de facto en múltiples aplicaciones y formatos de archivo, como ZIP y gzip. La capacidad de compresión del algoritmo, junto con su estructura de bloques y el uso combinado de LZ77 y Huffman, lo hacen ideal para aplicaciones que requieren una compresión sin pérdida y alta eficiencia, especialmente en el contexto de archivos de texto y transferencia de datos en la web.

Referencias

  • Deutsch, L. P. (1996). DEFLATE Compressed Data Format Specification version 1.3 (RFC 1951). Network Working Group. https://datatracker.ietf.org/doc/html/rfc1951
  • Salomon, D., Motta, G., & Bryant, D. (2007). Data compression: The complete reference (4th ed.). Springer Science & Business Media.
  • Jean-loup Gailly and Mark Adler. (2011). zlib. GitHub. https://github.com/madler/zlib?tab=readme-ov-file
  • OpenAI. (2024). Código C++ simplificado para compresión con Deflate [Respuesta generada por IA]. ChatGPT. https://chat.openai.com/