LZW (Lempel-Ziv-Welch)

Definición

El algoritmo LZW fue publicado en 1984 por Terry Welch como una mejora del algoritmo LZ78, desarrollado previamente por Abraham Lempel y Jacob Ziv. Es un método de compresión de datos sin pérdida que se basa en la codificación de secuencias repetidas. Su propósito es reducir el tamaño de los archivos mediante el almacenamiento más eficiente de patrones redundantes en los datos. LZW se utiliza en varios formatos de archivos, incluyendo GIF y TIFF, debido a su capacidad para comprimir datos de manera eficaz sin perder información.

La principal ventaja de LZW en comparación con sus predecesores, radica en su capacidad de construir y utilizar un diccionario eficiente sin necesidad de almacenar explícitamente punteros a posiciones previas del texto. Esto hace que tenga un rendimiento superior en escenarios donde se espera una alta redundancia en secuencias de datos.

Funcionamiento:

Compresión:

Inicialización del diccionario - Se inicia con un diccionario que contiene todas las secuencias posibles de un solo carácter del conjunto de entrada. Por ejemplo, si estamos trabajando con caracteres ASCII, el diccionario inicial contendría todos los caracteres individuales (con sus códigos asociados) comenzando desde 0. Asignación de variables:

Asignación de variables

Se asigna la cadena W como una cadena vacía o nula.
K es el carácter actual que se está leyendo del archivo.
WK es la concatenación de W y K.
Proceso de lectura y compresión:

Proceso de lectura y compresión

Se lee el primer carácter del archivo y se asigna a K.
Luego se concatena W con K para formar WK.
Si WK ya está en el diccionario, entonces se actualiza W con el valor de WK (ya que es una secuencia válida en el diccionario).

Actualización del diccionario

Si al concatenar W y K (WK) no se encuentra en el diccionario:
- Se emite el código asociado a W (la secuencia válida más larga encontrada hasta el momento).
- Se agrega WK al diccionario con un nuevo código.
- Se asigna K a W, y se sigue leyendo el siguiente carácter, que se convertirá en el nuevo K.

Repetición del proceso

El algoritmo continúa leyendo los caracteres del archivo, concatenando con W para formar nuevas cadenas WK y actualizando el diccionario según sea necesario.
A medida que se agregan nuevas entradas al diccionario, este crece y puede contener secuencias de dos, tres o más caracteres, dependiendo de las repeticiones encontradas en el texto.

Finalización

Este proceso se repite hasta que no quedan más caracteres que leer del archivo. Al final, se emite el código correspondiente a la última secuencia almacenada en W.

El diccionario va creciendo dinámicamente con nuevas secuencias que se encuentran durante la lectura del archivo, comenzando con cadenas de dos caracteres y eventualmente extendiéndose a secuencias más largas si esas combinaciones se repiten en los datos de entrada.

K es el carácter actual, y WK representa la concatenación de W (la secuencia válida más larga leída hasta el momento) con K. Siempre que no se encuentra una concatenación WK en el diccionario, se imprime el código asociado a W y se agrega WK al diccionario.

Descompresión: Es el proceso inverso, donde se interpreta cada código en la secuencia comprimida para reconstruir el texto original, actualizando el diccionario a medida que se encuentran nuevos patrones.

Inicialización del diccionario

Al igual que en la codificación, se empieza con un diccionario que contiene todas las secuencias de un solo carácter del conjunto de entrada.

Lectura de códigos

Se lee el primer código y se traduce al carácter correspondiente en el diccionario, estableciéndolo como la primera salida y como la cadena W.

Para cada código subsiguiente, se sigue uno de estos casos:
- Si el código está en el diccionario:
  - Se obtiene la secuencia correspondiente al código y se agrega a la salida.
  - K se convierte en la primera letra de esta secuencia.
  - Se agrega la concatenación W + K al diccionario.
  - W se actualiza con el valor de la secuencia encontrada.
- Si el código no está en el diccionario:
  - Esto ocurre si la secuencia no se ha visto antes, indicando que la secuencia actual es W + W[0].
  - Se agrega esta secuencia W + W[0] al diccionario y a la salida.
  - Se actualiza W con esta nueva secuencia.

