🚀 go-pugleaf

The following has been posted on behalf of Ghiora Drori
(drori@altos.Altos.COM) who is unable to post it from his site.

The first part of this post is the text of a US patent which was posted
by me several months ago;  his article in response follows.

Please direct all inquiries regarding this post to drori@altos.Altos.COM.

-------------------------------------------------------------------------
-------------------------------------------------------------------------
2182704   3156012
E/ APPARATUS AND METHOD FOR VERY HIGH DATA RATE-COMPRESSION INCORPORATING
    LOSSLESS DATA COMPRESSION AND EXPANSION UTILIZING A HASHING TECHNIQUE
Document Type: UTILITY
Inventors: Gibson Dean K (US); Graybill Mark D (US)
Assignee: Intersecting Concepts Inc
                   Applic      Applic     Patent      Issue
                   Number       Date      Number       Date
                  ---------    ------   ----------    ------
Patent:           US 539880    900618    US 5049881   910917
Priority Applic:  US 539880    900618
Abstract:
A method and apparatus for compressing digital data that is represented as
a sequence of characters drawn from an alphabet. An input data block is
processed into an output data block composed of sections of variable
length. Unlike most prior art methods which emphasize the creation of a
dictionary comprised of a tree with nodes or a set of strings, the present
invention creates its own pointers from the sequence characters previously
processed and emphasizes the highest priority on maximizing the data
rate-compression factor product. The use of previously input data acting as
the dictionary combined with the use of a hashing algorithm to find
candidates for string matches and the absence of a traditional string
matching table and associated search time allows the compressor to very
quickly process the input data block. Therefore, the result is a high data
rate-compression factor product achieved due to the absence of any string
storage table and matches being tested only against one string.

Exemplary Claim:
1. A compression method for compressing a stream of input data into a
   compressed stream of output data based on a minimum number of characters
   in each input data subblock to be compressed, said compression method
   comprising the steps of: a. initializing a hash table and initializing
   an SRC pointer; b. processing input data in the order in which the
   characters in the data appear and hashing input data subblocks of the
   minimum compression size selected; c. maintaining a hash table which
   contains at each entry, an SRC pointer which points to a previous
   subblock which hashed to this hash table entry, such that the
   possibility of any string of data previously occurring in the input
   block may be tested by hashing the current subblock to a hash table
   entry, obtaining the previous SRC pointer contained in that entry, and
   comparing the two strings of data; d. if the two strings of data match
   on at least the size of the subblock, then generating a backwards
   pointer to the previous occurrence of the same string of data and
   thereby compressing the second occurrence of the string of data; e. if
   the two strings of data do not match, then storing the string of data as
   incompressible data; and f. continuing steps b. through e. until the
   entire input data has been processed.

Class: 341095000
Class Cross Ref: 341051000; 341055000
IPC: H03M-007/30
-------------------------------------------------------------------------
-- 
Mike Doughney             mike@access.digex.com            +1 301 220 2020
Digital Express Group, 6006 Greenbelt Road #228, Greenbelt, Maryland 20770
  **** Express Access:  Public Access Unix for Washington/Baltimore ****
          **** For more information,  mail to info@digex.com ****





The following are parts of an article I submitted to the
College of Professional Studies at the University of San-
Francisco.



                        Compression
                      By Ghiora Drori

During 1986 I worked as a consultant for Algorithmic
Research. The company is based in Israel and it's main
business is software and hardware for securing data. The
company has a few products based on DES and RSA. These
products have been sold mainly to the banking industry in
Europe. Since some of these products are used for preparing
data for transmission over networks and telephones lines it
is useful to be able to compress the data before sending it.

-----
Unrelated part of the article deleted here..
-----

My task was to write a
new compression program based on a different method known as
LZ for them. This method has a few advantages over the
Huffman method among them:it usually gives better
compression and the algorithm is dynamic...

----------------
Unrelated part of the article deleted here..
----------------

