Data compression and decompression system with immediate dictionary updating interleaved with string search
First Claim
1. Data compression apparatus for compressing a stream of data characters into a stream of compressed codes, comprisingstorage means for storing strings of data characters, each said string having a code associated therewith,means for searching said stream of data characters by comparing said stream to said stored strings to perform a character-by-character match therewith until the longest match between said stream of data characters and said stored strings is determined,means for outputting the code associated with said longest match so as to provide said stream of compressed codes,means for entering extended strings into said storage means, the entry of said extended strings being interleaved with the matching of the data characters of said character-by-character match, said extended strings comprising the previous longest matched string corresponding to the last outputted code extended by each data character, in turn, as each data character is matched during said character-by-character match, one of said extended strings being entered for each said data character matched and before a next data character is matched during said character-by-character match, the entering of said extended strings during said character-by-character match continuing until said longest match is determined, andmeans for assigning respective codes to said extended strings.
3 Assignments
0 Petitions
Accused Products
Abstract
A dictionary based data compression and decompression system where, in the compressor, when a partial string W and a character C are matched in the dictionary, a new string is entered into the dictionary with C as an extension character on the string PW where P is the string corresponding to the last output compressed code signal. An update string is entered into the compression dictionary for each input character that is read and matched. The updating is immediate and interleaved with the character-by-character matching of the current string. The update process continues until the longest match is found in the dictionary. The code of the longest matched string is output in a string matching cycle. If a single character or multi-character string "A" exists in the dictionary, the string AAA . . . A is encoded in two compressed code signals regardless of the string length. This encoding results in an unrecognized code signal at the decompressor. The decompressor, in response to an unrecognized code signal, enters update strings into the decompressor dictionary in accordance with the recovered string corresponding to the previously received code signal, the unrecognized code signal, the extant code of the decompressor and the number of characters in the previously recovered string.
122 Citations
22 Claims
-
1. Data compression apparatus for compressing a stream of data characters into a stream of compressed codes, comprising
storage means for storing strings of data characters, each said string having a code associated therewith, means for searching said stream of data characters by comparing said stream to said stored strings to perform a character-by-character match therewith until the longest match between said stream of data characters and said stored strings is determined, means for outputting the code associated with said longest match so as to provide said stream of compressed codes, means for entering extended strings into said storage means, the entry of said extended strings being interleaved with the matching of the data characters of said character-by-character match, said extended strings comprising the previous longest matched string corresponding to the last outputted code extended by each data character, in turn, as each data character is matched during said character-by-character match, one of said extended strings being entered for each said data character matched and before a next data character is matched during said character-by-character match, the entering of said extended strings during said character-by-character match continuing until said longest match is determined, and means for assigning respective codes to said extended strings.
-
12. A data compression method for compressing a stream of data characters into a stream of compressed codes, comprising
storing strings of data characters in storage means, each said string having a code associated therewith, searching said stream of data characters by comparing said stream to said stored strings to perform a character-by-character match therewith until the longest match between said stream of data characters and said stored strings is determined, outputting the code associated with said longest match so as to provide said stream of compressed codes, entering extended strings into said storage means, the entry of said extended strings being interleaved with the matching of the data characters of said character-by-character match, said extended strings comprising the previous longest matched string corresponding to the last outputted code extended by each data character, in turn, as each data character is matched during said character-by-character match, one of said extended strings being entered for each said data character matched and before a next data character is matched during said character-by-character match, the entering of said extended strings during said character-by-character match continuing until said longest match is determined, and assigning respective codes to said extended strings.
Specification
-
- Resources
-
Current AssigneeUnisys Corporation
-
Original AssigneeUnisys Corporation
-
InventorsWelch, deceased, Terry A., Cooper, Albert B.
-
Primary Examiner(s)PHAN, TRONG Q
-
Application NumberUS09/223,352Time in Patent Office629 DaysField of Search341/51US Class Current341/51CPC Class CodesH03M 7/3088 employing the use of a dict...H03M 7/46 Conversion to or from run-l...
