JP5100220B2 - XML document conversion apparatus, XML document restoration apparatus, and XML document processing apparatus - Google Patents

Description

The present invention is an invention relating XML document conversion equipment, the XML document rehabilitation equipment and XML document processing apparatus.

  In recent years, with the spread of the Internet, opportunities for using structured documents such as HTML (Hyper Text Markup Language) documents and XML (Extensible Markup Language) documents are increasing. In particular, XML documents are attracting attention as a next-generation language that supplements HTML documents, and various methods have conventionally been used as mechanisms for compressing structures.

  As a typical compression method, there is a method of extracting a portion where the same structure is repeated from the structure of the XML document, and substituting the portion with an alias for compression. For example, in Patent Document 1, an XML document is searched, a document structure common to a plurality of locations is created as a template, a location having the same structure as the template is replaced with a template name, and the XML document after the replacement is further replaced. However, it is replaced again with tempate.

JP 2005-202507 A

  However, the conventional XML document compression method cannot be compressed unless the same structure exists in the XML document. For this reason, there is a problem that the conventional XML document compression method can be applied only to a specific XML document in which the same structure is repeated in the XML document.

  Further, in the conventional XML document compression method, tree-structured data finally remains in both the replaced XML document and the template. Therefore, even if a conventional XML document compression method is used, the structure of the finally obtained XML document is complicated, and as a result, there is a problem that a large amount of information is required.

The present invention has been made to solve the above problems, XML can be restored for any XML document, XML document conversion equipment that can convert a document structure to a number, a number in the document structure and to provide an XML document processing apparatus comprising a document rehabilitation equipment, further both devices.

According to the present invention, there is provided a node name extraction unit that extracts an XML document from an XML document storage unit that stores an XML (Extensible Markup Language) document, extracts a node name of each node from the XML document, and n nodes A node type extraction unit that extracts a node type of each node from an XML document having a node name and outputs the information list including the node name of each node extracted by the node name extraction unit to the list storage unit; A node depth measurement unit that measures a node depth when each node of the XML document is represented by a tree structure, and obtains a sequence of the measured node depths in order, and an upper left end point along n vertical and horizontal grids All the shortest paths from the right to the lower right end point are determined so that they never enter the upper right half, and each vertical path in each of the shortest paths starts with 2 at the upper left, Numbers added by 1 are sequentially assigned to the route, numbers subtracted by 1 are assigned to the vertical route adjacent to the right, and the node depth in the number sequence obtained by removing the leading one from the number sequence obtained by the node depth measurement unit. A structure number is assigned to each of the shortest paths obtained by the broken line conversion section, and a broken line conversion section that converts the number sequence to the shortest path by sequentially selecting the paths that are equal to each other and the numbers assigned to the respective vertical paths . And a numerical value conversion unit that outputs the structure number corresponding to the shortest path converted by the broken line conversion unit to the numerical value storage unit.

  An XML document conversion apparatus according to the present invention includes a line conversion unit that arranges node depths in order and converts a number sequence into a shortest path of a vertical and horizontal lattice, and a numerical conversion unit that outputs a structure number corresponding to the shortest path to a numerical value storage unit Therefore, for any XML document, the document structure can be converted into a numerical value, and the amount of information can be reduced.

