Method and apparatus for the compression and decompression of data using Lempel-Ziv based techniques

摘要

A method and apparatus for compressing and decompressing text and image data by forming fixed-length codewords from a variable number of data symbols. Data symbols are shifted into registers in the first half of a buffer, while an uncompressed string of data symbols are shifted into registers in the second half of the buffer. A systolic array of processors compares each data symbol in the second half of the buffer with each data symbol in the first half of the buffer. Each processor compares pairs of data symbols, and selectively passes the data symbols to an adjacent processor. A fixed-length output is provided indicating the length and the starting point of the longest substring in the first half of the buffer that matches a substring from the second half of the buffer. The matched data symbols in the second half of the buffer and the data symbol immediately following the matched data symbols are then shifted into the first half of the buffer, and uncompressed data symbols are then shifted into the second half of the buffer. A preselected shift register in the first half of the buffer provides a fixed-length output indicating the symbol that immediately follows the last matched data symbol. The length and the starting point information and the last symbol information are assembled to form a codeword having a predetermined length. The codeword is stored in memory and can be later retrieved and decompressed to provide the original string of data symbols.