Dictionary Coding: LZ77 & LZW

  • Replace repeats with references
  • Greedy match vs code cost tradeoff
  • Decoder reconstructs from output history
1 / 6

LZ77 tokens

  • Literal byte
  • (distance, length) match
  • Sliding window of previous output
2 / 6

Greedy pitfalls

  • Longest match is not always optimal
  • But simple and fast
  • We fix rules for determinism
3 / 6

LZW idea

  • Dictionary of phrases grows online
  • Emit codes for longest phrase
  • Decoder rebuilds dictionary
4 / 6

KwKwK case

  • Special case when a code refers to itself
  • Must handle to decode correctly
5 / 6

What you will build

  • LZ77 compress/decompress
  • LZW compress/decompress
6 / 6
Use arrow keys or click edges to navigate. Press H to toggle help, F for fullscreen.