摘要 |
<p>PROBLEM TO BE SOLVED: To improve locality of reference when restoring data.SOLUTION: In a character string compression method and apparatus, a substring length in a sample character string length M (M<<N) is set to S, and a substring from a starting position of an input character string N to the length S is acquired and stored in sample character string storing means. Then, a maximum matching length Lbetween a substring starting from an i-th starting position of the input character string N and a sample character string M read out from the sample character string storing means, and an appearance position Pof the substring are calculated. Also, a maximum matching length Lbetween a substring starting from the i-th starting point of the input character string N and a substring appeared between 0 to (i-1)th in the input character string N, and an appearance position of the appeared substring are calculated. In the case of L<L, a replace pointer is set to indicate a past position of the input character string N, and in the case of L≥L, the replace pointer is set to indicate a position on the sample character string M. Thereafter, the substring of [i...i+L+1] in the input character string N is set as the substring already appeared and stored in dynamic dictionary storing means, before outputting a replace pointer string and the sample character string.</p> |