Saltar a contenido

Zstandard

Zstandard (Zstd) es un algoritmo de compresión sin pérdida desarrollado por Yann Collet en Facebook, con el objetivo de ofrecer una alta velocidad tanto en la compresión como en la descompresión. Zstd sobresale en su adaptabilidad, ya que permite ajustar los niveles de compresión en función de las necesidades específicas, con 22 niveles que van desde compresión rápida y ligera (Nivel 1) hasta una compresión más profunda, optimizada para archivos de gran tamaño (Nivel 22). Este enfoque escalable permite que Zstd se utilice en aplicaciones que van desde la transmisión de datos en tiempo real hasta el archivado de datos.

Definición

El algoritmo Zstd combina el esquema de compresión LZ77 con técnicas avanzadas de codificación y optimización para maximizar la eficiencia. A continuación, se detallan sus componentes principales:

  1. Codificacion de huffman: Tras identificar y reemplazar patrones con LZ77, Zstd aplica la codificación de Huffman, un algoritmo de codificación de entropía. Este paso reemplaza secuencias de símbolos con códigos de longitud variable, optimizando aún más el espacio requerido para almacenar los datos.
  2. Diccionarios entrenados: Zstd permite el uso de diccionarios personalizados, especialmente útiles cuando se trabaja con datos que tienen patrones repetitivos. Los diccionarios preentrenados contienen secuencias comunes y pueden mejorar significativamente la relación de compresión para datos similares o en series continuas.
  3. Modelo de coincidencia de largo plazo (Long Distance Matching): Zstd incluye una optimización para encontrar coincidencias en distancias mayores. En lugar de limitarse a una ventana deslizante de tamaño fijo determinado por LZ77, este modelo permite que el algoritmo detecte y comprima patrones repetidos que aparecen con una separación significativa.
  4. Codificación de entropía asimétrica (Asymmetric Numeral Systems, ANS): Aunque opcional y dependiente de configuraciones avanzadas, Zstd también admite ANS para reemplazar la codificación Huffman en ciertas circunstancias.

Implementación

A continuacion podemos ver un par de ejemplos de funciones en C++, que realizan llamados a la API de la libreria oficial Zstd, disponible open-source en GitHub 1

Compresión

bool compressFile(const std::string& inputFile, const std::string& outputFile, int compressionLevel = 3) {
    // Abrir el archivo de entrada
    std::ifstream in(inputFile, std::ios::binary | std::ios::ate);
    if (!in.is_open()) {
        std::cerr << "Error al abrir el archivo de entrada." << std::endl;
        return false;
    }

    // Leer el archivo en un buffer
    std::streamsize inputSize = in.tellg();
    in.seekg(0, std::ios::beg);
    std::vector<char> inputBuffer(inputSize);
    if (!in.read(inputBuffer.data(), inputSize)) {
        std::cerr << "Error al leer el archivo de entrada." << std::endl;
        return false;
    }
    in.close();

    // Estimar el tamaño máximo del buffer comprimido
    size_t maxCompressedSize = ZSTD_compressBound(inputSize);
    std::vector<char> compressedBuffer(maxCompressedSize);
    // Comprimir los datos
    size_t compressedSize = ZSTD_compress(compressedBuffer.data(), maxCompressedSize, inputBuffer.data(), inputSize, compressionLevel);
    if (ZSTD_isError(compressedSize)) {
        std::cerr << "Error al comprimir los datos: " << ZSTD_getErrorName(compressedSize) << std::endl;
        return false;
    }

    // Guardar los datos comprimidos en el archivo de salida
    std::ofstream out(outputFile, std::ios::binary);
    if (!out.is_open()) {
        std::cerr << "Error al abrir el archivo de salida." << std::endl;
        return false;
    }

    out.write(compressedBuffer.data(), compressedSize);
    out.close();
    std::cout << "Compresión exitosa. Tamaño original: " << inputSize << " bytes, Tamaño comprimido: " << compressedSize << " bytes." << std::endl;
    return true;
}

Descompresión

bool decompressFile(const std::string& inputFile, const std::string& outputFile) {
    // Abrir el archivo comprimido
    std::ifstream in(inputFile, std::ios::binary | std::ios::ate);
    if (!in.is_open()) {
        std::cerr << "Error al abrir el archivo comprimido." << std::endl;
        return false;
    }

    // Obtener el tamaño del archivo comprimido
    std::streamsize compressedSize = in.tellg();
    in.seekg(0, std::ios::beg);
    std::vector<char> compressedBuffer(compressedSize);
    if (!in.read(compressedBuffer.data(), compressedSize)) {
        std::cerr << "Error al leer el archivo comprimido." << std::endl;
        return false;
    }
    in.close();

    // Estimar el tamaño máximo del archivo descomprimido
    size_t decompressedSize = ZSTD_getFrameContentSize(compressedBuffer.data(), compressedSize);
    if (decompressedSize == ZSTD_CONTENTSIZE_ERROR || decompressedSize == ZSTD_CONTENTSIZE_UNKNOWN) {
        std::cerr << "No se pudo determinar el tamaño del archivo descomprimido." << std::endl;
        return false;
    }

    // Crear un buffer para los datos descomprimidos
    std::vector<char> decompressedBuffer(decompressedSize);

    // Descomprimir los datos
    size_t actualDecompressedSize = ZSTD_decompress(decompressedBuffer.data(), decompressedSize, compressedBuffer.data(), compressedSize);
    if (ZSTD_isError(actualDecompressedSize)) {
        std::cerr << "Error al descomprimir los datos: " << ZSTD_getErrorName(actualDecompressedSize) << std::endl;
        return false;
    }

    // Guardar los datos descomprimidos en el archivo de salida
    std::ofstream out(outputFile, std::ios::binary);
    if (!out.is_open()) {
        std::cerr << "Error al abrir el archivo de salida." << std::endl;
        return false;
    }
    out.write(decompressedBuffer.data(), actualDecompressedSize);
    out.close();

    std::cout << "Descompresión exitosa. Tamaño comprimido: " << compressedSize << " bytes, Tamaño descomprimido: " << actualDecompressedSize << " bytes." << std::endl;
    return true;
}

Ejemplo

La tabla a continuación muestra los tamaños de varios archivos después de aplicar el algoritmo Zstandard con diferentes niveles de compresión. Los archivos fueron seleccionados para observar la eficiencia de compresión en diferentes tipos de contenido:

Tamaño Original Nivel de compresion 1 Nivel de compresion 5 Nivel de compresion 22
160400 Bytes (txt) 50291 Bytes 47933 Bytes 45484 Bytes
2307371 Bytes (pdf) 2274972 Bytes 2261866 Bytes 2251262 Bytes
288193 Bytes (png) 288211 Bytes 288211 Bytes 246225 Bytes

Como se observa, la compresión es altamente eficiente en archivos de texto, donde se logran reducciones significativas en tamaño al aumentar el nivel de compresión. Esto se debe a la redundancia inherente en los datos de texto, lo que facilita una mayor compactación. En el caso de los archivos PDF, la reducción es menos notoria, ya que estos contienen datos comprimidos previamente y, por tanto, ofrecen menos oportunidad para una compresión adicional. En cuanto a los archivos PNG, que ya utilizan un método de compresión propio sin pérdidas, el tamaño apenas varía, y solo a niveles de compresión altos de Zstd se observa una ligera reducción.

Referencias

  1. Facebook (2016). zstd ↩