انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

Move-to-Front Coding

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 hope 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 thus produces good results if the input stream satisfies this hope, 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.” 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.1a). Without the move-to-front step it is encoded as C_ = (0, 1, 2, 3, 3, 2, 1, 0, 4, 5, 6, 7, 7, 6, 5, 4) (Table 1.14b). Both C and C_ contain codes in the same range [0, 7], but the elements of C are smaller on the average, since the input starts with a concentration of “abcd” and continues with a concentration of “mnop”. (The average value of C is 2.5, while that of C_ is 3.5.)

        Table 1.1: Encoding With and Without Move-to-Front.

2. The input stream “abcdmnopabcdmnop” is encoded as C = (0, 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7) (Table 1.14c). Without the move-to-front step it is encoded as C_ = (0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7) (Table 1.14d). The average of C is now 5.25, greater than that of C_, which is 3.5. The move-to-front rule creates a worse result in this case, since the input does not contain concentrations of identical symbols (it does not satisfy the concentration property).