Understanding DEFLATE Algorithm: LZ77, Huffman Coding, Compression

DEFLATE algorithm, developed by Kent, combines LZ77 compression with Huffman coding. LZ77 algorithm compresses data using a sliding window technique, while Huffman coding assigns variable-size codewords to characters based on frequency. This process enables efficient data compression and decompression. Check out examples, symbol-codeword mappings, compression techniques, and references for further insights into DEFLATE.

• Data Compression
• DEFLATE Algorithm
• LZ77
• Huffman Coding
• Data Compression Techniques

homr Follow

Uploaded on Sep 18, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. DEFLATE Algorithm Kent 1

2. DEFLATE Algorithm DEFLATE uses a combination of the LZ77 algorithm and Huffman coding. 2

3. LZ77 Algorithm The LZ77 algorithm compresses data that has already appeared in the past (a sliding window of the last 32 kB of data) by encoding it with a pair (distance, length), where distance is a number in [1, 32768] length is a number in [3, 258] 3

4. Examples abcdefabcd abcdef(6, 4) <title>Test</title> <title>Test</[6;12] Blah blah blah blah blah! Blah b[D=5, L=18]! 4

5. Huffman Coding The Huffman coding transforming each 8-b character to a variable-size codeword. The more frequent the character is, the shorter its corresponding codeword. The codewords are coded such that No codeword is a prefix of another, so the end of each codeword can be easily determined. 5

6. Examples 38 Symbol Weight 0 1 E 1 22 e x 1 0 1 a 8 14 8 0 1 0 1 m 2 p 2 6 a 4 s 0 1 0 1 l 4 e 16 2 l m p 0 1 s 4 E x 6

7. Symbol Codeword E 00000 x 00001 a 001 m 0100 p 0101 l 0001 e 1 s 011 7

8. 0010101010100011 0110010100010100011 8

9. length codes 9

10. distance codes 10

11. Compression with fixed Huffman codes 11

12. Reference http://www.zlib.net/feldspar.html https://www.adayinthelifeof.nl/2010/06/02/d eflating-the-universe/ http://tools.ietf.org/html/rfc1951 Accelerating Multipattern Matching on Compressed HTTP Traffic Authors : Bremler-Barr, A. Interdiscipl. Center, Efi Arazi Sch. of Comput. Sci., Herzlia, Israel Koral, Y. Publication : IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 20, NO. 3, JUNE 2012 12