Databases Reference
In-Depth Information
20
15
10
5
4
6
9
2
8
10
F I GU R E 1 . 2
A sequence of data values.
In the following three examples, we will look at three different ways that data can be modeled.
We will then use the model to obtain compression.
Example1.2.1:
Consider the following sequence of numbers
{
x
1
,
x
2
,
x
3
,...
}
:
9
11
11
11
14
13
15
17
16
17
20
21
If we were to transmit or store the binary representations of these numbers, we would need to
use 5 bits per sample. However, by exploiting the structure in the data, we can represent the
sequence using fewer bits. If we plot these data as shown in Figure
1.2
, we see that the data
seem to fall on a straight line. A model for the data could, therefore, be a straight line given
by the equation
,...
The structure in this particular sequence of numbers can be characterized by an equation.
Thus,
x
n
=
ˆ
n
+
8n
=
1
,
2
x
1
=
ˆ
9, while
x
1
=
x
2
=
ˆ
10, while
x
2
=
11, and so on. To make use of this structure,
let's examine the difference between the data and the model. The difference (or residual) is
given by the sequence
9,
e
n
=
x
n
−ˆ
x
n
:
010
−
11
−
101
−
1
−
111
The residual sequence consists of only three numbers
{−
1
,
0
,
1
}
. If we assign a code of 00 to
−
1, a code of 01 to 0, and a code of 10 to 1, we need to use 2 bits to represent each element
of the residual sequence. Therefore, we can obtain compression by transmitting or storing the
parameters of the model and the residual sequence. The encoding can be exact if the required
compression is to be lossless, or approximate if the compression can be lossy.
