WO2005112270A1

WO2005112270A1 - Method and apparatus for structured block-wise compressing and decompressing of xml data

Info

Publication number: WO2005112270A1
Application number: PCT/IB2005/051088
Authority: WO
Inventors: Anthony Morel
Original assignee: Koninklijke Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 2004-05-13
Filing date: 2005-04-01
Publication date: 2005-11-24
Anticipated expiration: 2006-11-13
Also published as: CN1697327A; CN1951017A; KR20070011490A; EP1751873A1; JP2007537642A

Abstract

The present invention provides a method and a device for XML compression and decompression. The XML document is assumed to consist of similar data blocks that can be decomposed into a single metadata template and enclosed content data. This template is analysed and LZW-based data compression (ZLIB) of the content data is performed using references to the positions in the template. The template itself is compressed separately. The content data pertaining to a data block are compressed block-wise ( referred to as “sequentially” in the application ) so that selective decompression of any data block can be performed without decompressing the entire file.

Description

METHOD AND APPARATUS FOR STRUCTURED BLOCK-WISE < COMPRESSING AND DECOMPRESSING OF XML DATA

Background of the Invention

The present invention relates to a method and apparatus for compressing/ decompressing data, and more particularly relates to a method and apparatus for sequentially compressing/decompressing data.

At present, sequentially compressing/decompressing data is a common method for data compressing/decompressing. The method uses data already processed during the compressing process as references to compress /decompress following data, thus reducing the redundancy. The typical sequentially compressing schemes are LZ77 and Zlib. Zlib is a sequentially compressing scheme based on the Huffman code and LZ77.

Figure 1 is a structural schematic block diagram illustrating the apparatus for sequentially compressing/decompressing data in the prior art. As shown in Figure 1 , the apparatus comprises: sequential encoder 120, used to sequentially encode and compress the input N data segments as a whole; memory 130, used to store the compressed data; sequential decoder 140, used to sequentially decode the compressed data and separate the N data segments from each other using the data nature or an index table. Such compressing method can achieve the maximum compressing efficiency, and the redundancy degree between data segments can be stored. The data redundancy after compressing can be greatly reduced especially when the N data segments have the same or similar data structure.

In the apparatus shown in Figure 1 , however, it is impossible to access each of the compressed data segments at random. It is because that in the process of compressing as shown in Figure 1 , the compressing of next data segment, e.g. data segment K (K is a number between 1-N), is dependant on all the previously compressed data segments, i.e., data segments 1-K. Therefore, during the process of decompressing, it must first decompress all of the data segments (data segments1-K) prior to this data segment (data segment K), then the compressed data segment (data segment K) can be decompressed. As an extreme example, in order to get the last data segment (data segment N) from the compressed data, the data segment N can not be obtained until all of the compressed data segments prior to data segment N should be decompressed in order and discarded.

Figure 2 is a structural schematic block diagram illustrating another apparatus for sequentially compressing/decompressing data in the prior art. The difference from the above apparatus is that the data segments compressing /decompressing are independent to each other. As shown in

Figure 2, the apparatus includes: sequentially encoder 120, used to sequentially compress data segment K independently, this data segment K can be any one in data segments 1-N; memory 130, used to store the compressed data segment K; sequentially decoder 140, used to decompress the compressed data segment K and restore the data segment

K. In above compressing process, the N data segments are compressed/decompressed separately and compressing/ decompressing process of each data segment are independent, the sequentially compressing/decompressing of following data segment is not dependent on previously compressed data segments. If the data segment K is obtained by decompressing, it's only need to find the compressed data segment K from the memory 130 directly and do the sequentially decompressing, without need to decompress data segments prior to it. The data segment can be randomly accessed by some approach since this apparatus compresses data segments independently. However, because each data segment is compressed independently, the redundancy between them cannot be used, thus resulting in that the whole data compressing ratio is low.

