next up previous
Next: Lossless Compression Algorithms (Entropy Up: Video and Audio Compression Previous: Run-length Encoding

Lossless Compression Algorithms (Pattern Substitution)

This is a simple form of statistical encoding.

Here we substitue a frequently repeating pattern(s) with a code. The code is shorter than than pattern giving us compression.

A simple Pattern Substitution scheme could employ predefined code (for example replace all occurrences of `The' with the code '&').

More typically tokens are assigned to according to frequency of occurrenc of patterns:

A predefined symbol table may used ie assign code i to token i.

However, it is more usual to dynamically assign codes to tokens. The entropy encoding schemes below basically attempt to decide the optimum assignment of codes to achieve the best compression.

Dave Marshall