Apparatus for repeatedly compressing a data string and a method thereof

• US 6,392,567 B2
• Filed: 01/22/2001
• Issued: 05/21/2002
• Est. Priority Date: 03/31/2000
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Satoh, Noriko
• Primary Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US09/765,421
• Publication Number:
  US 20010026231A1
• Time in Patent Office: 484 Days
• Field of Search: 341/51, 341/50, 341/87, 341/106, 707/7
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: Y10S 707/99937 Sorting

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.

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.

2. The data compression apparatus according to claim 1 wherein the sort device rearranges character strings using a prefix of a predetermined number of characters included in each of the character strings.

3. The data compression apparatus according to claim 2 wherein the sort device rearranges character strings using a prefix of three characters included each of the character strings.

4. The data compression apparatus according to claim 2 wherein the sort device rearranges character strings in such a way that a plurality of same prefixes adjoin each other.

5. The data compression apparatus according to claim 2 wherein the sort device rearranges character strings using a radix sort method.

6. The data compression apparatus according to claim 2 wherein the sort device rearranges character strings using a quick sort method.

7. The data compression apparatus according to claim 1 further comprising a reverse rank unit storing information to obtain a rank of an address of each character string in the appearance location storage device from an address of the character string to be encoded, wherein

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.