Coding apparatus and decoding apparatus

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.

What is claimed is:  
     
         1 . A coding apparatus comprising: 
 symbol string detection means for detecting a second symbol string matching a first symbol string having a predetermined length from symbol strings;    matching length detection means for detecting a matching length between a third symbol string following the first symbol string and a fourth symbol string following the second symbol string; and    coding means for coding input symbol strings based on the symbol string detected by said symbol string detection means and the matching length detected by said matching length detection means.    
     
     
         2 . A coding apparatus comprising: 
 occurrence position storage means for storing an occurrence position of a symbol string;    occurrence position retrieval means for retrieving an occurrence position of a second symbol string associated with a code corresponding to a first symbol string from the occurrence position storage means;    matching length detection means for detecting a matching length between a third symbol string following the first symbol string and a fourth symbol string following the second symbol string; and    a matching length coding means for coding the third symbol string by coding the matching length detected by said matching length detection means.    
     
     
         3 . The apparatus according to  claim 1 , wherein 
 when said matching length is smaller than a predetermined value, a coding process is not performed on a corresponding symbol string based on a matching length.    
     
     
         4 . A decoding apparatus comprising: 
 coded data obtaining means for obtaining data coded based on a matching length of a third symbol string following a first symbol string having a predetermined length;    symbol string detection means for detecting a second symbol string matching the first symbol string; and    decoding means for obtaining a matching length from a code following a code indicating the first symbol string, and decoding a fourth symbol string for the matching length following the second symbol string as a third symbol string.    
     
     
         5 . A decoding apparatus comprising: 
 coded data obtaining means for obtaining data coded based on a matching length of a third symbol string following a first symbol string having a predetermined length;    occurrence position storage means for storing an occurrence position of a decoded symbol string;    occurrence position retrieval means for retrieving an occurrence position of a second symbol string associated with a code corresponding to the first symbol string from the occurrence position storage means; and    decoding means for obtaining a matching length from a code following a code indicating the first symbol string, and decoding a fourth symbol string for the matching length following the second symbol string as a third symbol string.    
     
     
         6 . A data transmission apparatus comprising: 
 input means for inputting a symbol string;    first symbol string detection means for detecting a second symbol string matching a first symbol string having a predetermined length from input symbol strings;    matching length detection means for detecting a matching length between a third symbol string following the first symbol string and a fourth symbol string following the second symbol string;    coding means for coding input symbol strings based on the symbol string detected by said symbol string detection means and the matching length detected by said matching length detection means;    coded data transmission means for transmitting data coded by said coding means;    coded data reception means for receiving data coded based on a matching length between the first symbol string and the third symbol string;    second symbol string detection means for detecting the second symbol string matching the first symbol string from a result of decoding the coded data; and    decoding means for decoding the fourth symbol string following the second symbol string as the third symbol string.    
     
     
         7 . 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 an n-character string (n≧1) in the Lempel buffer;    occurrence/non-occurrence check means for checking whether or not said occurrence position holding means holds an occurrence position of a character string matching the n-character string immediately before the Ziv buffer;    occurrence position obtaining means for obtaining the occurrence position of the character string matching the n-character string immediately before the Ziv buffer when the occurrence position is held by said occurrence position holding means;    matching length detection means for detecting a matching length between a character string after the occurrence position and a character string after a start of the Ziv buffer; and    matching length coding means for coding a portion matching the character string after the occurrence position based on the matching length when said occurrence/non-occurrence check means confirms that the occurrence position of the n-character string immediately before the Ziv buffer is held.    
     
     
         8 . The apparatus according to  claim 7 , further comprising: 
 character-with-context code holding means for holding a code of a character immediately succeeding 0 through (m−1) character string (m≧1) as a context;    character-with-context retrieval means for retrieving a character immediately succeeding 0 through (m−1) character string as a context from said character-with-context code holding means;    character-with-context coding means for coding a character retrieved by said character-with-context retrieval means based on a code held by said character-with-context code holding means; and    switch means for switching a coding process between said matching length coding means and said character-with-context coding means.    
     
     
         9 . The apparatus according to  claim 8 , further comprising: 
 link means for linking an n-character string of a context having the length of n−1 and a subsequent character to an occurrence position of an n-character string in said occurrence position holding means;    context length check means for checking whether or not a length of a character coded by said character-with-context coding means is n−1; and    notification means for notifying said occurrence/non-occurrence check means that said occurrence position holding means holds the occurrence position when the length of the context is n−1.    
     
     
         10 . The apparatus according to  claim 7 , further comprising: 
 character/character string code holding means for holding a code corresponding to a character or a character string having a length of 1 through m;    character/character string retrieval means for retrieving a character or a character string matching for a longest length the data to be compressed from a character or a character string held by said character/character string code holding means;    character/character string coding means for coding a character or a character string retrieved by said character/character string retrieval means according to a code held by said character/character string code holding means; and    switch means for switching a coding process between said matching length coding means and said character/character string coding means.    
     
     
         11 . The apparatus according to  claim 10 , further comprising: 
 link means for linking an n-character string held by said character/character string code holding means to an occurrence position of an n-character string in said occurrence position holding means;    context length check means for checking whether or not a length of a character or a character string coded by said character/character string coding means is n; and    notification means for notifying said occurrence/non-occurrence check means that when a length of the character or the character string is n, said occurrence position holding means holds the occurrence position.    
     
     
         12 . The apparatus according to  claim 7 , further comprising: 
 an intermediate buffer for holding a matching portion after an occurrence position of a character string matching the n-character string in the lempel buffer, with the matching portion replaced with a code indicating the matching length, and with the other portions held as data to be compressed as is;    character-with-context code holding means for holding a code of a next occurring character using an immediately previous 0 through (m−1) character string as a context;    character-with-context retrieval means for retrieving a subsequent character from said character-with-context code holding means using an immediately previous 0 through (m−1) character string as a context; and    character-with-context coding means for coding a character-with-context retrieved by said character-with-context retrieval means according to a code held by said character-with-context code holding means.    
     
     
         13 . The apparatus according to  claim 7 , further comprising: 
 an intermediate buffer for holding a matching portion after an occurrence position of a character string matching the n-character string in the lempel buffer, with the matching portion replaced with a code indicating the matching length, and with the other portions held as data to be compressed as is;    character/character string code holding means for holding a code corresponding to a character or a character string having a length of 1 through m;    character/character string retrieval means for retrieving a character or a character string matching for a longest length the data held in said intermediate buffer from a character or a character string held by said character/character string code holding means; and    character/character string coding means for coding a character or a character string retrieved by said character/character string retrieval means according to a code held by said character/character string code holding means.    
     
     
         14 . 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.    
     
     
         15 . The apparatus according to  claim 14 , 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.  
   
     
     
         16 . The apparatus according to  claim 15 , wherein 
 n=3 and p=0 or 2.    
     
     
         17 . 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.    
     
     
         18 . The apparatus according to  claim 17 , 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.  
   
     
     
         19 . The apparatus according to  claim 18 , wherein 
 q equals 2.    
     
     
         20 . 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;    matching length coding means for coding the character string after the start of the Ziv buffer based on the matching length when said occurrence position obtaining means holds the occurrence position in the Lempel buffer of the character string matching the n-character string immediately before the Ziv buffer;    character-with-context code holding means for holding a code of a next occurring character using an immediately previous character or a feature extracted from the immediately previous character as a context; and    character-with-context coding means for coding a character based on the code when said occurrence position obtaining means does not hold the occurrence position in the Lempel buffer of the character string matching the n-character string immediately before the Ziv buffer.    
     
     
         21 . A data reconstruction apparatus having an output buffer for holding original data obtained by reconstructing compressed data comprising an Lempel buffer for storing already reconstructed data and a Ziv buffer for storing data to be reconstructed, comprising: 
 occurrence position holding means for holding a part or all of an occurrence position of an n-character string in the Lempel buffer;    occurrence/non-occurrence check means for checking whether or not said occurrence position holding means holds an occurrence position of a character string matching the n-character string immediately before the Ziv buffer;    occurrence position obtaining means for obtaining the occurrence position of the character string matching the n-character string immediately before the Ziv buffer;    matching length reconstruction means for reconstructing a matching length from compressed data;    character string reconstruction means for obtaining a character string for the matching length following the n-character string in the Lempel buffer as a next reconstruction result of the n-character string immediately before the Ziv buffer.    
     
     
         22 . The apparatus according to  claim 21 , further comprising: 
 character-with-context code holding means for holding a code of a character next occurring with an immediately previous 0 through (m−1) character string as a context;    character-with-context retrieval means for retrieving a code from said character-with-context code holding means with the immediately previous 0 through (m−1) character string as a context;    character-with-context reconstruction means for reconstructing a character from the code retrieved by said character-with-context retrieval means; and    switch means for instructing said character-with-context reconstruction means to reconstruct a character when said occurrence position holding means does not hold the occurrence position of the character string matching the n-character string immediately before the Ziv buffer.    
     
     
         23 . The apparatus according to  claim 21 , further comprising: 
 character/character string code holding means for holding a code corresponding to a character or a character string having a length of 1 through m;    character/character string reconstruction means for reconstructing a character or a character string according to a code held by said character/character string code holding means; and    switch means for instructing said character/character string reconstruction means to reconstruct a character or a character string when said occurrence position holding means does not hold the occurrence position of the character string matching the n-character string immediately before the Ziv buffer.    
     
     
         24 . A data reconstruction apparatus, comprising: 
 character-with-context code holding means for holding a code of a character next occurring with an immediately previous 0 through (m−1) character string as a context;    character-with-context retrieval means for retrieving a code with the immediately previous 0 through (m−1) character string as a context;    character-with-context reconstruction means for reconstructing a character from compressed data according to the code held by said character-with-context code holding means;    an intermediate code buffer for holding data reconstrucred by said character-with-context reconstruction means;    an output buffer for storing already reconstructed data when data held in said intermediate code buffer defined as input data, said buffer comprising a Lempel buffer for storing already reconstructed data and a Ziv buffer for storing data to be reconstructed;    occurrence position holding means for holding a part or all of an occurrence position of an n-character string in the Lempel buffer;    occurrence/non-occurrence check means for checking whether or not said occurrence position holding means holds an occurrence position of a character string matching the n-character string immediately before the Ziv buffer;    occurrence position obtaining means for obtaining the occurrence position of the character string matching the n-character string immediately before the Ziv buffer when the occurrence position is held by said occurrence position holding means;    matching length reconstruction means for reconstructing a matching length from an intermediate code;    character string reconstruction means for obtaining a character string for the matching length following the n-character string in the Lempel buffer as a next reconstruction result of the n-character string immediately before the Ziv buffer; and    output means for outputting the intermediate code as a reconstruction result as is when said occurrence position holding means does not hold the occurrence position.    
     
     
         25 . A data reconstruction apparatus, comprising: 
 character/character string code holding means for holding a code corresponding to a character or a character string having a length of 1 through m;    character/character string reconstruction means for reconstructing a character or a character string according to a code held by said character/character string code holding means;    an intermediate code buffer for holding data reconstructed by said character/character string reconstruction means;    an output buffer for storing already reconstructed data when data held in said intermediate code buffer defined as input data, said buffer comprising a Lempel buffer for storing already reconstructed data and a Ziv buffer for storing data to be reconstructed;    occurrence position holding means for holding a part or all of an occurrence position of an n-character string in the Lempel buffer;    occurrence/non-occurrence check means for checking whether or not said occurrence position holding means holds an occurrence position of a character string matching the n-character string immediately before the Ziv buffer;    occurrence position obtaining means for obtaining the occurrence position of the character string matching the n-character string immediately before the Ziv buffer when the occurrence position is held by said occurrence position holding means;    matching length reconstruction means for reconstructing a matching length from an intermediate code;    character string reconstruction means for obtaining a character string for the matching length following the n-character string in the Lempel buffer as a next reconstruction result of the n-character string immediately before the Ziv buffer; and    output means for outputting the intermediate code as a reconstruction result as is when said occurrence position holding means does not hold the occurrence position.    
     
     
         26 . A data reconstruction apparatus having an output buffer for holding original data reconstructed, said buffer comprising a Lempel buffer for storing an already reconstructed portion, and a Ziv buffer for storing a portion to be reconstructed, 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 generated from the character string having the length n immediately before the Ziv buffer;    matching length reconstruction means for reconstructing a matching length from a leading code in the Ziv buffer; and    character reconstruction means for defining a character string for the matching length after the occurrence position in the Lempel buffer as a reconstruction result of the code at the start in the Ziv buffer.    
     
     
         27 . The apparatus according to  claim 26 , 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 a length p immediately before the Ziv buffer, wherein 
 said character string reconstruction means defines as a reconstruction result of a leading code in the Ziv buffer a character string having the matching length after the occurrence position in the Lempel buffer only when all of the p characters match the character string.  
   
     
     
         28 . A data reconstruction apparatus having an output buffer for holding original data reconstructed, said buffer comprising a Lempel buffer for storing an already reconstructed portion, and a Ziv buffer for storing a portion to be reconstructed, comprising: 
 occurrence position holding means for holding a part or all of an occurrence position of an n-character string in the Lempel buffer;    occurrence/non-occurrence check means for checking whether or not said occurrence position holding means holds an occurrence position of a character string matching the n-character string immediately before the Ziv buffer;    occurrence position obtaining means for obtaining the occurrence position of the character string matching the n-character string immediately before the Ziv buffer;    matching length reconstruction means for reconstructing a matching length from a leading code in the Ziv buffer;    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    character reconstruction means for defining as a reconstruction result of a leading code in the Ziv buffer a character string having the matching length after the occurrence position in the Lempel buffer when the non-matching information is not associated with the character string having the length n immediately before the Ziv buffer.    
     
     
         29 . A data reconstruction apparatus having an output buffer for holding original data reconstructed, said buffer comprising a Lempel buffer for storing an already reconstructed portion, and a Ziv buffer for storing a portion to be reconstructed, comprising: 
 occurrence position holding means for holding a part or all of an occurrence position of an n-character string in the Lempel buffer;    occurrence/non-occurrence check means for checking whether or not said occurrence position holding means holds an occurrence position of a character string matching the n-character string immediately before the Ziv buffer;    occurrence position obtaining means for obtaining the occurrence position of the character string matching the n-character string immediately before the Ziv buffer;    matching length reconstruction means for reconstructing a matching length from a leading code in the Ziv buffer;    character reconstruction means for defining a character string having the matching length after the occurrence position in the Lempel buffer as a reconstruction result of a leading code in the Ziv buffer when said occurrence position obtaining means holds the occurrence position in the Lempel buffer of the character string matching the n-character string immediately before the Ziv buffer;    character-with-context code holding means for holding a code of a next occurring character using an immediately previous character or a feature extracted from the immediately previous character as a context; and    character-with-context code reconstruction means for reconstructing a character based on the code when said occurrence position obtaining means does not hold the occurrence position in the Lempel buffer of the character string matching the n-character string immediately before the Ziv buffer.    
     
     
         30 . A data compressing method comprising the steps of: 
 coding parts of matching symbol strings based on a matching length; and    coding a symbol string not coded based on the matching length by a probability statistic type coding system or a dictionary type coding system.    
     
     
         31 . A data compressing method comprising the steps of: 
 coding parts of matching symbol strings based on a matching length; and    coding the symbol strings coded based on the matching length furthermore by a probability statistic type coding system or a dictionary type coding system.    
     
     
         32 . A data compressing method for coding a current character string based on a matching length with a previous character string, comprising the step of 
 using a character string immediately before the current character string for searching an occurrence position of the previous character string.    
     
     
         33 . A data compressing method comprising the steps of: 
 storing a occurrence position of a previous second character string;    detecting a first character string immediately before a third character string;    obtaining a occurrence position of the second character string matching the first character string for each character;    detecting a matching length between a fourth character string following the second character string and the third character string; and    coding the third character string based on the matching length.    
     
     
         34 . A data compressing method comprising the steps of: 
 determining whether or not a matching length between a current character string and a previous character string is equal to or larger than a predetermined value;    coding the current character string by a coding method of a high compression rate on a repetition of short character strings when the matching length is equal to or smaller than the predetermined value; and    coding the current character string by a coding method of a high compression rate on a repetition of long character strings when the matching length exceeds the predetermined value.    
     
     
         35 . A computer-readable storage medium comprising: 
 a data structure in which a first symbol string matching a second symbol string having a predetermined length is coded; and    a data structure in which a third symbol string following the first symbol string is coded based on a matching length with a fourth symbol string following the second symbol string.    
     
     
         36 . A computer-readable storage medium storing a program used to direct a computer to perform the steps of: 
 detecting a second symbol string matching a first symbol string having a predetermined length from symbol strings;    detecting a matching length between a third symbol string following the first symbol string and a fourth symbol string following the second symbol string; and    coding the third symbol string based on a matching length between the third and fourth symbol strings.