Since High speed was necessary it was not possible to scan
the buffer in a sequential method looking at each character
before the present character to see if it is the beginning
of a string that can be used. What was done is to create two
4096 byte buffers and two hash tables one for each buffer.
The buffers are initialized to 00h and the hash tables are
initialized to FFh when we start. The data to be compressed
is read into the first buffer. once the buffer is full or
the data stops coming in we proceed to compress. Each char
in the buffer is hashed. If the hash result points to an FFh
in the hash table while looking at the first hash table we
go to the next part of the program assuming that the string
is not in what we will call the old table. (This is always
the situation in the beginning.) If we find an address in
the table we check to see how long a match it makes with the
incoming string. This is repeated up to three times to get
around cases where different strings hash to the same
address in the hash buffer.

This is done twelve times each time with an additional char
being hashed. Each time the longest matching string found is
remembered; address and length. (Again when starting we
would only do this process once for each char since the hash
tables are all filled with FFh.) The same process is
repeated with second buffer and the second hash table
however this time when we hit an FFh we replace the FFh
with the address of the first char we started hashing with.
We now check to see what is the maximum length of string we
found in both parts of the buffer. If the length is zero or
one we write out a single char length followed by the char.
If we have a string greater than one we write out an address
and length. We now restart the search and hashing from the
character following the last one in the string we found. As
we go along the second hash buffer is filled with addresses.
once we get to its end it becomes the old buffer. What used
to be the old buffer and its hash table are cleared and they
become the new buffer and new hash table and we read chars
into (The first time the switching is done it is meaningless
since it is empty.) Once we pass the first 4096 bytes we
always have one full buffer that is still being used for
address data but its hash table is no longer being updated
and a new buffer whose hash table is being updated as we
scan through the text in it.
^M
Remarks:
The hashing is done by XOR'ing the next char with a random
number table and XOR'ing again with previous hash result.
The XOR hashing is very fast and provides us with good
randomizing.

The program as written is very fast and can work at up to 16
Kbytes per second on an IBM AT 10Mhz. It gives
very good compression.
To run it on an IBM compatible (It is in the back of the
folder.) Type lz Filename1 Filename2.  To expand a file use
expand Filename2 Filename3 and Filename3 will contain the
same data as Filename1.

--------------------------------------
More irrelevent stuff deleted here...
------------------------------------

                        BIBLIOGRAPHY


1  Jacob Ziv and Abraham Lempel, A Universal Algorithm for
   Sequential Data Compression.

2  The Lz algorithm overview (Enclosed.)

3  Robert Sedgewick, Algorithms ,Addison Wesley 1988 P
   319-333 File Compression.

The following is reference 2:

