Stem for dynamically compressing and decompressing electronic data
First Claim
1. An apparatus for dynamically compressing and decompressing an input stream of data characters into a compressed stream code and for decompressing said compressed stream of code into uncompressed data characters, the apparatus comprising:
- first dictionary means for storing a first plurality of strings of data characters, said first dictionary means comprising a plurality of unique codes each for identifying a corresponding respective one of said first plurality of strings, wherein said first plurality of strings comprises an initial set of unique data characters, with each character in said initial set being positioned in a corresponding respective one of said first plurality of strings;
second dictionary means for storing a second plurality of strings of data characters, said second dictionary means comprising a plurality of unique codes each for identifying a corresponding respective one of said second plurality of strings, wherein said second plurality of strings comprises an initial set of unique data characters that is identical to said initial set of unique data characters in said first plurality of strings, with each character in said initial set in said second plurality of strings being positioned in the one of said second plurality of strings that is identified by the same unique code as the string in said first plurality of strings in which the identical character from said initial set of characters in said first plurality of strings is positioned;
first match means for receiving and parsing said input stream of data characters into parsed strings of data characters and for comparing each of said parsed strings of data characters with said first plurality of strings so as to locate the one of said first plurality of strings that matches a corresponding one of said parsed strings, wherein the most recently matched one of said parsed strings is identified as the current match;
first transmitting means for transmitting the one of said plurality of unique codes identifying the one of said first plurality of stored strings that matches said current match, for each current match;
second match means for receiving said one unique code transmitted by said first transmitting means for each current match, and for comparing each said one unique code with said plurality of unique codes identifying said second plurality of strings so as to locate the one of said plurality of unique codes in said second dictionary means that matches said each said one unique code received from said first transmitting means;
second transmitting means for transmitting the string of character data in said second plurality of strings identified by the one of said plurality of unique codes in said second dictionary means that matches said one unique code received from said first transmitting means, for each string of character data matched by said second match means;
first update means for adding N new strings of data characters to said first dictionary means for each current match, wherein N equals the number of characters in said current match, said N new strings comprising the last current match concatenated with each non-empty prefix of said current match, and including means for assigning one of said plurality of unique codes to each of said new strings; and
second update means for adding said N new strings of data characters to said second dictionary means for each current match, including means for assigning the same one of said plurality of unique codes to each of said N new strings added to said second dictionary means that is assigned to corresponding respective ones of said N new strings added to said first dictionary means.
2 Assignments
0 Petitions
Accused Products
Abstract
A data compression system for encoding and decoding textual data, including an encoder for encoding the data and for a decoder for decoding the encoded data. Both encoder and decoder have dictionaries for storing frequently-appearing strings of characters. Each string is identified by a unique pointer. The input data stream is parsed and matched with strings in the encoder dictionary using a novel matching algorithm. The pointer associated with the matched string is then transmitted to a remote location for storage or decoding. Thereafter, using a novel update algorithm the encoder dictionary is updated to include new strings of data based on the matched string of data. If required, a novel deletion algorithm is employed to remove infrequently used strings of data to provide room for the newly generated strings of data. The strings of data may be arranged using a modified least recently used queue.
The decoder matches each unique pointer in the stream of compressed input data with a corresponding pointer in the decoder dictionary. The decoder then transmits the string of character data associated with the matched pointer, thereby providing textual data in original, uncompressed form. Thereafter, using the novel update and deletion algorithms, new strings of data are added to, and old strings of data are deleted from, the decoder dictionary, so as to ensure both encoder and decoder dictionaries contain identical strings of data.
-
Citations
55 Claims
-
1. An apparatus for dynamically compressing and decompressing an input stream of data characters into a compressed stream code and for decompressing said compressed stream of code into uncompressed data characters, the apparatus comprising:
-
first dictionary means for storing a first plurality of strings of data characters, said first dictionary means comprising a plurality of unique codes each for identifying a corresponding respective one of said first plurality of strings, wherein said first plurality of strings comprises an initial set of unique data characters, with each character in said initial set being positioned in a corresponding respective one of said first plurality of strings; second dictionary means for storing a second plurality of strings of data characters, said second dictionary means comprising a plurality of unique codes each for identifying a corresponding respective one of said second plurality of strings, wherein said second plurality of strings comprises an initial set of unique data characters that is identical to said initial set of unique data characters in said first plurality of strings, with each character in said initial set in said second plurality of strings being positioned in the one of said second plurality of strings that is identified by the same unique code as the string in said first plurality of strings in which the identical character from said initial set of characters in said first plurality of strings is positioned; first match means for receiving and parsing said input stream of data characters into parsed strings of data characters and for comparing each of said parsed strings of data characters with said first plurality of strings so as to locate the one of said first plurality of strings that matches a corresponding one of said parsed strings, wherein the most recently matched one of said parsed strings is identified as the current match; first transmitting means for transmitting the one of said plurality of unique codes identifying the one of said first plurality of stored strings that matches said current match, for each current match; second match means for receiving said one unique code transmitted by said first transmitting means for each current match, and for comparing each said one unique code with said plurality of unique codes identifying said second plurality of strings so as to locate the one of said plurality of unique codes in said second dictionary means that matches said each said one unique code received from said first transmitting means; second transmitting means for transmitting the string of character data in said second plurality of strings identified by the one of said plurality of unique codes in said second dictionary means that matches said one unique code received from said first transmitting means, for each string of character data matched by said second match means; first update means for adding N new strings of data characters to said first dictionary means for each current match, wherein N equals the number of characters in said current match, said N new strings comprising the last current match concatenated with each non-empty prefix of said current match, and including means for assigning one of said plurality of unique codes to each of said new strings; and second update means for adding said N new strings of data characters to said second dictionary means for each current match, including means for assigning the same one of said plurality of unique codes to each of said N new strings added to said second dictionary means that is assigned to corresponding respective ones of said N new strings added to said first dictionary means. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 43, 46, 47, 48, 53)
-
-
18. An apparatus for dynamically compressing an input stream of data characters into a stream of compressed code, and for dynamically decompressing said stream of compressed code into said input stream of data characters, the apparatus comprising:
-
encoder module means for encoding said stream of characters and for transmitting said stream of characters in encoded form; decoder module means for decoding said encoded stream of characters and for transmitting said stream of characters in uncoded form; wherein said encoder module means and said decoder module means each comprise; dictionary means for storing a plurality of strings of said characters, wherein each of said plurality of strings has a unique address; first match means (1) for receiving said input stream of data characters, (2) for matching strings of characters from said input stream of characters with ones of said plurality of strings of characters in said dictionary means in said encoder module, and (3) for transmitting the address of matched ones of said plurality of strings; second match means for (1) receiving the addresses of strings with which matches have been made, (2) matching said each of said addresses with the addresses of said plurality of strings in said dictionary means in said decoder module, and (3) transmitting the characters in those of said plurality of strings having addresses that match said addresses received by said second match means; update means for updating said dictionary means in said encoder module and said decoder module so that said plurality of strings stored therein contain strings of characters frequently present in said stream of characters, and for concatenating the last matched string with the currently matched string; and deletion means for deleting from said plurality of strings of characters in said dictionary means in said encoder module and in said dictionary means in said decoder module those strings with which strings of characters from said input stream are approximately least frequently matched by arranging said plurality of strings in said dictionary means in said encoder and decoder modules in a reverse order arrangement with the currently matched strings appearing after said concatenation of the last matched string and the currently matched string. - View Dependent Claims (54)
-
-
19. An apparatus for dynamically compressing an input stream of data characters into a compressed stream of code, the system comprising:
-
dictionary means for storing a plurality of strings of data characters, said dictionary means comprising a plurality of unique codes each for identifying a corresponding respective one of said plurality of strings, wherein said plurality of strings comprises an initial set of unique data characters, with each character in said initial set being positioned in a corresponding respective one of said plurality of strings; match means for receiving and parsing said input stream of data characters into parsed strings and for comparing each of said parsed strings of data characters with said plurality of strings in said dictionary means so as to locate the one of said stored plurality of strings that matches a corresponding one of said parsed strings, wherein the most recently matched one on said parsed strings is identified as the current match; transmitting means for transmitting said unique code identifying the one of said plurality of stored strings that matches said current match; and update means for adding N new strings of data characters to said dictionary means, wherein N equals the number of characters current match concatenated with each non-empty prefix of said current match, and including means for assigning one of said plurality of unique address codes to each of said N new strings. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 44, 49, 50)
-
-
35. A system for dynamically decompressing a compressed stream of code into uncompressed data characters, the system comprising:
-
dictionary means for storing a plurality of strings of data characters, said dictionary means comprising a plurality of unique codes for identifying a corresponding respective one of said plurality of strings, wherein said plurality of strings comprises an initial set of unique data characters, with each character in said initial set being positioned in a corresponding respective one of said plurality of strings; match means for receiving said compressed stream code, and for comparing said stream of code with said plurality of unique codes identifying said plurality of strings in said dictionary means so as to locate the ones of said plurality of unique codes in said dictionary means that match corresponding ones of code in said stream of code received by said match means, wherein the most recently matched one of said plurality of unique codes in said dictionary means is identified as the current match; transmitting means for transmitting the strings of character data identified by the ones of said plurality of unique codes in said dictionary that match said corresponding ones of said stream of code received by said match means; and update means for adding N new strings of data characters to said dictionary means for each string of characters transmitted by said transmitting means, wherein N equals the number of characters in a current match, said N new strings comprising the last current match concatenated with each non-empty prefix of said current match, and including means for assigning a unique address code to each of said new strings. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 45, 51, 52)
-
-
55. An apparatus for dynamically compressing and decompressing an input stream of data characters into a compressed stream of code and for decompressing said compressed stream of code into uncompressed data characters, the apparatus comprising:
-
first dictionary means for storing a first plurality of strings of data characters, said first dictionary means comprising a plurality of unique codes each for identifying a corresponding respective one of said first plurality of strings; second dictionary means for storing a second plurality of strings of data characters, said second dictionary means comprising a plurality of unique codes each for identifying a corresponding respective one of said second plurality of strings; first match means for receiving and parsing said input stream of data characters into parsed strings of data characters and for comparing each of said parsed strings of data characters with said first plurality of strings so as to locate the one of said first plurality of strings that matches a corresponding one of said parsed strings, wherein the most recently matched one of said parsed strings is identified as the current match; first transmitting means for transmitting the one of said plurality of unique codes identifying the one of said first plurality of stored strings that matches said current match, for each current match; second match means for receiving said one unique code transmitted by said first transmitting means for each current match, and for comparing each said one unique code with said plurality of unique codes identifying said second plurality of strings as to locate the one of said plurality of unique codes in said second dictionary means that matches said each one unique code received from said first transmitting means; second transmitting means for transmitting the string of character data in said second plurality of strings identified by the one of said plurality of unique codes in said second dictionary means that matches said one unique code received from said first transmitting means, for each string of character data matched by said second match means; first update means for adding N new strings of data characters to said first dictionary means for each current match, wherein N equals the number of characters in said current match, said N new strings comprising the last current match concentrated with each non-empty prefix of said current match, and including means for assigning one of said plurality of unique codes to each of said new strings; and second update means for adding said N new strings of data characters to said second dictionary means for each current match, including means for assigning the same one of said plurality of unique codes to each of said N new strings added to aid second dictionary means that is assigned to corresponding respective ones of said N new strings added to said first dictionary means.
-
Specification