Databases Reference
In-Depth Information
T A B L E 5 . 3
Thirty most frequently occurring
pairs of characters in a
collection of C programs
containing 64,983 characters.
Pair
Count
Pair
Count
bb
5728
st
442
nlb
1471
le
440
;
nl
1133
ut
440
in
985
f
(
416
nt
739
ar
381
=
b
687
or
374
bi
662
rb
373
tb
615
en
371
b
=
612
er
358
);
558
ri
357
,
b
554
at
352
nlnl
506
pr
351
bf
505
te
349
eb
500
an
348
b
∗
444
lo
347
5.4 Adaptive Dictionary
Most adaptive-dictionary-based techniques have their roots in two landmark papers by Jacob
Ziv and Abraham Lempel in 1977 [
52
] and 1978 [
53
]. These papers provide two different
approaches to adaptively building dictionaries, and each approach has given rise to a number of
variations. The approaches based on the 1977 paper are said to belong to the LZ77 family (also
known as LZ1), while the approaches based on the 1978 paper are said to belong to the LZ78,
or LZ2, family. The transposition of the initials is a historical accident and is a convention we
will observe in this topic. In the following sections, we first describe an implementation of
each of the adaptive-dictionary-based compression approaches followed by some of the more
well-known variations.
5.4.1 The LZ77 Approach
In the LZ77 approach, the dictionary is simply a portion of the previously encoded sequence.
The encoder examines the input sequence through a sliding window, as shown in Figure
5.1
.
The window consists of two parts, a
search buffer
that contains a portion of the recently encoded
sequence and a
lookahead buffer
that contains the next portion of the sequence to be encoded.
In Figure
5.1
, the search buffer contains eight symbols, while the lookahead buffer contains
seven symbols. In practice, the size of the buffers is significantly larger; however, for the
purpose of explanation, we will keep the buffer sizes small.
To encode the sequence in the lookahead buffer, the encoder moves a search pointer back
through the search buffer until it encounters a match to the first symbol in the lookahead