(Embodiment 1)
First, the configuration of an XML document handled in the present invention will be described. An XML document has nodes as constituent elements and attributes. The XML document node handled in the present invention is assumed to be composed of five types: “non-empty element”, “empty element”, “attribute”, “element text”, and “attribute text”. “Non-empty element” is the most basic information unit in an XML document. “Empty element” is an empty element having no content. “Attribute” adds additional information to the element in the XML document. “Element text” is the value of the element. “Attribute text” is the value of the attribute.

  There are other XML document nodes such as “XML declaration”, “processing instruction”, “CDATA section”, “comment”, “character reference”, “entity reference”, etc., which are the main nodes in the XML document. Since it is not a node, it is not considered as a node in the XML document handled in the present invention. Here, “XML declaration” declares that the XML document is an XML document. “Processing instruction” describes a processing instruction to the application. The “CDATA section” describes a sentence that ignores logic and semantic structure as an XML document element. “Comment” describes an annotation sentence that is not interpreted as an XML document element. “Character reference” describes the reference of a character by a character code. “Entity reference” describes an entity that refers to a character string or a file.

  Furthermore, in the XML document handled by the present invention, line breaks and white spaces (so-called Ignitable White Space) between nodes are not treated as nodes but are ignored. For example, in the XML document shown in FIG. 2, which will be described later, a line break or a line break from <aaa bbb = "ccc"> to <ddd> eee </ ddd>, <ddd> eee </ ddd> to </ aaa>. Although there is a blank, in the XML document handled in the present invention, the line feed or blank is not treated as a node and is ignored.

  FIG. 1 shows a schematic diagram of an XML document processing apparatus according to the present embodiment. The XML document processing apparatus shown in FIG. 1 includes an XML document storage unit 10, a list storage unit 20, an XML document conversion device 30, an XML document restoration device 40, and a numerical value storage unit 50.

  Here, the XML document storage unit 10 stores an XML document before being converted into table format data by the XML document conversion device 30 and an XML document restored from the table format data by the XML document restoration device 40. It is a storage unit. The list storage unit 20 is a storage unit for storing node names and node types in an XML document in an information list in a list format.

  The XML document conversion apparatus 30 converts the node name and node type from the XML document stored in the XML document storage unit 10 into a list format information list and sends it to the list storage unit 20 to convert the node structure into a numerical value. And sent to the numerical value storage unit 50. The XML document conversion apparatus 30 includes a node name extraction unit 31, a node type extraction unit 32, a node depth measurement unit 33, a polygonal line conversion unit 34, and a numerical value conversion unit 35.

  The node name extraction unit 31 extracts the node name of each node from the XML document extracted from the XML document storage unit 10. The node type extraction unit 32 extracts information representing the node type (specifically, “non-empty element”, “empty element”, “attribute”, “element text”, “attribute text”) from the XML document. The extracted node type is output to the list storage unit 20 as an information list together with the node name extracted by the node name extraction unit 31.

  When each node of the XML document is represented by a tree structure, the node depth measurement unit 33 measures the node depth of each node. The polygonal line conversion unit 34 arranges the node depths measured by the node depth measurement unit 33 in order and represents them as a number sequence, and converts the number sequence into the shortest path from the upper left end point to the lower right end point of the vertical and horizontal lattices. Here, the shortest path can arrive at the lower right end point by moving (n−1) times to the right and (n−1) times downward between the end points from the upper left end points of the n vertical and horizontal grids. It is a route. The numerical value conversion unit 35 assigns a structure number to each of the shortest paths from the upper left end point to the lower right end point of the vertical and horizontal lattices, and outputs the structure number corresponding to the shortest path converted by the polygonal line conversion unit 34 to the numerical value storage unit 50. .

  It should be noted that extracting or measuring the node name, node type, node depth, and the like of the XML document from the XML document can be realized by an API called DOM (Document Object Model). This DOM is an API standardized by the World Wide Web Consortium (W3C), which is a Web standardization organization, and is the de facto standard in this field.

  However, in this DOM, “attribute” is not handled as a child node of “element”. However, when an XML document is handled in the present invention, “attribute” is handled as a child node of “element”.

  The XML document restoration apparatus 40 includes a node name and a node type information list stored in the list storage unit 20 and a numerical value (structure number) representing the structure of the node stored in the numerical value storage unit 50. Restore the XML document. The XML document restoration device 40 includes a node name assignment unit 41, a node type assignment unit 42, a tree structure restoration unit 43, a number sequence restoration unit 44, and a broken line restoration unit 45. Each of the node name assigning unit 41 to the broken line restoring unit 45 performs a restoring operation corresponding to each converting operation in the node name extracting unit 31 to the numerical value converting unit 35.

  The broken line restoration unit 45 restores the numerical value (structure number) extracted from the numerical value storage unit 50 to the shortest path from the upper left end point to the lower right end point along the vertical and horizontal lattices. The number sequence restoration unit 44 restores the shortest path restored by the broken line restoration unit 45 to a number sequence in which the node depths of the nodes are arranged when each node of the XML document is represented by a tree structure. The tree structure restoration unit 43 restores the tree structure of each node of the XML document from the number sequence restored by the number sequence restoration unit 44. The node type restoration unit 42 extracts the node type stored in the list storage unit 20 as an information list, and for each node restored by the tree structure restoration unit 43, the node type “non-empty element” “empty element” "" Attribute "" element text "" attribute text ". The node name assigning unit 41 assigns a node name to each node restored by the tree structure restoring unit 43 to restore the XML document, and outputs the XML document to the XML document storage unit 10.

  The numerical value storage unit 50 is a storage unit for storing a structure number corresponding to the structure of the XML document by assigning a structure number to each of the shortest paths from the upper left end point to the lower right end point of the vertical and horizontal lattices.

  Next, the operation of the XML document processing apparatus according to this embodiment will be described. First, the operation of the XML document conversion apparatus 30 that converts XML documents into table format data will be described.

  First, the XML document conversion apparatus 30 takes out an XML document to be converted from the XML document storage unit 10 into table format data (information list and structure number). In the XML document conversion apparatus 30, after extracting the XML document, the node name extraction unit 31, the node type extraction unit 32, and the node depth measurement unit 33 perform the following operations on each node of the XML document. .

  First, (1) the node name extraction unit 31 acquires a node name from each node of the extracted XML document. (2) The node type extraction unit 32 acquires the node type from each node of the extracted XML document. (3) The node depth measurement unit 33 sets the depth of the root node to 1, and measures the node depth of each node. That is, the node depth of the child node of the root node is 2, the depth of the child node is 3, and so on.

  Further, (4) the broken line conversion unit 34 has a length n−1 in which XML documents of the number n of nodes whose node depth is measured by the node depth measurement unit 33 are arranged in order of the node depth for each node other than the root node. Represented by a number sequence. Then, the broken line conversion unit 34 associates the sequence with the shortest path from the upper left end point to the lower right end point that never enters the upper right half along the vertical and horizontal grids. Here, the shortest path to the lower right end point that never enters the upper right half is the shortest path from the upper left end point to the lower right end point. It is the shortest route that does not always exceed the number of times to perform. Numbers are sequentially assigned to the vertical paths of the lattice used in the polygonal line conversion unit 34 based on a predetermined standard, and the shortest path is selected so that the numbers and the sequence of length n-1 of the XML document are the same. To do.

  (5) The numerical value conversion unit 35 assigns a structure number to each of the shortest paths from the upper left end point to the lower right end point of the grid, and stores the structure number corresponding to the shortest path converted by the polygonal line conversion unit 34 in the numerical value storage unit 50. Output. Note that the structure number assigned to each of the shortest paths is a value obtained by adding the numbers assigned to some of the horizontal paths of the lattice based on a predetermined standard along the shortest path.

  Specifically, the operations (1) to (5) performed by the XML document conversion apparatus 30 when the XML document shown in FIG. 2 is extracted from the XML document storage unit 10 will be described. FIG. 3 is an explanatory diagram showing a tree structure of the XML document shown in FIG. FIG. 4 is an explanatory diagram of an information list (node name and node type) extracted from the XML document shown in FIG.

  First, in the node aaa shown in FIG. 2, the node name extraction unit 31 extracts the node name aaa. Then, the node type extraction unit 32 extracts the node type “non-empty element” of the node (aaa). The node aaa is a root node, and since the depth of the root node is 1, the node depth measurement unit 33 obtains a node depth of 1. With the above operation, the XML document conversion apparatus 30 stores aaa in the first line of the information list shown in FIG. 4 and “non-empty element” in the first line of the second line.

  Next, in the node bbb shown in FIG. 2, the node name extraction unit 31 extracts the node name bbb. Then, the node type extraction unit 32 extracts the node type “attribute” of the node (bbb). As described above, in the present application, since it is a promise that “attribute” is a child node of “element”, the depth of the bbb node is 2, and the node depth measurement unit 33 obtains the node depth 2. With the above operation, the XML document conversion apparatus 30 stores bbb in the second row of the first line of the information list shown in FIG. 4 and “attribute” in the second row of the second line.

  Next, in the node of ccc shown in FIG. 2, the node name extraction unit 31 extracts the node name ccc. Then, the node type extracting unit 32 extracts the node type “attribute text” of the node (ccc). The node depth of ccc is 3, and the node depth measurement unit 33 obtains the node depth 3. With the above operation, the XML document conversion apparatus 30 stores ccc in the third line of the first line of the information list shown in FIG. 4 and “attribute text” in the first line of the second line.

  Next, at the node ddd shown in FIG. 2, the node name extraction unit 31 extracts the node name ddd. Then, the node type extraction unit 32 extracts the node type “non-empty element” of the node (ddd). The node depth of ddd is 2, and the node depth measurement unit 33 obtains the node depth 2. With the above operation, the XML document conversion apparatus 30 stores ddd in the fourth line of the first line of the information list shown in FIG. 4 and “non-empty element” in the fourth line of the second line.

  Next, in the node of eee shown in FIG. 2, the node name extraction unit 31 extracts the node name eee. Then, the node type extraction unit 32 extracts the node type “element text” of the node (eee). The node depth of eee is 3, and the node depth measurement unit 33 obtains the node depth 3. With the above operation, the XML document conversion apparatus 30 stores eee in the fifth line of the first line of the information list shown in FIG. 4 and “element text” in the fifth line of the second line.

  As described above, the node (aaa) is the root node (parent node) with the node depth “1”, and the child node for this parent node is the node (bbb) with the node depth “2”. Node (ddd). Therefore, if the relationship is represented by the tree structure in FIG. 3, the node (bbb) and the node (ddd) hang from the node (aaa). Furthermore, a child node (a grandchild node for the node (aaa)) for the node (bbb) is a node (ccc) having a node depth of “3”. Therefore, if the relationship is represented by the tree structure of FIG. 3, the node (ccc) hangs from the node (bbb). Similarly, a child node for the node (ddd) (a grandchild node for the node (aaa)) is a node (eee) having a node depth of “3”. Therefore, if the relationship is represented by the tree structure in FIG. 3, the node (eee) hangs from the node (ddd).

  Further, the information list as shown in FIG. 4 is created by the above operation and stored in the list storage unit 20. Further, the node depth measurement unit 33 obtains a numerical sequence 12323 in which the node depth of each node is arranged in the order of the node depth.

  Next, in the polygonal line conversion unit 34, the number sequence 2323 (length n−1) excluding the depth 1 of the root node in the number sequence 12323 is taken from the upper left end point along the vertical and horizontal grids (n). Convert to the shortest path to the lower right corner so that it never enters the upper right half. The numerical value conversion unit 35 adds a number (structure number) to the numerical value so that the shortest route converted by the broken line conversion unit 34 can be identified from among the plurality of shortest routes. Note that these processes require mathematical knowledge described below.

  First, (a) an XML document is a labeled ordered tree. Therefore, the structure of the XML document is an ordered tree. (A) It is mathematically known that an ordered tree having n nodes and a binary tree having n nodes have a one-to-one correspondence. (C) It is mathematically known that the number of binary trees having n nodes is the Catalan number Cn-1. Here, the general formula for the Catalan number Cn (n ≧ 0) is Cn = (2n)! / ((N + 1)! N!). (D) It is mathematically known that the Catalan number Cn is equal to the number of shortest paths from the upper left end point to the upper right half point along the grid of n + 1 vertical and horizontal lines so as to never enter the upper right half point.

  According to the above conditions (a) to (d), the number of structures that can be taken by an XML document having n nodes is such that it never enters the upper right half from the upper left end point along n vertical and horizontal grids. It can be seen that it is equal to the number of shortest paths to the lower right end point.

  Although the Catalan number Cn−1 can be calculated by the general formula described above, it can also be obtained inductively. Specifically, the catalan number C4 in the case of n = 5 can be obtained by the number in the shortest distance from the upper left end point to the lower right end point of each of the five vertical and horizontal grids shown in FIG.

  The shortest path from the upper left end point to the lower right end point is equal to the shortest path from the lower right end point to the upper left end point. Therefore, in FIG. 5, the shortest distance from the vertex A that is the lower right end point to the vertex O that is the upper left end point will be described. First, since there are only one path from the vertex A to the vertex B, 1 is written in the vertex B as shown in FIG. The path from the vertex A to the vertex C is only one way through the vertex B, and 1 is written in the vertex C as shown in FIG. There is only one path from the vertex A to the vertex F when passing through the vertex B, and 1 is written in the vertex F as shown in FIG.

  There are two paths from the vertex A to the vertex G, when passing through the vertex C and when passing through the vertex F. Therefore, the path from the vertex A to the vertex G is a value obtained by adding the value 1 written in the vertex C and the value 1 written in the vertex F, and 2 is written in the vertex G as shown in FIG. . Based on the above relationship, the path from the vertex A to a vertex is equal to the sum of the path from the vertex A to the vertex immediately below the vertex and the path from the vertex A to the vertex immediately to the right of the vertex. I understand.

  Based on this rule, when values are written in order at each vertex, 14 is written at the vertex N as shown in FIG. Accordingly, there are 14 paths from the vertex A to the vertex O.

  Based on the above knowledge, the operation of the polygonal line converter 34 will be described. In the grid shown in FIG. 6, numbers are assigned to each vertical route in order. That is, 2, 3, 4, and 5 are assigned to the vertical path at the left end of FIG. 6, and 2, 3, and 4 are assigned to the next vertical path. Then, the broken line conversion unit 34 selects the shortest path so that the numerical sequence 2323 obtained by the node depth measurement unit 33 is equal to the number assigned to the vertical path. Specifically, the numbers assigned to the vertical path at the left end of FIG. 6 from the upper left end point are advanced to 2, 3 and advanced by two vertices in the horizontal direction, and the numbers assigned to the vertical path are further increased to 2, 3 Proceeding and then proceeding in the horizontal direction to reach the lower right end point, it becomes equal to the number sequence 2323. FIG. 7 shows all the shortest paths from the upper left end point to the lower right end point in FIG. In FIG. 7, the shortest path surrounded by a solid line represents the shortest path in the sequence 2323. Note that the numerical sequence shown in FIG. 7 is represented by adding a root node depth of 1.

  Next, the operation of the numerical value conversion unit 35 will be described. First, the numerical value conversion unit 35 assigns a number (structure number) to the shortest path of the lattice. For the lattice shown in FIG. 5, the 14th shortest path is numbered from 0th to 13th. More specifically, when proceeding from the vertex O to the vertex N, there are options that go down from the vertex N and go through the vertex L, and options that go right from the vertex N and go through the vertex M. As described with reference to FIG. 5, there are nine paths that go down from the vertex N and reach the vertex A via the vertex L, and there are 5 paths that go from the vertex N to the right and reach the vertex A via the vertex M. There are streets. Here, if a rule is given that the order is faster as it goes down rather than proceeding to the right, the path going from the vertex N to the right and passing through the vertex M is at least as low as the path going down from the vertex N and going through the vertex L. Since the order is the 9th latest, 9 is written on the path from the vertex N to the vertex M as shown in FIG.

  Further, when proceeding downward from the vertex N and proceeding to the vertex L, there are an option proceeding downward from the vertex L via the vertex I and an option proceeding right from the vertex L via the vertex K. As described with reference to FIG. 5, there are four paths that go down from the vertex L and reach the vertex A via the vertex I, and go to the right from the vertex L and reach the vertex A via the vertex K. There are streets. Then, the route going from the vertex L to the right and passing through the vertex K is at least 4th order lower than the route going from the vertex L and going through the vertex I, so the route from L to K is shown in FIG. As shown in FIG.

  Further, when going from the vertex L to the right and going to the vertex K, or going from the vertex N to the right and going to the vertex K via the vertex M, the option to go down from the vertex K and go through the vertex H, and from the vertex K to the right There is an option to go through the vertex J. As described with reference to FIG. 5, there are three paths that go down from the vertex K and reach the vertex A via the vertex H, and go to the right from the vertex K and reach the vertex A via the vertex J. There are streets. Then, the route going from the vertex K to the right and passing through the vertex J is at least 3 times slower than the route going from the vertex K and going through the vertex H, so the route from the vertex K to the vertex J As shown in FIG.

  Hereinafter, in the same way, when the option to go down and the option to go to the right can be selected, it is as shown in FIG.

  Then, using the numerical values assigned to the horizontal paths shown in FIG. 8, numbers (structure numbers) are assigned to the shortest paths of the lattice shown in FIG. That is, the number (structure number) for each shortest path is a value obtained by adding the numerical values assigned to the paths next to the trajectory passed through the shortest path. Specifically, among the shortest paths from the vertex O to the vertex A, the shortest path passing through the vertices N, L, I, E, D, C, and B is a numerical value assigned to the horizontal path shown in FIG. Since the value obtained by adding is 0, the number of the shortest path (structure number) is 0. Similarly, since the shortest path of the sequence 2323 corresponding to the XML document in FIG. 2 passes through the vertices N, L, K, J, G, C, and B, the numerical values assigned to the horizontal paths shown in FIG. The added value is 7, and the number of the shortest path (structure number) is 7. The result of assigning numbers to all the shortest paths shown in FIG. 7 is as shown in FIG.

  If the structure number of the shortest path in the sequence 2323 corresponding to the XML document in FIG. 2 is obtained as 7 as described above, the numerical value conversion unit 35 stores the number in the numerical value storage unit 50. Through the above processing, the structure of an arbitrary XML document composed of “non-empty element”, “empty element”, “element text”, “attribute”, and “attribute text” is converted into data in a table format including an information list and a structure number. can do.

  Next, the operation of the XML document restoration apparatus 40 that restores data in the table format (information list and structure number) to an XML document will be described. First, the XML document restoration device 40 extracts the structure number of the XML document to be restored from the numerical value storage unit 50. Then, the polygonal line restoration unit 45 converts the acquired structure number into the shortest path corresponding to the acquired structure number by associating it with the number of the shortest path from the upper left end point of the lattice to the lower right end point. Here, the structure number acquired from the numerical value storage unit 50 is determined by a value obtained by adding the numerical values assigned to the horizontal paths on the trajectory passing through the shortest path of the lattice as shown in FIG.

  A processing example in the polygonal line restoration unit 45 that restores the shortest path of the structure number 7 will be described using the lattice shown in FIG. First, when going from the vertex O to the vertex N, the route going from the vertex N to the right and passing through the vertex M is at least 9th order lower than the route going from the vertex N and going through the vertex L. This means that the route going from the vertex N and going through the vertex L is earlier than the ninth route, and the route going from the vertex N to the right and going through the vertex M is the ninth or slower. Therefore, the shortest path having the structure number 7 (seventh) is a path that goes down from the vertex N and passes through the vertex L.

  Next, when going from the vertex N to the vertex L, the route going from the vertex L to the right and passing through the vertex K is at least 4th order in turn lower than the route going from the vertex L and going through the vertex I. This means that the path going from the vertex L and going through the vertex I is earlier than the fourth path, and the path going from the vertex L to the right and going through the vertex K is the fourth or later. Therefore, the shortest path of structure number 7 (seventh) is a path that goes to the right from the vertex N and passes through the vertex K.

  Further, when going from the vertex L to the vertex K, the route going from the vertex K to the right and passing through the vertex J is at least the third slower than the route going down from the vertex K and going through the vertex H. Since the shortest path that passes through the vertices L and K is already the fourth or later, the path that goes down from the vertex K and passes through the vertex H is faster than the 4 + 3 = 7th, goes to the right from the vertex K, and reaches the vertex J The route via is 4 + 3 = 7th or slower. Therefore, the shortest path of structure number 7 (seventh) is a path that goes right from the vertex K and passes through the vertex J.

  When going from the vertex K to the vertex G via the vertex J, the route going from the vertex G to the right and going through the vertex F is at least as late as the route going down from the vertex G and going through the vertex C. Since the shortest path that passes through the vertices L, K, J, and G is already the seventh or later, the path that goes down from the vertex G and passes through the vertex C is earlier than the 7 + 1 = 8th, and is right from the vertex G. The route passing through the vertex F is 7 + 1 = 8th or later. Accordingly, the shortest path of structure number 7 (seventh) is a path that goes down from the vertex K and passes through the vertex C.

  When going down from the vertex G, there is no shortest path option, and the vertex A is reached via the vertices C and B. As described above, by calculating the order at the vertices with options, it can be seen that the shortest path of structure number 7 (seventh) is a path surrounded by a solid line in FIG.

  After the shortest path is restored by the broken line restoration unit 45, the number sequence restoration unit 44 sets the length n− in which the restored shortest path is arranged in the node depth order for each node other than the root node in the XML document with n nodes. Restore to a sequence of ones. The processing of the sequence reconstruction unit 44 will be described in detail. The shortest path surrounded by the solid line in FIG. 9, which is the shortest path of the structure number 7 (seventh), corresponds to the shortest path surrounded by the solid line in FIG. The number sequence becomes 2323. Further, since the depth of the root node is 1, the number sequence of the structure of the XML document to be restored is 12323.

  After the number sequence restoration, the tree structure restoration unit 43 restores the tree structure of the XML document corresponding to the restored number sequence. The numerical sequence 12323 is represented by the tree structure of the XML document as shown in FIG. After restoring the tree structure, the XML document restoration device 40 extracts the information list storing the node name and node type of each node of the XML document from the list storage unit 20, and the node type assignment unit 42 stores the information list in the information list. Based on this, a node type is assigned to each node of the XML document.

  The processing of the node type assignment unit 42 will be described based on the example of FIG. First, since the first value in the second line of the information list shown in FIG. 4 is “non-empty element”, the node type “non-empty element” is assigned to the first node of the XML document. Further, the node types are assigned to the second to sixth nodes of the XML document in the same manner for the second to sixth nodes in the second row of the information list shown in FIG.

  After assigning a node type to each node of the XML document, the node name assigning unit 41 assigns a node name to each node of the XML document based on the information list. The process of the node name assigning unit 41 will be described based on an example. First, since the first value in the first line of the information list shown in FIG. 4 is aaa, the node name of aaa is given to the first node of the XML document. Further, similarly, the node names are assigned to the second to sixth nodes of the XML document for the second to sixth nodes in the second row of the information list shown in FIG.

  Then, the XML document restoration apparatus 40 can restore the XML document by using the tree structure of the nodes, the node types, and the node names obtained by the processes of the node name assigning unit 41 to the broken line restoration unit 45. Note that the restored XML document is stored in the document storage unit 10 from the XML document restoration device 40.

  As described above, the XML document restoration apparatus 40 according to the present embodiment uses the “non-empty element”, “empty element”, “attribute”, “element text”, and “attribute text” nodes from the information list and the structure number. Any XML document can be restored.

  The XML document conversion apparatus 30 according to the present embodiment can convert an XML document into an information list and a structure number as described above. Further, the XML document conversion apparatus 30 according to the present embodiment can convert the XML document structure into a numerical value (structure number) by associating the structure of the XML document with the shortest path of the lattice. In the XML document conversion apparatus 30 according to the first embodiment, since the node type is a non-empty element, an empty element, an attribute, an element text, and an attribute text, the most basic information unit in the XML document is used. The structure of the XML document can be converted into a numerical value (structure number). Furthermore, since the structure of the XML document can be held with a numerical value (structure number), less memory is required for the operation of the XML document.

  As described above, the XML document restoration apparatus 40 of this embodiment can restore an XML document from the information list and the structure number. Further, the XML document restoration apparatus 40 according to the present embodiment can restore the structure of the original XML document from a numerical value (structure number) in which the structure of the XML document is made to correspond to the shortest path of the lattice by simple processing. . Furthermore, since the XML document restoration apparatus 40 according to the present embodiment uses the non-empty element, the empty element, the attribute, the element text, and the attribute text as the node type, a numerical value is used for the most basic information unit in the XML document. The structure of the XML document can be restored from (structure number).

