3
$\begingroup$

What is the difference between the LZW and Huffman's coding of text compression ?

I've read this and this , but I'm not able to distinguish ?

$\endgroup$

2 Answers 2

3
$\begingroup$

Lempel–Ziv encoding (or rather, encodings, since there are many different variants) and Huffman coding are very different algorithms.

Huffman coding. Choose a block length, usually one byte. For each possible value of the block, we choose some bit string, so that no bit string is a prefix of another one (this is known as a prefix-free code). This choice is either fixed (like the JPEG Huffman code, which while in principle adaptive, is often fixed to some standard code) or adaptive (chosen according to the actual text being compressed). Each block is encoded by its bit string, and the results are concatenated.

The name Huffman code proper refers to the optimal choice of code given a distribution on the value of the blocks. Huffman code satisfy the following optimality property: if the source being compressed consists of i.i.d. copies of some distribution, then as the block length tends to infinity, the average number of bits used to encode one copy is the entropy of the source.

Lempel–Ziv encoding. Here the idea is to separate the input bits (instead of bits, we can choose longer blocks) into pieces, where each piece consists of an earlier piece plus an additional bit at the end. For example, the input 01011100010 can be partitioned as (0)(1)(01)(11)(00)(010). The idea is to encode each piece by referring to an earlier piece, including the additional bit. For example, if we number the pieces from 1, 0 being the empty piece, then the previous example could be encoded as (0,0)(0,1)(1,1)(2,1)(1,0)(3,0).

There are many different variants of Lempel–Ziv encoding. In particular, in practice we don't keep all earlier pieces in memory, and there is some specific encoding for the pairs (p,b) encoding the earlier piece and the new bit. Lempel–Ziv encoding is optimal for ergodic sources – the expected length of the compressed stream tends to the entropy.

$\endgroup$
0
$\begingroup$

Both are lossless data compression algorithms.

I would say that the main difference is that Huffman's coding is a static technique$^1$ based on given or estimated probabilities that should be know a priori and produce a variable-length code.

LZW is in the same family of LZ77 and LZ78, it is "online" and it is based on a dictionary built during the encoding phase.

Here you can find more details.

$^1$ There is a dynamic version called dynamic Huffman coding

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.