Data compression method and apparatus implemented with limited length character tables

• US 6,400,286 B1
• Filed: 06/20/2001
• Issued: 06/04/2002
• Est. Priority Date: 06/20/2001
• Status: Active Grant

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Cooper, Albert B.
• Primary Examiner(s): JeanPierre, Peguy
• Assistant Examiner(s): Jeanglaude, Jean Bruner
• Application Number:
  US09/885,400
• Time in Patent Office: 349 Days
• Field of Search: 341/95, 341/51, 341/106, 341/87
• 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 new LZW compressor implementation architecture utilizes a plurality of limited length character tables corresponding to the respective characters of the alphabet. A string is stored by storing the code associated with the string in the character table corresponding to the extension character of the string at a character table location corresponding to the code of the string prefix. A character table is created when the character corresponding thereto is first encountered in the input. The input data character stream is searched by comparing the input stream to the stored strings to determine longest matches therewith. The codes associated with the longest matched strings are outputted so as to provide an output stream of compressed codes. The respective lengths of the character tables are limited in accordance with the frequency of occurrence of the characters of the alphabet. If a character table is limited in length to a number of strings less than a predetermined threshold, the character table is excluded from creation. The stored strings are updated by inserting extended strings into the character tables, terminating storage into a character table when the table is full. Additionally, an extended string is excluded from storage when the appropriate character table therefor is excluded from creation.

Claims

1. A data compression method for compressing an input stream of data characters into an output stream of compressed codes, said data characters being from an alphabet of data characters, comprising

providing a plurality of character tables corresponding to respective characters of said alphabet,

limiting the lengths of said character tables in accordance with frequency of occurrence of said characters of said alphabet, respectively,

storing in said character tables, strings of data characters encountered in said input stream, said stored strings having respective codes associated therewith, a string comprising a prefix string of at least one of said characters followed by an extension character,

a particular string being stored in said character tables by storing the code associated with said particular string in the character table corresponding to the extension character of said particular string at a character table location corresponding to the code of the prefix string of said particular string,

searching said input stream by comparing said input stream to said stored strings to determine the longest match therewith,

outputting the code associated with said longest match so as to provide said output stream of compressed codes,

inserting an extended string into said character tables, said extended string comprising said longest match extended by the next data character in said input stream following said longest match, said extended string being stored in the particular character table corresponding to said next data character, and

bypassing said inserting step if said particular character table is unavailable for string storage, thereby excluding said extended string from storage.

2. The method of claim 1 wherein said bypassing step comprises

bypassing said inserting step if said particular character table is full.

3. The method of claim 2 further comprising

providing a plurality of character table counters corresponding to said plurality of character tables, respectively,

providing a plurality of character table length limits corresponding to said plurality of character tables, respectively,

incrementing the character table counter associated with said particular character table when said extended string is inserted therein, and wherein said bypassing step comprises

bypassing said inserting step if said character table counter corresponding to said particular character table has attained the character table length limit associated with said particular character table.

4. The method of claim 3 further comprising configuring said character table length limits utilizing a sample input stream of data characters.

5. The method of claim 4 herein said configuring step comprises

providing a plurality of configuration tables corresponding to said plurality of character tables,

storing in said configuration tables, configuration strings of data characters encountered in said sample input stream, said configuration strings having respective codes assigned thereto from a code counter,

a particular configuration string being stored in said configuration tables by storing the code associated with said particular configuration string in the configuration table corresponding to the extension character of said particular configuration string at a configuration table location corresponding to the code of the prefix string of said particular configuration string,

searching said sample input stream by comparing said sample input stream to said stored configuration strings to determine the longest match therewith,

inserting an extended configuration string into said configuration tables, said extended configuration string comprising said longest match extended by the next data character in said sample input stream following said longest match, said extended configuration string being stored in the particular configuration table corresponding to said next data character,

assigning a code from said code counter to said stored extended configuration string and incrementing said code counter to a next available code,

providing respective counts of the number of strings stored in said configuration tables when said code counter has overflowed, and

providing said counts to said character table length limits, respectively, so as to configure said character table length limits.

6. The method of claim 5 wherein said configuring step further includes

determining which of said counts are below a predetermined threshold so as to provide character table exclusion indications, and

