Data compression apparatus, database system, data communication system, data compression method, storage medium and program transmission apparatus

• US 7,043,686 B1
• Filed: 09/26/2000
• Issued: 05/09/2006
• Est. Priority Date: 02/04/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Maruyama, Hiroshi, Uramoto, Naohiko, Tamura, Kento
• Primary Examiner(s): HUYNH, CONG LAC T
• Application Number:
  US09/670,489
• Time in Patent Office: 2,051 Days
• Field of Search: 715/513, 715/500, 717/143, 717/144, 707/101
• US Class Current: 715/242
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

It is one object of the present invention to perform data compression to encode the structure part of a document in a tree local language, such as XML or ASN.1.

A data compression apparatus for encoding data and for compressing the encoded data comprises: a grammar rule 12 for a tree local language in which data are represented by a labeled tree structure; an encoder 11 for reading a document written in the tree local language, for dividing the document into a structure part and contents, and for encoding the structure part using the grammar rule 12; and a compressor 13 for compressing the contents of the document extracted by the encoder 11, and for encoding the compressed contents.

Claims

1. A data compression apparatus for encoding data and for compressing the encoded data comprising:

a grammar storage unit for storing grammar rules for a tree local language in which data are represented by a labeled tree structure;

an encoder for reading a document written in said tree local language, for dividing said document into a structure part and contents, and for encoding said structure part using said grammar rules stored in said grammar storage unit; and

a compressor for compressing said contents of said document extracted by said encoder; and

wherein said encoder includes;

a divider for dividing a target document into a structure part and contents;

an automata constructor, for constructing pushdown automata that correspond to said grammar rules; and

an encoded data generator, for employing said pushdown automata that are constructed by said automata constructor to perform syntax analyzation of said structure part of said document that is obtained by said divider, and for generating an encoded data string for said structure part.

2. That data compression apparatus according to claim 1, wherein said encoded data generator of said encoder assigns symbols to choices resident in said pushdown automata that are constructed by said automata constructor;

and wherein said encoded data generator employs said pushdown automata to analyze said structure part of said document written in said tree local language, and outputs, at the location of the selected choices, said symbols that are assigned for said choices, so that the encoded data string for said structure part is generated.

3. The data compression apparatus according to claim 1, wherein said compressor performs compression and encoding not only for said contents of said document written in said tree local language, but also for said structure part of said document that is obtained by said encoder.

4. A database system for storing and managing data in a storage unit comprising:

a grammar storage unit for storing grammar rules for a tree local language in which data are represented by a labeled tree structure;

an encoder for reading a document written in said tree local language, for dividing said document into a structure part and contents, and for encoding said structure part using said grammar rules stored in said grammar storage unit;

a compressor for compressing said contents of said document extracted by said encoder and for encoding the compressed contents; and

a storage unit for storing said structure part of said document encoded by said encoder, and for storing said contents of said document that are compressed and encoded by said compressor; and

wherein said encoder includes;

a divider for dividing said document into said structure part and contents;

an automata constructor, for constructing pushdown automata that correspond to said grammar rules; and

an encoded data generator, for employing said pushdown automata that are constructed by said automata constructor to perform syntax analyzation of said structure part of said document that is obtained by said divider, and for generating an encoded data string for said structure part.

5. The database system according to claim 4, wherein said compressor performs compression and encoding not only for said contents of said document written in said tree local language, but also for said structure part of said document that is obtained by said encoder.

6. A data compression method for encoding data and for compressing the encoded data comprising the steps of:

reading a document written in a tree local language in which data are represented by a labeled tree structure, and dividing said document into a structure part and contents;

encoding said structure part using grammar rules for said tree local language; and

compressing said contents of said document extracted by said encoder; and

wherein said step of encoding said structure part of said document includes the steps of;

constructing pushdown automata that correspond to said grammar rules;

assigning symbols to choices resident in said pushdown automata;

employing said pushdown automata to analyze said structure part of said document in accordance with the depth-first searching, and to output, at the locations of said choices, said symbols that are assigned to said choices; and

outputting a symbol string that is obtained by employing said pushdown automata as encoded data strings of said structure part of said document that is written in said tree local language.

7. The data compression method according to claim 6, further comprising:

a step, to be performed before said step of encoding said structure part of said document written in said tree local language and when an attribute belongs to a node of a target document in said tree local language, of changing said attribute to a child node of an element possessing said attribute so as to convert said grammar rules of said tree local language and said document into a tree structure that is to be processed by said pushdown automata.

8. The data compression method according to claim 6, further comprising:

a step, to be performed after said step of encoding said structure part of said document, of employing another general-purpose compression method to further compress said encoded structure part of said document.

9. A storage medium on which input means of a computer stores a computer-readable program, said program permitting said computer to perform:

a process for reading a document written in a tree local language in which data are represented by a labeled tree structure, and for dividing said document into a structure part and contents;

a process for encoding said structure part using said grammar rules of said tree local language; and

a process for compressing said contents of said document extracted by said encoder; and

wherein the process for encoding said structure part includes;

an automatic constructing process, for constructing pushdown automata that correspond to said grammar rules; and

an encoded data generator process for employing said pushdown automata that are constructed by said automata constructing process to perform syntax analyzation of said structure part of said document and for generating an encoded data string for said structure part.

10. A program transmission apparatus comprising:

storage means for storing a program that permits a computer to perform

a process for reading a document written in a tree local language in which data are represented by a labeled tree structure, and for dividing said document into a structure part and contents,

a process for encoding said structure part using said grammar rules for said tree local language, and

a process for compressing said contents of said document extracted by said encoder; and

transmission means for reading said program from said storage means, and for transmitting said program; and

wherein the process for encoding said structure part includes;

an automata constructing process, for constructing pushdown automata that correspond to said grammar rules; and

an encoded data generator process for employing said pushdown automata that are constructed by said automata constructing process to perform syntax analyzation of said structure part of said document and for generating an encoded data string for said structure part.