Saltar a contenido

LZSS

El algoritmo LZSS (Lempel-Ziv-Storer-Szymanski) fue propuesto en 1982 por James A. Storer y Thomas G. Szymanski. Es una variante del algoritmo LZ77 (propuesto por Abraham Lempel y Jacob Ziv en 1977) y fue diseñado para mejorar la eficiencia de la compresión al incluir un mecanismo que reduce el uso de bits cuando no se encuentran coincidencias en la ventana de búsqueda. La ventaja de este algoritmo reduce ampliamente el tamaño del archivo cuando hay muchas secuencias repetidas, no obstante, la compresión no es buena con datos con mucha variabilidad.

Funcionamiento

La compresión LZSS reemplaza patrones repetidos en un archivo con referencias a sus previas apariciones, guardando la información necesaria para reconstruir los datos originales. El funcionamiento del algoritmo se puede resumir en 2 pasos:

  1. LZSS va leyendo los datos, mientras no aparezca una secuencia repetida, guarda los caracteres originales.
  2. Cuando encuentra una secuencia que ya ha aparecido antes, guarda una referencia a la ubicación donde fue vista previamente.

Así, cada vez que se encuentra una repetición, se registra la distancia de desplazamiento desde hasta el punto de inicio de la secuencia repetida junto con la longitud, es decir, cuántos caracteres estan repetidos. En el algoritmo originalmente propuesto se guarda una referencia hacia atrás desde el punto en que se repite la secuencia (como en ejemplo mostrado a continuación), pero existen variaciones que, por ejemplo, guardan la distancia desde el inicio del texto (ejemplo interactivo en referencia 1).

Ventana deslizante

La ventana deslizante es una parte fundamental del funcionamiento del LZSS, ya que representa la sección del texto que se analiza en un momento dado. Esta ventana se mueve a medida que el algoritmo avanza y contiene una parte del texto ya procesado. Las repeticiones solo se buscan dentro de la ventana, lo que limita la búsqueda a las secuencias cercanas. El tamaño de la ventana es un factor importante: una ventana más grande permite encontrar repeticiones más largas y distantes, mejorando la compresión, pero también aumenta el uso de memoria. Una ventana más pequeña es más rápida y consume menos memoria, aunque puede reducir la efectividad de la compresión al no detectar tantas repeticiones.

Ejemplo

El siguiente ejemplo guarda referencias cada vez que exista una repetición de al menos 2 caracteres.

Texto original

a mi me gusta el tangananica y yo prefiero el tanganana

Texto comprimido

A mi<3, 2 > e gusta el <6, 2 > ng<3, 2 > anic<15, 2 > y<2, 2 > o prefier<9, 2 > e<29, 10 > a

Explicación

  1. LZSS comienza leyendo el texto desde el inicio y durante los primero 3 caracteres no ve ninguna repetición anterior, por lo que guarda el texto sin modificación "A mi"
  2. Luego de esto detecta un patrón conocido que corresponde a un espacio vacío, seguido de una "m", por lo que guarda la referencia <3,2> (3 caracteres atrás y por 2 caracteres)
  3. No detecta repeticiones por 11 caracteres "e gusta el"
  4. Detecta una repetición del texto "ta" y guarda la referencia <6,2>
  5. No detecta repeticiones por 2 caracteres "ng"
  6. Detecta una repetición de 2 caracteres "an" y guarda la referencia <3,2>
  7. Continua así hasta el final del texto donde encuentra una repetición de 10 caracteres, correspondientes a "tanganan", así guarda la referencia <29,10>
  8. Finalmente se guarda el ultimo carácter, el cual corresponde a una "a".

Código

El siguiente código guarda referencias cada vez que exista una repetición de al menos 2 caracteres y tiene un tamaño de ventana deslizantes de 4096 caracteres.

/* Código desarrollado con ChatGPT de OpenAI */

#include <iostream>
#include <vector>
#include <string>
#include <tuple>

#define BUFFER_SIZE 4096 // Tamaño del buffer
#define MIN_MATCH_LENGTH 2 // Longitud mínima para una referencia
#define MAX_MATCH_LENGTH 18 // Longitud máxima para una referencia

