Databases Reference
In-Depth Information
T A B L E 6 . 6
Count array for zero-order
context.
Letter
Count
Cum
_
Count
t
2
2
h
2
4
i
2
6
s
2
8
b
2
10
Esc
1
11
Total_Count
11
T A B L E 6 . 7
Count array for first-order
contexts.
Context
Letter
Count
Cum
_
Count
t
h
2
2
Esc
1
3
Total_Count
3
h
i
1
1
Esc
1
2
Total_Count
2
i
s
2
2
Esc
1
3
Total_Count
3
b
i
1
1
t
1
2
Esc
1
3
Total_Count
3
b
s
2
2
Esc
1
3
Total_Count
3
6.3.2 The Escape Symbol
In our example we used a count of one for the escape symbol, thus inflating the total count in
each context by one. Cleary and Witten call this Method A, and the corresponding algorithm
is referred to as
ppma
. There is really no obvious justification for assigning a count of one
to the escape symbol. For that matter, there is no obvious method of assigning counts to the
escape symbol. There have been various methods reported in the literature.
Another method described by Cleary and Witten is to reduce the counts of each symbol by
one and assign these counts to the escape symbol. For example, suppose in a given sequence
a
occurs 10 times in the context of
prob
,
l
occurs 9 times, and
o
occurs 3 times in the same
