Method for improving the functionality of the binary representation of MPEG-7 and other XML-based content descriptions

The present invention relates to coding and decoding of XML-based structured documents such as MPEG-7. XML (extensible markup language) is a standard for defining document structures and is used to display structured data in text files, which is the basis of XHTML, for example. Such XML-based documents are based on a number of structuring elements, also referred to below as schemas, which use, for example, a document type definition (DTD), XML schema, or multimedia description schema (DS). Can be specified.

ISO / IEC CD 15938-1 Information Technology Draft-Multimedia Content Description Interface: System, ISO / IEC JTC 1 SC29 / WG11 / N3701, La Baule (France), 10. 2000, especially by pages 15-22 The structure of the navigation path using the binary format of the MPEG-7 data file and the tree branch code table is known.

<p num="0003"><nplcit num="1"><text>SO / IEC CD 15938-1 Information Technology draft</text></nplcit></p>

<p num="0004"> The present invention relates to optimizing the coding of structured XML documents. The underlying problem of the present invention is to reduce the amount of data to be transmitted as much as possible in a method for improving the binary representation function of XML-based content description such as an MPEG-7 document, and to perform a search process in the document. To make it as simple as possible, and to make it possible to extend instantiated documents that are not included in individual schema templates with as little effort as possible.</p>

<p num="0005"> According to the present invention, the problem is that the structure of the instantiated XML document corresponds to a tree-like data structure, and each tree node forms one element of the content description and has a structure defined in the schema. The schema has a tree node with a tree branch code, the tree branch code has a schema branch code, the decoder skips paths with unknown elements, and individual<u style="single">unknown</u>The number of bits in the tree structure located after the element as well<u style="single">Of the tree structure located behind the unknown element</u>The content is transmitted and the decoder jumps over the number of bits, or transmits a unique synchronization sequence after transmitting a path with a new element, and the decoder restarts only when it reaches a tree node belonging to a known schema. It is solved by a method of improving the binary representation function of XML-based content description, which is characterized by being<u style="single">。</u></p><p num="0006"> The ISO / IEC draft mentioned above specifically shows that the structure of an XML document can be interpreted as a data tree, and each element of the description corresponds to a node in this tree. The structure of a node is defined by the definitions in the schema that underlies the document. This defines, for example, the type and number of child elements. Prototypes of this type of node are described, for example, on page 19 of this draft. Such a tree structure node consists of the name of the element or compound, the field with the codeword TBC (Tree Branch Code) used to refer to the child element, and the tree branch that makes a reference to the corresponding child element. Become. In addition, the draft document shows that the TBC is divided into two components: the schema branch and the position information, while the schema information is derived from the elements that appear as child elements in the schema. , Position information has position information for elements that may appear many times. Here, the type of child element that can be considered is a complex type Complex that can also contain child elements. An element or attribute of a simple type that cannot contain an element of Type or a child element. The length of field #postion is specified by the maximum number of applicable elements ("maxOccurs") specified in the schema. For example, if the maximum number is greater than or is not limited to 7, the field is adaptively stretched until it can represent the position to be coded. Such a split has the property that the schema branch code or SBC "SchemaBranchCode" always remains the same, regardless of how many children exist or can exist in the current instantiation.</p><p num="0007"> The TBC or SchemaBranchCode and, in some cases, the position code are juxtaposed for the purpose of navigating within the document, which represents the path within the document. When you reach the desired element, the last code is inserted into the table. If the desired element does not have yet another child, that is, if it is an attribute or a simple type, then this termination code is unnecessary and will not be sent. In this case, the attribute or simple type element is still coded and transmitted.</p><p num="0008"> Next, the present invention will be described in detail based on examples with reference to the drawings.</p>

<figref num="1">A to D are diagrams showing the addressing of various element types to explain the compression improvement.</figref><figref num="2">Diagram showing XML schema text</figref><figref num="2A">Diagram showing a node table that belongs to the schema text</figref><figref num="2B">Diagram showing a node table that belongs to the schema text</figref><figref num="3A">The figure explaining the improvement of the search method by this invention.</figref><figref num="3B">The figure explaining the improvement of the search method by this invention.</figref><figref num="4A">Diagram showing an excerpt of a data stream to illustrate improvements in scalability</figref><figref num="4B">Diagram showing an excerpt of a data stream to illustrate improvements in scalability</figref><figref num="5A">Diagram showing an extended tree branch node to illustrate the improved extensibility</figref><figref num="5B">Diagram showing an extended tree branch node to illustrate the improved extensibility</figref><figref num="6A">Similar to Figure 2 and Figure 2B, but with expanded elements</figref><figref num="6B">Similar to Figure 2 and Figure 2B, but with expanded elements</figref><figref num="7">Diagram showing a sequence for a decoder to jump over unknown elements</figref><figref num="8">Diagram showing a sequence for a decoder to jump over unknown elements</figref>

