US6061398A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of and apparatus for compressing and restoring data
Assignee: Fujitsu Ltd
•
Filing: 1996-11-14
•
Granted: 2000-05-09
•
Expires: 2016-11-14
Abstract
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.
Inventors
- 👤 Noriko Satoh
- 👤 Yoshiyuki Okada
- 👤 Shigeru Yoshida
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 03:04
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
255 words
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`.
Claim 2
Dependent Claim
255 words
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`.
Claim 3
Dependent Claim
46 words
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.
Claim 4
Dependent Claim
62 words
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.
Claim 5
Dependent Claim
26 words
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.
Claim 6
Dependent Claim
28 words
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.
Claim 7
Dependent Claim
231 words
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.
Claim 8
Dependent Claim
231 words
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.
Claim 9
Dependent Claim
64 words
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.
Claim 10
Dependent Claim
54 words
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.
Claim 11
Dependent Claim
65 words
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.
Claim 12
Dependent Claim
34 words
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.
Claim 13
Dependent Claim
64 words
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.
Claim 14
Dependent Claim
100 words
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.
Claim 15
Dependent Claim
153 words
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.
Claim 16
Dependent Claim
153 words
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.
Claim 17
Dependent Claim
46 words
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.
Claim 18
Dependent Claim
65 words
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.
Claim 19
Dependent Claim
26 words
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.
Claim 20
Dependent Claim
28 words
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.
Claim 21
Dependent Claim
180 words
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.
Claim 22
Dependent Claim
180 words
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.
Claim 23
Dependent Claim
58 words
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.
Claim 24
Dependent Claim
52 words
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.
Claim 25
Dependent Claim
61 words
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.
Claim 26
Dependent Claim
30 words
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.
Claim 27
Dependent Claim
66 words
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.
Claim 28
Dependent Claim
100 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-09 | 2003-11-08 | 2004-05-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-09 | 2007-11-08 | 2008-05-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-09 | 2011-11-08 | 2012-05-09 | $7700.00 | Window Closed / Lapsed |