Encoding/decoding apparatus, method and computer program

The present invention relates to an information processing technique for encoding and decoding XML data.

Since structured documents such as XML documents and HTML documents are in text format, processing apparatuses that analyze these structured documents have largely performed reading/writing, saving and the like of the structured documents in text format. However, since structured documents include redundant data, it takes time for a computer to read/write a structured document as text data. Therefore, a technology has been developed in recent years called binary XML that reduces data size by representing/processing structured documents in binary data format. Note that XML stands for eXtensible Markup Language, while HTML stands for HyperText Markup Language.

With Fast Infoset developed by Sun Microsystems, for example, vocabularies such as element names and attribute names included in the XML data are encoded by being allocated numbers in the order in which they appear in XML data. This enables the size of XML data to be reduced. A table showing the correspondence between the codes and vocabularies is called an encoding table. Note that Fast Infoset is discussed in detailed at the page reached by the following link:

Where there is an array of numeric values partitioned by separators such as commas and spaces in the attribute values and element content, XEUS, developed by KDDI partitions the XML data with the separators and encodes the numeric values, rather than encoding the entire data as a character string. This enables XML data to be efficiently compressed. Note that XEUS stands for XML document Encoding with Uniformed Sheet.

With the configuration disclosed in Japanese Patent Laid-Open No. 2005-215951 and in BiM developed by MPEG, type information of data included in XHTML and SVG schemas which define the grammar (document structure) of structured documents is analyzed, and optimal encodings for the data type of the attribute values and element content are performed. This enables XML data to be efficiently compressed. Note that MPEG stands for Moving Picture Experts Group. BiM stands for Binary MPEG format for XML. Technical information on BiM can be acquired from the following link:

SVG stands for Scalable Vector Graphics. XHTML stands for Extensible HyperText Markup Language.

However, the schemas of XHTML, SVG and the like used with conventional technology define the generic grammar (document structure) of a structured document. Therefore, because conventional technology uses schema information defining the generic grammar of a structured document, application-specific document structure is not encoded, even when XML data of the same document structure appears repeatedly.

For example, assume there is a structured document written in SVG such as that in FIG. 1A . FIG. 1A illustrates a structured document in which the same document structure appears repeatedly. In FIG. 1A , reference numerals 9101 to 9103 have the same document structure, only the variables such as the attribute values and character strings are different. In this structured document, an empty element called “circle” has a plurality of attribute values cx, cy, r, fill, stroke, and stroke-width. A “text” element appears after this “circle” element. The “text” element has a plurality of attribute values x, y, and font-size, and includes a character string as element content. The “circle” elements and “text” elements included in this structured document are assumed to represent buttons, as shown by reference numeral 9104 in FIG. 1B .

With conventional binary XML technology, an encoding table such as in FIG. 2 is generated and a structured document such as shown in FIGS. 3 and 4 is encoded by analyzing the datatypes of the attribute values in the “circle” elements using SVG schema, and performing encoding for those datatypes. However, as with the button objects in FIG. 1A , there is a limit to the reduction in data size, since codes are not allocated to application-specific document structure that appears repeatedly.

FIG. 2 illustrates an encoding table generated using conventional binary XML technology. FIGS. 3 and 4 illustrate an encoded document encoded using conventional binary XML technology. With the conventional configuration, a code is allocated for every element name and attribute name, as in FIGS. 2 to 4 , despite the same document structure being repeatedly used in the structured document for encoding, as in FIG. 1A . Therefore, there is still room for further reductions in the data size of an encoded document generated using conventional encoding methods.

The present invention has been made in consideration of the above problems, and has as its object to provide a technique that enables a structured document to be encoded at an even smaller data size.

According to one aspect of the present invention, an information processing apparatus comprises:

a readout unit adapted to read out, from a storage unit, correspondence information that includes a document structure of a structured document and a first code for encoding the document structure;

a verification unit adapted to verify whether grammar of a portion included in a structured document for processing is valid, based on the document structure included in the correspondence information; and

