Data Compression Lec#6 Word

Move-to-Front Coding
Move To Front is a transformation algorithm which does not compress data. It is
used as a sub-step in several other compression algorithms by preprocess the message
sequence by converting it into a sequence of integers .
The basic idea of this method is to maintain the alphabet A of symbols as a list
where frequently occurring symbols are located near the front. A symbol s is encoded
as the number of symbols that precede it in this list. Thus if A=(t,h,e, s. . .,) and the
next symbol in the input stream to be encoded is e, it will be encoded as 2, since it is
preceded by two symbols. There are several possible variants to this method; the most
basic of them adds one more step: After symbol s is encoded, it is moved to the front
of list A. Thus, after encoding e, the alphabet is modified to A=(e, t, h,s,. . . ). This
move-to-front step reflects the expectation that once e has been read from the input
stream, it will be read many more times and will, at least for a while, be a common
symbol. The move-to-front method is locally adaptive, since it adapts itself to the
frequencies of symbols in local areas of the input stream.
The method produces good results if the input stream satisfies this expectation, i.e.,
if it contains concentrations of identical symbols (if the local frequency of symbols
changes significantly from area to area in the input stream).We call this the
concentration property (abcddcbamnopponm ).
Here are two examples that illustrate the move-to-front idea. Both assume the alphabet
A=(a, b, c, d, m, n, o, p).
1. The input stream abcddcbamnopponm is encoded as
C = (0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3) (Table 1.14a).