Data compression with dynamically compiled dictionary
First Claim
Patent Images
1. A data compression system comprising:
- a dictionary arranged to store strings of characters with an index for each of said strings, andmeans for matching strings of characters of a data stream with strings of characters stored in the dictionary and for outputting the index of a dictionary entry of a matched string when a following character of the data stream does not match with the stored strings,said means for matching including means for determining, for a matched string having at least three characters, a sequence of characters from said at least three characters, said sequence including at least a first and a second of said at least three characters, but not including all of said at least three characters, to update the dictionary by extending an immediately- preceding string by said sequence.
1 Assignment
0 Petitions
Accused Products
Abstract
A data compression system in which a dictionary stored strings of characters and an encoder matches the longest of the stored string with a current string of a data stream input to the encoder. The index of the longest matched stored string is output by the encoder and the dictionary is updated by a new string consisting of the previous match concatenated with the first two characters only of the present match. If the present match has only one or two characters, it is added without reduction.
197 Citations
5 Claims
-
1. A data compression system comprising:
-
a dictionary arranged to store strings of characters with an index for each of said strings, and means for matching strings of characters of a data stream with strings of characters stored in the dictionary and for outputting the index of a dictionary entry of a matched string when a following character of the data stream does not match with the stored strings, said means for matching including means for determining, for a matched string having at least three characters, a sequence of characters from said at least three characters, said sequence including at least a first and a second of said at least three characters, but not including all of said at least three characters, to update the dictionary by extending an immediately- preceding string by said sequence. - View Dependent Claims (2)
-
-
3. In a method of data compression of individual sequences of characters in a data stream including the steps of storing strings in a dictionary, and determining the longest string in the dictionary which matches a current string in the data stream staring from a current input position, the improvement comprising the steps of:
-
determining, for a matched string having at least three characters, a single sequence of characters from said at least three characters, said single sequence including at least a first and a second of said at least three characters, but not including all of said at least three characters, and updating the dictionary by extending an immediately-preceding string by said single sequence. - View Dependent Claims (4)
-
-
5. A method for updating dynamically compiled dictionary entries in a data compression system that generates an output code corresponding to a matched data string S'"'"' of successively encountered input characters found as an existing dictionary entry followed by a further matched string S of input characters also found as an existing dictionary entry, said method comprising the steps of
creating a new dictionary entry for a character string S'"'"'+S" where string S" is of shorter length than string S if string S is greater than two characters in length.
Specification