an encoding unit adapted to encode the structured document using the first code, in relation to a portion whose grammar is verified as being valid by the verification unit.

According to another aspect of the present invention, a control method of an information processing apparatus that generates an encoded document by encoding a structured document, comprises the steps of:

a readout unit reading out, from a storage unit, correspondence information that includes a document structure of a structured document and a first code for encoding the document structure;

a verification unit verifying whether grammar of a portion included in a structured document for processing is valid, based on the document structure included in the correspondence information; and

an encoding unit encoding the structured document using the first code, in relation to a portion whose grammar is verified as being valid in the verification step.

Further features of the present invention will become apparent from the following description of exemplary embodiments (with reference to the attached drawings).

FIGS. 1A & 1B illustrate a structured document in which the same document structure appears repeatedly.

FIG. 2 illustrates an encoding table generated using conventional binary XML technology.

FIGS. 3 & 4 illustrate an encoded document encoded using conventional binary XML technology.

FIG. 5 is a configuration diagram showing an overview of a system that includes an information processing apparatus.

FIG. 6 is a block diagram showing the configuration of a PC.

FIG. 7 shows a schema written in RELAX NG in relation to XML data in which the same document structure appears repeatedly.

FIG. 8 shows an example in which a textfield object for accepting text inputs from a user is defined in addition to a button object.

FIGS. 9A and 9B are flowcharts showing processing procedures for encoding a document structure.

FIG. 10 is a flowchart showing in detail the processing procedures executed in step S 103 .

FIG. 11 shows a vocabulary generated based on the schema of a button object.

FIG. 12 illustrates an encoding table.

FIG. 13 is a flowchart showing processing procedures for verifying whether XML data is a content model that appears repeatedly.

FIG. 14 illustrates an encoding table after a series of encoding processes has been performed.

FIGS. 15 , 16 & 17 illustrate an encoded document stored in an internal memory after the series of encoding processes has been performed.

FIG. 18 is a flowchart showing processing procedures for decoding an encoded document.

Hereinafter, an exemplary configuration of an encoding apparatus (information processing apparatus) and a decoding apparatus according to the present embodiment will be described with reference to the accompanying drawings. In the interests of simplicity, it will be illustratively assumed in the present embodiment that the encoding apparatus and the decoding apparatus are realized by the same information processing apparatus, although the encoding and decoding apparatuses may be realized by separate apparatuses. The constituent elements described in this embodiment are merely illustrative, and it is not intended to limit the scope of the invention to only these constituent elements.

Configuration of Information Processing Apparatus

FIG. 5 is a configuration diagram showing an overview of a system that includes an information processing apparatus according to the present embodiment. In FIG. 5 , a personal computer (PC) 101 , as an information processing apparatus according to the present embodiment, is connected to a local area network (LAN) 102 . A digital camera 103 , a printer 104 and a fileserver 105 are also connected to the LAN 102 .

FIG. 6 is a block diagram showing the configuration of the PC 101 , as an information processing apparatus according to the present embodiment. In FIG. 6 , a CPU 201 is a system control unit that controls the entire apparatus. A ROM 202 is a storage apparatus that stores the control programs of the CPU and various fixed data. The RAM 203 , constituted by an SRAM, DRAM or the like, is a storage apparatus for storing program control variables and the like. Various setting parameters and work buffers are also stored in the RAM 203 . A storage unit 204 , constituted by a hard disk or the like, is a storage apparatus for storing various data files containing document data, image data and the like. An operation unit 205 , constituted by a keyboard, mouse, touch panel or the like, is an instruction input apparatus for an operator to perform various input operations. A display unit 206 is a display apparatus such as a television that displays images. A LAN i/f 207 is an interface for connecting to a LAN line 208 . A USB i/f 209 is an interface for connecting to a USB line 210 .

Note that although it is assumed in the present embodiment that the information processing apparatus according to the present embodiment is realized by a PC, the present invention is not limited to this configuration. For example, the information processing apparatus according to the present embodiment may be realized by a workstation (WS), a personal digital assistant (PDA), or the like.

