Open RAR File

Compression Algorithms Families

Data compression algorithms gained popularity with a wide adoption of personal computers and internet. But data compression was used many years before computers. One of the data compression examples is Morse code which encodes symbols as dots and dashes. If you interpret dot and dashes as 0s and 1s then you will see that some of the characters are encoded with rather small number of bits. For example, letter T is encoded with just dash and letter E with just one dot. This technically makes Morse code one of the first compression coding schemes.

In 1949 with development of mainframes Shannon-Fano coding was introduced by Claude Shannon and Robert Fano. The Shannon-Fano codes characters based on their frequency in a stream. Characters with higher frequency are encoded with shorter codes and characters with lower frequency are encoded with longer codes. Later in 1951 David Huffman developed Huffman code which provides an optimal frequency-based prefix code.

But only in 1977 the next major step was made when Abraham Lempel and Jacob Ziv published LZ77 algorithm, which was the first algorithm to use dictionary to compress data. Next year they also published LZ78 algorithm thus creating two major compression algorithm families.

LZ77 further evolved into DEFLATE algorithm which is used in every operating system, console device, HTTP protocol and many other places. It is probably one of the most used compression algorithms nowadays.

LZ78 was further developed into LZW and was used in GIF and Unix “compress” and “decompress” utilities. LZW adoption was significantly slowed by patent legal issues which forced many developers to move to LZ77 based DEFLATE algorithm which was not patented.

Even though DEFLATE became de-facto compression standard new algorithms are being developed and used in certain implementations. In the beginning of 2000 RAR compression standard became popular which used PPMd modification of PPM (Prediction by Partial Matching) algorithm. Also, 7Z file format was developed around the same time which used LZMA (Lempel-Ziv-Markov chain algorithm).