Data compression and decompression scheme using a search tree in which each entry is stored with an infinite-length character string

• US 5,841,376 A
• Filed: 05/08/1996
• Issued: 11/24/1998
• Est. Priority Date: 09/29/1995
• Status: Expired due to Term

• Current Assignee: Kyocera Corporation
• Original Assignee: Kyocera Corporation
• Inventors: Hayashi, Takaaki
• Primary Examiner(s): Hoff, Marc S.
• Application Number:
  US08/646,516
• Time in Patent Office: 930 Days
• Field of Search: 341/50, 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/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A dictionary has a plurality of entries each for storing a pointer that indicates the head of a character string of input data stored in a data memory. A longest-coincidence character string that coincides with a character string to be coded over a longest length (i.e., a longest-coincidence length) is searched for from among the character strings indicated by the respective pointers. The longest-coincidence length and an index of an entry storing a pointer indicating the head of the longest-coincidence character string are coded, and a resulting code is written to a code memory. An entry storing the pointer indicating the head of the coded character string is added to the dictionary, to update it.

Claims

1. A data compressing apparatus comprising:

a data memory for storing input data;

a code memory for storing codes obtained by compressing the input data;

a dictionary having a plurality of entries each for storing a first pointer that indicates a character string of the input data stored in the data memory, the dictionary being expressed by a search tree including a main node for storing the first pointer, and a branching node for representing branching in the search tree,

longest-coincidence character string search means for searching for a longest-coincidence character string that coincides with a character string to be coded over a longest length from among the character strings indicated by the respective first pointers, the longest length being a longest-coincidence length;

coding means for coding the longest-coincidence length and an index of an entry storing a first pointer indicating the longest-coincidence character string, and for writing a resulting code to the code memory; and

dictionary updating means for adding to the dictionary an entry storing the first pointer indicating the coded character string,

wherein the dictionary allows registration of the entries with no limitation on lengths thereof by storing the first pointers in the respective entries, whereby a character string having an arbitrary length stored in the data memory can be found and coded by designating an index of an entry and the longest-coincidence length.

2. The data compressing apparatus according to claim 1, wherein each of the entries of the dictionary comprises:

the first pointer;

a number of characters existing on a path from a root of the search tree to a branching position, the number being an offset number;

a second pointer for representing a link to a first-occurring branching node in the main node; and

a third pointer for representing a link from a branching node to a next branching node.

3. The data compressing apparatus according to claim 1, wherein the search tree further comprises initial registration nodes for storing, preliminarily and respectively, all of characters appearing in the input data, and each of the initial registration nodes has an index that is equal to a value of a character stored in the initial registration node.

4. The data compressing apparatus according to claim 1, wherein the coding means expresses, in coding the longest-coincidence length, the longest-coincidence length by using a length that is counted from a branching node that is closest to an end character of the longest-coincidence character string on a side closer to the root of the search tree.

5. The data compressing apparatus according to claim 1, wherein the coding means expresses, in coding the longest-coincidence length, the longest-coincidence length by using a length that is counted from a root of the search tree.

6. A data decompressing apparatus comprising:

a code memory for storing compressed codes;

a data memory for storing data obtained by decompressing the compressed codes;

a conversion table having entries each correlating an index with a pointer indicating a restored character string stored in the data memory;

decoding means for decoding a code stored in the code memory into an index and a longest-coincidence length;

data copying means for copying a restored character string stored in the data memory which is determined based on the longest-coincidence length and a pointer that has been obtained by referencing the conversion table by using the decoded index, to the data memory at a restored data writing position; and

conversion table updating means for adding, to the conversion table, an entry correlating a non-registered index with the pointer indicating the copied character string stored in the data memory.

7. The data decompressing apparatus according to claim 6, wherein each of the entries of the conversion table correlates an index, a pointer indicating a restored character string stored in the data memory, and a number of characters of the restored character string as counted from a branching node that is closest to an end character of the restored character string on a side closer to a root of a search tree.