Statistical data compression/decompression method

• US 6,128,412 A
• Filed: 03/31/1997
• Issued: 10/03/2000
• Est. Priority Date: 09/02/1996
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Satoh, Noriko
• Primary Examiner(s): Kelley, Christopher S.
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US08/828,558
• Time in Patent Office: 1,282 Days
• Field of Search: 382/246, 382/240, 382/229, 382/228, 382/245
• US Class Current: 382/246
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

Provided is a probabilistic statistical data compression/restoration method for variable-length encoding a source character and restoring a variable-length code to a character using the probability of occurrence of the source character which appears following a character string (context) of n characters which immediately precede the source character. When variable-length encoding is performed, a context registration unit successively registers context based upon an entered character without fixing the length (degree) of context, and a compressing encoder selects registered context satisfying a predetermined condition, e.g., registered context for which the frequency of occurrence is greater than a fixed value, as context (encoding context) used in encoding, and variable-length encodes a source character by using this encoding context. A restoration unit restores a code to a character by executing processing which is the reverse of the processing executed by the compressing encoder.

Claims

1. A statistical data compression method for storing a character string (context) as well as a probability of occurrence of a character which appears following the context, and encoding a character to a variable-length code using the probability, comprising the steps of:

extending a number of characters of the context (degree of context) based upon an entered character, and storing the context as well as the probability of occurrence of said context;

selecting a context for encoding one of the entered characters from among the stored contexts satisfying a predetermined condition; and

encoding the entered character using the probability of occurrence of said entered character following the selected context,

wherein when a frequency of occurrence of said stored context is greater than a predetermined value, it is judged that said predetermined condition is satisfied.

2. A statistical data decompression method for storing a character string (context) as well as a probability of occurrence of a character which appears following the context, and decoding a variable-length code to a character using the probability, comprising the steps of:

extending a number of characters of the context (degree of context) based upon a decoded character, and storing the context as well as the probability of occurrence of said context;

selecting a context for decoding the variable-length code from among the stored contexts satisfying a predetermined condition; and

decoding the variable-length code to a character using the probability of occurrence of said character following the selected context, wherein when a frequency of occurrence of an arbitrary character following to the stored context is greater than a predetermined value, it is judged that said stored context satisfies said predetermined condition.

3. A statistical data compression method for storing a character string (context) as well as a probability of occurrence of a character which appears following the context, and encoding a character to a variable-length code using the probability, comprising the steps of:

comparing a number n of characters of the context that is used in encoding of an entered character and a number Pn of characters of the context that was used in encoding of a previous character;

deciding the context to be stored, based upon the context that was used in encoding of the previous character when the number n is smaller than the number Pn;

storing the decided context as well as a probability of occurrence of the entered character which appears following the context; and

selecting a prescribed stored context as the context used in encoding of a succeeding entered character and encoding the entered character using the probability of occurrence of said entered character following the selected context.

4. The method according to claim 3, wherein said context (to be stored) consists of a context which was used in encoding of the previous character and said previous character.

5. A statistical data compression method for storing a character string (context) as well as a probability of occurrence of a character which appears following the context, and encoding a character to a variable-length code using the probability, comprising the steps of:

calculating the number of times the degrees of encoding contexts used in encoding previous characters are successively equal to or greater than degree 1;

obtaining Pn by adding 1 to said number;

comparing a number n of characters of the context that is used in encoding of an entered character and the value of Pn;

deciding the context to be stored, based upon the context that was used in encoding of the previous character when the number n is smaller than the value Pn;

storing the decided context as well as the probability of occurrence of the entered character which appears following the context; and

selecting a prescribed stored context as the context used in encoding of a succeeding entered character and encoding the character using the probability of occurrence of said entered character following the selected context, wherein in a case where the number of characters of each encoding context used for encoding each previous character is continuously equal to or greater than 1, said context to be stored includes a context comprising each of the contexts and the previous character.

6. The method according to claim 5, wherein if correlation between characters of the encoding context used for encoding said entered character is strong, the probability of occurrence of a combination character obtained by combining parts of the encoding context and said entered character is stored.

7. The method according to claim 5, wherein if the number of characters of the encoding context used for encoding said entered character and the number of characters of the encoding context used for encoding said previous character which precedes said entered character is respectively greater than a predetermined degree, the probability of occurrence of a combination character obtained by combining said entered character and said previous character is stored.

8. The method according to claim 7, wherein said predetermined degree is degree 2.

9. A statistical data decompression method for storing a character string (context) as well as a probability of occurrence of a character which appears following the context, and decoding a variable-length code to the character using the probability, comprising the steps of:

comparing a number n of characters of the context that is used in decoding of the variable-length code and a number Pn of characters of the context that was used in decoding of a previous variable-length code which precedes said variable-length code;

deciding the context to be stored, based upon the context that was used in decoding of the previous variable-length code to a previous character when the number n is smaller than the number Pn;

storing the decided context as well as the probability of occurrence of the character which appears following the context; and

selecting a prescribed stored context as the context used in decoding of the variable-length code and decoding the variable-length code to the character using the probability of occurrence of said character following the selected context.

10. The method according to claim 9, wherein said context to be stored includes the context which was used in decoding the various variable-length codes to the previous character and said previous character.

11. A statistical data decompression method for storing a character string (context) as well as a probability of occurrence of a character which appears following the context, and decoding a variable-length code to a character using the probability, comprising the steps of:

calculating the number of times the degrees of decoding contexts used in decoding previous variable-length codes are successively equal to or greater than degree 1;

obtaining Pn by adding 1 to said number;

comparing a number n of characters of the context that is used in decoding an entered variable-length code to a character and the value of Pn;

deciding the context to be stored, based upon a context that was used in decoding the previous variable-length code to a previous character when the number n is smaller than the value Pn;

storing the decided context as well as the probability of occurrence of a decoded character which appears following the context; and

selecting a prescribed stored context as the context used in decoding of a succeeding entered variable-length code and decoding the variable-length code using the probability of occurrence of the character following the selected context, wherein when the number of characters of each decoding context used for decoding each variable-length code is continuously equal to or greater than 1, said context to be stored includes a context comprising each of the contexts and the previous decoded character.

12. The method according to claim 11, wherein if correlation between characters of the decoding context used for decoding said entered variable-length code to a character is strong, the probability of occurrence of a combination character obtained by combining parts of the decoding context and said decoded character is stored.

13. The method according to claim 11, wherein if the number of characters of a decoding context used for decoding said entered variable-length code and the number of characters of a decoding context used for decoding said previous variable-length code is respectively greater than a predetermined degree, the probability of occurrence of a combination character obtained by combining said decoded character obtained by decoding the entered variable-length code and said previous decoded character is stored.

14. The method according to claim 13, wherein said predetermined degree is degree 2.

15. A statistical data compression apparatus storing a character string (context) as well as a probability of occurrence of a character which appears following the context, and encoding a character to a variable-length code using the probability, comprising:

a first unit extending a number of characters of the context (degree of context) based upon an entered character, and storing the context as well as the probability of occurrence of said context;

a second unit selecting a context for encoding one of the entered characters from among the stored contexts satisfying a predetermined condition; and

a third unit encoding the entered character using the probability of occurrence of said entered character following the selected context;

wherein when a frequency of occurrence of said stored context is greater than a predetermined value, it is judged that said predetermined condition is satisfied.