Therefore, there is a need to new method and apparatus for sequentially compressing/decompressing data, by which the data can be efficiently compressed and also randomly accessed.

Summary of the Invention

One object of the invention is to solve the drawbacks of current sequentially compressing/decompressing schemes, providing a new method and apparatus for sequentially compressing/decompressing data, and thus is not only able to efficiently sequentially compress data but also able to randomly access data.

The present invention provides a method for sequentially compressing a data segment, which segment has a data structure. Firstly, obtain several compressing parameters; secondly, sequentially compress the data segment according to the obtained parameters and get a compressed data segment. Wherein the data segment can be obtained by preprocessing of the data. The compressing parameters come from a storage device; certainly, the compressing parameters can also obtained from the compressing of a template with this data structure. The compressing of a template with this data structure can get a compressed template in addition to the said compressing parameters. The compressed template is stored separately from the compressed data segment, or the compressed template is discarded.

Correspondingly, the present invention also provides a method for sequentially decompressing a compressed data segment, which data segment has a data structure. Firstly, obtain several decompressing parameters; secondly, sequentially decompress the compressed data segment according to the obtained decompressing parameters and get a decompressed data segment. The decompressing parameters come from a storage device; certainly, the decompressing parameters can also obtained from the sequentially decompressing of a compressed template, the template has said data structure. The sequentially decompressing of the compressed template can get a decompressed template in addition to the said decompressing parameters. The decompressed template is discarded.

The present invention also provides an apparatus for sequentially compressing a data segment, the apparatus includes an obtaining device and a compressing device, and the data segment has a data structure. The device for sequentially compressing a data segment can optionally include a preprocessing device, a storage device and a discarding device. The obtaining device is used to obtain several compressing parameters; and the compressing device is used to sequentially compress said data segment according to the obtained compressing parameters and thus gets a compressed data segment. The compressing device is also used to sequentially compress a template with the data structure, and consequently gets said compressing parameters and a compressed template; the preprocessing device is used to preprocess data and consequently gets said data segment; the storage device is used to store said compressing parameters; and the discarding device is used to discard said compressed template.

Correspondingly, the present invention provides an apparatus for sequentially decompressing a compressed data segment, the apparatus includes an obtaining device and a decompressing device. The device for sequentially decompressing a compressed data segment can also optionally include a storage device and a discarding device. The obtaining device is used to obtain several decompressing parameters; and the decompressing device is used to sequentially decompress the compressed data segment according to the obtained decompressing parameters and consequently gets a decompressed data segment, and the data segment has a special data structure. The decompressing device is also used to sequentially decompress a compressed template, and consequently gets said decompressing parameters and a decompressed template, and the template has said data structure; the storage device is used to store said decompressing parameters; and the discarding device is used to discard said decompressed template.

The above method and apparatus for sequentially compressing/ decompressing data provided by the present invention can improve the data compressing ratio in that the data structure part (template) can be filtered after compressing of a data segment with special data structure; after the separate compressing of several data segments with special data structures, the data structure part of each data segment can be filtered out, but only keep a compressed template or discard all the compressed templates, therefore the data compressing ratio is greatly increased and also the each data segment can be randomly processed.

By reference to the below descriptions incorporated with the drawings and the claims, other objects and achievements of present invention are obvious, and a comprehensive understanding of the present invention can be gained.

Brief Description of the Drawings

The present invention is elaborately explained through the embodiments and by reference to the drawings, in which: Figure 1 is a structural schematic block diagram illustrating the apparatus for sequentially compressing/decompressing data in the prior art;

Figure 2 is a structural schematic block diagram illustrating another apparatus for sequentially compressing/decompressing data in the prior art;

Figure 3 is a structural schematic block diagram illustrating an apparatus for sequentially compressing a data segment according to an embodiment of the present invention;

Figure 4 is a flow chart of sequentially compressing a data segment according to an embodiment of the present invention;

