Method of and an apparatus for compressing/decompressing data

Claim 3

A data compression method according to claim 1, including the step of consecutively numbering different codes to be prepared under the raw data mode and different coincident lengths to be found under the reproduction mode.

Claim 4

A data compression method according to claim 2, including the steps of: coding, according to a code book, at least a part of the position of a matching character string under the reproduction mode; and rearranging the code book according to the coded position, to shorten the length of the coded position.

Claim 5

A data compression method according to claim 1, including the step of consecutively numbering different codes to be prepared under the raw data mode and every combination of bits of at least a part of the address of a matching character string to be found under the reproduction mode.

Claim 6

A data compression method according to claim 4, including the steps of: coding, according to a code book, a coincident length under the reproduction mode; and rearranging the code book according to the code of the coincident length, to shorten the length of the code of the coincident length.

Claim 11

A data compression apparatus according to claim 7, including: a second code book containing a tree of codes corresponding to combinations of at least a part of bits of the address of a matching character string to be provided by the coding means under the reproduction mode; and second splay-tree coding means for retrieving, from the second code book, a code corresponding to at least a part of an input address, and rearranging the tree to halve the length of the retrieved code.

Claim 14

A data compression apparatus according to claim 9, including: a second code book containing a tree of codes corresponding to coincident lengths to be found by the coding means under the reproduction mode; and second splay-tree coding means for retrieving, from the second code book, a code according to an input coincident length, and rearranging the tree to halve the length of the retrieved code.

Claim 19

A data decompressing method according to claim 12, including the steps of: consecutively numbering code characters to be prepared under the raw data mode and different codes to be prepared under the reproduction mode; and decompressing an original character string according to the number decompressed from the first code if the first code indicates the raw data mode, and accumulating the original character string in a dictionary.

Claim 20

A data decompressing method according to claim 12, including the steps of: consecutively numbering different codes to be prepared under the raw data mode and different coincident lengths to be found under the reproduction mode; and decompressing a coincident length according to the number decompressed from the first code if the first code indicates the reproduction mode.

Claim 21

A data decompressing method according to claim 14, including the steps of: preparing a second code book containing codes corresponding to at least a part of the position of each matching character string; extracting a second code following the first code according to the second code book if the first code indicates the reproduction mode; decoding the second code according to the second code book, to decompress at least a part of the position of the matching character string; and rearranging the second code book according to the code, to shorten the length of the code.

Claim 22

A data decompressing method according to claim 12, including the steps of: consecutively numbering different codes to be prepared under the raw data mode and every combination of bits of at least a part of the address of a matching character string to be found under the reproduction mode, and preparing a first code book containing codes corresponding to the consecutive numbers; and decompressing at least a part of an address according to the number decompressed from the first code if the first code indicates the reproduction mode.

Claim 23

A data decompressing method according to claim 16, including the steps of: preparing a second code book containing codes corresponding to coincident lengths; extracting a second code following the first code according to the second code book if the first code indicates the reproduction mode; decompressing a coincident length from the second code according to the second code book; and rearranging the second code book according to the code, to shorten the length of the code.

Claim 24

A data decompressing method according to claim 12, including the steps of: consecutively numbering every combination of higher bits of a code character to be prepared under the raw data mode and different codes to be prepared under the reproduction mode; preparing a code book containing numbers allocated to combinations of lower bits of the code character, for each of the combinations of the higher bits of the code character; decompressing the higher part of a character according to the number decompressed from the first code that must be a variable-length code, if the first code indicates the raw data mode; extracting a variable-length code following the first code as a second code; and decompressing the lower part of the character from the second code according to the code book corresponding to the higher part of the character.

Claim 25

A data decompressing apparatus having decompress processing means for decompressing an original character string from codes prepared by a sliding-dictionary-type data compression method that finds a longest matching character string in a coding character string and in a coded character string stored in a dictionary and activates, according to the length of the longest matching character string, a raw data mode to provide the matching character string that must consist of a single character as it is as a code, or a reproduction mode to code the position and length of the matching character string in the dictionary, and a dictionary for accumulating the decompressed original character string, the decompress processing means comprising: a first code book containing a tree of codes corresponding to consecutive numbers allocated to characters to be prepared under the raw data mode and coincident lengths to be found under the reproduction mode; extraction means for extracting, from an input code, a variable-length code as a first code; first splay-tree decoding means for decoding the first code into a number according to the first code book and rearranging the tree to halve the length of the code; decision means for determining whether it is the raw data mode or reproduction mode according to the number decompressed from the first code; and character string decompressing means for decompressing a character string by finding the same according to the number if it is the raw data mode, or by retrieving the same from the dictionary according to a coincident length obtained from the number if it is the reproduction mode.

