Lempel-Ziv

Huffman is OK but
What if you don't have p(a_j)?
What if you need to code more than a few letters at a time?

Basic idea: Work from left $\rightarrow R$ in two passes

1.

Identify strings which have not come before to build up a codebook of phrases

2.

number the phrases and code the main string using those phrases

Ex. (from book)

Could do 2 things:

1.

Dumb: assume decoder knows the phrases ahead of time and simply send phrases numbers
dumb because

• the codebook is as big as the sequence
• each string has a different codebook

2.

Smart: Code as (phase II, new bit)
in example, (define "start phrase" as 0000) start phrase has zero length
(0000,0)(0000,1)(0001,0)(0011,1)(0010,0)(0011,0)....

Assuming the decoder know the maximum number of phrases ( or as in book, source and destination agree on what to throw out when)
then the destination can reconstruct the code

First time it sees 0000 it knows that the first bit in the sequence follows $\rightarrow$ which means it now knows the first phrase
Held sequence must be next phrase and so on.
Why does this work?
If ssequence has structure, phrases get longer and longer, because what comes next has probably been seen before

END