               Experiments in Data Compression III
                    (or "The Path Not Taken")
                         by John Kormylo
                         E.L.F. Software


State of the Art

     In the following table are shown the results for compressing 
three  different  files using  three  different  methods.   'ZIP' 
refers to STZIP 2.5 (deflating).  'LZA1' refers to the LZA method 
used  by ELFBACK v2.9.   'LZA2' refers to the LZA method used  by 
ELFARC v1.3.


       | DEMONSTR.DOC | ELFBACK.PRG | WORDLIST.TXT |
-------+--------------+-------------+--------------+
   ZIP |       25134  |      32417  |      496876  |
  LZA1 |       24860  |      34719  |      585185  |
  LZA2 |       22029  |      31997  |      453143  |
-------+--------------+-------------+--------------+

Back to Basics

     Huffman  and Arithmetic coding are fixed length to  variable 
length codes.   They take advantage of the fact that some symbols 
occur  more often than others,  and give them shorter codes  than 
the  less  common symbols.   LZW is a variable  length  to  fixed 
length code,  which attempts to create a dictionary of very  long 
sequences  which  all have the same  probability  of  occurrence.  
Whenever  a sequence is used,  the algorithm attempts to make  it 
longer.
     Previous  experience  indicates that a  variable  length  to 
variable length code is best.   There are certain sequences which 
occur relatively often,  but not necessarily together.   For text 
this  should  be obvious in that words are used  many  times  but 
usually in different combinations.  Therefore making the sequence 
longer  is often not nearly as useful as reducing the  number  of 
bits needed to code it.
     LZA  codes  sequences  using a length  code  (based  on  the 
relative  occurance  of matches of that length)  followed  by  an 
alphabetical order code (based on how many matches of that length 
were found in the dictionary).   Whether to use one long match or 
two  short  matches was determined by calculating  the  resulting 
number of bits for all possible combinations.   One would be hard 
pressed to devise a more effective coding system.
     The  problem with LZA is that it is slow.   In part this  is 
due  to the binary tree search,  which must perform  many  string 
comparisons to locate the first and last matches corresponding to 
a specified length.   This is also due to the large dictionary of 
possible sequences,  from which the best combination of sequences 
must be determined.   There are 16K text pointers and 64 possible 
lengths,  for  a  maximum  of  1  Meg  possible  strings  in  the 
dictionary (only about half that number are unique).
     A  smaller dictionary would require less time to search  and 
might make the search for the best coding sequence unnecessary.


Hash Tables

     Hash tables are faster than binary search trees.  Also, each 
entry in the table corresponds to a particular length of  string, 
and  is the only entry corresponding to that string.   Using  the 
index of the dictionary entry corresponds to a variable to  fixed 
length code (such as LZW).
     For a variable to variable length code,  one would also need 
to keep a count of how many times that string was used.   Because 
of the 16 bit limit for the arithmetic coder, this means that the 
total number of counts must be less than 64K.   Needless to  say, 
the total number of strings in such a dictionary would have to be 
much less than 1 Meg, probably less than 32K.


       | DEMONSTR.DOC | ELFBACK.PRG | WORDLIST.TXT |
-------+--------------+-------------+--------------+
   LZW |       32341  |      45147  |      905744  |
 Count |       31399  |      43143  |      771499  |
 Prune |       30574  |      39608  |      647192  |
 Merge |       28090  |      36325  |      606602  |
 Smart |       25974  |      35426  |      567752  |
-------+--------------+-------------+--------------+

     The above table shows the results for several LZ78 variants.  
The  first uses LZW for all sequences and arithmetic  for  single 
bytes.   The  second  keeps  track of the number  of  times  each 
sequence is used (variable to variable length coding).   Both use 
dictionaries with 8K entries.

     One of the problems with LZW is that once a string has  been 
added to the dictionary,  it can never be removed.   Instead, the 
entire  dictionary  is  thrown out  periodically  and  the  whole 
process  begins again.   However,  it is possible to implement  a 
hash table where entries can be removed.   Also,  one can set the 
count  of  an entry to 0 so that intermediate strings  which  are 
'never'  used  will  not affect the coding  (although  they  will 
continue to take up space in the hash table).
     'Prune'  in  the above table reduces the  count  on  every 
entry  whenever  the table is full (or the total  of  the  counts 
reaches 64K).   By doing all of the entries at once, we avoid the 
problem of having to re-sort.

    LZ78  and  LZW extend the strings in the  dictionary  by  one 
character  each  time  they are  used.   This  has  two  problems 
associated  with  it.   First,  the  strings  grow  very  slowly.  
Second, in the process of adding a long string which is repeated 
often,  one  will  also  form  lots of  short  strings  from  the 
leftovers at all the intermediate stages.
     A  much  more effective approach is to extend  a  string  by 
every  character in the following string when two  strings  occur 
concurently.   (Note,  this  means you cannot add strings to  the 
dictionary  until  they  have been sent to  the  receiver.)   The 
results for this method are shown as 'Merge' in the above table.

     It is not always best to choose the longest match available, 
since  the  end  may  not line up  with  another  string  in  the 
dictionary.   'Smart'  in the previous table shows  what  happens 
when  you  choose  the match length in order  to  code  the  most 
characters using two consecutive matches.   (Ties go to the match 
with the highest count.)  The best news is that this approach  is 
relatively fast.


LZ79 (combining LZ77 & LZ78)

     It  was observed that tweaking the algorithm  produced  very 
little change in the performance.  Also, the results were similar 
to  the 'backwards matching' algorithm discussed in the  previous 
chapter.   In  other words,  this is about as much as you can  do 
with  dictionary compression.   The next logical thing to try  is 
adding a 'FIFO buffer.'
     A  64  byte sliding window was added to  the  match  search. 
Lengths  2-64 were coded as 257-319 in the  arithmetic  character 
set (256 is used for the hash table).   Offsets were sent without 
weights.   'Long'  shows the results using the longer of the  two 
matches  (with  ties  going  to the hash  table)  and  no  length 
optimization  (compares to 'Merge' rather  than  'Smart').   This 
achieved a minor improvement in the first two files,  and a major 
improvement in WORDLIST.

       | DEMONSTR.DOC | ELFBACK.PRG | WORDLIST.TXT |
-------+--------------+-------------+--------------+
  Long |       28086  |      35397  |      522226  |
  Ties |       28829  |      35880  |      493510  |
  Best |       25785  |      34833  |      448995  |
  Tree |       25498  |      34410  |      465510  |
  Lags |       25397  |      34330  |      415494  |
  16K  |       24489  |      34218  |      415349  |
-------+--------------+-------------+--------------+

     'Ties' show the results of the above method when ties go  to 
the sliding window instead of the hash table.   This demonstrates 
the need for a more intelligent method for chosing which match to 
use, since the results are highly data dependent.
     'Best'  shows the results of using a Viterbi like  algorithm 
to  determine  the  best match & length (the  same  one  used  in 
'LZA2').  This method looks at every possible way to compress the 
next 64 bytes, at least until all paths have the same first step.  
Of course, this approach is very slow even with the hash table.
     'Tree'  uses a binary search tree together with  the  'Best' 
algorithm.   Instead  of looking at the last  64  characters,  it 
uses text pointers corresponding to the last 64 sequences coded.
     'Lags'  uses counts of how often a match was found based  on 
how  far  it  was  from  the  location  matched  (sort  of   like 
autocorrelation data).   As shown in the appendix of the previous 
report, these counts vary from file to file.
     Experiments  with  the  buffer sizes  found  that  the  best 
results  in  general were for a 64 entry FIFO buffer  and  a  16K 
entry HASH table.  These results are shown as '16K.'
     At  this point we are able to beat ZIP on two of  the  three 
files.  Unfortunately, nothing seems to help the third file much.  
Increasing  the  size of the FIFO buffer  helps  a  little.   The 
problem  with this file is that it doesn't compress well at  all, 
and the matches found tend to be very short.

Exhaustion

     Unfortunately,  I  was unable to find any way to  achieve  a 
substantial  inprovement over the above  results.   However,  the 
methods  developed during these experiments should be  applicable 
to improving the speed using the old LZA algorithm.