Claim 26

A data decompressing apparatus having decompress processing means for decompressing an original character string from codes prepared by a sliding-dictionary-type data compression method that finds a longest matching character string in a coding character string and in a coded character string stored in a dictionary and activates, according to the length of the longest matching character string, a raw data mode to provide the matching character string that must consist of a single character as it is as a code, or a reproduction mode to code the position and length of the matching character string in the dictionary, and a dictionary for accumulating the decompressed original character string, the decompress processing means comprising: a first code book containing a tree of codes corresponding to consecutive numbers allocated to characters to be prepared under the raw data mode and coincident lengths to be found under the reproduction mode; extraction means for extracting, from an input code, a variable-length code as a first code; first splay-tree decoding means for decoding the first code into a number according to the first code book and rearranging the tree to halve the length of the code; decision means for determining whether it is the raw data mode or reproduction mode according to the number decompressed from the first code; and character string decompressing means for decompressing a character string by finding the same according to the number if it is the raw data mode, or by retrieving the same from the dictionary according to a coincident length obtained from the number if it is the reproduction mode.

Claim 27

A data decompressing apparatus according to claim 19, wherein the decompress processing means includes: a second code book containing a tree of codes corresponding to every combination of at least a part of bits of the address of a matching character string to be found under the reproduction mode; and second splay-tree decoding means for decompressing a bit string from an input variable-length code according to the second code book and rearranging the tree to halve the length of the code, the extraction means extracting, as a second code, a variable-length code following the first code if the first code indicates the reproduction mode and sending the second code to the second splay-tree decoding means, the character string decompressing means retrieving, if it is the reproduction mode, a matching character string from the dictionary according to the coincident length specified by the number provided by the first splay-tree decoding means and an address represented by a bit string provided by the second splay-tree decoding means.

Claim 28

A data decompressing apparatus having decompress processing means for decompressing an original character string from codes prepared by a sliding-dictionary-type compression method that finds a longest matching character string in a coding character string and in a coded character string stored in a dictionary and activates, according to the length of the longest matching character string, a raw data mode to provide the matching character string that must consist of a single character as it is as a code, or a reproduction mode to code the position and length of the matching character string in the dictionary, and a dictionary for accumulating the decompressed original character string, the decompressing processing means comprising: a first code book containing a tree of codes corresponding to consecutive numbers allocated to characters to be prepared under the raw data mode and every combination of bits of at least a part of the address of a matching character string to be found under the reproduction mode; extraction means for extracting, from an input code, a variable-length code as a first code; first splay-tree decoding means for decoding the first code into a number according to the first code book and rearranging the tree to halve the length of the code; decision means for determining whether it is the raw data mode or reproduction mode according to the number decompressed from the first code; and character string decompressing means for decompressing a character string by finding the same according to the number if it is the raw data mode, or by retrieving the same from the dictionary according to at least a part of an address obtained from the number if it is the reproduction mode.

Claim 29

A data decompressing apparatus having decompress processing means for decompressing an original character string from codes prepared by a sliding-dictionary-type compression method that finds a longest matching character string in a coding character string and in a coded character string stored in a dictionary and activates, according to the length of the longest matching character string, a raw data mode to provide the matching character string that must consist of a single character as it is as a code, or a reproduction mode to code the position and length of the matching character string in the dictionary, and a dictionary for accumulating the decompressed original character string, the decompressing processing means comprising: a first code book containing a tree of codes corresponding to consecutive numbers allocated to characters to be prepared under the raw data mode and every combination of bits of at least a part of the address of a matching character string to be found under the reproduction mode; extraction means for extracting, from an input code, a variable-length code as a first code; first splay-tree decoding means for decoding the first code into a number according to the first code book and rearranging the tree to halve the length of the code; decision means for determining whether it is the raw data mode or reproduction mode according to the number decompressed from the first code; and character string decompressing means for decompressing a character string by finding the same according to the number if it is the raw data mode, or by retrieving the same from the dictionary according to at least a part of an address obtained from the number if it is the reproduction mode.

Claim 30

