DEFLATE Algorithm: LZ77, Huffman Coding, Compression

DEFLATE Algorithm
Kent
1
DEFLATE Algorithm
DEFLATE uses a combination of the
LZ77 algorithm
 and 
Huffman coding
.
2
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
Examples
abcdefabcd
abcdef
(6, 4)
<title>Test</title>
<title>Test</
[6;12]
Blah blah blah blah blah!
Blah b
[D=5, L=18]
!
4
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
Examples
6
E
x
m
s
e
p
a
l
4
38
14
22
8
2
6
 
1
 
1
 
1
 
1
 
1
 
1
 
1
 
0
 
0
 
0
 
0
 
0
 
0
 
0
 
7
 
0010101010100011
0110010100010100011
8
length codes
9
distance codes
10
Compression with fixed Huffman
codes
11
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
Slide Note
Embed
Share

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

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.

E N D

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

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#