(Embodiment 2)
In the first embodiment, in the numerical value conversion unit 35 and the broken line restoration unit 45, a rule is set such that the order of the shortest path is faster when proceeding downward than when proceeding to the right. However, the numerical value conversion unit 35 and the broken line restoration unit 45 according to the present invention are not limited to the rule. Therefore, in the numerical value conversion unit 35 and the broken line restoration unit 45 according to the present embodiment, a rule is set such that the order of the shortest path is faster when proceeding to the right than proceeding downward. In this case, numbers are assigned to some of the vertical paths of the lattice, and the value obtained by adding the numbers on the trajectory passed through the shortest path is the shortest path number (structure number). Since the XML document processing apparatus according to the present embodiment has the same configuration as that of the first embodiment except for the above rules, the same elements are denoted by the same reference numerals, and detailed description thereof is omitted.

  In the present embodiment, a method for assigning 0th to 13th numbers (structure numbers) to the shortest path of the lattice shown in FIG. 5 will be described below. First, when going from the vertex O to the vertex N shown in FIG. 5, there are options that go down from the vertex N via the vertex L and options that go right from the vertex N and go through the vertex M. There are nine paths that go down from the vertex N and reach the vertex A via the vertex L, and there are five paths that go right from the vertex N and reach the vertex A via the vertex M. Here, in the present embodiment, a rule is set in which the order of the shortest path is faster in the right direction than in the downward direction. Therefore, the path that goes down from the vertex N and passes through the vertex L is from the vertex N. This means that the order is at least 5 slower than the route passing right and going through the vertex M, and 5 is written on the route from the vertex N to the vertex L as shown in FIG.

  Next, when proceeding downward from the vertex N and proceeding to the vertex L, there are an option proceeding downward from the vertex L via the vertex I and an option proceeding right from the vertex L via the vertex K. As described in FIG. 5, there are four paths that go down from the vertex L and reach the vertex A via the vertex I, and there are 5 paths that go from the vertex L to the right and reach the vertex A via the vertex K. There are streets. Therefore, the route going from the vertex L and going through the vertex I is at least 5th in order than the route going from the vertex L to the right and going through the vertex K, so the route going from the vertex L to the vertex I. As shown in FIG.

  Further, when going from the vertex L to the right and going to the vertex K, or going from the vertex N to the right and going through the vertex M to the vertex K, the option to go down from the vertex K and go through the vertex H, and from the vertex K There is an option to go right and go through vertex J. As described in FIG. 5, there are three paths that go down from the vertex K and reach the vertex A via the vertex H, and go to the right from the vertex K and reach the vertex A via the vertex J. There are streets. Therefore, the path going from the vertex K and going through the vertex H is at least the second order in the order going from the vertex K to the right and going through the vertex J. As shown in FIG.

  In the same way, if the option to go down and the option to go to the right can be selected in the same way, at least how much the order is delayed when going down is written in the vertical path. FIG. 10 shows the result of assigning numbers to the vertical paths by the above-described method for the lattice shown in FIG.

  The shortest path number (structure number) is a value obtained by adding the numbers assigned to the vertical paths on the trajectory passed through the shortest path. In the XML document shown in FIG. 2, the shortest route becomes a route surrounded by a solid line in FIG. 7, and on this route (vertices O, N, L, K, J, G, C, B, A) The sum of the numbers assigned to a certain vertical path is 6. Therefore, the shortest path number (structure number) of the XML document shown in FIG. In the present embodiment, the numbers for all the shortest paths shown in FIG. 7 are as shown in FIG.

  Next, a case where the shortest path in the lattice shown in FIG. 10 is restored from the number (structure number) 6 in the processing of the broken line restoration unit 45 will be described. First, when going from the vertex O to the vertex N, the route that goes down from the vertex N and passes through the vertex L is at least 5th order in the order that goes from the vertex N to the right and goes through the vertex M. This means that the path going from the vertex N to the right and passing through the vertex M is earlier than the fifth, and the path going down from the vertex N and going through the vertex L is the fifth or later. Accordingly, the sixth route is a route that goes down from the vertex N and passes through the vertex L.

  Next, when going from the vertex N to the vertex L, the route going from the vertex L and going through the vertex I goes to the right from the vertex L and is at least 5th in turn in the order of going through the vertex K. Since the shortest path that passes through the vertices N and L is already the fifth or later, the path going to the right from the vertex L and going through the vertex K is faster than the 5 + 5 = 10th, going down from the vertex L and moving the vertex I. This means that the route that passes is 5 + 5 = 10th or slower. Therefore, the sixth route is a route that goes to the right from the vertex N and passes through the vertex K.

  Further, when going from the vertex L to the vertex K, the path going from the vertex K and passing through the vertex H is at least 2nd in turn in the order going from the vertex K to the right and going through the vertex J. Since the shortest path that passes through the vertices N, L, and K is already the fifth or later, the path that goes to the right from the vertex K and goes through the vertex J is earlier than the 5 + 2 = 7th and goes down from the vertex K to the vertex. This means that the route via H is 5 + 2 = 7th or slower. Accordingly, the sixth route is a route that goes to the right from the vertex K and passes through the vertex J.

  Further, when going from the vertex K to the vertex G via the vertex J, the path going down from the vertex G and going through the vertex C is at least as late as the path going from the vertex G to the right and going through the vertex F. . Since the path that passes through the vertices N, L, K, J, and G is already the fifth or later, the path that goes to the right from the vertex G and passes through the vertex F is earlier than the 5 + 1 = 6th and descends from the vertex G. And the route passing through the vertex C is 5 + 1 = 6th or later. Therefore, the sixth path is a path that goes down from the vertex K and passes through the vertex C.

  When going downward from the vertex G, there is no shortest path option, and the vertex A is reached via the vertex C and vertex B. As described above, it is understood that the shortest path having the structure number 6 (sixth) is a path surrounded by a solid line in FIG.

  As described above, in the XML document conversion apparatus 30 and the XML document restoration apparatus 40 according to the present embodiment, the numerical value storage unit 35 is based on a rule that is earlier in order as it proceeds to the right than to proceed downward in the order of the shortest path. Since the broken line restoration unit 45 restores the shortest path based on the rule, the same effect as in the first embodiment can be expected.

