Data compression apparatus for compensating a deviation of a compression

Abstract

In a data compression apparatus for compensating a deviation of a compression rate of an input stream of characters (ISC's), a candidate string matching (CSM) circuit, based on codewords (CD's) in a CD dictionary, performs a CSM on the ISC's to provide a first maximum length candidate string (MLCS) and a second MLCS immediately following the first MLCS. A candidate string (CS) storing circuit, based on the CD dictionary, the first MLCS and the second MLCS, generates derived CS pairs (DCSP's) to thereby store a DCSP table listing the DCSP's. A compression rate deviation (CRD) evaluation circuit evaluates a CRD between the first MLCS and the second MLCS, thereby providing the first MLCS and the second MLCS as a first string and a second string, respectively, if a first predetermined CRD evaluation criterion (PCRDEC) is satisfied; and supplying a reduction string matching (RSM) command signal if otherwise. An RSM circuit, in response to the RSM command signal, performs an RSM based on the DCSP table to select a DCSP as a selected DCSP having a first string and a second string, wherein a CRD between the first string and the second string satisfies a second PCRDEC. An encoder encodes first and second CD's corresponding to the first and second string's to thereby generate encoded first and second CD's, respectively.