Databases Reference
In-Depth Information
Move back 7
Copy 1
c
a
b
r
a
ca
d
c
a
b
r
a
ca
d
a
Copy 2
Copy 3
c
a
b
r
a
b
ca
d
a
b
c
a
b
r
a
b
c
a
d
a
b
r
Copy 4
Decode
C(r)
c
a
b
r
a
b
c
a
d
a
b
r
a
c
a
b
r
a
b
a
d
a
b
r
a
r
c
F I GU R E 5 . 3
Decoding the triple
7, 4,
C
(
r
)
.
Move back 3
Copy 1
a
b
a
b
r
a
r
a
b
a
b
r
a
r
r
Copy 2
Copy 3
a
b
a
b
r
a
r
r
a
a
b
a
b
r
a
r
r
a
r
Copy 4
Copy 5
a
b
a
b
r
a
r
r
a
r
r
a
b
a
b
r
a
r
r
a
r
r
a
Decode
C(d)
a
b
a
b
r
a
r
r
a
r
r
a
d
F I GU R E 5 . 4
Decoding the triple
3, 5, C(d)
.
As we can see, the LZ77 scheme is a very simple adaptive scheme that requires no prior
knowledge of the source and seems to require no assumptions about the characteristics of
the source. The authors of this algorithm showed that the performance of this algorithm
asymptotically approached the best that could be obtained by using a scheme that had full
knowledge about the statistics of the source. While this may be true asymptotically, in practice
there are a number of ways of improving the performance of the LZ77 algorithm as described
here. Furthermore, by using the recent portions of the sequence, there is an assumption of
sorts being used here—that is, that patterns recur “close” together. As we shall see, the authors
