Previous | ToC | Next Labs: Error Correction and Compression. Part 2. Math Alive

Lempel-Ziv Algorithm: Coding Individual Strings

The first example was:
,I,f,_,o,n,e,_d,oc,t,or,_do,c,to,r,s,_a,no,th,er,_doc,tor,,,_doe,s_,the,_doct,or_,w,h,o_, d,oct,ors,_t,he,_docto,r_,do,ct,or_t,he_,doc,tor_,the_,wa,y,_th,e_,doct,or_h,e_i,s_d, octo,ri,ng,_doctor,s?,_O,r_d,oe,s_h,e_d,octor,_the,_doctor_,the_w,a,y_,the_d,octor_, wh,o_d,octors,_doctors,?

Parsing the sequence was the first step. Next we number the strings, numbering first "empty" string as zero. We check what the Prefix is (that is the piece of the string before its last character) and the Position Number of that prefix (which, by construction, is a string that was encountered before). The coded string is then constructed by taking the Position Number of the Prefix, and following that by the last character of the string that we are considering.

This table shows the proper method for encoding. (We use the "_" symbol to show the blank space). Fill in the empty slots:

Practice
Coding Individual Strings for Lempel-Ziv Algorithm

StringPosition Number
of this string
Prefix Position Number
of Prefix
Coded String
I 1empty00I
f 2empty00f
_ 3empty00_
o 4empty00o
n 5empty00n
e 6empty00e
_d7_33d
oc8o44c
t9
or 10
_do 11
c 12
to 13
r 14
s 15
_a 16
no 17
th 18
er 19
_doc 20