Open ZIP File

LZ78, LZMA and BWT Compression

LZ78 algorithm was developed by Abraham Lempel and Jacob Ziv in 1978. It is an algorithm in the family of dictionary coders which means that it maintains the dictionary to code the data and doesn’t use any statistical models. So, the efficiency of coding is strictly dependent on the dictionary chosen for coding. That is why it is critical to choose the most appropriate dictionary to achieve high ratio of compression. Many modifications of LZ77 and LZ78 algorithms are different on different ways how they build coding dictionaries. LZ78 compression is quite efficient but it hadn’t become very popular because of the certain patent restrictions. LZW compression which is based on LZ78 is used to perform lossless compression of GIF files. LZW compression was restrictively patented by Unisys and Compuserve which limited adoption of GIF and LZW. Instead PNG file format was developed as a replacement for GIF.

LZMA or Lempel–Ziv–Markov chain algorithm was first released by Igor Pavlov in 1998. It ships with 7-Zip compression utility which produces files in 7Z file format. LZMA algorithm uses much larger dictionaries than competing LZ77 and DEFLATE algorithm. This is possible because modern computers are able to hold much larger dictionaries in memory and CPU performance is much higher. Another difference of LZMA is that it is not using byte-based compression but rather works with bitfields. This makes it more computationally intensive but produces significantly better compression ratios.

BWT or Burrows Wheeler Transform is an important compression technique used in several important applications. To be precise it is not exactly a compression technique but rather a data preparation technique which makes it more susceptible to compression. BWT produces an output string which has significantly more repetitions than original string. This is achieved by a special way of block-based transform which takes all rotations of the string, sorts them lexicographically and takes the last letter in each string. BWT transformation has proven very effective for certain kinds of data like genome information. Also, BWT is used in bzip2 archiver which achieves quite good compression results.