Databases Reference
In-Depth Information
2.3.3 Markov Models
One of the most popular ways of representing dependence in the data is through the use of
Markov models, named after the Russian mathematician Andrei Andrevich Markov (1856-
1922). For models used in lossless compression, we use a specific type of Markov process
called a
discrete time Markov chain
.Let
{
x
n
}
be a sequence of observations. This sequence is
said to follow a
k
th-order Markov model if
P
(
x
n
|
x
n
−
1
,...,
x
n
−
k
)
=
P
(
x
n
|
x
n
−
1
,...,
x
n
−
k
,...)
(13)
In other words, knowledge of the past
k
symbols is equivalent to the knowledge of the entire
past history of the process. The values taken on by the set
are called the
states
of the process. If the size of the source alphabet is
l
then the number of states is
l
k
.The
most commonly used Markov model is the first-order Markov model, for which
{
x
n
−
1
,...,
x
n
−
k
}
(
x
n
|
x
n
−
1
)
=
(
x
n
|
x
n
−
1
,
x
n
−
2
,
x
n
−
3
,...)
(14)
P
P
Equations (
13
) and (
14
) indicate the existence of dependence between samples. However,
they do not describe the form of the dependence. We can develop different first-order Markov
models depending on our assumption about the form of the dependence between samples.
If we assumed that the dependence was introduced in a linear manner, we could view the
data sequence as the output of a linear filter driven by white noise. The output of such a filter
can be given by the difference equation
x
n
=
ρ
x
n
−
1
+
n
(15)
where
n
is a white noise process. This model is often used when developing coding algorithms
for speech and images.
The use of the Markov model does not require the assumption of linearity. For example,
consider a binary image. The image has only two types of pixels, white pixels and black pixels.
We know that the appearance of a white pixel as the next observation depends, to some extent,
on whether the current pixel is white or black. Therefore, we can model the pixel process as
a discrete time Markov chain. Define two states
S
would correspond to the case
where the current pixel is a white pixel, and
S
b
corresponds to the case where the current pixel
is a black pixel). We define the transition probabilities
P
and
S
b
(
S
w
w
(w/
b
)
and
P
(
b
/w)
and the probability
of being in each state
P
(
S
w
)
and
P
(
S
b
)
. The Markov model can then be represented by the
state diagram shown in Figure
2.3
.
The entropy of a finite state process with states
S
i
is simply the average value of the entropy
at each state:
M
=
(
S
i
)
(
S
i
)
(16)
H
P
H
i
=
1
For our particular example of a binary image
H
(
S
w
)
=−
P
(
b
|
w)
log
P
(
b
|
w)
−
P
(w
|
w)
log
P
(w
|
w)
where
P
(w
|
w)
=
1
−
P
(
b
|
w)
.
H
(
S
b
)
can be calculated in a similar manner.
