View Full Document

7 views

Unformatted text preview:

Lempel Ziv Algorithms LZ77 Sliding Window Variants LZSS Lempel Ziv Storer Szymanski Applications gzip Squeeze LHA PKZIP ZOO LZ78 Dictionary Based Variants LZW Lempel Ziv Welch LZC Lempel Ziv Compress Applications compress GIF CCITT modems ARC PAK Traditionally LZ77 was better but slower but the gzip version is almost as fast as any LZ78 15 583 Algorithms in the Real World Data Compression III Lempel Ziv algorithms Burrows Wheeler Introduction to Lossy Compression 15 853 Page1 LZ77 Sliding Window Lempel Ziv 15 853 Page2 LZ77 Example Cursor a a c a a c a b c a b a b a c Dictionary Lookahead previously coded Buffer Dictionary and buffer windows are fixed length and slide with the cursor On each step Output p l c p relative position of the longest match in the dictionary l length of longest match c next char in buffer beyond longest match Advance window by l 1 15 853 Page3 a a c a a c a b c a b a a a c 0 0 a a a c a a c a b c a b a a a c 1 1 c a a c a a c a b c a b a a a c 3 4 b a a c a a c a b c a b a a a c 3 3 a a a c a a c a b c a b a a a c 1 2 c Dictionary size 6 Longest match Next character 15 853 Page4 1 LZ77 Optimizations used by gzip LZ77 Decoding Decoder keeps same dictionary window as encoder For each message it looks it up in the dictionary and inserts a copy What if l p only part of the message is in the dictionary E g dict abcd codeword 2 9 e Simply copy starting at the cursor for i 0 i length i out cursor i out cursor offset i LZSS Output one of the following formats 0 position length or 1 char Typically use the second format if length 3 a a c a a c a b c a b a a a c 1 a a a c a a c a b c a b a a a c 1 a a a c a a c a b c a b a a a c 1 c a a c a a c a b c a b a a a c 0 3 4 Out abcdcdcdcdcdc 15 853 Page5 Optimizations used by gzip cont Page6 Theory behind LZ77 Huffman code the positions lengths and chars Non greedy possibly use shorter match so that next match is better Use hash table to store dictionary Hash is based on strings of length 3 Find the longest



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Lecture-compress and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture-compress and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?