Saltar a contenido

LZW

Definición

El algoritmo LZW (Lempel-Ziv-Welch) 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.

Compresión

Se toma una secuencia de entrada y se reemplaza por una secuencia más corta al ser comprimida. Durante este proceso, se crea y actualiza un diccionario que almacena patrones repetidos a medida que se identifican en los datos, reduciendo la redundancia y el tamaño de la información. El diccionario se inicializa con códigos únicos que corresponden a caracteres individuales (por ejemplo, ASCII o Unicode).

1. Inicialización del diccionario
Se crea un diccionario vacío, y se le añaden todas las cadenas de un solo carácter del alfabeto de entrada con sus códigos correspondientes.

2. Creación de variables
Se crean tres variables:

  • Un arreglo vacío w para almacenar la cadena actual.
  • Un arreglo vacío k para almacenar el siguiente carácter leído.
  • Un arreglo vacío s para almacenar los códigos generados.

3. Procesar caracteres de entrada Mientras haya caracteres en la entrada:

  • 3.1. Leer el siguiente carácter y asignarlo a k.
  • 3.2. Concatenar w y k para formar una nueva cadena temporal wk.
  • 3.3. Si no hay caracteres en la entrada, pasar al paso 5.

4. Verificar wk en el diccionario

  • Si la cadena contenida en wk se encuentra en el diccionario:
    • 4.1. Asignar wk a w y volver al paso 3.
  • Si la cadena contenida en wk no se encuentra en el diccionario:
    • 4.2. Añadir el código de w al arreglo s.
    • Agregar wk al diccionario con un nuevo código.
    • Asignar a w el valor de k y volver al paso 3.

5. Finalizar
Buscar el código de w y añadirlo a s.

Así, al finalizar el arreglo s contiene el conjunto de códigos comprimidos generados por el algoritmo.

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.

  1. Inicialización del diccionario
    Se empieza con un diccionario que contiene todas las secuencias de un solo carácter del conjunto de entrada, con sus códigos correspondientes.

  2. Lectura de códigos

    • Leer el primer código de la secuencia comprimida.

    • Traducir el código al carácter correspondiente en el diccionario.

    • Establecer este carácter como la primera salida y como la cadena w.

  3. Procesar los códigos restantes
    Para cada código subsiguiente en la secuencia comprimida:

    • 3.1. Si el código está en el diccionario:
      • Obtener la secuencia correspondiente al código y agregarla a la salida.
      • Asignar a k la primera letra de esta secuencia.
      • Concatenar w y k para formar una nueva cadena, luego agregarla al diccionario como una nueva entrada.
      • Actualizar w con el valor de la secuencia encontrada.
    • 3.2. Si el código no está en el diccionario:
      • Construir una nueva secuencia concatenando w con la primera letra de w (w[0]).
      • Agregar esta nueva secuencia al diccionario y a la salida.
      • Actualizar w con esta nueva secuencia.

  4. Repetición hasta el final
    Repetir el paso 3 hasta que no queden códigos por leer en la secuencia comprimida.

De esta manera, el diccionario se llena dinámicamente con secuencias a medida que se leen los códigos, reconstruyendo el texto original sin pérdida de información.

Implementación del Algoritmo

Se presentan implementaciones en C++ de compresión y descompresión LZW. La compresión se lleva a cabo utilizando un árbol binario de búsqueda como estructura para el diccionario, mientras que la descompresión emplea un array lineal.

Compresió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;
}
Código de Michael Dipperstein, enlace a su repositorio: https://github.com/MichaelDipperstein/lzw
Descompresió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;
}
Código de Michael Dipperstein, enlace a su repositorio: https://github.com/MichaelDipperstein/lzw

Complejidades e implementaciones

Las complejidades de este algoritmo dependen en gran medida de la implementación específica de la estructura de datos utilizada para el diccionario, entre las más comunes se tienen las imlpementaciones que usan: arreglo, árbol binario de búsqueda y tabla hash con listas enlazadas.

Parámetros de Complejidad:

\(m\): Es el tamaño del texto de entrada que se está procesando para la compresión.

\(n\): Es el tamaño del diccionario.

\(k\): Es el tamaño del texto comprimido.

  • Arreglo:

    • Tiempo de Compresión: \(O(m \cdot n)\), debido a la búsqueda lineal en el diccionario para cada carácter procesado.

    • Tiempo de Descompresión: \(O(k)\), ya que accede directamente a los índices del diccionario, sin búsquedas.

    • Espacio: \(O(n)\), dado que el array crece con las entradas al diccionario.

  • Árbol Binario de Búsqueda:

    • Tiempo de Compresión:

      1. Promedio: \(O(m \cdot log \ n)\), Porque las búsquedas e inserciones son \(O(log \ n)\) en un árbol balanceado.
      2. En peor caso: \(O(m \cdot n)\), si el árbol está desbalanceado.

    • Tiempo de Descompresión: \(O(k)\), ya que no se realizan búsquedas en el diccionario, dado que este se reconstruye secuencialmente a medida que se procesan los códigos comprimidos.

    • Espacio: \(O(n)\), porque el árbol almacena n nodos correspondientes al diccionario

  • Tabla hash con listas enlazadas:

    • Tiempo de Compresión:

      1. Promedio: \(O(m)\), debido a búsquedas constantes en el diccionario \(O(1)\).
      2. Peor caso: \(O(m \cdot n)\), si hay un alto número de colisiones.

    • Tiempo de Descompresión: \(O(k)\), similar a otras implementaciones por el acceso directo al diccionario.

    • Espacio: \(O(n)\), ya que la tabla hash crece con las entradas al diccionario.

Como se mencionaba anteriormente, la implementación del LZW puede mejorarse dependiendo de la estructura de datos utilizada. Por ejemplo, las tablas hash con listas enlazadas presentan una mejora sobre la compresión.

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.

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.

Referencias

  • Nishad, P. M., & Chezian, R. M. (2014). Behavioral study of data structures on Lempel Ziv Welch (LZW) data compression algorithm and its computational complexity.

  • 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