Encoding and decoding apparatus with matching length means for symbol strings

Abstract

A symbol string detection unit detects the second symbol string matching the first symbol string having a predetermined length n from input character strings. A matching length detection unit detects a matching length k between the third symbol string following the first symbol string and the fourth symbol string following the second symbol string. A coding unit codes an input symbol string based on the symbol string detected by the symbol string detection unit and the matching length k detected by the matching length detection unit.

1. A data compressing apparatus having an input buffer for holding a string of data to be compressed, said input buffer comprising a Lempel buffer for storing an already compressed portion and a Ziv buffer for storing a portion to be compressed, comprising:
 hash code generation means for generating a hash code from a character string having the length n;  
 occurrence position holding means for holding an occurrence position of the n-character string in the Lempel buffer in association with the hash code generated from the n-character string in the Lempel buffer;  
 occurrence position obtaining means for obtaining an occurrence position associated with the hash code from said occurrence position holding means by retrieving the hash code generated from the character string having the length n immediately before the Ziv buffer from said occurrence position holding means;  
 matching length obtaining means for comparing a character string after the occurrence position with a character string after a start of the Ziv buffer, and obtaining a matching length; and  
 matching length coding means for coding the character string after the start of the Ziv buffer based on the matching length.  
 
     
     
       2. The apparatus according to  claim 1 , further comprising:
 hash conflict confirmation means for comparing a character string in the Lempel buffer specified by said occurrence position obtaining means with a character string having the length p immediately before the Ziv buffer, wherein  
 said matching length coding means codes a character string after a start of the Ziv buffer based on the matching length only when all of p characters match the character string.  
 
     
     
       3. The apparatus according to  claim 2 , wherein
 n=3 and p=0 or 2.  
 
     
     
       4. A data compressing apparatus having an input buffer for holding a string of data to be compressed, said input buffer comprising a Lempel buffer for storing an already compressed portion and a Ziv buffer for storing a portion to be compressed, comprising:
 occurrence position holding means for holding a part or all of an occurrence position of a character string having a length n in the Lempel buffer;  
 occurrence/non-occurrence check means for checking whether or not an occurrence position in the Lempel buffer of a character string matching a character string having a length n immediately before the Ziv buffer is held;  
 occurrence position obtaining means for obtaining an occurrence position in the Lempel buffer of a character string matching an n-character string immediately before the Ziv buffer;  
 matching length obtaining means for comparing for matching a character string after the occurrence position with a character string after a start of the Ziv buffer, and obtaining a matching length;  
 non-matching information holding means for holding non-matching information in association with the n-character string when a matching length obtained by said matching length obtaining means is 0; and  
 matching length coding means for coding the character string after the start of the Ziv buffer based on the matching length when the non-matching information is not associated with the character string having the length n immediately before the Ziv buffer.  
 
     
     
       5. The apparatus according to  claim 4 , further comprising:
 same character sequence confirmation means for confirming whether or not all of characters in a character string having a length q immediately before the Ziv buffer are same characters, wherein  
 when the all characters in the immediately previous character string having the length q are identical, said non-matching information holding means does not set the non-matching information for the n-character string even when the matching length is 0.  
 
     
     
       6. The apparatus according to  claim 5 , wherein
 q equals 2.