It is a block diagram of the XML document processing apparatus which concerns on Embodiment 1 of this invention. It is a figure for demonstrating the XML document which concerns on Embodiment 1 of this invention. It is a figure for demonstrating the tree structure of the XML document which concerns on Embodiment 1 of this invention. It is a figure for demonstrating the information list | wrist of the XML document which concerns on Embodiment 1 of this invention. It is a figure for demonstrating the shortest path | route of the grating | lattice corresponding to the XML document which concerns on Embodiment 1 of this invention. It is a figure for demonstrating the number sequence corresponding to the XML document which concerns on Embodiment 1 of this invention. It is a figure for demonstrating the number sequence corresponding to the XML document which concerns on Embodiment 1 of this invention. It is a figure for demonstrating the structure number of the XML document which concerns on Embodiment 1 of this invention. It is a figure for demonstrating the structure number of the XML document which concerns on Embodiment 1 of this invention. It is a figure for demonstrating the structure number of the XML document which concerns on Embodiment 2 of this invention. It is a figure for demonstrating the structure number of the XML document which concerns on Embodiment 2 of this invention.

Explanation of symbols

  10 XML document storage unit, 20 list storage unit, 30 XML document conversion device, 31 node name extraction unit, 32 node type extraction unit, 33 node depth measurement unit, 34 polygonal line conversion unit, 35 numerical value conversion unit, 40 XML document restoration Device, 41 Node name assigning unit, 42 Node type restoring unit, 43 Tree structure restoring unit, 44 Number sequence restoring unit, 45 Polygonal line restoring unit, 50 Numerical value storing unit.