The present invention is basically configured as follows. That is, two different schema branch codes are used, one of which is used quite often, so compression is applied, the schema branch code and position code are grouped together, and a bit for the schema branch code. The length is transmitted together. In this case, the type of the referenced element is specified only by the first part, and the scalability improvement is realized based on the schema version number to be transmitted and the fixed extension strategy known to the decoder. To.

Improved compression Figure 1A shows the traditional addressing of simple type elements or attributes, and Figure 1B shows the traditional addressing of complex type elements, which corresponds to known methods. It is a thing. FIGS. 1C and 1D show a corresponding addressing method according to the method of the present invention. As is clear from this figure, two different schema branch codes SBC-A and SBC-B are used, not just the common schema branch code SBC-B. As mentioned at the beginning, this kind of address path consists of concatenated TBC code, which means that there is a position code #pos between each schema branch code SBC-A if necessary, only at the end. A schema branch code with a pastorization code is provided, which is not accompanied by further position information, followed by a common schema branch code SBC-B, which is a simple type or a tree-structured leaf. Attribute elements may also be included.

Only the last TBC in the path can reference an attribute or simple type element, as can be seen from the above-mentioned structure of the path consisting of the concatenated TBC code. All preceding TBCs must reference composite elements because only they can have child elements. Therefore, in the case of the method according to the present invention, two for the schema branch code #SchemaBranchCode for each node for the purpose of reducing the length of the positioning code in the document from the ISO / IEC draft document mentioned at the beginning. A different table is introduced. Table A contains only complex type elements, that is, only elements that can have child elements. The other table contains all the elements, that is, the attributes and simple type elements. However, there is no need to reserve an SBC for pastormination here. The schema branch codes for both of these tables are referred to below as SBC-A or SBC-B. The entire path is also formed by the concatenation of TBCs, with the exception of SBC-A and possibly the last TBC with the corresponding position code # position-code. The end of the first part of the path created using table A is signaled by a termination code, eg, all bits 1. After that, there is always a TBC with the schema branch code #SchemaBranchCode read from table B. It should be noted here that when an attribute or simple type element is addressed, the termination code must also be transmitted in the method according to the invention. The length of the schema branch code depends on the number of possible elements, so the code in table A, or code SBC-A, is shortened accordingly. The fact that code SBC-A is used much more frequently than code SBC-B also has a positive effect on compression.

Figure 2 shows an example of XML Schema text, and Figures 2A and 2B show the corresponding node tables for SBC-A and SBC-B. As you can see from this figure, the schema branch code can be shortened for SBC-A. That's because we don't need to refer to simple type elements and attributes here.

Improved search function A feature required for binary representation but not constrained by the ISO / IEC draft method is a simplified search for a given element in a document. This search can be optimally performed by a simple filter mechanism as follows, which uniquely addresses the searched elements in the document and patterns a pre-determined bitstream in the bitstream. It is done by searching by comparison. When quickly searching for a given element in the document tree, the bitstream is parsed and only the elements mentioned for the proper path fragment are considered in detail. For the methods described in the ISO / IEC draft, this type of filtering is not feasible without restrictions. The reason is that the length of the position code #PositionCode cannot be pre-determined unless the maximum number of at least one element in the schema in this case is greater than or limited to 7.

Therefore, in the case of the method according to the present invention, the tree branch node (TBC) that describes the path is partially re-sorted for the purpose of simple filtering of the bitstream. At that time, the position code is shifted to the end of the path. The advantage of this is that the first part of the path containing the schema branch fragment #SchemaBranchFragment specifies only the type of the referenced element.

According to the alternative solution method, in the first step, the position code #PositionCode is divided into a fixed length part and a variable length part. In the second step, the variable length portion is removed from the TBC and shifted to the end of the path.

As a result, in the case of an absolute address, a bit pattern can already be determined in advance for searching for a predetermined element. When using relative addresses, the pattern depends on the current position in the document. In this case, a new method simplifies it, eliminating the need to decode and evaluate the position code #PositionCode for filtering.

For a complete reference, you need to read and decode the entire path, including the complete position code #PositionCode, so that you can properly branch to the referenced child elements on a node-by-node basis.

