Databases Reference
In-Depth Information
6.7 Summary
The context in which a symbol occurs can be very informative about the value that the symbol
takes on. If this context is known to the decoder, then this information need not be encoded;
it can be inferred by the decoder. In this chapter we have looked at several creative ways in
which the knowledge of the context can be used to provide compression.
Further Reading
1.
The basic
ppm
algorithm is described in detail in
Text Compression
, by T.C. Bell, J.G.
Cleary, and I.H. Witten [
1
].
2.
For an excellent description of Burrows-Wheeler coding, including methods of imple-
mentation and improvements to the basic algorithm, see “Burrows-Wheeler Compres-
sion,” by P. Fenwick [
81
]inthe
Lossless Compression Handbook
.
3.
The ACB algorithm is described in “Symbol Ranking and ACB Compression,” by P.
Fenwick [
78
]inthe
Lossless Compression Handbook
, and in
Data Compression: The
Complete Reference
, by D. Salomon [
79
]. The chapter by Fenwick also explores com-
pression schemes based on Shannon's experiments.
6.8 Projects and Problems
1.
Decode the bitstream generated in Example 6.3.1. Assume you have already decoded
this
bis
and Tables
6.1
-
6.4
are available to you.
2.
Consider the sequence
the
/
bbeta
/
/
bcat
/
bate
bthe
/
/
bceta
bhat
:
/
(a)
Encode the sequence using the
ppma
algorithm and an adaptive arithmetic coder.
Assume a six-letter alphabet
{
h
,
e
,
t
,
a
,
c
,/
b
}
.
(b)
Decode the encoded sequence.
3.
Consider the sequence
eta
bceta
/
/
band
/
bbeta
/
bceta
:
(a)
Encode the sequence using the Burrows-Wheeler transform and move-to-front cod-
ing.
(b)
Decode the encoded sequence.
4.
A sequence is encoded using the Burrows-Wheeler transform. Given
L
=
elbkkee
, and
index = 5 (we start counting from 1, not 0), find the original sequence.
5.
Consider the sequence
onionopinion
:
(a)
Encode the sequence using the
ppma
algorithm and an adaptive arithmetic coder.
Assume a four-letter alphabet
{
i
,
n
,
o
,
p
}
.
(b)
Decode the encoded sequence.