Figure 5 is a structural schematic block diagram illustrating an apparatus for sequentially decompressing a compressed data segment according to an embodiment of the present invention; and

Figure 6 is a flow chart of sequentially decompressing a compressed data segment according to an embodiment of the present invention.

In all the drawings, the same reference number refers to the similar or same feature and functionality. The present invention is further described below by reference to drawings and embodiments.

Preferred Embodiments of the Invention

Figure 3 is a structural schematic block diagram illustrating an apparatus for sequentially compressing a data segment according to an embodiment of the present invention, which data segment has a data structure. Apparatus 300 includes obtaining device 310 and compressing device 320. Apparatus 300 can also include preprocessing device 330, storage device 340 and discarding device 350.

Obtaining device 310 is used to obtain several compressing parameters, which indicate the encoded compressing information of the template with the data structure, including the information such as the compressing mode, storage position and data structure of the template. The compressing parameters can be obtained from storage device 340. The compressing parameters correspond to the internal state of the compressing device 320 after compressing a template with the data structure.

The compressing device 320 is used to sequentially compress the data segments to be compressed according to the obtained compressing parameters, and consequently gets a compressed data segment. The compressing device 320 is also used to sequentially compress a template with the data structure, and thus obtains said compressing parameters. The data to be compressed come from preprocessing device 330, certainly, it can also come from other data sources (not shown in drawings).

Preprocessing device 330 is used to preprocess inputted data, and consequently generates a data segment conforming to said data structure. The data segment is dynamic data and varies with the differences of inputted data. For example, one appropriate instance of preprocessing devices is the publishing process unit of the database records in the XML (extensible Markup Language) format. If the inputted data is blank data without any content, the preprocessing device 330 can generate a template with said data structure. The template describes the data structure of the data segment, but it does not include any dynamic content data. The preprocessing device 330 can output all kinds of categories of data segments according to different situations. For example, it can generate different data segment according to different type of data inputted from database. In the case, for each kind of data segment, it can consequently generate a template with corresponding data structure used to compress the corresponding data segment. Certainly, a general template can be designed for use by all kinds of data segments during compressing, but this scheme can only provide compressing ratio with sub-optimum performance.

Storage device 340 is used to store compressed data segment and compressing parameters, and also used to store the compressed data structure template. The storage device 340 may be a hard disk, a USB (Universal Serial Bus) disk, or a cache, etc. But it should be noted that the compressed data segment and compressed template should be stored separately, e.g. they can be stored with different file names. The compressed template stored in storage device 340 is for use during the decompressing of the data segment.

Discarding device 350 is used to discard the compressed template. The compressed template came from the compressing device 320. To prevent taking up too much space in the storage device, the compressed template can also be discarded.

The running process of apparatus 300 is detailed in Figure 4 below.

Figure 4 is a flow chart of sequentially compressing a data segment according to an embodiment of the present invention. The data segment has a data structure. Firstly, obtain a template with this data structure (step S410). The template can be obtained after preprocessing data without any valid content. In the process of preprocessing, a tag can be added to the end of the template, e.g. the file ending tag, the tag is used to indicate the ending position of the template file.

The data structure for the TV program data is described below:

</radioshow>

Above data structure is the content of said template.

Next, sequentially compress the template (step S420). Particularly, initiate encoding state firstly, and then sequentially compress the template, e.g. using the Zlib sequentially compressing algorithm, thus get a compressed template and several compressing parameters. The compressing parameters indicate the encoded compressing information of the template and its storage position in the compressing device, including the information such as its compressing mode, data structure, Huffman list, etc. It should be noted that the Zlib sequentially compressing algorithm is not the only compressing scheme. Implementers can choose different compressing algorithms according to their needs.

