Databases Reference
In-Depth Information
T A B L E 5 . 5
Development of the dictionary.
Dictionary
Encoder Output
Index
Entry
0
,
C
(w)
01
w
0
,
C
(
a
)
02
a
0
,
C
(
b
)
03
b
3
,
C
(
a
)
04
ba
0
,
C
(
b
)
05
b
1
,
C
(
a
)
06
w
a
3
,
C
(
b
)
07
bb
2
,
C
(
b
)
08
ab
6
,
C
(
b
)
09
w
ab
4
,
C
(
b
)
10
bab
9
,
C
(
b
)
11
w
abb
8
,
C
(w)
12
ab
w
0
,
C
(
o
)
13
o
13
,
C
(
b
)
14
ob
,
C
(
o
)
w
o
1
15
14
,
C
(w)
16
ob
w
13
,
C
(
o
)
17
oo
Variations on the LZ78 Theme—The LZW Algorithm
There are a number of ways the LZ78 algorithm can be modified, and as is the case with the
LZ77 algorithm, anything that can be modified probably has been. The most well-known mod-
ification, one that initially sparked much of the interest in the LZ algorithms, is a modification
by Terry Welch known as LZW [
56
]. Welch proposed a technique for removing the necessity
of encoding the second element of the pair
. That is, the encoder would only send the
index to the dictionary. In order to do this, the dictionary has to be primed with all the letters
of the source alphabet. The input to the encoder is accumulated in a pattern
p
as long as
p
is contained in the dictionary. If the addition of another letter
a
results in a pattern
p
i
,
c
∗
denotes concatenation) that is not in the dictionary, then the index of
p
is transmitted to the
receiver, the pattern
p
∗
a
(
a
is added to the dictionary, and we start another pattern with the letter
a
. The LZW algorithm is best understood with an example. In the following two examples,
we will look at the encoder and decoder operations for the same sequence used to explain the
LZ78 algorithm.
∗
Examp l e 5 . 4 . 3 : The LZW Algorithm—Encoding
We will use the sequence previously used to demonstrate the LZ78 algorithm as our input
sequence:
w
abba
/
b
w
abba
/
b
w
abba
/
b
w
abba
b
/
w
oo
/
b
w
oo
/
b
w
oo
Assuming that the alphabet for the source is
{
/
b
,
a
,
b
,
o
,w
}
, the LZW dictionary initially looks
like Table
5.6
.
