CP/M/CPM_CDROM.iso/mbug/mbug078.arc/ABSTRACT.TEC

Text File | 1979-12-31 | 4KB | 74 lines

                       Technical Abstract

CRUNCH 1.x maintained a table representing up to 4096 strings  of
varying lengths using the so called LZW algorithm, which has been
described in the earlier documentation.  These strings were  ent-
ered into a table in a manner where the strings content was  used
to  determine the physical location (hashing), and that  location
was used as the output code.  Hash "collisions" were resolved  by
maintaining another 12 bits of data per entry which was a "link",
or pointer to another entry.

In contrast, CRUNCH 2.x uses an "open-addressing, double hashing"
method similar to that employed in the UNIX COMPRESS.  This meth-
od  involves a table of length 5003, where only 4096 entries  are
ever made, insuring the table never gets much more than about 80%
full.  When a hash collision occurs, a secondary hash function is
used to check a series of additional entries until an empty entry
is  encountered.   This method creates a table filled  with  many
criss-crossed "virtual" chains, without the use of a "link" entry
in the table.

One reason this is important is that [without using any addition-
al  memory] the 1 1/2 bytes which were previously allocated as  a
link can now become the [output] code number.  This enables us to
assign  code  numbers, which are kept right alongside  the  entry
itself,  independently  of the entry's physical  location.   This
allows  the codes to be assigned in order, permitting the use  of
9-bit  representations  until there are 512 codes in  the  table,
after which 10 bit representations are output, etc.

The  variable bit length method has three ramifications.   It  is
particularly  helpful when encoding very short files,  where  the
table  never even fills up.  It also provides a fixed  additional
savings  (not  insubstantial) even when the table does  fill  up.
Thirdly,  it  reduces the overhead associated with  an  "adaptive
reset"  to the point where it becomes a very viable  alternative.
"Adaptive  reset" simply means throwing out the whole  table  and
starting over.  This can be quite advantageous when used  proper-
ly.  CRUNCH v2.x employs this provision, which was not  incorpor-
ated in the V1.x algorithm.

"Code  reassignment" is an advancement I introduced with the  re-
lease  of CRUNCH v2.0 based on original work.  It is not used  in
COMPRESS,  any  MS-DOS ARC program, or [to the best of  my  know-
ledge]  any other data compression utility  currently  available.
There are many ways one might go about this (and at least as many
possible pitfalls).  The algorithm I selected seemed to represent
a good tradeoff between speed, memory used, and improved  perfor-
mance, while maintaining "soundness of algorithm" (ie it works).


Briefly,  it works as follows: Once the table fills up, the  code
reassignment process begins. (At this same time, the  possibility
of  adaptive reset is also enabled).  Whenever a new  code  would
otherwise be made (if the table weren't full), the entries  along
the  hash  chain  which  would normally  contain  the  entry  are
scanned.  The first, if any, of those entries which was made  but
never  subsequently referenced is bumped in favor of the new  en-
try.   The uncruncher, which would not normally need  to  perform
any  hash  type function, has an auxiliary  physical  to  logical
translation table, where it simulates the hashing going on in the
cruncher.   In this fashion it is able to exactly  reproduce  the
reassignments made my the cruncher, which is essential.

---

I  hope to write an article soon on "Recent Advancements in  Data
Compression".  It would cover the recent history generally, along
with a more detailed description of some of the algorithms, and a
series of additional ideas for future enhancement.

                                              Steven Greenberg
                                              16 November 1986