lz78

ENCODING

Pseudocode

  P = null;
  
  loop
    exit when { not exists next char };
    
    C = { next char }
    
    if P + C { in the dictionary } then
     P = P + C;
    else
     { write index of P };
     { write C };
     { add P + C to dictionary };
     P = null;
    end if;
  end loop;

  if P not equal to null then
   { write index of P }
  end if;

Example

string: ABBCBCABA

Step	P	Code (index + next char)	Index + char added to the dictionary
1	A	0 A	1 A
2	B	0 B	2 B
3	B, BC	2 C	3 BC
4	B, BC, BCA	3 A	4 BCA
5	B, BA	2 A	5 BA