Method and apparatus for data compression
First Claim
1. A real-time digital processing apparatus for dynamically compressing an input data stream of characters into a compressed stream of digital codes, and for dynamically decompressing a compressed stream of digital codes into an uncompressed stream of characters, the apparatus comprising:
- a plurality of digital data storage and processing cells connected in a systolic pipe array, each digital data storage and processing cell including digital data storage means for storing digital data,the digital data storage means in each digital data storage and processing cell being in communication with a digital data storage element in a preceding or a succeeding digital data storage and processing cell in the systolic pipe of digital data storage and processing cells,the systolic pipe including;
input means for receiving the input data stream of characters at an input end of the systolic pipe array,dictionary means for storing an indexed dictionary of strings of characters received in the input data stream, each stored string in the dictionary of strings being stored in association with a corresponding digital pointer value representative of the corresponding stored string,comparator means for comparing successive portions of the input stream with the strings stored in the digital data storage elements, to detect a portion of the input stream that matches a corresponding one of the stored strings,the comparator means including match means for detecting the longest possible portion of the input stream that will match a corresponding one of the stored strings, the match means including means for constructing successively longer matched portions of the input stream for pairs of smaller, previously matched portions of the input stream,means for transmitting, in place of the detected portion of the input stream that matches a corresponding stored string, the pointer representative of the corresponding stored string, thereby to convert the input stream in a compressed set of pointers representative of the input stream,decompression means for receiving a stream of pointers representative of strings of characters, the decompression means comprisingmeans for comparing each received pointer with strings stored in the dictionary to locate a string corresponding to each received pointer, andmeans for transmitting, in place of each received pointer corresponding to a stored string, the stored string corresponding to the pointer, thereby to decompress the stream of pointers into an uncompressed stream of characters,means for ensuring that the encoder and decoder have a consistent method for leaning pairs of pointers by employing a modified learning rule and/or retiming of the input-output stream.
0 Assignments
0 Petitions
Accused Products
Abstract
A data compression system utilizes multiple encoding/decoding processing units arranged in a massively parallel systolic pipe array for compressing a stream of input characters received at an input end of the pipe. The systolic pipe executes data compression by textual substitution, converting the uncompressed stream of input characters into a compressed set of pointers representative of the input. The processors store a dictionary of strings of previously-read input characters in association with corresponding pointers. The processors match portions of the input stream with the stored strings, and transmit the corresponding pointers in place of the strings. In order to execute decoding or decompression of the stream of pointers, the processors maintain a dictionary identical to that generated during encoding. The processors match received pointers with stored strings of data and transmit the corresponding data strings in place of the pointers. Novel methods for matching, update, and deletion in a massively parallel systolic pipe structure enhance processing speed.
163 Citations
23 Claims
-
1. A real-time digital processing apparatus for dynamically compressing an input data stream of characters into a compressed stream of digital codes, and for dynamically decompressing a compressed stream of digital codes into an uncompressed stream of characters, the apparatus comprising:
-
a plurality of digital data storage and processing cells connected in a systolic pipe array, each digital data storage and processing cell including digital data storage means for storing digital data, the digital data storage means in each digital data storage and processing cell being in communication with a digital data storage element in a preceding or a succeeding digital data storage and processing cell in the systolic pipe of digital data storage and processing cells, the systolic pipe including; input means for receiving the input data stream of characters at an input end of the systolic pipe array, dictionary means for storing an indexed dictionary of strings of characters received in the input data stream, each stored string in the dictionary of strings being stored in association with a corresponding digital pointer value representative of the corresponding stored string, comparator means for comparing successive portions of the input stream with the strings stored in the digital data storage elements, to detect a portion of the input stream that matches a corresponding one of the stored strings, the comparator means including match means for detecting the longest possible portion of the input stream that will match a corresponding one of the stored strings, the match means including means for constructing successively longer matched portions of the input stream for pairs of smaller, previously matched portions of the input stream, means for transmitting, in place of the detected portion of the input stream that matches a corresponding stored string, the pointer representative of the corresponding stored string, thereby to convert the input stream in a compressed set of pointers representative of the input stream, decompression means for receiving a stream of pointers representative of strings of characters, the decompression means comprising means for comparing each received pointer with strings stored in the dictionary to locate a string corresponding to each received pointer, and means for transmitting, in place of each received pointer corresponding to a stored string, the stored string corresponding to the pointer, thereby to decompress the stream of pointers into an uncompressed stream of characters, means for ensuring that the encoder and decoder have a consistent method for leaning pairs of pointers by employing a modified learning rule and/or retiming of the input-output stream. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A real time method for dynamically compressing an input data stream of characters into a compressed stream of digital pointers, the method comprising the steps of
electrically connecting a plurality of digital data storage and processing cells into a systolic pipe array such that a digital data storage element in each digital data storage and processing cell can communicate with a digital data storage element in a preceding or a succeeding digital data storage and processing cell in the systolic pipe of digital data storage and processing cells, receiving the input data stream of characters at an input end of the systolic pipe array, storing, in the connected digital data storage elements of the digital data storage and processing cells of the systolic pipeline array, an indexed dictionary or strings of characters received in the input data stream, each stored string in the dictionary of strings being stored in association with a corresponding digital pointer value representative of the corresponding stored string, comparing, in digital processing elements in the connected digital data storage and processing cells, successive portions of the input stream with the strings stored in the digital data storage elements, to detect a portion of the input stream that matches a corresponding one of the storm strings, and transmitting, in place of the detected portion of the input stream that matches a corresponding stored string, the pointer representative of the corresponding stored string, thereby converting the input stream into a compressed set of pointers representative of the input stream, wherein the comparing step includes the step of detecting a portion that will match a corresponding one of the stored strings, the step of detecting a portion including the step of constructing successively longer matched portions of the input stream from pairs of smaller, previously matched portions of the input stream, said method ensuring that the encoder learns pairs of pointers in a way such that consistent decoding is possible by employing a modified learning rule and or retiming of the input/output stream.
-
23. A real time method for dynamically decompressing a compressed stream of digital pointers into an uncompressed stream of characters, the method comprising the steps of
electrically connecting a plurality of digital data storage and processing cells into a systolic pipe array such that a digital data storage element in each digital data storage and processing cell can communicate with a digital data storage element in a preceding or a succeeding digital data storage and processing cell in the systolic pipe of digital data storage and processing cells, receiving an input stream of pointers representative of strings of characters at an input end of the systolic pipe array, storing, in the connected digital data storage elements of the digital data storage and processing cells of the systolic pipeline array, an indexed dictionary or strings of characters received in the input data stream, each stored string in the dictionary of strings being stored in association with a corresponding digital pointer value representative of the corresponding stored string, comparing each received pointer with the strings stored in the dictionary to locate a string corresponding to each received pointer, and transmitting, in place of each pointer corresponding to a stored string, the stored string corresponding to the received pointer, thereby to decompress the stream of pointers into an uncompressed stream of characters said method ensuring that the decoder learns pairs of pointers in a way that is consistent with an encoding by employing a modified learning rule and or retiming of the input/output stream.
Specification