For the purpose of simplifying the implementation of this method, information about the overall length L of the path can be typically transmitted in bits at the beginning of the path without the position code being followed, which allows the position code to be transmitted in this way. The pointer Z to is also sent together, so the proper position can be decoded in parallel to the SBC. This additionally enables a search for a specific position (#position) for the element being searched, even for the extensibility cases described below where part of the path is not known to each decoder. Is supported.

Figure 3A shows this relationship as an example of addressing a simple element or attribute in the traditional way. FIG. 3B shows the same with respect to the method according to the invention. As can be seen from Figure 3B, all the schema branch codes SBC-B1 to SBC-B5 in each one path are arranged one after the other, which has a length L as a whole, and this length. L is first transmitted immediately after the start. Position codes # pos1 to # pos5 are separated from SBC and are arranged one after the other. From this schema pattern definition, a bit pattern for absolute addressing having a bit length L can be obtained, and therefore bit stream filtering becomes possible by pattern comparison.

Improved extensibility The coding scheme based on the ISO / IEC draft algorithm is context-dependent, meaning that each element is coded with only another possibility determined by the context. The decoder can read the bit pattern and interpret it properly only if it knows the schema definition. The decoder must know which TBC code references which element, and how long the bit code in each element is, the purpose of which is to read the correct number of bits for each path fragment. To do so.

In practice, it is common to later extend a defined schema to consider new boundary conditions, such as new metadata categories. Such extensions can be optional elements or attributes. Documents created according to the old schema definition and retained in the XML text form are still valid for the new definition (upward compatible). However, they may be derived data types by inheritance, holding TBC in the case of constraints (driven by restriction), or extended in the case of extensions (derived by extension) as described below. Holds the TBC table.

However, this is not the case, for example, in the case of a binary representation of a document as shown in the ISO / IEC draft. This is because there may be a new element / attribute assigned to a TBC that has previously addressed another element / attribute. With the method according to the present invention, this drawback can be avoided by the following rules.

According to the method according to the invention, new optional elements can only be inserted after an existing one in a Tree Structure Node (TSN), and in some cases only before an existing Path Termination Code. Can be inserted. Here, the new element is assigned a previously unused schema branch code SBC, while the existing element does not lose its schema branch code assignment.

If the extension results in addressing with longer addresses, then all binary representations can no longer be decoded due to changes in code length. In order to solve this problem, the following addressing is adopted according to the present invention.

New elements / attributes are entered after existing elements / attributes with respect to the schema branch code and before past terminations that may exist in the tree structure node TSN. If the schema branch code is no longer available at that time, the addressing is extended by one bit or multiple bits, for example the most significant bit. Existing code is extended with zero, for example. The exception is the pasteration code, which is extended by 1 so the last node of the tree structure node remains. The new element / attribute is then assigned to the newly available schema branch code SBC. The change in bit length of the schema branch code must be notified to the decoder. The previous version of the schema must be known for the purpose of achieving incremental extensibility. It is not necessary to store the complete information of each version for this. Instead, it only needs to remember the number or number of bits or number of schema branch codes in the new version of the appropriately modified tree-structured node and transmit it as needed so that the erroneous code can be identified. The second method is advantageous for doing so. This information must be transmitted before the modified coded schema branch code. In this way, the bit length of the schema branch code is combined with the schema version number. Before binary coding a document, you only need to specify the version of the schema used, not all the schemas used in the past. For example, the bitstream definition of the ISO / IEC draft can be extended by the field for version information. If version control is not performed, the schema definition in the standard, such as MPEG-7, is used as a surely known reference. This schema definition can be determined as version 1, for example. One for this kind of version information

In the case of this embodiment, both version information and bit length information are additionally stored in the stream header as specified in the ISO / IEC draft. For this purpose, information as shown in Figure 4 is stored in the data stream.

A standardized version can be assigned a unique version identifier, which is designated as M7_Version_ID in Figure 4A. In addition, nine extensions can be represented by extension identifiers, which are designated EXtension_ID in Figure 4A. The bit length of the extended tree structure node TSN can also be stored in the bitstream. This is signaled by the flag DS_Extension, as shown in Figure 4A. The bit length information of the tree branch code TBC of the extended tree structure node TSN is coded in DS_Update_Info () shown in Figure 4A as shown in Figure 4B. The number of tree-structured nodes changed by the symbol Number_of_changed_nodes is reported. This number can be coded in variable length according to the position information proposed in the ISO / IEC draft.

The modified tree structure node information can be addressed in the bitstream by the navigation instruction Navigation_Command and the navigation path Navigation_Path (). In that case, it applies to all later transmitted elements of the same type as the addressed node. Below, the modified codeword length SBC_Length or the modified number of schema branch codes is inserted into the data stream. The codeword length or number is also coded according to the method used to code Number_of_changed_nodes.

In another embodiment, the modified tree structure nodes can be identified in the schema by a complex type of direct addressing. This direct addressing can be achieved, for example, by counting complex types defined in the schema.

Yet another problem is that documents coded according to the new schema are decoded by a decoder that only knows the preceding schema definition (backward compatibility). For XML-based text XML documents, this is possible for elements that were already known in the old schema. It is based on two characteristics. -The complex type elements defined in the old schema are retained, but the contained elements, attributes or data types may be different. -Element start and end marks So-called tags allow you to jump over new elements and decode known elements.

If the bit lengths of different versions of the tree-structured node are transmitted according to the predecessor addressing approach, as shown in the example above, the known elements of the extended tree-structured node still operate based on the predecessor schema. It can be processed by the "old" decoder. However, the path identifier leading to the new element cannot be jumped over by this "old" decoder, and the decoder can no longer continue decoding. For the purposes of supporting this important feature, the following alternatives apply to backward compatible coded documents in the case of the method according to the invention. a) When a new element / attribute in the TSN is addressed, the number of bits for the complete subtree or subsequent tree for that element / attribute is additionally transmitted, including the content data of the inserted N bits. Will be done. In this way, the decoder can jump over the next N bits coded in a way unknown to itself and resume from the known TSN. b) After transmission of the path containing the new element / attribute, a unique synchronization sequence is transmitted and the decoder can use this synchronization sequence to resume from a known TSN. c) When propagating a path containing a new element, the TSN of that path, which is part of the complete schema, must be pre-transmitted. d) When transmitting a path containing a new element, the complete schema must be transmitted in advance.