A data decompressing apparatus according to claim 21, wherein the decompress processing means includes: a second code book containing a tree of codes corresponding to coincident lengths to be found under the reproduction mode; and second splay-tree decoding means for decompressing a coincident length from an input variable-length code according to the second code book and rearranging the tree to halve the length of the code, the extraction means extracting, as a second code, a variable-length code following the first code if the first code indicates the reproduction mode and sending the second code to the second splay-tree decoding means, the character string decompressing means retrieving, if it is the reproduction mode, a matching character string from the dictionary according to an address specified by the number provided by the first splay-tree decoding means and a coincident length provided by the second splay-tree decoding means.

Claim 31

A data decompressing apparatus having decompress processing means for decompressing an original character string from codes prepared by a sliding-dictionary-type data compression method that finds a longest matching character string in a coding character string and in a coded character string stored in a dictionary and activates, according to the length of the longest matching character string, a raw data mode to provide the matching character string that must consist of a single character as it is as a code, or a reproduction mode to code the position and length of the matching character string in the dictionary, and a dictionary for accumulating the restored original character string, the decompressing processing means comprising: a first code book containing a tree of codes corresponding to consecutive numbers allocated to every combination of higher bits of a character to be prepared under the raw data mode and different codes to be prepared under the reproduction mode; a second code book containing a tree of codes corresponding to every combination of lower bits of the character, for each of the combinations of the higher bits of the character; first extraction means for extracting, from an input code, a variable-length code as a first code; first splay-tree decoding means for decoding the first code into a number according to the first code book and rearranging the tree to halve the length of the code; decision means for determining whether it is the raw data mode or reproduction mode according to the number decompressed from the first code; second extraction means for extracting a variable-length second code following the first code if it is the raw data mode; second splay-tree decoding means for selecting one of the trees from the second code book according to the higher part of a character specified by the number provided by the first splay-tree decoding means if it is the raw data mode, decoding the second code into the lower part of the character, and rearranging the trees to halve the length of the code; and character string decompressing means for decompressing the character string by combining the higher part of the character specified by the number provided by the first splay-tree decoding means with the lower part of the character provided by the second splay-tree decoding means if it is the raw data mode, or by retrieving the same from the dictionary according to a code corresponding to the number if it is the reproduction mode.

Claim 32

A data decompressing apparatus having decompress processing means for decompressing an original character string from codes prepared by a sliding-dictionary-type data compression method that finds a longest matching character string in a coding character string and in a coded character string stored in a dictionary and activates, according to the length of the longest matching character string, a raw data mode to provide the matching character string that must consist of a single character as it is as a code, or a reproduction mode to code the position and length of the matching character string in the dictionary, and a dictionary for accumulating the restored original character string, the decompressing processing means comprising: a first code book containing a tree of codes corresponding to consecutive numbers allocated to every combination of higher bits of a character to be prepared under the raw data mode and different codes to be prepared under the reproduction mode; a second code book containing a tree of codes corresponding to every combination of lower bits of the character, for each of the combinations of the higher bits of the character; first extraction means for extracting, from an input code, a variable-length code as a first code; first splay-tree decoding means for decoding the first code into a number according to the first code book and rearranging the tree to halve the length of the code; decision means for determining whether it is the raw data mode or reproduction mode according to the number decompressed from the first code; second extraction means for extracting a variable-length second code following the first code if it is the raw data mode; second splay-tree decoding means for selecting one of the trees from the second code book according to the higher part of a character specified by the number provided by the first splay-tree decoding means if it is the raw data mode, decoding the second code into the lower part of the character, and rearranging the trees to halve the length of the code; and character string decompressing means for decompressing the character string by combining the higher part of the character specified by the number provided by the first splay-tree decoding means with the lower part of the character provided by the second splay-tree decoding means if it is the raw data mode, or by retrieving the same from the dictionary according to a code corresponding to the number if it is the reproduction mode.

Claim 35

A data compression apparatus according to claim 24, including: a second code book containing a tree of codes corresponding to combinations of at least a part of bits of the address of a matching character string to be provided by the coder under the reproduction mode; and a second splay-tree coder retrieving, from the second code book, a code corresponding to at least a part of an input address, and rearranging the tree to halve the length of the retrieved code.

Claim 38

A data compression apparatus according to claim 26, including: a second code book containing a tree of codes corresponding to coincident lengths to be found by the coder under the reproduction mode; and a second splay-tree coder retrieving, from the second code book, a code according to an input coincident length, and rearranging the tree to halve the length of the retrieved code.

Claim 41

