[prev] 59 [next]

Text Compression

Problem: Efficiently encode a given string X by a smaller string Y

Applications:

  • Save memory and/or bandwidth
Huffman's algorithm
  • computes frequency f(c) for each character c
  • encodes high-frequency characters with short code
  • no code word is a prefix of another code word
  • uses optimal encoding tree to determine the code words