Also, in the interests of convenience, the present embodiment describes a configuration in which the information processing apparatus according to the present embodiment is realized by a single apparatus. However, the information processing apparatus according to the present embodiment may be realized by a configuration in which resources are distributed to a plurality of apparatuses. For example, storage and computation resources may be distributed to a plurality of apparatuses. Alternatively, resources may be distributed for each constituent element realized virtually on the information processing apparatus, and processing performed in parallel.

Hereinafter, a method of reducing data size by encoding the actual document structure will be described in relation to a structured document in which the same document structure appears repeatedly, as with the button objects 9101 to 9103 in FIG. 1A . Note that although it is assumed in the present embodiment that processing is performed on XML data as an exemplary structured document, the present invention is not limited to this configuration.

Schema

FIG. 7 shows a schema written in RELAX NG (REgular LAnguage for XML Next Generation) in relation to XML data in which the same document structure appears repeatedly, which is exemplified in FIG. 1A . This schema needs to be created prior to encoding, based on the document structure of the structured document. The information processing apparatus (PC 101 ) according to the present embodiment encodes a structured document that includes a document structure appearing repeatedly, based on this schema.

The schema illustrated in FIG. 7 defines the schema of a “circle” element and a “text” element constituting a single button object in 701 and 702 respectively, using a “define” element in RELAX NG. These “circle” and “text” elements are defined using an “element” element in RELAX NG ( 703 , 704 ). The attributes of the “circle” and “text” elements are defined using an “attribute” element in RELAX NG. Here, the datatype of the attribute values of the attributes cx, cy, r and stroke-width included in the “circle” element is defined as “double” ( 705 - 708 ), while the datatype of the attribute values of the attributes fill and stroke is defined as “string” ( 709 , 710 ). The various datatypes are defined in the W3C recommendation “XML Schema Part 2: Datatypes Second Edition” (http://www.w3.org/TR/2004/REC-xmlschema-2-20041028/datatypes.html). The datatype of the attribute values of the attributes x, y and font-size included in the “text” element is defined as “double” ( 711 - 713 ). Note that in the present embodiment data such as attribute values and element content are collectively referred to as variables.

If there are objects other than the button object composed of the “circle” and “text” elements, the schema of these objects are defined as the subelements of different “define” elements. FIG. 8 shows an example in which a textfield object for accepting text inputs from a user is defined in addition to the above button object. In FIG. 8 , reference numeral 801 shows the object definition of the textfield. As shown in FIG. 8 , a plurality of repeatedly occurring document structures of objects can be defined by providing any number of “define” elements.

Here, RELAX NG is described as an example of a schema language in the present embodiment, although other schema languages may be used such as DTD and XML Schema (W3C XML Schema). Alternatively, shorthand for schema may be used (http://www.oasis-open.org/committees/relax-ng/compact-20021121.html)

Encoding Structured Documents

Next, procedures performed by the PC 101 in relation to a structured document in which the same document structure appears repeatedly to encode the actual document structure will be described with reference to FIGS. 9 A and 9 B. FIGS. 9A and 9B are flowcharts showing processing procedures for encoding a document structure. The following processing is executed under the control of the CPU 201 , included in the PC 101 , which is an information processing apparatus according to the present embodiment.

When the processing is started in step S 101 , firstly the schema for processing as illustrated in FIG. 7 is read out from the storage unit 204 or the like, analyzed, and stored in an internal memory (step S 102 ).

Next, a content model appearing repeatedly is encoded using the data of the schema stored in the internal memory (step S 103 ). Step S 103 will now be described in detail with reference to FIG. 10 . FIG. 10 is a flowchart showing in detail the processing procedures executed in step S 103 .

When processing (step S 103 ) is started in step S 201 , firstly, in relation to the schema stored in the internal memory, the schema below each “define” element that defines a content model appearing repeatedly is analyzed (step S 202 ). Next, the schema below the “define” element is stored in the internal memory as a vocabulary in an encoding table (step S 203 ). FIG. 11 shows a vocabulary generated based on the schema of the button object illustrated in FIG. 7 . As shown in FIG. 11 , the content of the schema below the “define” element defining the button object corresponds to a vocabulary.

Next, the vocabulary generated in step S 203 is added to the encoding table (step S 204 ). That is, in steps S 202 to S 204 , schema information showing the document structure of the structured document is analyzed, codes are allocated to the document structure, and the encoding table is updated based on the correspondence relation between the document structure and the codes. Respective codes are assigned to the partial document structures (in the present embodiment, partial document structures starting with <define> and ending with </define>) included in the schema. Note that in step S 204 a start flag and an end flag of the content model appearing repeatedly are added to the encoding table. The start flag indicates the start of the vocabulary of the document structure appearing repeatedly, while the end flag indicates the end of the vocabulary of the document structure appearing repeatedly. That is, the start flag and the end flag function as a third code for encoding a valid range in comparison with a predefined document structure. These start and end flags are also used as a code indicating the start and end with respect to other document structures that appear repeatedly.

The above procedures are performed for each “define” element of the schema stored in the internal memory. That is, when the processing of step S 204 ends, it is determined in step S 205 whether the processing of steps S 202 to S 204 has been completed for all “define” elements. If all “define” elements have been processed (YES in step S 205 ), step S 103 is ended. If all “define” elements have not been processed (NO in step S 205 ), the processing returns to step S 202 , and the processing of steps S 202 to S 204 is executed for a “define” element not yet processed.

FIG. 12 illustrates an encoding table after the end of step S 103 . A code 0x05 stores the start flag of the content model appearing repeatedly as vocabulary ( 1201 ), and a code 0x06 stores the end flag of the content model appearing repeatedly as vocabulary ( 1202 ). A code 0x07 stores the vocabulary of FIG. 11 ( 1203 ). If there are other content models that appear repeatedly, the schema of those content models is added as vocabulary from the subsequent code 0x08. As in FIG. 12 , the encoding table functions as correspondence information that includes the document structure of the structured document and a first code for encoding the document structure. Note that the above encoding table may be created in advance and stored in the storage unit 204 or the like, and a readout unit realized by the functions of the information processing apparatus may read out the stored encoding table for use from the storage unit 204 when necessary.

Returning to the description of FIGS. 9A and 9B , when the processing of step S 103 ends, next a DOM (Document Object Model) tree is generated based on the analyzed schema information, and the generated DOM tree is saved to the internal memory after converting the structure thereof to a simple tree structure (step S 104 ). Simplified processing of the tree structure is performed based on the simplified processing procedures of the RELAX NG specifications (http://www.relaxng.org/spec-20011203.html#simplification). Each node in the schema DOM tree has a flag showing whether XML data has been verified, and these flags are initialized to an unverified state with respect to the XML data.

Next, in the processing from step S 105 , XML data is analyzed and encoded using the encoding table of FIG. 12 generated in step S 103 . The structured document encoded and stored in the internal memory is here called an encoded document. The encoded document in an initial state is assumed not to store any codes. Firstly, in step S 105 , analysis of XML data not yet analyzed is performed.

Next, it is determined whether all XML data of the structured document has been analyzed (step S 106 ). If all XML data has been analyzed (YES in step S 106 ), the processing ends. If all XML data has not been analyzed (NO in step S 106 ), the processing proceeds to step S 107 .

In step S 107 , it is verified whether the XML data is data that appears repeatedly, based on the schema stored as vocabulary in the encoding table. For example, in parsing the XML data in FIG. 1A , the XML data is verified as schema, or vocabulary, of the button object after the elements have been read and saved to the internal memory.

The procedures executed in step S 107 for verifying XML data as schema, or vocabulary, allocated to the code 0x07 of FIG. 11 will now be described in detail using FIG. 13 . FIG. 13 is a flowchart showing the processing procedures for verifying whether XML data is a content model that appears repeatedly.

When the processing is started (step S 301 ), firstly it is determined whether all nodes have been verified by checking, for each node in the schema DOM tree stored in the internal memory in step S 104 , the flag indicating whether the node has been verified as XML data (step S 302 ). If it is determined that not all nodes have been verified (step NO at S 302 ), unverified nodes in the DOM tree related to XML data are verified (step S 303 ). At this time, element name, element namespace, number of available attributes, attribute name, attribute namespace, element content datatype, and attribute value datatype are verified.

Next, in step S 304 , it is determined whether the XML data is valid with respect to unverified nodes. That is, in step S 304 , validity verification is performed to verify whether the grammar of a portion included in the XML data for processing is valid, based on the document structure shown in the encoding table. If it is determine to be valid (YES in step S 304 ), the processing proceeds to step S 305 . In step S 305 , a verified flag is set for the node of the DOM tree referred to in the verification, and the processing returns to step S 302 . The verification process is similarly repeated for all nodes with respect to subsequent XML data, and a verified flag is set if the XML data is determined to be valid. At this time, verified XML data is continuously saved to the internal memory without being released, until the verification process ends for this schema.

After the processing of steps S 303 to S 305 has thus been repeated, it is determined in step S 302 that all nodes in the schema DOM tree have been verified (YES in step S 302 ), and the processing proceeds to step S 306 . In step S 306 , it is determined that the partial XML data verified up until this point is valid, and step S 107 is ended (step S 309 ). Passing through step S 306 equates to YES in step S 107 . Consequently, once the processing of step S 107 ends, the content model that appears repeatedly is encoded in steps S 108 to S 111 . Note that the code of the content model functions as the first code.

On the other hand, if it is determined during the verification of step S 304 that XML data is invalid (NO in step S 304 ), all validated flags of the DOM tree are initialized to an unverified state in step S 307 . Next, in step S 308 , it is determined that the XML data is invalid, and the processing of step S 107 is ended (step S 309 ). Passing through step S 308 , equates to NO in step S 107 . Consequently, when the processing of step S 107 ends, the conventional encoding processes of steps S 112 to S 118 are performed using the verified XML data saved to the internal memory up until that point.

In terms of the structured document in FIG. 1A , for example, the “svg” element appears initially, so this is determined in step S 304 to be invalid (NO in step S 304 ). Therefore, the processing of steps S 112 to S 118 is performed. The processing then returns to step S 105 , and proceeds to step S 107 via step S 106 (NO in step S 106 ). In step S 107 , the “circle” element that follows the “svg” element is determined to be valid in step S 304 as a result of the verification in step S 303 (YES in step S 304 ). Therefore, in step S 305 , a verified flag is set for the nodes in the DOM tree referred to in verifying the “circle” element. Then, when the “text” element that follows is read in step S 302 , it is determined that all nodes of the DOM tree have not been validated (NO in step S 302 ). Therefore, the “text” element is verified with respect to unverified nodes in step 303 . The XML data is determined to be valid as a result of the verification, and a verified flag is similarly set for the nodes referred to in the verification process.

Since all nodes in the DOM tree are determined to have been verified when the processing of step S 302 is next executed (YES in step S 302 ), the “circle” and “text” elements are determined to be valid as constituent elements of the button objects (step S 306 ). Therefore, the determination result in step S 107 is YES, and the processing proceeds to step S 108 , where the code 0x05 in the encoding table of FIG. 11 is stored in the encoded document as the code showing the start of the content model appearing repeatedly. The code corresponding to the vocabulary (i.e., schema) used in the verification just ended is added to the encoded document (step S 109 ). In the present invention, the code of the content model that appears repeatedly is 0x07, so the code 0x07 is added to the encoded document. Next, the attribute values and element content included in the content model that appears repeatedly are analyzed and added to the encoding table, and the codes thereof are similarly added to the encoded document in order (step S 110 ). After the content model that appears repeatedly has been encoded, 0x06 is added to the encoded document as the code showing the end of the content model (step S 111 ). Here, the XML data relating to the “circle” and “text” elements just stored in the internal memory is released. Then, all XML data is analyzed in step S 105 , and it is determined in step S 106 whether the encoding has ended for all XML data.

If it cannot be determined in step S 107 , with respect to the schema (i.e., vocabulary) of the encoding table, that the XML data is a content model appearing repeatedly (NO in step S 107 ), the processing proceeds to step S 112 . In steps S 112 to S 118 , the elements of the XML data temporarily stored in the internal memory are encoded. For example, consider the case where the above “circle” element is determined in step S 304 to be valid, whereas the “text” element that follows is determined to be invalid. In this case, encoding processes are performed respectively on the “circle” element stored in the internal memory when determined to be valid, and the following “text” element determined to be invalid.

First, it is determined whether the initial data is a start tag (step S 112 ), and if it is determined to be a start tag (YES in step S 112 ), this data is encoded as a start tag (step S 113 ). If it cannot be determined in step S 112 that the initial data is a start tag (NO in step S 112 ), it is determined whether the data is an attribute (step S 114 ). If it is determined to be an attribute (YES in step S 114 ), the data is encoded as an attribute (step S 115 ). If it cannot be determined in step S 114 that the data is an attribute (NO in step S 114 ), it is determined whether the data is element content (step S 116 ). If it is determined to be element content (YES in step S 116 ), the data is encoded as element content (step S 117 ). If it is not determined in step S 116 that the data is element content (NO in step S 116 ), the data is encoded as an end tag (step S 118 ). After the encoding processes have ended, the XML data temporarily stored in the internal memory is released.

FIG. 14 illustrates the encoding table after the series of encoding processes has been performed. FIGS. 15 to 17 illustrate the encoded document stored in the internal memory after the series of encodings has been performed. The code of the content model that appears repeatedly is stored after the code 0x05 indicating the start of this content model. The codes of the attribute values and element content included in this content model are stored after the code of the content model. The code indicating the end of this content model is then stored after the set of codes of the attribute values and element content included in the content model. As described above, the structured document of FIG. 1A is encoded as shown in the encoded document of FIGS. 15 to 17 , using the codes in the encoding table shown in FIG. 14 . On comparing FIGS. 3 , 4 and 15 - 17 , it is clear that the data size of the encoded document resulting from the configuration according to the present embodiment is smaller, and that it is thus possible to encode a structured document with a smaller data size. This is because in the present embodiment a code (first code) is allocated to a content model that appears repeatedly, that is, to the document structure of a structured document that appears repeatedly, and encoding is performed using this code.

Next, the process of decoding an encoded document to obtain the original structured document will be described. FIG. 18 is a flowchart showing the processing procedures for decoding an encoded document encoded using the method according to the present embodiment.

When the processing is started (step S 401 ), firstly the encoding table included in the encoded document is analyzed and stored in the internal memory (step S 402 ). Next, a DOM tree is generated based on the schema of the content model that appears repeatedly included in the encoding table, and the generated DOM tree is saved to the internal memory (step S 403 ). That is, a DOM tree is generated based on the document structure shown by the encoding table, and the generated DOM tree is stored in a memory apparatus. Next, the encoded document is analyzed and decoded from the start thereof using the encoding table.

Next, it is determined whether the entire encoded document has been analyzed (step S 404 ), and if it is determined that the entire encoded document has not been analyzed (NO in step S 404 ), it is then determined whether the code being analyzed is the start code of the content model that appears repeatedly (step S 405 ). If it is determined that the entire encoded document has been analyzed (YES in step S 404 ), the decoding process ends (step S 410 ).

If it is determined in step S 405 that the code being analyzed is not the start code of the content model that appears repeatedly (NO in step S 405 ), the processing proceeds to step S 407 . In step S 407 , it is determined whether the code being analyzed is the end code of the content model that appears repeatedly, and if it is not the end code (NO in step S 407 ), the processing proceeds to step S 408 . In step S 408 , processing is performed to allocate a value to a node of the DOM. In steps S 407 and S 408 , values referred to by the codes are thereby allocated in order to the nodes of the attribute values and element content in the DOM of the content model and stored in the internal memory, until the end code appears.

If it is determined in step S 407 that the end code has appeared (YES in step S 407 ), the processing proceeds to step S 409 . In step S 409 , XML data is generated based on the DOM tree stored in the internal memory in steps S 407 to S 408 . XML data is generated by moving from the root node through the child nodes of the tree in order and analyzing the element names, attribute names, element content and attribute values. The generated XML data is stored in the internal memory, and the processing returns to step S 404 .

Note that if it is determined in step S 405 that the code being analyzed is the start code of the content model that appears repeatedly (YES in step S 405 ), decoding is performed in step S 406 by referring to the vocabulary of the encoding table using that code. The processing then returns to step S 404 .

If it is determined in step S 404 that the entire encoded document has been analyzed (YES in step S 404 ), processing ends.

With the configuration according to the present embodiment, as described above, if XML data of the same content model appears repeatedly in a structured document in text format, the actual document structure of the content model is encoded using a schema. Attribute values and element content included in the content model are then added after the code of the content model. This enables the data size of XML data after encoding to be reduced.

Additional Embodiments

Although the embodiments of the present invention have been detailed above, the invention can, for example, be embodied as a system, apparatus, method, program or storage medium. Specifically, the invention may be applied to a system constituted by a plurality of devices, or to an apparatus composed of a single device.

Note that the invention is also achieved by directly or indirectly supplying a program that realizes the functions of the foregoing embodiments to a system or apparatus, and reading out and executing the supplied program code with a computer of the system or apparatus.

Consequently, the technical scope of the invention also covers the actual program code installed on the computer, in order to realize the functional processing of the invention by computer. That is, the invention also covers the actual computer program for realizing the functional processing of the invention.

In this case, provided the system or apparatus has the functions of the program, the program may be executed in any form, such as an object code, a program executed by an interpreter, or script data supplied to an operating system.

Storage media for supplying the program include, for example, floppy (registered trademark) disk, hard disk, optical disk, magneto-optical disk, CD-ROM, CD-R, CD-RW, magnetic tape, nonvolatile memory card, ROM, and DVD (DVD-ROM, DVD-R).

Alternatively, it is conceivable to supply the program by connecting to a website on the Internet using the browser of a client apparatus, and downloading the computer program according to the invention or a compressed file including an auto-install function from the website to a recording medium such as a hard disk. Further, the program can be supplied by dividing the program code constituting the program according to the invention into a plurality of files and downloading the respective files from different websites. That is, a World Wide Web (WWW) server that allows a plurality of users to download program files for realizing the functional processing of the invention by computer is also covered by the invention.

The following supply mode is also conceivable. That is, the program according to the invention is firstly encrypted, stored on a storage medium such as a CD-ROM and distributed to users. Then, users that meet prescribed requirements are allowed to download decryption key information from a website via the Internet, and the program decrypted using this key information is executed and installed on a computer to realize a configuration according to the invention. Such a supply mode is possible.

Apart from the functions of the foregoing embodiments being realized by a computer executing the read program, the following modes of realizing these functions are also envisioned. That is, an operating system or the like running on a computer performs part or all of the actual processing based on instructions in the program, with the functions of the foregoing embodiments being realizable as a result of this processing.

Further, the program read out from the storage medium may also be written to a memory provided in a function expansion board inserted in a computer or a function expansion unit connected to a computer, with the functions of the foregoing embodiments being realized based on instructions in the program. That is, a CPU or the like provided in the function expansion board or the function expansion unit performs part or all of the actual processing, with the functions of the foregoing embodiments being realized as a result of this processing.

The present invention enables a technique to be provided that makes it possible encode a structured document at an even smaller data size.

While the present invention has been described with reference to exemplary embodiments, it is to be understood that the invention is not limited to the disclosed exemplary embodiments. The scope of the following claims is to be accorded the broadest interpretation so as to encompass all such modifications and equivalent structures and functions.

This application claims the benefit of Japanese Patent Application No. 2007-036808, filed Feb. 16, 2007, which is hereby incorporated by reference herein in its entirety.