LZW

LZW

It is a compression algorithm that uses a lookup table known as dictionary table or just dictionary. It was created by Abraham Lempel, Jacob Ziv, and Terry Welch. It is used in GIF and TIFF images. The encoded data consist of a sequences of codes. Each code has length from 9 to 12 bits. Each code represents:
  1. One byte of input dada, a value from zero to 255
  2. A clear-table marker, a value of 256
  3. An end of data marker, a value of 257
  4. A value in the dictionary table representing a multiple-byte sequence than has been found previously in the input, a value from 258 to 4095
At the beginning, the length of the code is 9 bits and the dictionary table contains the 258 fixed codes (0 to 257). As the codding process continues, more entries are added to the dictionary table, combining new codes with longer sequences of input bytes. The encoder and the decoder maintain identical copies of the dictionary table. When the encoder (or the decoder) realize that the length of the current code is not long enough to represent the number of entries in the dictionary, it increases the number of bits per code by one. Consequently, when the dictionary has 511 entries, all next codes will be 10 bits long. When the dictionary has 1023 entries, all next codes will be 11 bits long. When the dictionary has 2047 entries, all next codes will 12 bits long. As the maximum length for the codes is 12, the last entry in the dictionary is 4095.
Es un algoritmo de compresión que usa una tabla de Lookup conocida como tabla diccionario o solamente diccionario. Este fue creado por Abraham Lempel, Jacob Ziv y Terry Welch. Es usado en las imágenes de GIF y TIFF. Los datos codificados consiste de una secuencia de códigos. Cada código tiene una longitud de 9 a 12 bits. Cada código representa:
  1. Una byte de datos de entrada, un valor de cero a 255
  2. Un marcador para indicar que hay que limpiar tabla diccionario, un valor de 256
  3. Un marcador para indicar el final de los datos, un valor de 257
  4. Un valor en la tabla diccionario representando una secuencia de varios bytes que se ha encontrado previamente en la entrada, un valor desde 258 a 4095
Al principio, la longitud del código es de 9 bits y la tabla diccionario contiene los 258 códigos fijos (0 a 257). A medica que el proceso de codificación continua, más entradas son agregadas a la tabla diccionario, combinando nuevos códigos con secuencias de bytes de entrada largas. El codificador y el decodificador mantienen copias idénticas de la tabla diccionario. Cuando el codificador (o el decodificador) se dan cuenta que la longitud del código no es suficiente para representar el número de entradas en el diccionario, el codificador incremente el número de bits por código en uno. Consecuentemente, cuando el diccionario tiene 511 entradas, todos los códigos siguientes tendrán una longitud de 10 bits. Cuando el diccionario tiene 1023 entradas, todos los códigos siguientes tendrán una longitud de 11 bits. Cuando el diccionario tiene 2047 entradas, todos los códigos siguientes tendrán una longitud de 12 bits. Cómo la longitud máxima de los códigos es 12, la última entrada en el diccionario es 4095.

Encoder

It performs the following steps (see the pseudo code below):
  1. Concatenate a sequence of one or more input bytes trying to match a sequence already in the dictionary
  2. Write the corresponding code (entry in the dictionary) to the output
  3. Add a new entry to the dictionary
See http://www2.cs.duke.edu/csed/curious/compression/lzw.html.
Este realiza los siguientes pasos (vea el pseudo código de abajo):
  1. Concatenar una secuencia de uno o más bytes de la entrada tratando de encontrar esa secuencia en la tabla diccionario
  2. Escribir el código correspondiente (entrada en el diccionario) a la salida
  3. Agregue una nueva entrada al diccionario
Ver http://www2.cs.duke.edu/csed/curious/compression/lzw.html.

LzwAlgorithm

Lzw0

Lzw1

Lzw2

Lzw3

Lzw4

Lzw5

Lzw6

Problem 1
Create a dialog application called AbrahamJacob using Wintempla. After creating the application create the GUI shown. You may set the multiline property on the three textboxes.
Cree una aplicación de Diálogo llamada AbrahamJacob usando Wintempla. Después de crear el programa cree la GUI mostrada. Usted puede fijar la propiedad de multiline en las tres cajas de texto.

AbrahamJacobGui

AbrahamJacobRun

AbrahamJacob.h
#pragma once //______________________________________ AbrahamJacob.h
#include "Resource.h"
class AbrahamJacob: public Win::Dialog
{
public:
     AbrahamJacob()
     {
     }
     ~AbrahamJacob()
     {
     }
     string compressedData;
     . . .
};


AbrahamJacob.cpp
. . .
void AbrahamJacob::btCompress_Click(Win::Event& e)
{
     compressedData.clear();
     //__________________________________________________________ 1. Get input
     wstring data = tbxInput.Text;
     string input;
     Sys::Convert::WstringToString(data, input);
     //__________________________________________________________ 2. Compress
     Sys::Lzw lzw;
     lzw.Compress(input, compressedData);
     //__________________________________________________________ 3. Display compressed data
     vector<unsigned __int32>::iterator p;
     wstring text;
     wchar_t tmp[32];
     for (p = lzw.outputCodes.begin(); p != lzw.outputCodes.end(); p++)
     {
          _snwprintf_s(tmp, 32, _TRUNCATE, L"%d ", (unsigned int)*p);
          text += tmp;
     }
     tbxCompressed.Text = text;
}

void AbrahamJacob::btUncompress_Click(Win::Event& e)
{
     //__________________________________________________________ 1. Expand
     Sys::Lzw lzw;
     string restored;
     lzw.Expand(compressedData, restored);
     //__________________________________________________________ 2. Display compressed data
     string::iterator p;
     wstring text;
     Sys::Convert::StringToWstring(restored, text);
     tbxRestored.Text = text;
}



Packeting of bits in a GIF file

The figure below shows how the codes produced by the LZW algorithm are packed in a GIF file.
La figura de abajo muestra como los códigos producidos por el algoritmo de LZW son empaquetados en archivo GIF.

GifLzw

Packeting of bits in a PDF file

The figure below shows how the codes produced by the LZW algorithm are packed in a PDF file.
La figura de abajo muestra como los códigos producidos por el algoritmo de LZW son empaquetados en archivo PDF.

PdfLzw

Expanding a LZW

The algorithm below shows how to obtain the original data from the LZW compressed data. A basic algorithm is shown to illustrate how it works. The correct algorithm handles when a code is not in the dictionary.
El algoritmo de abajo muestra cómo obtener los datos originales desde los datos comprimidos LZW. Un algoritmo básico ilustra como este funciona. El algoritmo correcto procesa cuando un código no está en el diccionario.

Expand

ExpandCorrect

Expand0

Expand2

Expand3

Expand4

Expand5

Expand6

Tip
The following examples show some complete examples for this algorithm.
El siguiente ejemplos muestran algunos ejemplos completos de este algoritmo.

FullExample

© Copyright 2000-2021 Wintempla selo. All Rights Reserved. Jul 22 2021. Home