Contents

1 Why (text) compress?

• After the digitalization of any signal we get a sequence $s\left[\right]$ of samples that represent the signal $s$ with more or less fidelity.
• $s\left[\right]$ is encoded using PCM (Pulse Code Modulation), in which every sample is represented with the same number of bits. For example, in a CD we have a data-rate of
  $$\left(16+16\right)\frac{\text{bits}}{\text{sample}}\times 44.100\frac{\text{samples}}{\text{second}}=1.411.200\frac{\text{bits}}{\text{second}}.$$

• Always remember that compression not necessary reduces the number of bits at the output. Sometimes, an expansion could be generated.

2 Sources of redundancy

• In general, the signal $s\left[\right]$ has different types of redundancy:
  1. Statistical redundancy. It can be removed using probabilistic models of the signal producing lossless codecs. The codecs are also known as text codecs.
  2. Spatial/temporal redundancy. It can be removed using spatial/temporal models of the signal and produces also lossless codecs.
  3. Psychological redundancy. Some information that signal carry can not be perceived by humans. This kind of pseudo-redundancy is removed normally by means of quantization, producing lossy codecs.

3 Symbols, runs, strings, code-words and code-streams

• In the context of statistical coding, each sample of $s\left[\right]$ is called a symbol.
• Depending on the type of statistical relationship between symbols, we will speak also about strings when we process more than one symbol and about runs when all the symbols are the same in a string.
• In any case, the output of the encoder is a sequence of code-words that all together generates a code-stream.

4 Main techniques

1. A summary.
2. Run-length encoding.
3. String encoding.
4. Symbol encoding.

5 An example

1. gzip/bzip2.