Adaptive data compression system

• US 5,229,768 A
• Filed: 01/29/1992
• Issued: 07/20/1993
• Est. Priority Date: 01/29/1992
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Traveling Software, Incorporated
• Inventors: Thomas, Kasman E.
• Primary Examiner(s): Logan, Sharon D.
• Application Number:
  US07/827,737
• Time in Patent Office: 538 Days
• Field of Search: 341/51, 341/50, 341/95, 341/55, 341/60, 341/79, 341/81, 341/87, 341/65, 341/67, 341/107, 383/56, 358/261.2
• US Class Current: 341/51
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A system for data compression and decompression is disclosed. A series of fixed length overlapping segments, called hash strings, are formed from an input data sequence. A retrieved character is the next character in the input data sequence after a particular hash string. A hash function relates a particular hash string to a unique address in a look-up table (LUT). An associated character for the particular hash string is stored in the LUT at the address. When a particular hash string is considered, the content of the LUT address associated with the hash string is checked to determine whether the associated character matches the retrieved character following the hash string. If there is a match, a Boolean TRUE is output; if there is no match, a Boolean FALSE along with the retrieved character is output. Furthermore, if there is no match, then the LUT is updated by replacing the associated character in the LUT with the retrieved character. The process continues for each hash string until the entire input data sequence is processed. The method of decompression includes the steps of initializing a decompression LUT to mirror the initial compression LUT and receiving a representational form output from the compressor. The representational form is generally analyzed one character at a time. If the character is a Boolean TRUE, then the content of the LUT addressed by the most recently decoded hash string is output. Otherwise, if the character is a Boolean FALSE, the next character (exception character) in the representational form is output and the content of the LUT addressed by the most recently decoded hash string is output.

Claims

1. An adaptive data compression method for compressing an input data sequence comprised of a plurality of sequential discrete characters, said method comprising the steps of:

(a) forming a current hash string by sequentially retrieving from said input data sequence a predetermined number of characters, said current hash string having an associated character;

(b) retrieving a retrieved character, said retrieved character sequentially following said current hash string in said input data sequence;

(c) comparing said retrieved character to said current hash string'"'"'s associated character;

(i) if said retrieved character matches said current hash string'"'"'s associated character, outputting a match indicator; and

(ii) if said retrieved character does not match said current hash string'"'"'s associated character, outputting both a no-match indicator and said retrieved character as an exception character and associating said retrieved character with said current hash string;

(d) forming a new hash string having said predetermined number of characters and including said retrieved character, said new hash string having an associated character;

(e) assigning said new hash string as said current hash string; and

(f) repeating steps (b) through (e).

2. The method of claim 1, wherein said step of repeating steps (b) through (e) is repeated until no more characters are present in said input data sequence.

3. The method of claim 1, wherein said step of forming a new hash string includes the step of concatenating said retrieved character to said current hash string and deleting the first character of said current hash string'"'"'s.

4. The method of claim 1, further including the step of forming a hash table in a memory device, said hash table for storing said associated characters, said hash table comprising a plurality of memory slots for storing said associated characters, each of said memory slots having a memory address.

5. The method of claim 4, wherein said step of comparing said retrieved character includes the steps of:

generating a memory slot address by performing a hash function on said current hash string;

looking-up said current hash string'"'"'s associated character at said memory slot address; and

if said retrieved character does not match said current hash string'"'"'s associated character, associating said retrieved character with said current hash string by storing said retrieved character at said memory slot address.

6. The method of claim 4, wherein an initial associated character is stored in each of said memory slots prior to said step of comparing said retrieved character.

7. The method of claim 4, wherein the output of step (c) is written to a compressed data file in said memory device.

8. The method of claim 1, wherein said match indicator is a Boolean TRUE bit and said no-match indicator is a Boolean FALSE bit.

9. The method of claim 1, wherein said hash strings are two characters in length.

10. The method of claim 1, wherein said hash strings are three characters in length.

11. The method of claim 7, further comprising the steps of decompressing said compressed input data by:

(a) outputting a current decompression output hash string equivalent to said current hash string of step (a) of claim 1, said current decompression output hash string having an associated character;

(b) retrieving a next sequential character from said compressed data file; and

(i) if a match indicator is retrieved, outputting said current decompression output hash string'"'"'s associated character; and

(ii) if a no-match indicator is retrieved, retrieving and outputting said next sequential exception character from said compressed data file and associating said exception character to said current decompression output hash string;

(c) forming a new decompression output hash string including said character output at step (b);

(d) assigning said new decompression output hash string as said current decompression output hash string; and

(e) repeating steps (b) through (d).

12. The method of claim 11, wherein said step (e) is repeated until no more characters are remaining in said compressed data file.

13. The method of claim 11, wherein said step of forming a new decompression output hash string includes the step of concatenating said retrieved character to said current decompression output hash string and deleting said current decompression output hash string'"'"'s first character.

14. The method of claim 11, further including the step of forming a decompression hash table for storing said associated characters, said decompression hash table comprising a plurality of decompression memory slots for storing said associated characters.

15. The method of claim 2 further comprising the steps of decompressing said input data by:

(a) forming a current output hash string identical to the current hash string of step (a) of claim 1;

(b) outputting said current output hash string, said current output hash string having an associated character;

(c) receiving the next match indicator or no match indicator; and

(i) if a match indicator is received, outputting said current output hash string'"'"'s associated character; and

(ii) if a no-match indicator is received, receiving and outputting a next sequential exception character and associating said exception character to said current output hash string;

(d) forming a new output hash string by deleting said current output hash string'"'"'s first character and concatenating the last character output;

(e) assigning said new output hash string as said current output hash string; and

(f) repeating steps (c) through (e) until no more match indicators or no-match indicators are received.

16. The method of claim 15, further including the step of forming a decompression hash table in a memory device, said decompression hash table for storing said associated characters, said decompression hash table comprising a plurality of memory slots for storing said associated characters, each of said memory slots having a memory address.

17. A data compressor for compressing an input data sequence comprised of a plurality of sequential discrete characters, the data compressor comprising:

(a) an input component for receiving an input data sequence;

(b) processor means for;

(i) forming a current hash string by sequentially retrieving from said input data sequence a predetermined number of characters, said current hash string having an associated character;

(ii) retrieving and comparing a retrieved character, said retrieved character next sequentially following said current hash string in said input data sequence, to said current hash string'"'"'s associated character; and

(iii) outputting a match indicator if said retrieved character matches said associated character; and

outputting both a no-match indicator and said retrieved character as an exception character if said retrieved character does not match said associated character and associating said retrieved character with said current hash string.

18. A data compressor as claimed in claim 17, wherein said processor means further includes means for forming a new hash string having said predetermined number of characters and by concatenating said retrieved character to said current hash string and deleting a first character from said current hash string, and for assigning said new hash string as said current hash string, and for analyzing said entire input data sequence.

19. The compressor of claim 17, further including a memory device in which a hash table is established, said hash table comprising a plurality of memory slots for storing associated characters, each of said memory slots having a memory address.

20. The compressor of claim 17, wherein said means for comparing a retrieved character to said current hash string'"'"'s associated character performs a hash function on said hash string to derive a memory slot address and compares said associated character at said memory slot address to said retrieved character and further associates said retrieved character with said current hash string by storing said retrieved character in said memory slot address.