Databases Reference
In-Depth Information
0
b
s
1
b
s
e
2
h
3
h
t
4
h
t
5
i
h
i
6
b
s
i
7
s
i
8
t
b
9
t
e
10
F I GU R E 6 . 1
Decoding process.
he
b
. With high probability,
he
/
/
b
would be preceded by
t
. Therefore, in
L
we would get a long
run of
t
s.
6.4.1 Move-to-Front Coding
A coding scheme that takes advantage of long runs of identical symbols is move-to-front (
mt f
)
coding. In this coding scheme, we start with some initial listing of the source alphabet. The
symbol at the top of the list is assigned the number 0, the next one is assigned the number 1,
and so on. The first time a particular symbol occurs, the number corresponding to its place in
the list is transmitted. Then it is moved to the top of the list. If we have a run of this symbol,
we transmit a sequence of 0s. This way, long runs of different symbols get transformed to a
large number of 0s. Applying this technique to our example does not produce very impressive
results due to the small size of the sequence, but we can see how the technique functions.
Example6.4.3:
=
/
/
Let's encode
L
sshtth
bi i
be
. Let's assume that the source alphabet is given by
A
={
/
,
,
,
,
,
}
b
e
h
i
s
t
We start out with the assignment
0
1
2
3
4
5
b
e
h
i
s
t
