Method, apparatus, computer program and storage medium for data compression
AssigneeCanon Kabushiki Kaisha
InventorMasami Kugai
Life of this patent
Estimating the term…
Abstract
A technique for reversible compression of digital data enables lossless data compression at high speed while taking advantage of high-speed decompression. In the technique, a dictionary area is reserved and initialized, the dictionary area being constructed with first and second storage areas. A computer program and storage medium are provided as well.
Claims25
A data compression method of reading input data from a predetermined input storage area, searching previous input data that matches the input data, generating coded data based on code generation information corresponding to the previous input data, and outputting the coded data to a predetermined output storage area, comprising the steps of:
- reserving a dictionary for storing input data related information related to the previous input data, and code generation information of the input data in association with each other, said dictionary comprising an element area which includes link information for linking the element area to another element area;
- searching the dictionary reserved;
- registering input data related information, related to the previous input data, and code generation information of the input data in the element area;
- and
- tracking the element area according to the link information in said dictionary searching step to search input data related information in the dictionary, which corresponds to the input data related information related to current input data, then obtaining code generation information related to the input data related information, and generating coded data based on the code generation information.
A data compression method of reading input data from a predetermined input storage area, searching previous input data that matches the input data, generating coded data based on code generation information corresponding to the previous input data, and outputting the coded data to a predetermined output storage area, comprising the steps of:
- reserving a dictionary constructed with a first storage area and a second storage area, the first storage area storing representative data related to the input data and classification information in association with each other, while the second storage area storing auxiliary data related to the input data and code generation information in association with each other for each of the classification information;
- and
- searching the dictionary, said searching step including a first searching step and a second searching step,
- wherein in said first searching step, the first storage area is searched using the representative data as a key, and in said second searching step, the second storage area is searched using the auxiliary data as a key,
- representative data is led from the input data to search the first storage area in said first searching step, thereby obtaining the classification information related to the representative data,
- the second storage area, which is designated by the classification information, is searched using the auxiliary data led from the input data as a key in said second searching step, and code generation information related to the auxiliary data is obtained, and
- coded data is generated from the code generation information and outputted to an output storage area.
A computer program functioning as a data compression apparatus, which reads input data from a predetermined input storage area, searches previous input data that matches the input data, generates coded data based on code generation information corresponding to the previous input data, and outputs the coded data to a predetermined output storage area, by having a computer read and execute said program, said computer program comprising:
- program codes for a step of reserving a dictionary for storing input data related information related to the previous input data, and code generation information of the input data in association with each other, said dictionary comprising an element area which includes link information for linking the element area to another element area;
- program codes for a step of searching the dictionary reserved;
- program codes for a step of registering input data related information related to the previous input data, and code generation information of the input data in the element area;
- and
- program codes for a step of tracking the element area according to the link information in said dictionary searching step to search input data related information in the dictionary, which corresponds to the input data related information related to current input data, then obtaining code generation information related to the input data related information, and generating coded data based on the code generation information.
A computer program functioning as a data compression apparatus, which reads input data from a predetermined input storage area, searches previous input data that matches the input data, generates coded data based on code generation information corresponding to the previous input data, and outputs the coded data to a predetermined output storage area, by having a computer read and execute said program, said computer program comprising:
- program codes for a step of reserving a dictionary constructed with a first storage area and a second storage area, the first storage area storing representative data related to the input data and classification information in association with each other, while the second storage area storing auxiliary data related to the input data and code generation information in association with each other for each of the classification information;
- and
- program codes for a step of searching the dictionary, said searching step including a first searching step and a second searching step,
- wherein in said first searching step, the first storage area is searched using the representative data as a key, and in said second searching step, the second storage area is searched using the auxiliary data as a key,
- representative data is led from the input data to search the first storage area in said first searching step, thereby obtaining the classification information related to the representative data,
- the second storage area, which is designated by the classification information, is searched using the auxiliary data led from the input data as a key in said second searching step, and code generation information related to the auxiliary data is obtained, and
- coded data is generated from the code generation information and outputted to an output storage area.
A data compression apparatus for reading input data from a predetermined input storage area, searching previous input data that matches the input data, generating coded data based on code generation information corresponding to the previous input data, and outputting the coded data to a predetermined output storage area, comprising:
- reserving means reserving a dictionary which stores input data related information related to the previous input data, and code generation information of the input data in association with each other, said dictionary comprising an element area which includes link information for linking the element area to another element area;
- searching means for searching the dictionary reserved;
- registering means for registering input data related information, related to the previous input data, and code generation information of the input data in the element area;
- and
- coded data generating means for tracking the element area according to the link information by said dictionary searching means to search input data related information in the dictionary, which corresponds to the input data related information related to current input data, then obtaining code generation information related to the input data related information, and generating coded data based on the code generation information.
A data compression apparatus for reading input data from a predetermined input storage area, searching previous input data that matches the input data, generating coded data based on code generation information corresponding to the previous input data, and outputting the coded data to a predetermined output storage area, comprising:
- reserving means reserving a dictionary constructed with a first storage area and a second storage area, the first storage area storing representative data related to the input data and classification information in association with each other, while the second storage area storing auxiliary data related to the input data and code generation information in association with each other for each of the classification information;
- and
- searching means for searching the dictionary, said searching means including first searching means and second searching means,
- wherein said first searching means searches the first storage area using the representative data as a key, and said second searching means searches the second storage area using the auxiliary data as a key,
- representative data is led from the input data to search the first storage area by said first searching means, thereby obtaining the classification information related to the representative data,
- the second storage area, which is designated by the classification information, is searched by said second searching means using the auxiliary data led from the input data as a key, and code generation information related to the auxiliary data is obtained, and
- coded data is generated from the code generation information and outputted to an output storage area.
Dependencies are inferred from the claim text.