Databases Reference
In-Depth Information
P(b|w)
P(w|w)
S
w
S
b
P(b|b)
P(w|b)
F I GU R E 2 . 3
A two-state Markov model for binary images.
Example2.3.1: Markov Model
To see the effect of modeling on the estimate of entropy, let us calculate the entropy for a binary
image, first using a simple probability model and then using the finite state model described
above. Let us assume the following values for the various probabilities:
P
(
S
w
)
=
30
/
31
P
(
S
b
)
=
1
/
31
P
(w
|
w)
=
0
.
99
P
(
b
|
w)
=
0
.
01
P
(
b
|
b
)
=
0
.
7
P
(w
|
b
)
=
0
.
3
Then the entropy using a probability model and the
iid
assumption is
H
=−
0
.
8log0
.
8
−
0
.
2log0
.
2
=
0.206 bits
Now using the Markov model
H
(
S
b
)
=−
0
.
3log0
.
3
−
0
.
7log0
.
7
=
0.881 bits
and
H
(
S
w
)
=−
0
.
01 log 0
.
01
−
0
.
99 log 0
.
99
=
0.081 bits
which, using Equation (
16
), results in an entropy for the Markov model of 0.107 bits, about
half of the entropy obtained using the
iid
assumption.
Markov Models in Text Compression
As expected, Markov models are particularly useful in text compression, where the probability
of the next letter is heavily influenced by the preceding letters. In fact, the use ofMarkovmodels
for written English appears in the original work of Shannon [
3
]. In current text compression
literature, the
k
th-order Markov models are more widely known as
finite context models
, with
the word
context
being used for what we have earlier defined as state.
Consider the word
preceding
. Suppose we have already processed
precedin
and are going
to encode the next letter. If we take no account of the context and treat each letter as a surprise,
the probability of the letter
g
occurring is relatively low. If we use a first-order Markov model
or single-letter context (that is, we look at the probability model given
n
), we can see that the
