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

Claim 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.