Repetición hasta el final:

Este proceso se repite hasta que no hay más códigos por leer en la secuencia comprimida.

De esta forma, el diccionario se va llenando con secuencias a medida que se leen los códigos, reconstruyendo el texto sin pérdida de información.

2. Implementación del Algoritmo

A continuación se presentan implementaciones en C++ de compresión y decodificación.

Codificación

int LZWEncodeFile(FILE *fpIn, FILE *fpOut)
{
    bit_file_t *bfpOut;                 /* encoded output */

    unsigned int code;                  /* code for current string */
    unsigned char currentCodeLen;       /* length of the current code */
    unsigned int nextCode;              /* next available code index */
    int c;                              /* character to add to string */

    dict_node_t *dictRoot;              /* root of dictionary tree */
    dict_node_t *node;                  /* node of dictionary tree */

    /* validate arguments */
    if ((NULL == fpIn) || (NULL == fpOut))
    {
        errno = ENOENT;
        return -1;
    }

    /* convert output file to bitfile */
    bfpOut = MakeBitFile(fpOut, BF_WRITE);

    if (NULL == bfpOut)
    {
        perror("Making Output File a BitFile");
        return -1;
    }

    /* initialize dictionary as empty */
    dictRoot = NULL;

    /* start MIN_CODE_LEN bit code words */
    currentCodeLen = MIN_CODE_LEN;

    nextCode = FIRST_CODE;  /* code for next (first) string */

    /* now start the actual encoding process */

    c = fgetc(fpIn);

    if (EOF == c)
    {
        return -1;      /* empty file */
    }
    else
    {
        code = c;       /* start with code string = first character */
    }

    /* create a tree root from 1st 2 character string */
    if ((c = fgetc(fpIn)) != EOF)
    {
        /* special case for NULL root */
        dictRoot = MakeNode(nextCode, code, c);

        if (NULL == dictRoot)
        {
            perror("Making Dictionary Root");
            BitFileToFILE(bfpOut);
            return -1;
        }

        nextCode++;

        /* write code for 1st char */
        PutCodeWord(bfpOut, code, currentCodeLen);

        /* new code is just 2nd char */
        code = c;
    }

    /* now encode normally */
    while ((c = fgetc(fpIn)) != EOF)
    {
        /* look for code + c in the dictionary */
        node = FindDictionaryEntry(dictRoot, code, c);

        if ((node->prefixCode == code) &&
            (node->suffixChar == c))
        {
            /* code + c is in the dictionary, make it's code the new code */
            code = node->codeWord;
        }
        else
        {
            /* code + c is not in the dictionary, add it if there's room */
            if (nextCode < MAX_CODES)
            {
                dict_node_t *tmp;

                tmp = MakeNode(nextCode, code, c);

                if (NULL == dictRoot)
                {
                    perror("Making Dictionary Node");
                    FreeTree(dictRoot);
                    BitFileToFILE(bfpOut);
                    return -1;
                }

                nextCode++;

                if (MakeKey(code, c) <
                    MakeKey(node->prefixCode, node->suffixChar))
                {
                    node->left = tmp;
                }
                else
                {
                    node->right = tmp;
                }
            }
            else
            {
                fprintf(stderr, "Error: Dictionary Full\n");
            }

            /* are we using enough bits to write out this code word? */
            while ((code >= (CURRENT_MAX_CODES(currentCodeLen) - 1)) &&
                (currentCodeLen < MAX_CODE_LEN))
            {
                /* mark need for bigger code word with all ones */
                PutCodeWord(bfpOut, (CURRENT_MAX_CODES(currentCodeLen) - 1),
                    currentCodeLen);
                currentCodeLen++;
            }

            /* write out code for the string before c was added */
            PutCodeWord(bfpOut, code, currentCodeLen);

            /* new code is just c */
            code = c;
        }
    }

    /* no more input.  write out last of the code. */
    PutCodeWord(bfpOut, code, currentCodeLen);

    /* we've encoded everything, free bitfile structure */
    BitFileToFILE(bfpOut);

    /* free the dictionary */
    FreeTree(dictRoot);

    return 0;
}

