Data Compression Lec#11 Word

Dictionary Methods
Statistical compression methods use a statistical model of the data, which is why the
quality of compression they achieve depends on how good that model is.
Dictionary-based compression methods do not use a statistical model, nor do they
use variable-size codes. Instead they select strings of symbols and encode each string
as a token using a dictionary.
String Compression
In general, compression methods based on strings of symbols can be more efficient
than methods that compress individual symbols in principle, better compression is
possible if the symbols of the alphabet have very different probabilities of
occurrence. We use a simple example to show that the probabilities of strings of
symbols vary more than the probabilities of the individual symbols constituting the
strings.
We start with a 2-symbol alphabet a1 and a2, with probabilities P1 = 0.8 and P2 = 0.2,
respectively. The average probability is 0.5, and we can get an idea of the variance
(how much the individual probabilities deviate from the average) by calculating the
sum of absolute differences (variance )= |0.8 ? 0.5| + |0.2 ? 0.5| = 0.6.
Any variable-size code would assign 1-bit codes to the two symbols, so the average
size of the code is one bit per symbol.
We now generate all the strings of two symbols. There are four of them, shown in
Table 3.1a,