Lesson 1

In this section, we consider data compression algorithms. We will need to both prove their correctness and analyze them.

Suppose we are given an alphabet \(\Sigma = \{a_{1}, \dotsc, a_{n}\}\) (of messages we want to encode). In this section, a code is defined as a function \(\phi \colon \Sigma \to \{0,1\}^{*}\). A message \(m = a_{i_1}\dotsc a_{i_k}\) will be encoded as \(\phi(m) = \phi(a_{i_1})\dotsc \phi(a_{i_k})\). Naturally, we want the code to be uniquely decodable: any message should be decoded unambiguously. This can be achieved by making the code uniform (all symbol codes have the same length), prefix-free (no symbol's code is a prefix of another), or suffix-free. There also exist uniquely decodable codes that possess none of these properties: e.g., \(\phi(a_{1}) = 0\), \(\phi(a_{2}) = 010\).

When might it be beneficial to use codes of different lengths for different symbols? For example, when some symbols appear much more frequently than others. Consider a toy example:

As we can see, the prefix code yields nearly twice as short a code (compared to uniform). As we will see later, the code with minimum redundancy can be found among prefix codes. Prefix codes are conveniently represented as leaves of a binary tree. Such a tree is also used for decoding.