Claims (5)

A node name extraction unit that extracts the XML document from an XML document storage unit that stores an XML (Extensible Markup Language) document, and extracts a node name of each node from the XML document;
Extract the node type of each node from the XML document with n nodes, the said node type and the node name and list storage information list including for each node extracted by the node name extraction unit of each node Node type extraction unit to output to
A node depth measurement unit that measures a node depth when each node of the XML document is represented by a tree structure, and obtains a sequence in which the measured node depths are arranged in order ;
All shortest paths from the upper left end point to the upper right half along the vertical and horizontal n grids are obtained so that the upper left corner is 2 in each vertical path in each of the shortest paths. Starting from, a number added by 1 is assigned to the vertical path immediately below, and a number minus 1 is assigned to the vertical path immediately to the right, and the leading 1 is removed from the sequence obtained by the node depth measurement unit. A polygonal line conversion unit for converting the number sequence to the shortest path by sequentially selecting a path in which each of the node depths in the number sequence is equal to a number assigned to each vertical path ;
Of the plurality of structure numbers for identifying each of the shortest paths obtained by the broken line conversion unit, the structure number corresponding to the shortest path converted by the broken line conversion unit is output to the numerical value storage unit XML document conversion device comprising: a numerical value converter for the. The XML document conversion device according to claim 1,
Each of the plurality of structure numbers identifying each of the shortest paths is less than one of the options when an option to go down and an option to go to the right can be selected at a point where the vertical and horizontal paths in the grid intersect. In the lattice in which the numerical values set under the rule that the order going to the other is earlier is written in all of the one path of the options, the numerical value is recorded in one path of the options in each of the shortest paths. XML document conversion device that is the sum of the numerical values obtained . Any of the shortest paths from the upper left corner to the upper right half of the structure of an XML (Extensible Markup Language) document having n nodes along the vertical and horizontal grids. The structure number is extracted from the numerical value storage unit stored as the structure number corresponding to, and matches the structure number extracted from the numerical value storage unit among the plurality of structure numbers that identify each of the shortest paths. A polygonal line restoration unit that selects the shortest path corresponding to what to do;
Each vertical path in each of the shortest paths is assigned a number starting from 2 at the top left, a number added by 1 to the vertical path immediately below, and a number subtracted by 1 from the vertical path immediately to the right. In the case where each node of the XML document is represented by a tree structure by adding 1 to the head of the number sequence allocated to the vertical path in the shortest path selected by the broken line restoration unit A number sequence restoration unit for restoring a number sequence in which the node depth of each node is arranged;
A tree structure restoring unit for restoring the tree structure of the XML document based on the number sequence restored by the number sequence restoring unit;
The XML document tree retrieved from the list storage unit storing the information list having the node name and node type of each node of the XML document, and restored by the tree structure restoration unit based on the information list A node type assigning unit for assigning the node type to each node in the structure;
A node that outputs the XML document obtained by assigning the node name to each node in the tree structure of the XML document restored by the tree structure restoration unit to the XML document storage unit based on the information list An XML document restoration device comprising: a name assigning unit . The XML document conversion device according to claim 3,
Each of the plurality of structure numbers identifying each of the shortest paths is less than one of the options when an option to go down and an option to go to the right can be selected at a point where the vertical and horizontal paths in the grid intersect. In the lattice in which the numerical values set under the rule that the order going to the other is earlier is written in all of the one path of the options, the numerical value is recorded in one path of the options in each of the shortest paths. XML document restoration device that is the sum of the numerical values obtained .   An XML document storage unit for storing the XML document;
  A list storage unit storing an information list having a node name and a node type of each node of the XML document;
  The structure of the XML document having n nodes is stored as a structure number corresponding to the shortest path from the upper left end point to the upper right half point so as to never enter the upper right half along the vertical and horizontal n grids. A numeric storage unit,
  The XML document conversion device according to claim 1 or 2,
  An XML document processing apparatus comprising the XML document restoration apparatus according to claim 3.

Images