A data decompressing apparatus having decompress processing unit decompressing an original character string from codes prepared by a sliding-dictionary-type data compression method that finds a longest matching character string in a coding character string and in a coded character string stored in a dictionary and activates, according to the length of the longest matching character string, a raw data mode to provide the matching character string that must consist of a single character as it is as a code, or a reproduction mode to code the position and length of the matching character string in the dictionary, and a dictionary for accumulating the decompressed original character string, the decompress processing unit comprising: a first code book containing a tree of codes corresponding to consecutive numbers allocated to characters to be prepared under the raw data mode and coincident lengths to be found under the reproduction mode; an extractor extracting, from an input code, a variable-length code as a first code; a first splay-tree decoder decoding the first code into a number according to the first code book and rearranging the tree to halve the length of the code; a decision unit determining whether it is the raw data mode or reproduction mode according to the number decompressed from the first code; and a character string decompressing unit decompressing a character string by finding the same according to the number if it is the raw data mode, or by retrieving the same from the dictionary according to a coincident length obtained from the number if it is the reproduction mode.

Claim 42

A data decompressing apparatus having decompress processing unit decompressing an original character string from codes prepared by a sliding-dictionary-type data compression method that finds a longest matching character string in a coding character string and in a coded character string stored in a dictionary and activates, according to the length of the longest matching character string, a raw data mode to provide the matching character string that must consist of a single character as it is as a code, or a reproduction mode to code the position and length of the matching character string in the dictionary, and a dictionary for accumulating the decompressed original character string, the decompress processing unit comprising: a first code book containing a tree of codes corresponding to consecutive numbers allocated to characters to be prepared under the raw data mode and coincident lengths to be found under the reproduction mode; an extractor extracting, from an input code, a variable-length code as a first code; a first splay-tree decoder decoding the first code into a number according to the first code book and rearranging the tree to halve the length of the code; a decision unit determining whether it is the raw data mode or reproduction mode according to the number decompressed from the first code; and a character string decompressing unit decompressing a character string by finding the same according to the number if it is the raw data mode, or by retrieving the same from the dictionary according to a coincident length obtained from the number if it is the reproduction mode.

Claim 43

A data decompressing apparatus according to claim 29, wherein the decompress processing unit includes: a second code book containing a tree of codes corresponding to every combination of at least a part of bits of the address of a matching character string to be found under the reproduction mode; and a second splay-tree decoder decompressing a bit string from an input variable-length code according to the second code book and rearranging the tree to halve the length of the code, the extractor extracting, as a second code, a variable-length code following the first code if the first code indicates the reproduction mode and sending the second code to the second splay-tree decoder, the character string decompressing unit retrieving, if it is the reproduction mode, a matching character string from the dictionary according to the coincident length specified by the number provided by the first splay-tree decoder and an address represented by a bit string provided by the second splay-tree decoder.

Claim 44

A data decompressing apparatus having decompress processing unit decompressing an original character string from codes prepared by a sliding-dictionary-type compression method that finds a longest matching character string in a coding character string and in a coded character string stored in a dictionary and activates, according to the length of the longest matching character string, a raw data mode to provide the matching character string that must consist of a single character as it is as a code, or a reproduction mode to code the position and length of the matching character string in the dictionary, and a dictionary for accumulating the decompressed original character string, the decompressing processing means comprising: a first code book containing a tree of codes corresponding to consecutive numbers allocated to characters to be prepared under the raw data mode and every combination of bits of at least a part of the address of a matching character string to be found under the reproduction mode; an extractor extracting, from an input code, a variable-length code as a first code; a first splay-tree decoder decoding the first code into a number according to the first code book and rearranging the tree to halve the length of the code; a decision unit determining whether it is the raw data mode or reproduction mode according to the number decompressed from the first code; and a character string decompressing unit decompressing a character string by finding the same according to the number if it is the raw data mode, or by retrieving the same from the dictionary according to at least a part of an address obtained from the number if it is the reproduction mode.

Claim 45