providing said character table exclusion indications to determine character tables to be excluded from creation.

7. The method of claim 1 wherein said bypassing step comprises

bypassing said inserting step if said particular character table is an excluded table.

8. The method of claim 7 further comprising

providing a directory comprising links to said character tables indexed by said respective characters of said alphabet,

setting a link of said directory to table exclusion when the character table corresponding to said link is limited to a length less than a predetermined threshold, and wherein said bypassing step comprises

bypassing said inserting step when the link associated with said particular character table is set to table exclusion.

9. The method of claim 1 further comprising

utilizing a code counter for providing the codes associated with said strings of data characters stored in said character tables, and

incrementing said code counter to a next available code when said extended string is inserted into said character tables and when said inserting step is bypassed.

10. The method of claim 6 further including

detecting when said code counter has overflowed, and wherein said bypassing step comprises

bypassing said inserting step when said code counter has overflowed.

11. The method of claim 1 wherein a character table includes a list of prefix codes corresponding to respective locations of said character table.

12. The method of claim 11 wherein said searching step includes

(a) matching one of said stored strings thereby providing a current match,

(b) fetching the next data character from said input stream following said current match thereby providing a current character,

(c) determining if said current match is one of the prefix codes in the prefix code list of said character table corresponding to said current character, and

(d) if said current match is one of said prefix codes, setting said current match to the code stored in the character table location corresponding to said one of said prefix codes and repeating steps (b) through (d) until said current match of step (c) is determined not to be one of said prefix codes in said prefix code list,

thereby determining said longest match.

13. The method of claim 12 wherein, if in step (c) said current match is determined not to be one of said prefix codes in said prefix code list, said inserting step includes

storing said current match in said prefix code list of said character table corresponding to said current character, thereby establishing a location corresponding to said current match in said character table corresponding to said current character,

providing a next available string code, and

storing said next available string code in said established location,

thereby inserting said extended string into said character table corresponding to said current character.

14. The method of claim 12 wherein, if in step (c) said current match is determined not to be one of said prefix codes in said prefix code list,

said outputting step comprises outputting said current match.

15. The method of claim 14 wherein said compression method operates in compression cycles, further including

setting said current match to said current character in preparation for performing a next compression cycle.

16. The method of claim 1 further comprising

creating a character table when the character corresponding thereto is first encountered.

17. The method of claim 8 further comprising

providing a directory comprising links to said character tables indexed by said respective characters of said alphabet,

setting a link of said directory to table exclusion when the character table corresponding to said link is limited to a length less than a predetermined threshold, and

bypassing said creating step when the link corresponding to a character table to be created is set to table exclusion.

18. Data compression apparatus for compressing an input stream of data characters into an output stream of compressed codes, said data characters being from an alphabet of data characters, comprising

a plurality of character tables corresponding to respective characters of said alphabet for storing strings of data characters encountered in said input stream, said stored strings having respective codes associated therewith, a string comprising a prefix string of at least one of said characters followed by an extension character,

a particular string being stored in said character tables by storing the code associated with said particular string in the character table corresponding to the extension character of said particular string at a character table location corresponding to the code of the prefix string of said particular string,

means for limiting the lengths of said character tables in accordance with frequency of occurrence of said characters of said alphabet, respectively,

means for searching said input stream by comparing said input stream to said stored strings to determine the longest match therewith,

means for outputting the code associated with said longest match so as to provide said output stream of compressed codes,

means for inserting an extended string into said character tables, said extended string comprising said longest match extended by the next data character in said input stream following said longest match, said extended string being stored in the particular character table corresponding to said next data character, and

means for bypassing the inserting of said extended string into said character tables if said particular character table is unavailable for string storage, thereby excluding said extended string from storage.

19. The apparatus of claim 18 wherein said bypassing means comprises

means for bypassing the inserting of said extended string into said character tables if said particular character table is full.

20. The apparatus of claim 19 further comprising

a plurality of character table counters corresponding to said plurality of character tables, respectively,

a plurality of character table length limits corresponding to said plurality of character tables, respectively,

means for incrementing the character table counter associated with said particular character table when said extended string is inserted therein, and wherein said bypassing means comprises

