Open RAR File

LZ77 and DEFLATE

LZ77 is a compression algorithm developed by Abraham Lempel and Jacob Ziv in 1977 (hence the name LZ77). LZ77 and all other LZ family algorithms main idea is to find matching substrings in preceding parts of the input data and store references to them instead of repeating. LZ77 uses a concept of sliding window. It means that matches are only looked for within that window scope. This is done to make repeating sequence search more performance efficient. Size of the sliding window not only affects performance but also compression effectiveness of LZ77 algorithm. Small sliding window could lead to matches far from each other not being found.

DEFLATE is the most popular implementation of LZ77 algorithm which combines it with Huffman coding. Huffman coding stores characters from the data stream in a tree structure built based on the frequency of character occurrence. Most frequent characters are assigned smaller number of bits and less frequent characters are assigned larger number of bits. This compresses the LZ77 output even further.

DEFLATE is probably the most popular compression algorithm. It is used by GZIP, ZIP, PNG file formats, and zlib library. DEFLATE is one of the compression schemes used in all web servers and internet browsers to compress and decompress HMTL documents sent over the internet. Zlib library was developed by Jean-loup Gailly and Mark Adler on May 1, 1995. It was released for free and open source under “zlib license”. This license allows free distribution and modification of zlib library for public domain and commercial use. Due to the open source nature of zlib it became widely popular and is now used in Linux, Windows, Unix, Mac OS and iOS operating systems. It is also used in gaming consoles like PlayStations 4, PlayStation 3, Wii U, Wii, Xbox One, Xbox 360. This library is also used for PNG images compression and is one of the HTTP standard compression methods.