Decodificación

int LZWDecodeFile(FILE *fpIn, FILE *fpOut)
{
    bit_file_t *bfpIn;                  /* encoded input */

    unsigned int nextCode;              /* value of next code */
    unsigned int lastCode;              /* last decoded code word */
    unsigned int code;                  /* code word to decode */
    unsigned char currentCodeLen;       /* length of code words now */
    unsigned char c;                    /* last decoded character */

    /* validate arguments */
    if ((NULL == fpIn) || (NULL == fpOut))
    {
        errno = ENOENT;
        return -1;
    }

    /* convert input file to bitfile */
    bfpIn = MakeBitFile(fpIn, BF_READ);

    if (NULL == bfpIn)
    {
        perror("Making Input File a BitFile");
        return -1;
    }

    /* start MIN_CODE_LEN bit code words */
    currentCodeLen = MIN_CODE_LEN;

    /* initialize for decoding */
    nextCode = FIRST_CODE;  /* code for next (first) string */

    /* first code from file must be a character.  use it for initial values */
    lastCode = GetCodeWord(bfpIn, currentCodeLen);
    c = lastCode;
    fputc(lastCode, fpOut);

    /* decode rest of file */
    while ((int)(code = GetCodeWord(bfpIn, currentCodeLen)) != EOF)
    {

        /* look for code length increase marker */
        while (((CURRENT_MAX_CODES(currentCodeLen) - 1) == code) &&
            (currentCodeLen < MAX_CODE_LEN))
        {
            currentCodeLen++;
            code = GetCodeWord(bfpIn, currentCodeLen);
        }

        if (code < nextCode)
        {
            /* we have a known code.  decode it */
            c = DecodeRecursive(code, fpOut);
        }
        else
        {
            /***************************************************************
            * We got a code that's not in our dictionary.  This must be due
            * to the string + char + string + char + string exception.
            * Build the decoded string using the last character + the
            * string from the last code.
            ***************************************************************/
            unsigned char tmp;

            tmp = c;
            c = DecodeRecursive(lastCode, fpOut);
            fputc(tmp, fpOut);
        }

        /* if room, add new code to the dictionary */
        if (nextCode < MAX_CODES)
        {
            dictionary[nextCode - FIRST_CODE].prefixCode = lastCode;
            dictionary[nextCode - FIRST_CODE].suffixChar = c;
            nextCode++;
        }

        /* save character and code for use in unknown code word case */
        lastCode = code;
    }

    /* we've decoded everything, free bitfile structure */
    BitFileToFILE(bfpIn);

    return 0;
}

Ejemplo de uso

Supongamos que queremos comprimir la cadena de texto: ABABABA

Paso 1: Inicialización del diccionario

Al iniciar, el diccionario contiene solo los caracteres individuales de nuestro conjunto de entrada, cada uno con su propio código.

Código	Entrada
65	A
66	B

Paso 2: Compresión paso a paso

Vamos a ir recorriendo la cadena y construyendo secuencias para ir agregándolas al diccionario y generando la salida comprimida. Usaremos tres variables clave: - W: la secuencia válida más larga hasta el momento. - K: el carácter actual que se está leyendo. - WK: concatenación de W y K.

1. Leer el primer carácter A - W = "" (inicialmente vacío) - K = A - Concatenación WK = A - Salida: Aún nada - W = A ya está en el diccionario, por lo tanto se actualiza W = A

2. Leer el segundo carácter B - K = B - Concatenación WK = AB - AB no está en el diccionario. - Salida: código de W = A → 65 - Agregamos AB al diccionario y le damos un nuevo código, 256.

Código	Entrada
65	A
66	B
256	AB

Actualizar W = B.

3. Leer el siguiente carácter A - K = A - Concatenación WK = BA - BA no está en el diccionario. - Salida: código de W = B → 66 - Agregamos BA al diccionario con un nuevo código, 257.

Código	Entrada
65	A
66	B
256	AB
257	BA

Actualizar W = A.

