Patent ID: 6104323
Filing Date: 2000-08-15
Classification: H03M

Abstract:
A data compression apparatus for compensating a deviation of a compression rate of an input stream of characters, comprising:means for storing a codeword corresponding to a string of characters to thereby provide a codeword dictionary having a plurality of different codewords for strings, wherein each codeword identifies a corresponding one of the strings;means, based on the codewords in the codeword dictionary, for performing a candidate string matching on the input stream of characters in accordance with a predetermined string matching technique to thereby provide a first maximum length candidate string (MLCS) and a second MLCS immediately following the first MLCS, wherein each of the first MLCS and the second MLCS is a candidate string having a longest character length thereof among all of the candidate strings having corresponding codewords in the codeword dictionary, respectively;means, based on the codeword dictionary, the first MLCS and the second MLCS, for generating derived candidate string pairs (DCSP's) to thereby store a DCSP table listing the DCSP's, each DCSP having a first derived candidate string (DCS) and a second DCS, said each DCSP being generated in accordance with a predetermined DCSP generation rule;means for evaluating a compression rate deviation (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 is satisfied; and supplying a reduction string matching command signal if the first predetermined CRD evaluation criterion is not satisfied; andmeans, in response to the reduction string matching command signal, for performing a reduction string matching based on the DCSP table to thereby select a DCSP as a selected DCSP having a first string and a second string among the DCSP's listed in the DCSP table, wherein a CRD between the first string and the second string of the selected DCSP satisfies a second predetermined CRD evaluation criterion.