A data decompressing apparatus having decompress processing unit decompressing an original character string from codes prepared by a sliding-dictionary-type compression method that finds a longest matching character string in a coding character string and in a coded character string stored in a dictionary and activates, according to the length of the longest matching character string, a raw data mode to provide the matching character string that must consist of a single character as it is as a code, or a reproduction mode to code the position and length of the matching character string in the dictionary, and a dictionary for accumulating the decompressed original character string, the decompressing processing means comprising: a first code book containing a tree of codes corresponding to consecutive numbers allocated to characters to be prepared under the raw data mode and every combination of bits of at least a part of the address of a matching character string to be found under the reproduction mode; an extractor extracting, from an input code, a variable-length code as a first code; a first splay-tree decoder decoding the first code into a number according to the first code book and rearranging the tree to halve the length of the code; a decision unit determining whether it is the raw data mode or reproduction mode according to the number decompressed from the first code; and a character string decompressing unit decompressing a character string by finding the same according to the number if it is the raw data mode, or by retrieving the same from the dictionary according to at least a part of an address obtained from the number if it is the reproduction mode.

Claim 46

A data decompressing apparatus according to claim 31, wherein the decompress processing means includes: a second code book containing a tree of codes corresponding to coincident lengths to be found under the reproduction mode; and a second splay-tree decoding unit decompressing a coincident length from an input variable-length code according to the second code book and rearranging the tree to halve the length of the code, the extractor extracting, as a second code, a variable-length code following the first code if the first code indicates the reproduction mode and sending the second code to the second splay-tree decoder, the character string decompressing unit retrieving, if it is the reproduction mode, a matching character string from the dictionary according to an address specified by the number provided by the first splay-tree decoder and a coincident length provided by the second splay-tree decoder.

Claim 47

A data decompressing apparatus having decompress processing unit decompressing an original character string from codes prepared by a sliding-dictionary-type data compression method that finds a longest matching character string in a coding character string and in a coded character string stored in a dictionary and activates, according to the length of the longest matching character string, a raw data mode to provide the matching character string that must consist of a single character as it is as a code, or a reproduction mode to code the position and length of the matching character string in the dictionary, and a dictionary for accumulating the restored original character string, the decompressing processing means comprising: a first code book containing a tree of codes corresponding to consecutive numbers allocated to every combination of higher bits of a character to be prepared under the raw data mode and different codes to be prepared under the reproduction mode; a second code book containing a tree of codes corresponding to every combination of lower bits of the character, for each of the combinations of the higher bits of the character; a first extractor extracting, from an input code, a variable-length code as a first code; a first splay-tree decoder decoding the first code into a number according to the first code book and rearranging the tree to halve the length of the code; a decision unit determining whether it is the raw data mode or reproduction mode according to the number decompressed from the first code; a second extractor extracting a variable-length second code following the first code if it is the raw data mode; a second splay-tree decoder selecting one of the trees from the code book according to the higher part of a character specified by the number provided by the first splay-tree decoder if it is the raw data mode, decoding the second code into the lower part of the character, and rearranging the trees to halve the length of the code; and a character string decompressing unit decompressing the character string by combining the higher part of the character specified by the number provided by the first splay-tree decoder with the lower part of the character provided by the second splay-tree decoder if it is the raw data mode, or by retrieving the same from the dictionary according to a code corresponding to the number if it is the reproduction mode.

Claim 48

A data decompressing apparatus having decompress processing unit decompressing an original character string from codes prepared by a sliding-dictionary-type data compression method that finds a longest matching character string in a coding character string and in a coded character string stored in a dictionary and activates, according to the length of the longest matching character string, a raw data mode to provide the matching character string that must consist of a single character as it is as a code, or a reproduction mode to code the position and length of the matching character string in the dictionary, and a dictionary for accumulating the restored original character string, the decompressing processing means comprising: a first code book containing a tree of codes corresponding to consecutive numbers allocated to every combination of higher bits of a character to be prepared under the raw data mode and different codes to be prepared under the reproduction mode; a second code book containing a tree of codes corresponding to every combination of lower bits of the character, for each of the combinations of the higher bits of the character; a first extractor extracting, from an input code, a variable-length code as a first code; a first splay-tree decoder decoding the first code into a number according to the first code book and rearranging the tree to halve the length of the code; a decision unit determining whether it is the raw data mode or reproduction mode according to the number decompressed from the first code; a second extractor extracting a variable-length second code following the first code if it is the raw data mode; a second splay-tree decoder selecting one of the trees from the code book according to the higher part of a character specified by the number provided by the first splay-tree decoder if it is the raw data mode, decoding the second code into the lower part of the character, and rearranging the trees to halve the length of the code; and a character string decompressing unit decompressing the character string by combining the higher part of the character specified by the number provided by the first splay-tree decoder with the lower part of the character provided by the second splay-tree decoder if it is the raw data mode, or by retrieving the same from the dictionary according to a code corresponding to the number if it is the reproduction mode.