4. Leer el siguiente carácter B - K = B - Concatenación WK = AB - AB ya está en el diccionario. - Actualizar W = AB

5. Leer el siguiente carácter A - K = A - Concatenación WK = ABA - ABA no está en el diccionario. - Salida: código de W = AB → 256 - Agregamos ABA al diccionario con un nuevo código, 258.

Código	Entrada
65	A
66	B
256	AB
257	BA
258	ABA

Actualizar W = A.

6. Leer el último carácter B - K = B - Concatenación WK = AB - AB ya está en el diccionario. - Actualizar W = AB

Paso 3: Finalización No quedan más caracteres para leer. El último valor de W es AB, y se emite su código.

Salida final: código de W = AB → 256

Resultado La cadena de salida comprimida será: 65, 66, 256, 256

Diccionario final: Al finalizar la compresión, el diccionario tiene las siguientes entradas:

Código	Entrada
65	A
66	B
256	AB
257	BA
258	ABA

La salida comprimida (65, 66, 256, 256) es una versión compacta de la secuencia original. Gracias al diccionario generado, es posible reconstruir la secuencia completa sin pérdida de información.

3. Usos Comunes

LZW se usa en diversas aplicaciones de compresión sin pérdida debido a su eficiencia en la reducción de tamaño en datos repetitivos.

Imágenes y gráficos:

Formato GIF: LZW es el algoritmo de compresión que subyace en el formato de imágenes GIF. Es especialmente efectivo en imágenes con áreas de color sólido y repetitivo, como gráficos y logotipos. La compresión reduce el tamaño del archivo sin perder calidad.
Formato TIFF: En archivos TIFF, LZW se usa como una opción de compresión para gráficos de alta calidad y documentos escaneados que necesitan conservar detalles sin pérdida de datos. Compresión de archivos:
Compresores de archivos (Unix compress): El comando compress en sistemas Unix y Linux originalmente usaba LZW para reducir el tamaño de archivos en sistemas de almacenamiento, siendo un precursor de otros métodos como gzip.

Impresoras y transmisión de datos:

-Fuentes de impresoras: Algunas impresoras utilizan LZW para comprimir las fuentes y así reducir el tiempo y el ancho de banda necesario para enviar archivos de impresión. -Transmisión de datos: En protocolos antiguos de transmisión de datos, LZW se usaba para reducir la cantidad de datos transmitidos, acelerando así las velocidades de comunicación en redes de baja capacidad.

Documentos y archivos digitales:

Almacenamiento de documentos electrónicos: Cuando se almacenan grandes cantidades de documentos escaneados o digitalizados, LZW se puede usar para reducir el tamaño sin perder calidad en archivos de texto e imágenes.
LZW es especialmente útil cuando se requiere que la compresión sea rápida y eficiente, sin sacrificar calidad ni datos, y sigue siendo una técnica relevante en contextos donde se manejan archivos gráficos, documentación digital y comunicaciones de datos.

4. Referencias

GeeksforGeeks. (2024, 21 de mayo). LZW (Lempel–Ziv–Welch) compression technique. GeeksforGeeks. https://www.geeksforgeeks.org/lzw-lempel-ziv-welch-compression-technique/
Dipperstein, M. (n.d.). lzw: A simple LZW compression implementation [Repositorio de GitHub]. GitHub. https://github.com/MichaelDipperstein/lzw -Madrid, J. M. (2015, 15 de febrero). Algoritmo LZW - Compresión [Video]. YouTube. https://www.youtube.com/watch?v=8Hxo1bPPgCU -Madrid, J. M. (2015, 25 de febrero). Algoritmo LZW - Descompresión [Video]. YouTube. https://www.youtube.com/watch?v=fiAReFNIrKc
Wikipedia. LZW. En Wikipedia, La enciclopedia libre. https://es.wikipedia.org/wiki/LZW
Gastaldo Ramon, B. (24 de julio de 2014). Estudio de implementación del algoritmo LZW (Lempel-Ziv-Welch) en una plataforma Zynq 7000 de Xilinx Tesis de licenciatura. Universitat Politècnica de València.