Then, the compressed template is discarded (step S430). The compressed template can be discarded by the system for not affecting the whole data compressing ratio and storing the storage space. Since there is a tag in the end of the template, e.g. the file ending tag, the system can discard the compressed template automatically after reading the tag. Certainly, the compressed template can also be stored in a special place of a local storage device for the decompressing in the future. In particular, when several data segments with this data structure are compressed in order using the method of the present invention, one of the compressed templates can be kept and other compressed templates can be discarded.

Above steps S410-S430 are procedures of sequentially compressing a template with this data structure and then obtaining compressing parameters. The compressing parameters can be stored, e.g. in a local storage device, for the use of compressing another data segment with the same or similar data structure. In the case, if the compressing parameters have been stored in the local storage device, the above steps S410-S430 can be omitted when compressing another data segment with same data structure, that is, the compressing parameters can be obtained directly from the storage device without compressing a template with this data structure.

It should be noted that, before directly obtaining the compressing parameters from the storage device, the encoding state should be initiated first to make sure that the current process is not affected by the , compressing parameters at the end of previous process.

Next, obtain a data segment which has said data structure (step S440). This data segment is obtained from the preprocessing of the data, e.g. obtaining a data segment conforming to XML (extensible Markup Language) format from the publishing process unit of the database records in XML format. Certainly, the data segment can also come from other data sources.

The relation between template and data segment can be explained more detailed using below example. For instance, after format preprocessing, two data segments of the TV program data are obtained, and the data segment 1 is: <radioshow radioshowlD="new talk show"> <description> a new TV talk show every Friday </description> <start_time>7pm</start_time> <end_time>8pm</end_time> <party><host>Mr.XYZ</host><participant>Mr.ABC</participant></party>

</radioshow>

Data segment 2 is:

<radioshow radioshowlD="News report"> <description> news report every evening </description>

<start_time>6pm</start_time> <end_time>7pm</end_time>

Both of above data segments have the same data structure of above template, and the difference between them is each the data segments includes different valid content, e.g. "new talk show", a new TV talk show every Friday, etc in the data segment 1 , "News report", news report every evening, etc in the data segment 2.

Next, sequentially compress data segment according to the obtained compressing parameters (step S450). Because the compressing parameters include the compressing information of the template with the same data structure and the information of the storage address and length, etc., the character of sequentially compressing can automatically search the character strings have shown up when sequentially compressing the data segment according to the compressing parameters and can automatically output the character strings' appearing position and length in template. Therefore, sequentially encoding principle can automatically replace the same part of data segment and compressed template to storage address and length, the storage address points to the compressed template and the size of the data segment after replacing is much less than that of the original data segment. Since data segment is sequentially compressed with the compressing parameters generated during the process of compressing the template and the compressed template may be discarded, the compressing ratio of the data segment can be greatly improved.

Last, store the compressed data segment (step S460). The storing place of the compressed data segment and the compressed template is different for not affecting the compressing ratio, e.g. storing them with different file names.

Above embodiment finishes the compressing for one data segment, in many cases, it is needed to sequentially compress several data segments with the same template. For example, it may compress 20 TV program data (that is, 20 data segments) in turn, and these TV program data have same or similar data structure after preprocessing. After compressing a data segment according to above process S460, the next data segment can be compressed sequentially according to above process. It should be noted that, in the beginning of every process, the encoding state should be initiated, e.g. cleaning all the compressing parameters in the compressing device to make sure that the compressing parameters will not affect the next process when the current process end since when current process ends the parameters have already included some compressing parameters corresponding to the valid content in the data segment.

Figure 5 is a structure schematic block diagram illustrating an apparatus for sequentially decompressing a compressed data segment according to an embodiment of the present invention. The compressed data segment is obtained from apparatus 300, and the data segment has said data structure. Apparatus 500 includes an obtaining device 510 and a decompressing device 520. Apparatus 500 can also include a storage device 540 and a discarding device 550.

The obtaining device 510 is used to obtain several decompressing parameters. These decompressing parameters indicate the decompressing information of the compressed template, including the information such as decompressing style, storage position and data structure, etc of the template. These compressing parameters may come from storage device

