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: