                 Experiments in Data Compression
                         by John Kormylo
                         E.L.F. Software


Introduction

     When first developed,  LZA compression was superior to  that 
obtained  using ZIP or LZH.   Since then,  both ZIP and LZH  have 
improved their compression efficiency dramatically.   This report 
documents attempts to improve LZA to regain its advantage.  While 
it  is possible to out-perform ZIP  consistently,  the  resulting 
algorithm is glacially slow.


LZA Description

     The  LZA  algorithm  is  a  variant  of  LZSS  and  adaptive 
arithmetic (see "The Data Compression Book" by Mark Nelson).   It 
differs  from standard adaptive arithmetic by using a "new  code" 
character.   It  differs from LZSS by using additional  codes  to 
transmit match tokens.
     The  "new  code"  character is followed  by  a  (relatively) 
uncompressed character which had previously been assigned a count 
of zero.  Adaptive arithmetic normally assigns a minimum count of 
one  to all 256 characters,  which makes the  coding  inefficient 
when  only a few characters are used  (e.g.,  text  files).   The 
overhead  for  entering the character set using  the  "new  code" 
character  is comparable to the overhead for  transmitting  count 
information for a non-adaptive method. 
     The  "new code" character always has a count of  one  (until 
no  new codes are left.)  The new codes are entered  by  dividing 
the  current range (high - low) into 'n' segments of equal  size, 
where  'n' is the number of remaining characters with a count  of 
zero.

     LZSS adds an extra bit before every character or match token 
to  indicate which is being used.   LZA introduces an  additional 
character  which is followed by the match token.   If  there  are 
exactly the same number of tokens as characters transmitted, then 
this  additional character will require only one bit to be  coded 
and  every other character will require one additional bit to  be 
coded.   For any ratio other than one to one,  using this special 
character is more efficient than using a single bit.
     Actually, LZA adds 64 additional characters corresponding to 
64 possible match lengths.  This takes advantage of the fact that 
short matches are far more common than long matches by  assigning 
a count to each match length.  Also, since matches longer than 32 
bytes are rare,  assigning an initial count of zero and using the 
"new code" character turns out to be very effective.
     Past  locations  in the message are organized into  a  self-
balancing  binary  search  tree for faster matching.


LZA Improvements

     Not  all  past locations should be included  in  the  binary 
search tree.   Nelson mentioned that it is common to not  include 
those locations skipped over when a match is found for reasons of 
speed.  As it turns out, the probability of matching one of these 
locations  is so low that not including them in the  search  tree 
improves the compression as well.
     This is not the case,  however,  with the location  matched.  
While there is already another location in the search tree  which 
matches  the first few characters,  the probability of finding  a 
longer  match  using the new location is high enough  to  justify 
its inclusion.
     Another  improvement can be made by keeping a count for  how 
often  each location is used.   Rather than dividing the  current 
range into segments of equal size for each location in the search 
tree,  the size of the segments can be made proportional to  this 
count (set to one initially).   Also,  when the tree is full, the 
new  LZA does not throw out old entries with counts greater  than 
one.   Instead  it  decrements the count and allows it  to  cycle 
through again (until the count goes to zero).
     For speed,  LZA keeps a table of search tree indexes  sorted 
by  count  (in decreasing order),  plus an array  containing  the 
number  of  entries with counts 1 through 16.   The  sum  of  all 
counts up to an entry with a count of one is given by the sum of 
all  counts (precomputed) minus the number of entries  after  the 
index  (times one).   This is much faster than summing up to  16K 
numbers.
     Also, if a location is used more than once, odds are that it 
will use the same length as before.  Therefore, one of the length 
codes means "use the same length as last time."  (It replaced the 
length  =  2 code,  which was never used in practice.)   Since  a 
location  must  have  been  used before for  this  length  to  be 
defined,  only those search tree entries with counts greater than 
one are used when computing the index code.
     While  searching through the binary tree will easily  locate 
the longest match,  it will not necessarily locate the best match 
of that length (the one with the highest count).   Any match with 
the same length as the one found will be in the sub-tree starting 
with the entry found,  but one must search both branches to  find 
all  of  them.   This can be done using a recursive  function  to 
search both branches whenever a duplicate match is found.


Tree Size Experiments

     Text  files  generally do best with a very large  tree  (16K 
entries  or  more).   Programs do better with  trees  with  fewer 
entries.  A sorted text file (actually, a dictionary) worked best 
with a 16 entry search tree.
     The following table shows the compressed file size for three 
test  datasets as a function of tree size.   For  comparison  the 
corresponding  ZIP compressed file sizes are included.   (Two  of 
these  files can be downloaded from Genie,  and one is  from  the 
Atari developer's package.)
     One  way  to improve performance over a wide range  of  tree 
sizes  is to use more than one tree at a time and include a  code 
to select which tree to use.   Best results were obtained using 3 
trees:  sizes 16,  512 & 16K.   These results are included in the 
following table (as "3 trees").
     Actually,  there are many ways to do this.  One way would be 
to use a different group of length codes for each tree.   Another 
would be to use regular codes to indicate the tree selected and a 
separate code set (like the index code) for the length indicator.  
However best results were obtained using the same length codes as 
before  and  a  separate  set of codes  for  the  tree  selection 
indicator.


  tree | DEMONSTR.DOC | ELFBACK.PRG | WORDLIST.TXT |
-------+--------------+-------------+--------------+
    16 |       45055  |      46100  |  >   476285  |
    32 |       44186  |      43144  |      488860  |
    64 |       40211  |      41018  |      506394  |
   128 |       37345  |      38961  |      521958  |
   256 |       34163  |      36954  |      539121  |
   512 |       31198  |      35443  |      559172  |
  1024 |       28756  |      34483  |      582964  |
  2048 |       27039  |      33763  |      612184  |
  4096 |       25765  |  >   33673  |      639819  |
  8192 |       25114  |      33822  |      658753  |
 16384 |  >    24942  |      34003  |      670774  |
-------+--------------+-------------+--------------+
   ZIP |       25207  |      32444  |      496880  |
-------+--------------+-------------+--------------+
3 trees|       24928  |      33073  |      559810  |
  avg  |       24638  |      33139  |      556216  |
-------+--------------+-------------+--------------+
  gaps |       28202  |      33867  |      471766  |
  trim |       24910  |      33163  |      531371  |
  best |       22828  |      32191  |      457176  |


     It is interesting to note that this method out-performed the 
best  single tree size for two of the  three  files.   Also,  the 
resulting   counts  showed  that  all  three  trees   were   used 
frequently,  and that the smaller trees were used far more  often 
than would be indicated by their relative sizes.
     Up to this point,  comparisons between matches of  different 
lengths were made by adding the cost of the missing characters to 
the  shorter of the two matches.   However,  it is possible  that 
more  than  one  short match could  replace  a  long  match.   To 
overcome  this  problem,  one can compare the  average  cost  per 
character for the two matches.   Specifically,  this is  computed 
using
              avg = log(4294967296.0 / size) / len

where 'len' is the number of characters and 'size' is the segment 
size   (starting  from  4294967296)  for   resulting   arithmetic 
compression for the length,  tree,  and index codes.
     This  not only works well for selecting which tree  to  use, 
but also whether to use a match at all (by comparing the  average 
cost  per  character to the cost of the  first  character).   The 
results are shown in the first table (as 'avg').

     The most surprizing thing is that this approach performed so 
poorly  on WORDLIST.TXT relative to how it performed  using  only 
the 16 entry tree.   A test was run which used the 16 entry  tree 
wherever  possible,  and the other trees only when no  match  was 
found.  The resulting compressed dataset was 556869 bytes long.
     It  was  also discovered that the 'avg' method used  the  16 
entry tree 93278 times, the "use 16 if possible" test used the 16 
entry tree 99475 times,  but using the 16 tree only found  164708 
matches.   These  matches must have come from INSIDE the  matches 
found  in the 512 and 16K entry trees.   Obviously,  no  "greedy" 
algorithm was going to find those matches.
     Another test was run which only looked for matches from  the 
large  search trees to fill in the gaps between matches with  the 
small  trees.   The  results  are shown in the  first  table  (as 
'gaps').   While this worked well for WORDLIST.TXT,  it performed 
very poorly on DEMONSTR.DOC.
     A  similar test was run which used shorter matches when  the 
longest  match found extended past the start of a match from  the 
16  entry  tree.   The results are shown in the first  table  (as 
'trim').   This  performed well on all test files.
     While these tests were not good enough,  they did show  that 
using  three  trees could give acceptable results if  the  proper 
matches were used.   However,  to find these matches it would  be 
necessary  to test all possible ways to compress the  data.   The 
algorithm tried would check all possible combinations of  matches 
and  characters until a unique first step was found,  32 bits  of 
compressed output was produced,  or 256 bytes of input data  were 
compressed  (whichever  came first).   After the first  step  was 
implemented,  the  process was started all over again  since  the 
counts  and search trees had been modified and the  old  analysis 
was  no longer valid.   The results are shown in the first  table 
(as  'best').   The only problem with this method is that  it  is 
VERY slow.


Finding Contiguous Matches

     In  this  section  we  will  attempt  to  equal  the  'best' 
algorithm using another approach.
     If  a  match can be found which extends past the  end  of  a 
larger match,  but no match can be found at the end of the larger 
match,  then the location inside the smaller match  corresponding 
to the end of the larger match must have been skipped.  Therefore 
by including the skipped locations in (some) of the search trees, 
one should be able to locate more contiguous matches.
     The following table shows the compressed file sizes using  a 
single  search tree which includes all locations  (no  skipping).  
These do not perform nearly as well as the corresponding trees in 
the first table.
     If  we  combine  the 3 trees  as  before,  the  results  are 
surprisingly  respectable.   The '0,3' values use no skipping  in 
all three trees (16,  512, & 16K).  The '1,2' values use skipping 
in the 16K entry tree but not in the other two.  The '2,1' values 
use skipping in all but the 16 entry tree.

  tree | DEMONSTR.DOC | ELFBACK.PRG | WORDLIST.TXT |
-------+--------------+-------------+--------------+
    16 |       45334  |      47560  |      623420  |
   512 |       39661  |      40590  |      620509  |
 16384 |       34762  |      37505  |      696476  |
-------+--------------+-------------+--------------+
  0,3  |       25401  |      32829  |      516093  |
  1,2  |       24570  |      33000  |      514302  |
  2,1  |       24641  |      33163  |      511917  |
-------+--------------+-------------+--------------+
  3,1  |       24612  |      33094  |      507442  |
  3,2  |       24457  |      32843  |      504815  |
-------+--------------+-------------+--------------+
 mixed |       24261  |      32854  |      503976  |


     Even  better results can be obtained using additional  trees 
which contain only the (previously) skipped locations.  The '3,1' 
values  use  the  previous  3 trees  (16,  512  &  16K)  plus  an 
additional  16 entry tree which contains ONLY skipped  locations.  
The  '3,2' values use the same plus an additional 512 entry  tree 
which also contains ONLY skipped locations.
     The  best  results for this approach were obtained  using  a 
'3,2' tree combination as before, but now the first 16 entry tree 
contains  ONLY  the matched locations while the second  16  entry 
tree  contains  ALL locations.   These results are shown  in  the 
above table (as 'mixed').
     

Biting the Bullet

     While the results in Table 2 are interesting,  the only  way 
to  consistently  out-perform  ZIP  is to  use  the  full  search 
('best')  algorithm.   In this section we will be concerned  with 
improving this approach.
     There  are  several reasons why this approach is  more  time 
consuming.   First, it must search for a match at every location.  
Second,  it  must  search for the best match  for  each  possible 
length.   The  time  required to perform this search  is  roughly 
proportional  to how many matches are found.   Finally,  it  must 
repeat some of these searches,  since the results are thrown away 
once the next code is determined.
     In  the original algorithm,  the limiting factor was  almost 
always  the  32 bits of output.   In fact,  one  can  reduce  the 
maximum  number  of  input bytes to 65 with no  penalty  at  all.  
Further  reduction  requires  also  reducing  the  maximum  match 
length.   The  results for various length parameters in shown  in 
the next table.  However, the resulting increase in speed was not 
substantial.

length | DEMONSTR.DOC | ELFBACK.PRG | WORDLIST.TXT |
-------+--------------+-------------+--------------+
    65 |       22828  |      32191  |      457176  |
    33 |       22928  |      32261  |      457174  |
    17 |       23794  |      32726  |      455700  |
     9 |       26552  |      34073  |      484471  |

     On the other hand,  by increasing the number of output  bits 
(actually,  by  computing  segments  sizes  with  floating  point 
numbers   instead  of  unsigned  longs)  one  can   improve   the 
compression, as shown in the next table.  At least using floating 
point operations does not significanly slow it down any  further.  
The  limiting  factor now becomes the number of tests  needed  to 
determine  a unique first step.   This is usually  only  slightly 
larger than the initial match length.


length | DEMONSTR.DOC | ELFBACK.PRG | WORDLIST.TXT |
-------+--------------+-------------+--------------+
    65 |       22196  |      32035  |      455017  |
    33 |       22329  |      32137  |      455261  |
-------+--------------+-------------+--------------+
   len |       22522  |      32054  |      461290  |
 first |       22595  |      32067  |      479614  |
  save |       22170  |      32037  |      456498  |


     One way to reduce the number of match searches is to  assume 
that  a match taken from a smaller tree is always  preferable  to 
the same length match taken from a larger tree.   This turns  out 
not  to be the case,  however,  as shown in the above  table  (as 
'len').  Nor does it run much faster.
     Alternatively,  one  could  eschew the search for  the  best 
match, taking the first match found.  Again, there is little time 
saved  at the cost of compression efficiency.   The  results  are 
shown in the above table (as 'first').
     Another  possible way to improve speed would be to save  the 
results after each step (as opposed to starting all over  again).  
This would mean far fewer searches.   However,  it would  require 
performing  all of the search tree updates and sorts  and  saving 
enough information to undo them.   Because of all the  additional 
tree and sort operations,  this approach is only slightly  faster 
than the 'best' algorithm.  The good news is that the performance 
is about the same, as shown in the above table (as 'save').
     Since LZW is inherently faster than LZSS, attempts were made 
to use LZW variants together with the full search.   However, not 
only  were  the  results  not even  in  the  same  ballpark,  the 
algorithm speed still left a lot to be desired.

