Statistical data compression/decompression method

• US 6,542,644 B1
• Filed: 09/28/1999
• Issued: 04/01/2003
• Est. Priority Date: 09/02/1996
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Satoh, Noriko
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US09/406,811
• Time in Patent Office: 1,281 Days
• Field of Search: 382/246, 382/228, 382/229, 382/240, 382/245, 382/232, 382/233, 382/239, 382/247, 382/248, 341/51, 341/107, 375/240.23, 358/539
• 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 as a context, and 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:

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

identifying a selected context for encoding one of entered characters from among stored contexts, where standard deviation of the probability of occurrence of each character following an eligible stored context is greater than a fixed value; and

encoding the one of the entered characters using a probability of occurrence of the one of the entered characters following the selected context.

2. A statistical data decompression method for storing a character string as a context, and 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:

extending a number of characters of the context to define a degree of context based upon a decoded character, and storing the context and a probability of occurrence of the context;

identifying a selected context for decoding a variable-length code, from among stored contexts for which a frequency of occurrence of each eligible context is greater than a predetermined value; and

decoding the variable-length code to a character using the probability of occurrence of the character following the selected context.

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

limiting a search range of contexts to include only contexts having respective degrees not greater than Pn, where Pn is obtained by adding 1 to a degree of a first context used to encode a character immediately previous to the target character; and

selecting, from the search range, a second context used to encode the target character.

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

limiting a search range of contexts to include only contexts having a degree of 1, 0 and Pn, where Pn is obtained by adding 1 to a degree of a first context used to encode a character immediately previous to the target character; and

selecting, from the sear search range, a second context used to encode the target character.

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

limiting a search range of contexts to include only contexts having respective degrees not greater than Pn, where Pn is obtained by adding 1 to a degree of an encoding context used to encode a character immediately previous to the target character; and

selecting, from the search range, a decoding context used to decode the variable-length target code.

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

limiting a search range of contexts to include only contexts having a degree of 1, 0 and Pn, where Pn is obtained by adding 1 to a degree of a first context used to decode a variable-length code immediately previous to the variable-length target code; and

selecting, from the search range, a second context used to decode the variable-length target code.

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

a first unit limiting a search range of contexts to include only contexts having respective degrees not greater than Pn, where Pn is obtained by adding 1 to a degree of a first context used to encode a character immediately previous to the target character; and

a second unit selecting, from said search range, a second context used to encode the target character.

8. A statistical data decompression apparatus storing a character string as a context, and a probability of occurrence of a character which appears following the context, and decoding a variable-length target code to a target character using the probability, comprising:

a first unit limiting a search range of contexts to include only contexts having a degree of 1, 0 and Pn, where Pn is obtained by adding 1 to a degree of a first context used to decode a variable-length code immediately previous to the target code; and

a second unit selecting, from the search range, a second context used to decode the target code.