;---------------------------------------------------------------------
;  The LZ algorithm overview:
;
; Three different Hash "functions":
;
;  RANDOM:-
;  A random table of 256 word values, each in the range 0..8K-1.
; i points to the hash and input buffers to be used (1 or 2)
; len is the length of the string we are hashing.
;
;  Case length = 1 :
;   Hash1(i,pointer,1) := Random(Inbuf(i,pointer))
;   Hash2(i,pointer,1) := Hash1(i,pointer,1) xor
;         Random((Inbuf(i,pointer) xor Hash1(i,pointer,1)) mod 0FFh)
;   Hash3(i,pointer,1) := Hash2(i,pointer,1) xor
;         Random((Inbuf(i,pointer) xor Hash2(i,pointer,1)) mod 0FFh)
;
;---------------------------------------------------------------------
;   Case length > 1:
;    Hash1(i,pointer,len) :- returns a Hash value of the string
;           Inbuf(i,pointer),Inbuf(i,pointer+1),... Inbuf(i,pointer+len-1)
;    Hash2(i,pointer,len), Hash3(i,pointer,len) :- as above.
;
;   Hash1(i,pointer,len):= Hash3(i,pointer,len-1) xor
;         Random((Hash3(i,pointer,len-1) xor Inbuf(i,pointer+len-1)) and 0FFh)
;
;   Hash2(i,pointer,len):= Hash1(i,pointer,len) xor
;         Random((
;         Hash1(i,pointer,len) xor
;         Inbuf(i,pointer+len-1)) and 0FFh)
;
;   Hash3(i,pointer,len):= Hash2(i,pointer,len) xor
;         Random((
;         Hash2(i,pointer,len) xor
;         Inbuf(i,pointer+len-1)) and 0FFh)
;-----------------------------------------------------------------------
;
;  function compstr(i,p1,ii,p2:integer);
;  {Returns the maximal equal prefix length
;  compares Inbuf(i,p1) with Inbuf(ii,p2)
;           Inbuf(i,p1+1) with Inbuf(ii,p2+1),
;           etc.}
; for j:=0 to 30
;     if Inbuf[i,p1+j] <> Inbuf[ii,p2+j] then goto 199;
; end;
; 199:compstr:=j;
; end;
;
;
;  Given an index i (for buffer i=0,1) and a pointer p that points
;  to the current character in Inbuf(i) do as follows:
;    ii:=1-i; {ii denotes the other index}
;
;
;  maxlen:=1;
;
;  maxlenii:=1;
;  for j:=2 to 12 do
;  begin
;     hp:=hash1(ii,p,j)
;     p2:=Hash(ii,hp);
;     If p2 = FFFFh then goto 99;
;     m := compstr(i,p,ii,p2);
;     if m < j then begin
;             hp:=hash2(ii,p,j)
;             p2:=Hash(ii,hp);
;             if p2=FFFFh then goto 99;
;             m := compstr(i,p,ii,p2);
;             if m < j then begin
;                  hp:=hash3(ii,p,j)
;                  p2:=Hash(ii,hp);
;                  if p2=FFFFh then goto 99;
;                  m := compstr(i,p,ii,p2);
;                  if m < j then goto 99;
;             end;
;      end;
;     if m>maxlen then begin
;        maxlenii:=m;
;        maxpii:=p2;
;     end;
;  end;
;
; 99:
;
;  maxleni:=1;
;  for j:=2 to 12 do
;  begin
;     hp:=hash1(i,p,j)
;     p2:=Hash(i,hp);
;     If p2 = FFFFh then begin
;                      Hash(i,hp):=p;
;                      goto 98;
;                     end;
;     m := compstr(i,p,i,p2);
;     if m < j then begin
;             hp:=hash2(i,p,j)
;             p2:=Hash(i,hp);
;             If p2 = FFFFh then begin
;                               Hash(i,hp):=p;
;                               goto 98;
;                             end;
;             m := compstr(i,p,i,p2);
;             if m < j then begin
;                  hp:=hash3(i,p,j)
;                  p2:=Hash(i,hp);
;                  If p2 = FFFFh then begin
;                                    Hash(i,hp):=p;
;                                    goto 98;
;                                 end;
;                  m := compstr(i,p,i,p2);
;                  if m < j then goto 98;
;             end;
;      end;
;     if m>maxlen then begin
;        maxleni:=m;
;        maxpi:=p2;
;     end;
;  end;
;
;  98: if maxlenii > maxleni then begin
;            maxlen:=maxlenii;
;            maxp:=maxpii+4K;
;         end
;         else begin
;            maxlen:=maxleni;
;            maxp:=maxpi;
;         end;
;
;-----------------------------------------------------------------
;
The above article was evaluated on 4/24/89 by an evaluator
>from the University of San Francisco. I have a copy of all the
original documents including a signed report granting me credit for this
article. I believe the above algorithm is simmilar to the one in
the patent described in the FAQ...

Ghiora Drori

Disclaimer:
The above posting is my own and in no way represents Acer America inc,
or Algorithmic Research Inc.


-- 
Mike Doughney              mike@access.digex.com               +1 301 220 2020
Digital Express Group, 6006 Greenbelt Road #228, Greenbelt, Maryland 20770 USA
Express Access Online Communications for Washington/Baltimore:  info@digex.com
       Login as "new": Washington 301-220-0462, Baltimore 410-531-2044