Method of and an apparatus for compressing/decompressing data

A method of compressing data by a slide dictionary technique 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 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 101, comprising the steps of:

• consecutively numbering different codes to be prepared under the raw data mode and reproduction mode;
• coding, according to a code book, a number corresponding to a code prepared under one of the raw data mode and reproduction mode;
• rearranging the code book according to the code of the number, to shorten the length of the code of the number;
• 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;
• and
• forming, under the raw data mode, a variable-length code of a number allocated to the lower bits of a given code character, the number being found in the code book associated with the higher bits of the code character.

An apparatus for compressing data by a sliding-dictionary technique, having matching means for finding a longest matching character string in a coding character string and in a coded character string in a coded character string stored in a dictionary and coding means for selectively activating, 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 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 by the coding means under the raw data mode and different codes to be prepared by the coding means under the reproduction mode;
• a second code book containing a tree of codes allocated to every combination of lower bits of the character, for each of the combinations of the higher bits of the character;
• first splay-tree coding means for retrieving, from the first code book, a code corresponding to the higher part of a character prepared under the raw data mode or a code prepared under the reproduction mode, and rearranging the tree to halve the length of the retrieved code;
• and
• second splay-tree coding means for selecting one of the trees in the second code book according to the higher part of the character prepared under the raw data mode, retrieving a code corresponding to the lower part of the character, and rearranging the tree to halve the length of the retrieved code.

A method of 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, comprising the steps of:

• consecutively numbering different codes to be prepared under the raw data mode and reproduction mode and preparing a first code book containing codes corresponding to the consecutive numbers;
• extracting, from an input code, a first code corresponding to one of the consecutive numbers and decoding the first code according to the first code book;
• rearranging the first code book according to the code, to shorten the length of the code;
• determining whether it is the raw data mode or reproduction mode according to the number restored from the first code;
• and
• carrying out a decompressing process proper for the determined mode, on a code corresponding to the number.

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.

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.

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.

An apparatus for compressing data by a sliding-dictionary technique, having a matching unit which finds a longest matching character string in a coding character string and in a coded character string in a coded character string stored in a dictionary and a coder which selectively 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 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 by the coder under the raw data mode and different codes to be prepared by the coder under the reproduction mode;
• a second code book containing a tree of codes allocated to every combination of lower bits of the character, for each of the combinations of the higher bits of the character;
• a first splay-tree coder retrieving, from the first code book, a code corresponding to the higher part of a character prepared under the raw data mode or a code prepared under the reproduction mode, and rearranging the tree to halve the length of the retrieved code;
• and
• a second splay-tree coder selecting one of the trees in the second code book according to the higher part of the character prepared under the raw data mode, retrieving a code corresponding to the lower part of the character, and rearranging the tree to halve the length of the retrieved code.

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.

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.

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.