540. The decompressed parameters correspond to the internal state of the decompressing device 520 after decompressing the compressed template.

The decompressing device 520 is used to sequentially decompress the compressed data segment according to the obtained decompressing parameters and thereby gets a decompressed data segment. If the decompressing parameters cannot be obtained directly from the obtaining device 510, the decompressing device 520 can also used to sequentially decompress a compressed template to get a decompressed template and said decompressing parameters, and the template has the said data structure.

Storage device 540 is used to store the decompressed data segments and also to store the said decompressing parameters.

Discarding device 550 is used to discard the decompressed template.

The running process of apparatus 500 is described in Figure 6 below. Figure 6 is a flow chart of sequentially decompressing a compressed data segment according to an embodiment of the present invention. The compressed data segment is generated by the process of Figure 4 and the data segment has said data structure.

Firstly, obtain a compressed template (step S610), and the template has said data structure. The compressed template is obtained from a storage device and may also transferred from the network or other device. The compressed template can also be obtained by sequentially compressing a template with the said data structure.

Then, sequentially decompress the compressed template (step S620). More particularly, after initiating the decoding state, the compressed template is sequentially decompressed and a decompressed template and several decompressing parameters are obtained. These decompressing parameters can be used to decompress the following data segments to be decompressed and include the decompressing information of the compressed template comprising the information such as the decompressing style, address and data structure, etc. The sequentially decompressing can use Zlib sequentially decompressing principle. To store the storage space, the decompressed template can be discarded (step S630), and the discarding can be implemented by the file ending tag of the template.

Above steps S610-S630 are procedures of sequentially decompressing the compressed template and thereby obtaining the decompressing parameters. These decompressing parameters can be stored, for example, to a local storage device, and used to sequentially decompress another compressed data segments, which have the same or similar data structure. In the case, if the decompressing parameters have been stored in a local storage device, the above steps S410-S430 can be skipped when decompressing another compressed data segment, that is, the decompressing parameters can be obtained directly from the storage device without decompressing a compressed template. It should be noted that, before directly obtaining the decompressing parameters from the storage device, the encoding state should be initiated firstly to make sure the current process is not affected by the decompressing parameters at the end of the previous process.

Next, obtain a compressed data segment (step S640). The compressed data segment can be obtained from a storage device or transferred from network or other devices.

Subsequently, sequentially decompress the compressed data segments (step S650), and the sequentially decompressing can use Zlib sequentially decompressing principle. Find the corresponding replacement information according to the obtained decompressing parameters and storage address in the compressed data segment and replace the decompressed data segment with the replacement information, then get a completed decompressed data segment. The decompressed data segment has said data structure and includes the specific valid content.

Last, store the decompressed data segment (step S660).

Above decompressing process completes the decompressing of a compressed data segment, and in many cases, it needs to sequentially decompress many compressed data segments in turn, which have same/ similar data structure. After decompressing a compressed data segment using above process S660, the next compressed data segment can be decompressed sequentially using above process. It should be noted that, in the beginning of each process, the encoding state should be initiated; for example, cleaning all the decompressing parameters in the compressing device to make sure next process is not affected by the decompressing parameters at the end of current process since the parameters at the end of current process include some decompressing parameters corresponding to the valid content in the data segment.

The method of sequentially compressing/decompressing data in above embodiment mainly transfers the data to data segments with the same data structure by preprocessing and at the same time, gets a template constructing the data segments for compressing/decompressing data. The method obtains the compressing parameters needed for the compressing of data segments with the same data structure by compressing a template with a data structure and sequentially compresses the data segments according the parameters and discards the compressed template, thus gets data segments with high compressing ratio. Meanwhile, because each data segment is separately sequentially compressed, it may randomly access each data segment. Correspondingly, the method obtains the compressing parameters needed for the decompressing of compressed data segments by decompressing a compressed template, the data segment has the same data structure with the template, decompresses the compressed data segments according to the parameters and thus gets a decompressed data segment. Meanwhile, since each data segment is separately sequentially compressed, it may decompress each compressed data segment separately.

