Method of and apparatus for compressing and restoring data

• US 6,061,398 A
• Filed: 11/14/1996
• Issued: 05/09/2000
• Est. Priority Date: 03/11/1996
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Okada, Yoshiyuki, Yoshida, Shigeru, Satoh, Noriko
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Tran, Congvan
• Application Number:
  US08/749,330
• Time in Patent Office: 1,272 Days
• Field of Search: 375/240, 375/241, 375/253, 341/65-67, 341/50, 341/51, 341/64, 358/426, 358/261.1, 358/261.2, 358/427
• US Class Current: 375/240
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

A data compression apparatus is capable of compressing data at a high compression rate and at a high speed. A data decompression apparatus is used in combination with this data compression apparatus to decode the compressed data. The data compression apparatus includes a RAM which stores Huffman code trees each of which corresponds to a character string, i.e. "context." A CPU encodes each character which is to be encoded by use of a Huffman code tree corresponding to the context at that time. Each time a character is encoded, the Huffman code tree used is reconstructed so as to account for the encoded character. The data decompression apparatus stores Huffman code trees corresponding to contexts respectively, decodes the code to be decoded by use of a Huffman code tree corresponding to the context (a character string previously decoded). Each time one character is decoded, the Huffman code tree used for decoding is reconstructed so as to account for the decoded character.

Claims

1. A data compression apparatus comprising:

storage means for storing contexts and code trees according to a Huffman code rule, each of the code trees is related to a context;

input means for inputting a character string to be compressed;

character obtaining means for obtaining a character to be encoded from the inputted character string;

context specifying means for specifying a context occurred just preceding to the character obtained by said character obtaining means;

code outputting means for outputting a code corresponding to the character obtained by said character obtaining means in the code tree with respect to the context specified by said context specifying means;

updating means for updating the code tree used by said code outputting means in accordance with the Huffman code rule,

wherein

each of the code trees contains a special code `escape` which is transmitted to signal a decoder to shorten the context,

if the data relative to the character obtained by said character obtaining means does not exist in the code tree stored in said storage means with respect to the context specified by said context specifying means, said code outputting means outputs the special code `escape` within the code tree and repeats the outputting of the special code `escape` while shortening the context until the code for the character related to the context is found, and outputs the code of the character; and

adding means for adding data about unregistered combinations of character and contexts to said storage means when said code outputting means outputs the special code `escape`.

2. A data compression apparatus according to claim 1, further comprising:

using frequency managing means for managing a using frequency of each context by said code outputting means; and

deleting means for deleting data about a context with a minimum using frequency out of said storage means.

3. A data compression apparatus according to claim 1, further comprising:

degree managing means for managing degrees related to the contexts respectively and, when said code outputting means outputs the code, imparting a higher degree to the context used for outputting the code;

deleting means for deleting data about a context to which a lowest degree is imparted from within said storage means.

4. A data compression apparatus according to claim 1, wherein said degree managing means imparts a first degree to the context used for said code outputting means.

5. A data compression apparatus according to claim 1, wherein said degree managing means imparts a degree higher by one to the context used for said code outputting means.

6. A data compression apparatus comprising:

storage means for storing code trees according to a Huffman code rule and an occurrence frequency table, each of the code trees and the occurrence frequency table is related to a context;

input means for inputting a character string to be compressed;

character obtaining means for obtaining a character to be encoded from the inputted character string;

context specifying means for specifying a context that occurs just preceding to the character obtained by said character obtaining means;

first code outputting means for outputting, if data stored in said storage means for the context specified by said context specifying means is a code tree, a code corresponding to the character obtained by said character obtaining means in that by the code tree;

first updating means for updating the code tree used by said first code outputting means in accordance with the Huffman code rule;

second code outputting means for calculating, if data stored in said storage means for the context specified by said context specifying means is the occurrence frequency table, a code of the character obtained by said character obtaining means based on arithmetic coding rules using the occurrence frequency table, and for outputting the code; and

second updating means for increasing occurrence frequency relative to the character obtained by said character obtaining means within the occurrence frequency table used by said second code outputting means.

7. A data compression apparatus according to claim 6, wherein each of the code trees stored in said storage means are data for a context such that the divergence of each character'"'"'s probability from multiplication of 1/2 is small, and

each of the occurrence frequency table is used for such a context that the divergence of each character'"'"'s probability from multiplication of 1/2 is big.

8. A data compression apparatus according to claim 6, wherein each of the code trees stored in said storage means is data for such a context that order is less than a predetermined value, and

each of the occurrence frequency table is data for such a context that order is the predetermined value or larger.

9. A data compression apparatus according to claim 6, wherein each of the code tree stored in said storage means is made corresponding to such a context that a predetermined or larger number of characters occur following the context, and