means for bypassing the inserting of said extended string into said character tables if said character table counter corresponding to said particular character table has attained the character table length limit associated with said particular character table.

21. The apparatus of claim 20 further comprising

means for configuring said character table length limits utilizing a sample input stream of data characters.

22. The apparatus of claim 21 wherein said configuring means comprises

a plurality of configuration tables corresponding to said plurality of character tables for storing configuration strings of data characters encountered in said sample input stream, said configuration strings having respective codes assigned thereto from a code counter,

a particular configuration string being stored in said configuration tables by storing the code associated with said particular configuration string in the configuration table corresponding to the extension character of said particular configuration string at a configuration table location corresponding to the code of the prefix string of said particular configuration string,

means for searching said sample input stream by comparing said sample input stream to said stored configuration strings to determine the longest match therewith,

means for inserting an extended configuration string into said configuration tables, said extended configuration string comprising said longest match extended by the next data character in said sample input stream following said longest match, said extended configuration string being stored in the particular configuration table corresponding to said next data character,

means for assigning a code from said code counter to said stored extended configuration string and incrementing said code counter to a next available code,

means for providing respective counts of the number of strings stored in said configuration tables when said code counter has overflowed, and

means for providing said counts to said character table length limits, respectively, so as to configure said character table length limits.

23. The apparatus of claim 22 wherein said configuring means further includes

means for determining which of said counts are below a predetermined threshold so as to provide character table exclusion indications, and

means for providing said character table exclusion indications to determine character tables to be excluded from creation.

24. The apparatus of claim 18 wherein said bypassing means comprises

means for bypassing the inserting of said extended string into said character tables if said particular character table is an excluded table.

25. The apparatus of claim 24 further comprising

a directory comprising links to said character tables indexed by said respective characters of said alphabet;

means, for setting a link of said directory to table exclusion when the character table corresponding to said link is limited to a length less than a predetermined threshold, and wherein said bypassing means comprises

means for bypassing the inserting of said extended string into said character tables when the link associated with said particular character table is set to table exclusion.

26. The apparatus of claim 18 further comprising

a code counter for providing the codes associated with said strings of data characters stored in said character tables, and

means for incrementing said code counter to a next available code when said extended string is inserted into said character tables and when said inserting of said extended string into said character tables is bypassed.

27. The apparatus of claim 26 further including

means for detecting when said code counter has overflowed, and wherein said bypassing means comprises

means for bypassing the inserting of said extended string into said character tables when said code counter has overflowed.

28. The apparatus of claim 18 further comprising

means for creating a character table when the character corresponding thereto is first encountered.

29. The apparatus of claims 28 further comprising

a directory comprising links to said character tables indexed by said respective characters of said alphabet,

means for setting a link of said directory to table exclusion when the character table corresponding to said link is limited to a length less than a predetermined threshold, and wherein said bypassing means comprises

means for bypassing the creating of a character table when the link corresponding to the character table to be created is set to table exclusion.

30. The apparatus of claim 18 wherein a character table includes a list of prefix codes corresponding to respective locations of said character table.

31. The apparatus of claim 30 wherein said searching means comprises means operative for

(a) matching one of said stored strings thereby providing a current match,

(b) fetching the next data character from said input stream following said current match thereby providing a current character,

(c) determining if said current match is one of the prefix codes in the prefix code list of said character table corresponding to said current character, and

(d) if said current match is one of said prefix codes, setting said current match to the code stored in the character table location corresponding to said one of said prefix codes and repeating (b) through (d) until said current match of (c) is determined not to be one of said prefix codes in said prefix code list,

thereby determining said longest match.

32. The apparatus of claim 31 wherein said inserting means includes

means for storing said current match in said prefix code list of said character table corresponding to said current character, thereby establishing a location corresponding to said current match in said character table corresponding to said current character,

means for providing a next available string code, and

means for storing said next available string code in said established location,

thereby inserting said extended string into said character table corresponding to said current character.

33. The apparatus of claim 31 wherein said outputting means comprises means for outputting said current match.

34. The apparatus of claim 33 wherein said apparatus operates in compression cycles, further including

means for setting said current match to said current character in preparation for performing a next compression cycle.