Description:
Lempel-Ziv-Algorithms belong to the group of dictionary-based compression. This
dictionary is initialized with the single characters appearing in the text for
encoding as well as for decoding. As for decoding only the initial dictionary
is needed, there is no redundant information needed.
When encoding, in the beginning the prefix is empty. As second
step the next character is read from the input. Now the algorithm tries
to find "prefix + character" in the dictionary. When found,
"prefix + character" become the new prefix, otherwise the
code for the prefix is written out,
"prefix + character" receives a new entry in the dictionary
and the character becomes the new prefix. As long as the end of the
input is not reached, second step is next, otherwise the code for the
prefix is written out in the end.
When decoding, in the beginning the prefix is empty. The first
code, which always belongs to a single letter, is read and its clear
text is written out. As first step of the loop this "old
code" is always kept in memory. The next code is read and
searched for in the dictionary. When found, itsclear text is written
out, the old code is assigned to the prefix and the first
character of the code is assigned to character. "prefix +
character" now receive a new dictionary entry. If not found, the
old code is assigned to the prefix and the first character of the
code is assigned to character. Now "prefix + character"
receive a new dictionary entry and are written out.
Applet's Usage:
Go back to Lossless Compression
Go on to my German Documentation