For alternatives c) and d), the decoder can also decode the contents of the newly added document, which can be stored or subsequently processed as needed.

The examples shown in Figures 5a and 5b represent changes in the new version of the schema definition, with extended tree-structured nodes for complex elements in Figure 5a and extensions in the deformed schema in Figure 5b. The tree structure node is drawn. Elements 3-6 have been added to the new version. This extends the length of the schema branch code from 2 to 3. However, the old address remains the same except that it has been extended to zero as the MSB.

Next, an example of coding the extended schema elements is shown in Figures 6A and 6B. Here, as a starting point, the example used in relation to Fig. 2 is used. For the sake of clarity, the above method of partitioning the node table is omitted in this drawing. We will also extend the original schema "PurchaseOrderType" by a few elements. In Figure 6A, extensions that differ from Figure 2 are shown in bold.

In other words, the elements "billTo", "MethodOfPayment", and "BankData" are newly inserted here. Therefore, the new tree branch code table needs to be extended accordingly. So three bits are not enough to code all the possibilities. This extension of the tree branch code with four bits is described in detail with reference to Figure 6b.

Now, let's deal with two cases under such a general condition.

Case 1: Documents coded according to the old schema definition are transmitted to a decoder that knows the new schema. The version number that forms the basis of the coded document must first be communicated to the decoder. For this purpose, the decoder has a table for each version number that stores the bit width or number of schema branch code SBCs for every element. This confirms that the "PruchaseOrderType" type element is coded in the decoder with only 3 bits instead of 4 bits. You can properly decode the document just by using this information.

Case 2: Documents coded according to the old schema definition are transmitted to a decoder that only knows the old schema. The decoder identifies that unknown elements may be transmitted and that unknown elements may be coded with different bit widths, based on the version number of the schema. The decoder must know the new bit width of the element, because otherwise it will lose synchronization with the encoder. In this case, the information that maps the individual elements to the bit width, for example, the table is transmitted before the original document, or the decoder sends this information at the specified address (URI). According to the method of the invention, the encoder has four possible options for coding the document.

Option 1: For each new element, the appropriate subtree length below is transmitted, as shown in Figure 7. The decoder identifies that elements not included in the standard schema are addressed based on schema branch code 0101. Correspondingly, the decoder interprets the next bit as the length L of the unknown element. This length information can be done according to adaptive variable integer coding as shown in the ISO / IEC draft. Using this length information, the decoder jumps over the lower subtree "billTo" and restarts at # SchemaBranch-Code 0010. You can then decode it again from the next element "comment".

Option 2: As shown in Figure 8, a unique synchronization sequence is transmitted after the new element. The decoder parses the bitstream until it finds a normatively defined resynchronization marker, and then continues decoding again. In the case of this method, a plurality of new elements can be coded as a group, and the resynchronization mark can be transmitted only after the last element.

Option 3: Tree structure nodes containing new elements as well as their position in the document tree are transmitted before the original document. Therefore, this technique updates the schema known to the decoder. Therefore, the transmission of the document depends on the situation where the schema is known. Moreover, given a unique version number that identifies the new schema, the decoder can use the newly transmitted schema to extend known elements with respect to those new elements.

Option 4: One completely new schema is transmitted. In this case, the decoder can treat the document as if it were coded according to a known schema. Moreover, given a unique version number that identifies the new schema, the decoder can use the newly transmitted schema to extend the known elements with respect to those new elements.

In addition, the individual methods according to the present invention can be carried out by themselves or in combination.