Lempel-ziv compression with expulsion of dictionary buffer matches

• US 5,635,932 A
• Filed: 07/21/1995
• Issued: 06/03/1997
• 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/505,760
• Time in Patent Office: 683 Days
• Field of Search: 341/51, 341/87
• US Class Current: 341/51
• 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 processing apparatus, comprising:

a dictionary buffer for storing one or more pieces of dictionary data formed by utilizing pieces of input data; and

dictionary control means for

comparing the dictionary data stored in the dictionary buffer with the input data input one after another for the purpose of coding and compressing a piece of particular dictionary data which is included in the dictionary data and agrees with the input data by comparing the dictionary data with the input data or for the purpose of decoding a piece of particular coded compressed data,

expelling the particular dictionary data from the dictionary buffer in case where the particular dictionary data agrees with the input data, placing the dictionary data stored in a data writing range of the dictionary buffer, from which the particular dictionary data is expelled, close together in a direction, and

writing a piece of particular input data agreeing with the particular dictionary data in the dictionary buffer in which the dictionary data of the data writing range are placed close together.

2. The data processing apparatus according to claim 1, in which at least one or more input data strings are used as the input data, and at least one or more dictionary data strings are used as the dictionary data.

3. The data processing apparatus according to claim 1, the data processing apparatus further comprising an auxiliary dictionary buffer for storing the particular dictionary data expelled from the dictionary buffer.

4. The data processing apparatus according to claim 1, the data processing apparatus further comprising a fixed dictionary buffer for storing one or more pieces of fixed data or one or more fixed data strings, which are selected from the input data and occur at a high occurring frequency as compared with the input data by examining the occurring frequency of each of the input data in advance, as pieces of dictionary data or a plurality of dictionary data strings.

5. The data processing apparatus according to claim 1 in which the dictionary buffer of the data processing apparatus comprises a memory region formed in a ring-shaped structure by connecting ends of the memory region in a non-ending loop shape, the particular input data being written in the memory region as a piece of dictionary data.

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

comparing one or more pieces of dictionary data with one or more pieces of input data input one after another for the purpose of coding and compressing a piece of particular dictionary data agreeing with the input data by comparing the dictionary data with the input data or a piece of coded compressed data is decoded;

expelling the particular dictionary data from a data writing range of a dictionary in case where the particular dictionary data agrees with the input data;

placing the dictionary data stored in the data writing range of the dictionary, from which the particular dictionary data is expelled, close together in a direction; and

writing a piece of particular input data agreeing with the particular dictionary data in the dictionary in which the dictionary data of the data writing range are placed close together.

7. The data processing method according to claim 6, the data processing method further comprising the step of referring the particular dictionary data expelled from the dictionary in the step of comparing one or more pieces of dictionary data with one or more pieces of input data.

8. The data processing method according to claim 6, the data processing method further comprising the step of referring one or more pieces of fixed data or one or more fixed data strings, which are selected from the input data and occur at a high occurring frequency as compared with the input data by examining the occurring frequency of each of the input data in advance, in the step of comparing one or more pieces of dictionary data with one or more pieces of input data.

9. The data processing method according to claim 6, the data processing method further comprising the step of regarding the particular input data written in an input memory region subsequent to a dictionary memory region of the dictionary, in which the dictionary data are written, as a piece of dictionary data in the step of comparing one or more pieces of dictionary data with one or more pieces of input data.