The experiment results below can further show the advantage of the compressing ratio of the present invention comparing to the technologies in the prior art. The experiment is based on the compressing ratio of the data segments using the technology described in Figure 2, and when sequentially compressing the same data segments, the compressing ratio is improved 38.4% using the present invention. All these methods use Zlib as the sequentially compressing/decompressing principle. The two results are described in below table.

Table 1: experiment results

While this invention has been described in terms of preferred embodiments, it will be apparent to those of skilled in the art that substitutes, modification and changes can be applied to the processes described herein. Therefore, all such substitutes, modifications and changes are deemed to be within the scope and concept of the invention as it is set out in the following claims.

Claims

What is claimed is :

1. A method for sequentially compressing a data segment with a data structure, comprising: a. Obtaining a plurality of compression parameters; b. Sequentially compressing said data segment according to the obtained compression parameters thereby to get a compressed data segment.

2. The method of Claim 1 , wherein the step a is: sequentially compressing a template with said data structure thereby obtaining said compression parameters.

3. The method of Claim 2, wherein step a further comprises: obtaining a compressed template.

4. The method of Claim 3, further comprising: discarding said compressed template.

5. The method of Claim 3, further comprising: storing said compressed template and compressed data segment respectively.

6. The method of Claim 1 , wherein said compression parameters in step a come from a storage device.

7. The method of Claim 1 , further comprising: preprocessing data and thereby obtaining said data segment.

8. The method of Claim 1 , further comprising: storing said compressed data segment.

9. A method for sequentially decompressing a compressed data segment with a data structure, comprising: a. Obtaining a plurality of decompressing parameters; b. Sequentially decompressing said compressed data segment according to the obtained decompression parameter and thereby obtaining a decompressed data segment.

10. The method of Claim 9, wherein the step a is: sequentially decompressing a compressed template with said data structure, and thereby obtaining said decompression parameters.

11. The method of Claim 10, further comprising: sequentially compressing a template with said data structure and thereby obtaining said compressed template.

12. The method of Claim 11 , said compressed template is obtained from a storage device.

13. The method of Claim 10, wherein the step a further comprising: obtaining a decompressed template.

14. The method of Claim 13, further comprising: discarding said decompressed template.

15. The method of Claim 10, further comprising: storing said decompressed data segment.

16. The method of Claim 9, said decompressing parameters is obtained from a storage device.

17. An apparatus for sequentially compressing data segment with a data structure, comprising: obtaining means for obtaining a plurality of compression parameters; compressing means for sequentially compressing said data segment according to the obtained compression parameters thereby obtaining a compressed data segment.

18. The apparatus of claim 17, further comprising: preprocessing means for preprocessing data thereby obtaining said data segment.

19. The apparatus of claim 17, further comprising: storing means for storing said compression parameters.

20. The apparatus of claim 17, wherein said compressing means can also be used for: sequentially compressing a template with said data structure thereby obtaining said compression parameters and compressed template.

21. The apparatus of claim 20, further comprising: discarding means for discarding said compressed template.

22. An apparatus for sequentially decompressing a compressed data segment with a data structure, comprising: obtaining means for obtaining a plurality decompression parameters; decompressing means for sequentially decompressing said compressed data segment according to the obtained decompressing parameters thereby obtaining a decompressed data segment.

23. The apparatus of Claim 22, further comprising: storing means for storing said decompression parameters.

24. The apparatus of Claim 22, wherein said decompressing means can also be used for: sequentially decompressing a compressed template thereby obtaining said decompressing parameters and decompressed template with said data structure. The apparatus of Claim 24, further comprising: discarding means for discarding said decompressed template.