jueves, 25 de abril de 2013

Activity Point Extra - Lempel-Ziv-Welch

Lempel–Ziv–Welch (LZW) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch.

The algorithm is simple to implement, and has the potential for very high throughput in hardware implementations. It was the algorithm of the widely used Unix file compression utility compress, and is used in the GIF image format.

Encoding

A high level view of the encoding algorithm is shown here:

  • Initialize the dictionary to contain all strings of length one.
  • Find the longest string W in the dictionary that matches the current input.
  • Emit the dictionary index for W to output and remove W from the input.
  • Add W followed by the next symbol in the input to the dictionary.
  • Go to Step 2.
A dictionary is initialized to contain the single-character strings corresponding to all the possible input characters (and nothing else except the clear and stop codes if they're being used).

The algorithm works by scanning through the input string for successively longer substrings until it finds one that is not in the dictionary.

Algorithm Compress:
Symbols and variables

Algorithm Decompress
Symbols an variables

Example Code in Python

Results

Funcionality

Compress


The string is "HolaHola".

Compressed program sequence of 8-bit symbols.

First, the word "Hello", it's the same, and not added the same.

Then, the string "Ho" is added to the 256:
Ho = 256

After the next, the character "la" one adds the 258:
la = 258

They met the characters "Ho" and "la".

Decompress

256,258 = Hola


The values ​​are replaced by the characters

References

1 comentario:

  1. Pues, si habrías hecho caso a lo que encargué, tuvieras más puntos extra. Van 2 para la tarea 5.

    ResponderEliminar