Data compression apparatus and method

Patent metadata

Field	Value
Publication number	US-9455740-B2
Application number	US-201213669689-A
Country	US
Kind code	B2
Filing date	Nov 6, 2012
Priority date	Oct 22, 2012
Publication date	Sep 27, 2016
Grant date	Sep 27, 2016

Abstract

A data compression apparatus generates a global symbol table for an overlapping data using a part of the entire data to be compressed and a local symbol table that is not overlapped with the global symbol table and compressing data with a block as a unit. The apparatus increase compression efficiency.

First claim

What is claimed is:

1. A data compression apparatus, comprising:
a global symbol table generation unit configured to divide original columns of a data table into reference blocks of a predetermined size, select a first overlapping original column extracted from each of the reference blocks as a global target for compression, and generate a global symbol table corresponding to the global target, wherein the global target is not updated after the global symbol table generation unit finishes generating the global symbol table, even if an original column is newly input:
a local symbol table generation unit configured to search for a second overlapping original column whenever an original column is input, select the second overlapping original column as a local target for compression, and generate a local symbol table corresponding to the local target, wherein the local target is updated whenever an original column is input: and
a data compression unit configured to generate global compressed data or local compressed data by compressing the overlapping original column corresponding to the global symbol table or the local symbol table, and generate at least a compressed block having a predetermined size, wherein the second overlapping original column selected for the local target is different from the first overlapping original column selected for the global target;
wherein the local symbol table generation unit excludes the first overlapping original column selected as the global target from the local target when the global symbol table is completed.

2. The data compression apparatus of claim 1 , wherein the data compression unit generates the local compressed data by compressing the original column corresponding to the local symbol table before the global symbol table is completed.

3. The data compression apparatus of claim 1 , wherein the data compression unit determines whether the size of the block becomes larger than the predetermined size whenever the original column is input and generates compressed block.

4. The data compression apparatus of claim 3 , wherein the data compression unit generates the local compressed data or global compressed data corresponding to the original column input until now as the compressed block, when the size of the block becomes larger than the predetermined size.

5. The data compression apparatus of claim 1 , wherein the global symbol data generating unit comprises:
a global buffer for storing the original column temporally;
a global data pattern search unit configured to search for an occurrence frequency of the original column stored temporally, extract an overlapping original column and select the global target; and
a global symbol assignment unit configured to assign global symbol to the global target.

6. The data compression apparatus of claim 5 , wherein the global data pattern search unit selects the global target according to the length and occurrence frequency of the overlapping original column.

7. The data compression apparatus of claim 1 , wherein the local symbol table generating unit comprises:
a local buffer for storing the original column; a local data pattern search unit configured to search for an occurrence frequency of the original column stored temporally, extract an overlapping original column and select the local target; and
a local assignment unit configured to assign local symbol to the local target.

8. The data compression apparatus of claim 7 , wherein the local data pattern unit excludes the original column selected as the global target from the local target when the global symbol table is completed.

9. The data compression apparatus of claim 7 , wherein the local data pattern search unit updates the local target whenever the original column is input.

10. The data compression apparatus of claim 1 , wherein the predetermined size of the reference block is larger than that of the compressed block.

11. The data compression apparatus of claim 1 , wherein the local symbol table is stored in the compressed block.

12. The data compression apparatus of claim 11 , wherein the global symbol table is stored in a space separated from the space where the global compressed data and local compressed data are stored.

13. A data compression method, comprising:
loading original columns of a data table;
dividing original columns of the data table into reference blocks of a predetermined size and selecting a first overlapping original column extracted from each of the reference blocks as a global target of compression;
generating a global symbol table corresponding to the global target;
wherein the global target is not updated after the global symbol table is finished being generated, even if an original column is newly input; and
searching for a second overlapping original column whenever an original column is input and selecting the second overlapping original column as a local target for compression;
generating a local symbol table corresponding to the local target, wherein the local target is updated whenever an original column is input;
generating a global compressed data or local compressed data by compressing the overlapping original column corresponding to the global symbol table or the local symbol table; and
generating at least a compressed block having a predetermined size, wherein the second overlapping original column selected for the local target is different from the first overlapping original column selected for the global target;
wherein the first overlapping original column selected as the global target is excluded from the local target when the global symbol table is completed.

14. The data compression method of claim 13 , further comprising:
searching for the original columns and selecting an overlapping original column as the local target, in case that the global symbol table was not generated in determining whether the global symbol table was completed.

15. The data compression method of claim 14 , further comprising:
generating a local compressed data by compressing the original column according to the local symbol table in case that the global symbol table was not completed.

16. The data compression method of claim 13 , wherein the generating the compressed block comprises determining whether the size of the block becomes larger than the predetermined size whenever the original column is input.

17. The data compression method of claim 16 , further comprising:
generating the local compressed data or the global compressed data corresponding to the original column input until now as the compressed block in case that the size of the block becomes larger than the predetermined size in determining whether the size of the block stored.

18. The data compression method of claim 13 , wherein the selecting the local target comprises updating the local target whenever the original column is input.

Assignees

• Tibero Co Ltd
• Tmaxdata Co Ltd

Inventors

• An Jae Seok
• Park Sang Young

Classifications

• H03M7/30 Primary

  Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction · CPC title

• G06F17/30595

  Physics · mapped topic

• G06F17/30315

  Physics · mapped topic

• G06F16/284

  Relational databases · CPC title

• G06F16/221

  Column-oriented storage; Management thereof · CPC title