each of the occurrence frequency table is made corresponding to such a context that a less than the predetermined number of characters occur following the context.

10. A data compression apparatus according to claims 6, wherein said second code outputting means outputs a fraction of the code as a theretofore encoded result when said first code outputting means outputs the code.

11. A data compression apparatus according to claim 6, further comprising:

code storage means having first and second storage areas stored with the codes as compressed results,

wherein said first code outputting means writes the code to said first storage area within said code storage means, and

said second code outputting means writes the code to said second storage area within said code storage means.

12. A data compression apparatus according to claim 6, further comprising:

code storage means having a storage area of a predetermined size, stored with the code as a compressed result; and

code outputting means for outputting the code stored in said storage means when said code storage means is incapable of storing a new code,

wherein said first code outputting means writes the codes to said storage area within said code storage means from a front part thereof, and

said second code outputting means writes the codes to said storage area within said code storage means from a rear part thereof.

13. A data decompression apparatus comprising:

storage means for storing contexts and code trees according to a Huffman code rule, each of the code trees is related to a context;

context specifying means for specifying a context to be used for restoring data;

character outputting means for outputting a character corresponding to the code in the code tree stored in said storage means with respect to the context specified by said context specifying means;

updating means for updating the code tree used by said character outputting means in accordance with the Huffman code rule, wherein each of the code trees contains a special code `escape`, and if the code is the special code in the code tree is the special character, said character outputting means repeats the restoration while shortening the context until the character is restored; and

registering means for registering said storage means with data about unregistered combinations of contexts and character.

14. A data decompression apparatus according to claim 13, further comprising:

using frequency managing means for managing a using frequency of each context by said character outputting means; and

deleting means for deleting data about a context with a minimum using frequency out of said storage means.

15. A data decompression apparatus according to claim 13, further comprising:

degree managing means for managing degrees by imparting a degree to each context and, when said character outputting means outputs the character, imparting a higher degree to the context used for outputting the character and;

deleting means for deleting data about a context to which a lowest degree is imparted from within said storage means.

16. A data decompression apparatus according to claim 15, wherein said degree managing means imparts a first order to the context used for said code outputting means.

17. A data decompression apparatus according to claim 15, wherein said degree managing means imparts a degree higher by one to the context used for said code outputting means.

22. A data decompression apparatus according to claim 17, wherein said second character outputting means removes fractions of the theretofore arithmetic codes when said first character outputting means performs the decoding.

18. A data decompression apparatus comprising:

storage means for storing code trees according to a Huffman code rule and an occurrence frequency table, each of the code trees and occurrence frequency table is related to a context;

context specifying means for specifying a context used for decoding;

first character outputting means for outputting, if data stored in said storage means for the context specified by said context specifying means is a code tree, a character made corresponding to the code in that code tree;

first updating means for updating the code tree used by said first character outputting means in accordance with the Huffman code rule;

second character outputting means for performing, if data stored in said storage means for the context specified by said context specifying means is the occurrence frequency table, arithmetic decoding of the code on the basis of the occurrence frequency table and outputting the character obtained as a decoded result; and

second updating means for increasing the occurrence frequency relative to the outputted character in the occurrence frequency table used by said second character outputting means.

19. A data decompression apparatus according to claim 18, wherein the code tree stored in said storage means is data for such a context that the divergence of each character'"'"'s from multiplication of 1/2 is small, and

the occurrence frequency table is data for such a context that the divergence of each character'"'"'s from multiplication of 1/2 is big.

20. A data decompression apparatus according to claim 18, wherein the code tree stored in said storage means is data for such a context that a order is less than a predetermined value, and

the occurrence frequency table is data for such a context that the order is the predetermined value or larger.

21. A data decompression apparatus according to claim 18, wherein the code tree stored in said storage means is made corresponding to such a context that a predetermined or larger number of characters occur following the context, and

the occurrence frequency table is made corresponding to such a context that a less than the predetermined number of characters occur following the context.

23. A data decompression apparatus according to claim 18, further comprising:

code storage means having first and second storage areas stored with the codes to be restored,

wherein said first character outputting means restores the code stored in said first storage area within said code storage means, and

said second character outputting means restores the code stored in said second storage area within said code storage means.

24. A data decompression apparatus according to claim 18, further comprising:

code storage means having a storage area of a predetermined size, stored with the code as a compressed result; and

code inputting means for inputting a new code into said code storage means when there is no code to be decoded within said code storage means,

wherein said first character outputting means decodes the codes from the front part of said storage area within said code storage means, and

said second character outputting means decodes the codes from the rear part of said storage area within said code storage means.