Data processing apparatus and data processing method

• US 5,748,122 A
• Filed: 03/03/1997
• Issued: 05/05/1998
• Est. Priority Date: 10/17/1994
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Abe, Yuko, Ohno, Hitoshi, Shinagawa, Akio
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US08/813,943
• Time in Patent Office: 428 Days
• Field of Search: 341/51, 341/65, 341/67, 341/58, 341/59
• US Class Current: 341/67
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A data processing apparatus has a dictionary control unit in which pieces of dictionary data stored in a dictionary buffer are compared with pieces of input data to be compressed input one after another, a piece of particular dictionary data agreeing with a piece of particular input data is expelled from the dictionary buffer, the dictionary data stored in the dictionary buffer are placed close together in a direction, and the particular input data is written in the dictionary buffer. Also, a data processing apparatus has an occurrence frequency producing editor for counting an occurrence frequency of each of types of pieces of input data to be compressed and producing an occurrence frequency table formed of a plurality of occurrence frequencies of the types of the input data to be compressed, a data comparing editor for predicting an occurrence of a piece of next input data subsequent to a piece of input data, and a code converting editor for converting the types of pieces of input data according to the occurrence prediction of the next input data in the data comparing editor on condition that a type of a piece of input data is converted into a piece of compressed data having a shorter bit length as an occurrence probability of the type of the input data is higher.

Claims

1. A data compressing apparatus comprises;

a data producing means for counting an occurrence frequency of each of types of pieces of input data to be compressed and producing an occurrence frequency table formed of a plurality of occurrence frequencies of the types of the input data to be compressed;

a data predicting means for predicting an occurrence of a piece of next input data input to the data producing means subsequent to a piece of input data of which a type is just counted by the data producing means; and

a data converting means for converting the types of pieces of input data according to the occurrence prediction of the next input data in the data predicting means on condition that a type of a piece of input data is converted into a piece of compressed data having a shorter bit length as an occurrence probability of the type of the input data is higher and on condition that a type of a piece of input data is converted into a piece of compressed data having a longer bit length as an occurrence probability of the type of the input data is lower.

2. The data compressing apparatus according to claim 1 in which the occurrence frequency table is renewed by the data producing means each time a piece of input data to be compressed is input to the data producing means in the data processing apparatus.

3. The data compressing apparatus according to claim 1, the data processing apparatus further comprising level adjusting means for adjusting a length of each of the compressed data converted by the data converting means.

4. The data compressing apparatus according to claim 1 in which the occurrence frequency table is produced by the data producing means by fetching all pieces of input data to be compressed or a piece of input data to be compressed.

5. The data compressing apparatus according to claim 1 in which pieces of data of the occurrence frequencies arranged in the occurrence frequency table are rearranged in order of degree of occurrence frequency in the data producing means, a plurality of data positions ranging from a highest data position for a piece of data of a highest occurrence frequency to a lowest data position for a piece of data of a lowest occurrence frequency be defined in the occurrence frequency table, a piece of shorter positional information be allocated to a data position in which a piece of data of an occurrence frequency is arranged as the occurrence frequency is higher, a piece of longer positional information be allocated to a data position in which a piece of data of an occurrence frequency is arranged as the occurrence frequency is lower, and a code table obtained by allocating the pieces of positional information to the data positions in the occurrence frequency table be referred by the data converting means.

6. The data compressing apparatus according to claim 1 in which the compressed data is rewritten by the data converting means while the occurrence frequency table is renewed by the data producing means.

7. A data processing method, comprising the steps of:

counting an occurrence frequency of each of types of pieces of input data to be compressed in advance and producing an occurrence frequency table formed of a plurality of occurrence frequencies of the types of the input data to be compressed;

predicting an occurrence of a piece of next input data subsequent to a piece of input data to be compressed while referring the occurrence frequency table produced; and

converting the types of pieces of input data according to the occurrence prediction of the next input data on condition that a type of a piece of input data is converted into a piece of compressed data having a shorter bit length as an occurrence probability of the type of the input data is higher and on condition that a type of a piece of input data is converted into a piece of compressed data having a longer bit length as an occurrence probability of the type of the input data is lower.

8. The data processing method according to claim 7 in which the step of converting the types of pieces of input data comprises the steps of:

rearranging pieces of data of the occurrence frequencies arranged in the occurrence frequency table in order of degree of occurrence frequency;

defining a plurality of data positions ranging from a highest data position for a piece of data of a highest occurrence frequency to a lowest data position for a piece of data of a lowest occurrence frequency in the occurrence frequency table;

allocating a piece of shorter positional information to a data position in which a piece of data of an occurrence frequency is arranged as the occurrence frequency is higher;

allocating a piece of longer positional information to a data position in which a piece of data of an occurrence frequency is arranged as the occurrence frequency is lower; and

referring a code table obtained by allocating the pieces of positional information to the data positions in the occurrence frequency table.

9. The data processing method according to claim 7 in which the step of counting an occurrence frequency comprises the step of renewing the occurrence frequency table and the code table each time a piece of input data to be compressed is input.

10. The data processing method according to claim 7 in which the step of converting the types of pieces of input data comprises the step of adjusting a bit length of the compressed data after the input data to be compressed is converted into the compressed data.

11. The data processing method according to claim 7 in which the step of counting an occurrence frequency comprises the step of producing the occurrence frequency table according to all pieces of input data to be compressed or a piece of input data to be compressed.

12. The data processing method according to claim 7 in which the step of predicting an occurrence of a piece of next input data comprises the step of comparing pieces of data of the occurrence frequencies written in the occurrence frequency table with a piece of next input data subsequent to a piece of input data to be compressed to predict the occurrence of the next input data subsequent to the input data.

13. The data processing method according to claim 7 in which the step of converting the types of pieces of input data comprises the steps of:

defining pieces of positional information indicating a plurality of data positions ranging from a highest data position for a piece of data of a highest occurrence frequency to a lowest data position for a piece of data of a lowest occurrence frequency in the occurrence frequency table;

defining an identification code for identifying the pieces of positional information; and

making each of the compressed data by combining one of the pieces of positional information and the identification code.