# 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

## 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 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.

 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; }