Apparatus for repeatedly compressing a data string and a method thereof
First Claim
Patent Images
1. A data compression apparatus comprising:
- a data storage device storing character string data to be compressed;
a sort device rearranging each character string of which a start point is each of addresses in the data storage device based on contents of each character string;
an appearance location storage device storing address information indicating an address of each character string in an order of rearranged character strings;
a detection device detecting repetition based on the address information stored in the appearance location storage device; and
an encoding device encoding and outputting the detected repetition.
2 Assignments
0 Petitions
Accused Products
Abstract
A character string of which a start point is each address of character string data in an input buffer is rearranged in the predetermined order, so that a rank list is generated. Next, the location of the matching candidate of a character string to be encoded is obtained on the basis of the rank list. Then, the character string to be encoded is compared with a matching candidate, thereby obtaining a matching length. Further, a code is generated using the location of the matching candidate and the matching length, and the code is output as compression data.
-
Citations
16 Claims
-
1. A data compression apparatus comprising:
-
a data storage device storing character string data to be compressed;
a sort device rearranging each character string of which a start point is each of addresses in the data storage device based on contents of each character string;
an appearance location storage device storing address information indicating an address of each character string in an order of rearranged character strings;
a detection device detecting repetition based on the address information stored in the appearance location storage device; and
an encoding device encoding and outputting the detected repetition. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
the detection device sets as a matching candidate a character string corresponding to address information stored in a higher rank than a rank obtained by using the reverse rank device, and compares the character string to be encoded with the matching candidate, thereby obtaining a matching length, and the encoding device encodes the character string to be encoded using information indicating a location of the matching candidate and the matching length. -
8. The data compression apparatus according to claim 1 further comprising a matching location storage device storing address information of a character string, which is the same as each character string and appears latest, corresponding to an address of each character string, wherein
the detection device generates address information to be stored in the matching location storage device from address information stored in the appearance location storage device, compares address information with adjoining address information in the matching location storage device, and detects a continuation area where address information continuously changes, and the encoding device sets a character string corresponding to a location of the continuation area as a character string to be encoded, and encodes the character string to be encoded using address information stored in the continuation area and a length of the continuation area. -
9. The data compression apparatus according to claim 8 wherein
when the detection device focuses on a rank of the appearance location storage device, and a prefix of a character string in the focused-on rank is identical with a prefix of a character string in a rank one higher than the focused-on rank, the detection device stores address information stored in the rank one higher at a location in the matching location storage device which corresponds to address information stored in the focused-on rank. -
10. The data compression apparatus according to claim 8 wherein
the detection device detects a part where two or more continuation areas are connected in the matching location storage device and obtains character strings of a plurality of matching candidates based on address information stored in the two or more continuation areas, and the encoding device encodes the character string to be encoded using information indicating a location of a matching candidate with a longest matching length among the plurality of matching candidates and also using the longest matching length. -
11. The data compression apparatus according to claim 1 further comprising a retrieval device storing information to obtain a rank of a character string, that includes a same prefix as a prefix of a predetermined number of characters included in a character string to be encoded, in the appearance location storage device from the prefix of the predetermined number of characters, wherein
the detection device sets as a matching candidate a character string corresponding to address information stored in the rank obtained by using the retrieval device, and compares the character string to be encoded with the matching candidate to obtain a matching length, and the encoding device encodes the character string to be encoded using information indicating a location of the matching candidate and the matching length. -
12. The data compression apparatus according to claim 11 wherein
the detection device updates information stored in the retrieval device so that a rank obtained from the retrieval device corresponding to a prefix of the predetermined number of character strings is made to be a rank of a character string including the same prefix that appears latest.
-
-
13. A computer readable storage medium recording a program for a computer, the program causing the computer to perform:
-
rearranging each character string of which a start point is each of addresses in character string data to be compressed, based on contents of each character string;
recording address information indicating an address of each character string in an order of the rearranged character strings;
detecting repetition based on the recorded address information; and
encoding the detected repetition.
-
-
14. A data compression method comprising:
-
rearranging each character string of which a start point is each of addresses in character string data to be compressed, based on contents of each character string;
recording address information indicating an address of each character string, in an order of the rearranged character strings;
detecting repetition based on the recorded address information; and
encoding the detected repetition.
-
-
15. A data compression apparatus comprising:
-
data storage means for storing character string data to be compressed;
sort means for rearranging each character string of which a start point is each of addresses in the data storage means, based on contents of each character string;
appearance location storage means for storing address information indicating an address of each character string in an order of the rearranged character strings;
detection means for detecting repetition based on the address information stored in the appearance location storage means; and
encoding means for encoding and outputting the detected repetition.
-
-
16. A propagation signal propagating a program to a computer, the program causing the computer to perform:
-
rearranging each character string of which a start point is each of addresses in character string data to be compressed, based on contents of each character string;
recording address information indicating an address of each character string, in an order of the rearranged character strings;
detecting repetition based on the recorded address information; and
encoding the detected repetition.
-
Specification