Data Compression Lec#6 PowerPoint

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).