homechevron_rightProfessionalchevron_rightComputers

LZW

This calculator compresses/decompresses a sting using Lempel-Ziv-Welch (LZW) algorithm.

The calculators in this article are used to compress and decompress a string using the LZW algorithm. The LZW method is simple and reliable, it does not require storing a dictionary - the dictionary is dynamically generated during compression and decompression.
To study the operation of the algorithm, check the "Show details" box - the calculators will display the work log and generated phrase dictionaries.

PLANETCALC, LZW text compression

LZW text compression

Text to count words
A character to replace invisible symbol.
A symbol that is used to indicate the position of the missing byte of an incomplete multibyte character.
Number of bits in the original text
 
Number of bits in the compressed message
 
Zero bits added
 
Compressed message in binary form
 
File
 
Initial dictionary
 
Dictionary
 
The file is very large. Browser slowdown may occur during loading and creation.

The binary dump or binary file generated by the previous calculator can be passed to the next calculator, which will restore the original string. It is necessary to set the method of forming the source dictionary in the same way as for the compression calculator. (choose the same encoding or specify the same dictionary explicitly).

PLANETCALC, LZW decompression

LZW decompression

An encoded message. If a file is given, then the input data will be taken from the file.
File
  • Drag files here
A character to replace invisible symbol.
A symbol that is used to indicate the position of the missing byte of an incomplete multibyte character.
Text
 
The file is very large. Browser slowdown may occur during loading and creation.

Lempel-Ziv-Welch algorithm

The lossless compression algorithm LZ78 was published in 1978 by Abraham Lempel and Jacob Ziv and then modified by Terry Welch in 1984. After Welch's publication, the algorithm was named LZW after the first letters of the authors' surnames (Lempel, Ziv, Welch). The algorithm has been patented, but by now all patents have expired, which gives us a great opportunity to publish our implementation here.

LZW algorithm description

  1. Create the initial dictionary containing all possible characters.
  2. Put the first character to the input phrase W.
  3. Read next character K.
  4. If EOF return W, else:
    If WK phrase is already in the dictionary, W ⟵ WK, go to 3 ,
    Else return the code of W , add WK to the dictionary, W ⟵ K. Go to 3.

To decode the data generated in this way, you do not need to store the dictionary, it is recreated by itself in the process of the decompression:

  1. Create the initial dictionary containing all possible characters.
  2. Put the first code to the input phrase W.
  3. Read the next code K.
    4.If EOF, return the character having the code W, else:
    If the phrase with the WK code is not in the dictionary, return the phrase with the W code, and add the phrase with the WK code to the dictionary.
    Else, assign the WK code to the input phrase and go to 3.

Welch's original article intended to encode a phrase in a dictionary with a fixed-size 12-bit code, but for small messages this approach may even increase the length of the encoded message compared to the original text. Therefore, it is quite common to use dynamic code length, which changes every time the dictionary limit is reached.

Dictionary size growth handling

In the compression algorithm described above, the size of the dictionary is not limited. In practice, this can lead to resource constraints when packing large amounts of data.
There are known modifications to the algorithm trying to address this problem:

  • LZC - the implementation of the algorithm in the compress utility limits the maximum dictionary size to 16 bits. When the maximum size is reached, the dictionary stops changing. The algorithm monitors the compression ratio and, if it degrades significantly, resets the dictionary and begins to form it anew.
  • LZT - on overflow, removes from the dictionary a phrase that has not been used for the longest time

Our implementation features

Initial dictionary

Our calculators implement an endlessly growing vocabulary, which can be too expensive for very large data. The size of phrase codes starts at 8 bits for the initial dictionary specified by standard encoding, or less for a dictionary entered by hand. In the latter case, the size of the phrase codes is the minimum number of bits required to express the number of characters in the dictionary. Bit length.

Multibyte encodings

Some encodings can take more than 1 byte per character, for example, UTF-8 encoding contains characters of variable length from 1 to 4 bytes. In any case, the initial dictionary will contain 256 items with codes from 0 to 255 for whatever encoding you choose.
For multibyte encodings, a dynamically generated dictionary will look quite exotic - its phrases will inevitably be composed of different parts of adjacent characters. In this case, for clarity in the output tables, we use a missing byte marker (by default, this is the '~' character). For example, when compressing the phrase "9 €", represented in UTF-8 encoding, the dynamic dictionary can be filled with combinations of the following characters:
9 - nine,
' ' - space,
€~~ - first byte of euro symbol,
~€~ - second byte of euro symbol,
~~€ - third byte of euro symbol,
€~ - the first two bytes of the euro symbol,
~€ - the last two bytes of the euro symbol,
€ - all three bytes of the euro symbol.
We have introduced this character description for convenience only, remember that the constituent parts of many multibyte characters are just bytes of 8 bits each, and they may be the same for different characters.
for example:
€ ~~ - the first byte of the euro symbol, its code in utf-8 = 226
₽ ~~ - the first byte of the ruble symbol, its code in utf-8 = 226.

Trailing with zeros

The compression algorithm can produce a bit array, the size of which is not a multiple of 8. In this case, the compression calculator fills the end with zero bits. Since our implementation uses a variable size of the phrase code, this approach can cause problems if the manually set initial dictionary is very small.
In this example the final message will be only 18 bits and 6 bits would have to be padded with zeros to store the entire message in a binary file.
Since with the specified parameters, the size of the phrase code is only 4 bits, then the extra word will be read during unpacking, and if we were to create the original dictionary with the code of the first character = 0, then the extra character would be unpacked.
We solve this problem by adding a null character to the beginning of the dictionary, which is commonly interpreted as the end of a string.
When using the encoding as the initial dictionary, this problem will never arise, since the size of the phrase code is always at least 8 bits.

URL copied to clipboard
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, LZW

Comments