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 (always look for the longest sequence in the dictionary)
  2. Write the corresponding code (entry in the dictionary) to the output
  3. Add a new entry to the dictionary with the first unused code
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 (siempre trate de buscar por la secuencia más larga en el diccionario)
  2. Escribir el código correspondiente (entrada en el diccionario) a la salida
Ver http://www2.cs.duke.edu/csed/curious/compression/lzw.html.

Encoder.cpp
unsigned char c;
string sequence;
unsigned int code = 258;
unsigned int code_len = 9;
map<string, unsigned int> dictionary;
while (input.get(c))
{
     sequence += c;
     if (dictionary.find(sequence) == false)
     {
          dictionary[sequence] = code;
          code++;
          sequence.pop_back();
          if (code < 512)
          {
               code_len = 9;
          }
          else if (code < 1024)
          {
               code_len = 10;
          }
          else if (code < 2048)
          {
               code_len = 11;
          }
          else
          {
               code_len = 12;
          }
          output.Write(dictionary[sequence], code_len);
          sequence = c;
     }
}
if (sequence.empty() == false)
{
     output.Write(dictionary[sequence], code_len);
}


Problem 1
Manually compute of an LZW encoder when the hexadecimal input is: 2D 2D 2D 2D 2D 41 2D 2D 2D 41. Answer (hexadecimal): 80 0B 60 50 22 0C 0C 85 01.
Manualmente calcula la salida de un codificador LZW cuando la entrada hexadecimal es: 2D 2D 2D 2D 2D 41 2D 2D 2D 41. Respuesta (hexadecimal): 80 0B 60 50 22 0C 0C 85 01.

Problem 2
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
     string::iterator p;
     wstring text;
     wchar_t tmp[32];
     for (p = compressedData.begin(); p != compressedData.end(); p++)
     {
          _snwprintf_s(tmp, 32, _TRUNCATE, L"%02X ", (unsigned char)*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;
}


© Copyright 2000-2019 Wintempla selo. All Rights Reserved. Sep 05 2019. Home