// Estructura para representar una referencia (offset, longitud)
struct Match {
    int offset;
    int length;
    char nextChar;
};

// Función para encontrar la mejor coincidencia en el buffer
std::tuple<int, int> findBestMatch(const std::string &buffer, const std::string &lookahead, int bufferStart) {
    int bestLength = 0;
    int bestOffset = 0;

    for (int i = bufferStart; i < buffer.size(); ++i) {
        int length = 0;
        while (length < lookahead.size() && buffer[i + length] == lookahead[length] && length < MAX_MATCH_LENGTH) {
            ++length;
        }
        if (length >= MIN_MATCH_LENGTH && length > bestLength) {
            bestLength = length;
            bestOffset = i;
        }
    }

    return {bestOffset, bestLength};
}

// Función para comprimir un texto usando LZSS
std::vector<Match> compressLZSS(const std::string &input) {
    std::vector<Match> compressed;
    int pos = 0;

    while (pos < input.size()) {
        std::string lookahead = input.substr(pos, MAX_MATCH_LENGTH);
        int bufferStart = std::max(0, pos - BUFFER_SIZE);
        std::string buffer = input.substr(bufferStart, pos - bufferStart);

        auto [bestOffset, bestLength] = findBestMatch(buffer, lookahead, 0);

        if (bestLength >= MIN_MATCH_LENGTH) {
            int offset = pos - (bufferStart + bestOffset);
            compressed.push_back({offset, bestLength, input[pos + bestLength]}); // Guarda la referencia correcta
            pos += bestLength + 1;
        } else {
            compressed.push_back({0, 0, input[pos]});
            ++pos;
        }
    }

    return compressed;
}

// Función para descomprimir un texto usando LZSS
std::string decompressLZSS(const std::vector<Match> &compressed) {
    std::string decompressed;
    for (const auto &m : compressed) {
        if (m.length > 0) {
            // Descomprimir utilizando el offset y la longitud
            int start = decompressed.size() - m.offset;
            for (int i = 0; i < m.length; ++i) {
                decompressed.push_back(decompressed[start + i]);
            }
            // Agregar el siguiente carácter
            decompressed.push_back(m.nextChar);
        } else {
            // Si no es una referencia, simplemente agregar el carácter
            decompressed.push_back(m.nextChar);
        }
    }
    return decompressed;
}

// Función auxiliar para mostrar el texto comprimido
void printCompressed(const std::vector<Match> &compressed) {
    for (const auto &m : compressed) {
        if (m.length > 0) {
            std::cout << "<" << m.offset << ", " << m.length << " > " << m.nextChar;
        } else {
            std::cout << m.nextChar;
        }
    }
    std::cout << endl;
}

int main() {
    std::string input;
    std::cout << "Ingrese el texto a comprimir: ";
    std::getline(std::cin, input);

    // Compresión
    std::vector<Match> compressed = compressLZSS(input);
    std::cout << "Texto comprimido: \n";
    printCompressed(compressed);

    // Descompresión
    std::string decompressed = decompressLZSS(compressed);
    std::cout << "Texto descomprimido: \n" << decompressed << std::endl;


    return 0;
}

Referencias

  1. CS Field Guide, "LZSS Compression Interactive", CS Field Guide. [Online]. Available: https://www.csfieldguide.org.nz/en/interactives/lzss-compression/.
  2. G. E. Blelloch, Introduction to Data Compression. Pittsburgh, PA, USA: Computer Science Department, Carnegie Mellon University, Jan. 2013. [Online]. Available: https://www.cs.cmu.edu/~guyb/realworld/papersDir/intro-data-compression.pdf.
  3. J. A. Storer and T. G. Szymanski, "Data Compression via Textual Substitution," Journal of the ACM (JACM), vol. 29, no. 4, pp. 928-951, Oct. 1982.
  4. “LZSS - The Hitchhiker's Guide to Compression.” [Online]. Available: https://go-compression.github.io/algorithms/lzss/.