Data compression/decompression method and apparatus

• US 5,281,967 A
• Filed: 01/29/1992
• Issued: 01/25/1994
• Est. Priority Date: 09/04/1991
• Status: Expired due to Term

• Current Assignee: Teledata Sound LLC (Intellectual Ventures LLC)
• Original Assignee: Computervision Corp. (PTC Inc.)
• Inventors: Jung, Robert K.
• Primary Examiner(s): Hoff, Marc S.
• Application Number:
  US07/827,634
• Time in Patent Office: 727 Days
• Field of Search: 341/51, 341/55, 341/65, 341/67, 341/95, 341/106
• US Class Current: 341/55
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A method and apparatus for compressing digital data uses data which has been previously compressed as a dictionary of substrings which may be replaced in an input data stream. The method and apparatus uses a hash table to take advantage of principles of locality and probability to solve the maximal matching substring problem inherent in this type of compressing apparatus, most of the time. The hash table consists of first-in, first-out (FIFO) collision chains of fixed, uniform numbers of pointers to substrings of data already compressed which potentially match an input substring. A link list is maintained for linking pointers to corresponding potentially matching strings. A companion decompressing method and apparatus receives compressed data from the compressing apparatus and expand that data back to its original form.

Claims

1. A system for processing digital input data, said input data being divisible into strings of bits representing symbols, comprising:

a memory for holding at least first and second strings of symbols from said input data, said first string having a prefix substring of a fixed length;

means for receiving said prefix substring and computing a first string hash value therefrom;

a hash table for receiving said first string hash value and providing one pointer to each of a number of locations in said second string having an associated second string substring of said fixed length with a second string hash value which matches said first string hash value;

means for receiving said first and second strings of symbols from said memory;

means for determining the longest second string substring match of a first string substring including said first string prefix substring, said means for determining including means for finding a second string substring match of a certain length pointed to by a first pointer, and means for performing a symbol comparison of said first string substring with a second string substring pointed to by a second pointer, beginning with a symbol being at least one symbol beyond said certain length; and

means for generating compressed output data responsive to said means for determining.

2. A system as claimed in claim 1 further including a link list for storing accessible pointer information, said information including a link between every pointer which points to a location having the same associated second string hash value.

3. A system as claimed in claim 1, wherein said memory further comprises:

a first buffer for holding said first string; and

a second buffer for holding at least one said second string.

4. A system as claimed in claim 1 wherein said compressed output data includes:

at least one of;

a pointer to one of said locations in said second string and

a partial pointer to one of said locations in said second string;

a first symbol corresponding to said location; and

a flag for identifying which of said pointer or partial pointer is included.

5. A system as claimed in claim 4 wherein said means for generating compressed output data comprises:

means for selecting at least one of said pointer and said partial pointer; and

means for generating said flag.

6. A system as claimed in claim 5, further including:

means for receiving said compressed output data; and

means for decompressing said compressed output data received;

wherein said means for decompressing said compressed output data comprises;

means for decoding said flag, and

means responsive to said means for decoding said flag, for translating said at least one of said pointer and said partial pointer into a decompressed data sequence identical to said input data.

7. A system as claimed in claim 6, wherein said means for translating comprises:

a memory for receiving sequences of decompressed data; and

means for identifying in said memory for receiving decompressed data sequences pointed to by said pointers and said partial pointers; and

means for copying said sequences identified by said means for identifying to new locations in said memory.

8. A system as claimed in claim 4, wherein said pointer comprises:

an offset for identifying said first symbol; and

a length over which said first string substring and a second string substring match.

9. A system as claimed in claim 4, wherein said partial pointer comprises:

a length over which said first string substring and a second string substring match.

10. A system for processing digital input data, said input data being divisible into strings of bits representing symbols, comprising:

a memory for holding at least first and second strings of symbols from said input data, said first string having a prefix substring of a fixed length;

means for receiving said prefix substring and computing a first string hash value therefrom;

a hash table for receiving said first string hash value and providing a pointer to a location in said second string having an associated second string substring of said fixed length with the same hash value;

a link list including a link between each pointer which points to a location having an associated second string substring of said fixed length with a same second string hash value;

means for receiving said first and second strings of symbols from said memory;

means for determining the longest second string substring match of a first string substring including said first string prefix substring, said means for determining including means for comparing said first string substring with a selected limited number of second string substrings, a fixed length of which has a same hash value as that of said first string hash value; and

means for generating compressed output data responsive to said means for determining.

11. A system as claimed in claim 10 wherein said means for determining further includes:

means for finding a second string substring match of a certain length pointed to by a first pointer; and

means for performing a symbol comparison of said first string substring with a second string substring pointed to by a second pointer, said means for performing beginning with a symbol being at least one symbol beyond said certain length.

12. A system as claimed in claim 10, wherein said memory further comprises:

a first buffer for holding said first string; and

a second buffer for holding at least one said second string.

13. A system as claimed in claim 10 wherein said compressed output data includes:

at least one of;

a pointer to one of said locations in said second string and

a partial pointer to one of said locations in said second string;

a first symbol corresponding to said location; and

a flag for identifying which of said pointer or partial pointer is included.

14. A system as claimed in claim 13 wherein said means for generating compressed output data comprises:

means for selecting at least one of said pointer and said partial pointer; and

means for generating said flag.

15. A system as claimed in claim 14 further including:

means for receiving said compressed output data; and

means for decompressing said compressed output data received, wherein said means for decompressing said compressed output data comprises;

means for decoding said flag; and

means responsive to said means for decoding said flag, for translating said at least one of said pointer and said partial pointer into a decompressed data sequence identical to said input data.

16. A system as claimed in claim 15, wherein said means for translating comprises:

a memory for receiving sequences of decompressed data; and

means for identifying in said memory for receiving decompressed data sequences pointed to by said pointers and said partial pointers; and

means for copying said sequences identified by said means for identifying to new locations in said memory.

17. A system as claimed in claim 13, wherein said pointer comprises:

an offset for identifying said first symbol; and

a length over which said first string substring and a second string substring match.

18. A system as claimed in claim 13, wherein said partial pointer comprises:

a length over which said first string substring and a second string substring match.

19. A method for processing digital input data, said input data being divisible into symbols, comprising the steps of:

receiving input data, including a first string having a prefix substring of a fixed length being less than a length of said first string;

computing a hash value of said prefix substring;

storing pointers in a hash table to each location in a second string;

generating a link list for linking pointers together in said hash table which point to locations having fixed lengths which have a same hash value;

comparing said first string with a selected limited number of substrings in said second string having linked pointers and fixed length hash values which match that of said prefix substring hash value; and

generating compressed output data based upon said comparison.

20. A system as claimed in claim 19 wherein said step of comparing includes:

locating a second string substring match of a certain length pointed to by a first pointer; and

performing a symbol comparison of said first-string with a second string substring pointed to by a second pointer, beginning with a symbol being one symbol beyond said certain length.

21. A system as claimed in claim 20 wherein the step of generating comprises the steps of:

outputting at least one of a pointer to a location in said second string and a partial pointer to a location in said second string;

outputting a first symbol corresponding to said location; and

outputting a flag for identifying which of said pointer or partial pointer is outputted.

22. A system as claimed in claim 20 further comprising the step of:

decompressing said compressed output data.