Efficient evaluation for diff of XML documents
First Claim
1. A method comprising the steps of:
- receiving a hash level indicating a particular depth in a first document and a second document, wherein;
the first document comprises a first plurality of nodes, wherein one or more nodes of the first plurality of nodes are at a depth that is greater than the particular depth; and
the second document comprises a second plurality of nodes, wherein one or more nodes of the second plurality of nodes are at a depth that is greater than the particular depth;
based on the hash level, identifying a first subset, of the first plurality of nodes, that do not include any nodes, in the first plurality of nodes, that are at a depth that is greater than the particular depth, wherein the first subset includes at least two nodes that are at the same depth;
based on the hash level, identifying a second subset, of the second plurality of nodes, that do not include any nodes, in the second plurality of nodes, that are at a depth that is greater than the particular depth, wherein the second subset includes at least two nodes that are at the same depth;
for each node included in the first and second subsets, computing a hash value based on said each node and one or more descendants of said each node;
performing a plurality of comparisons between hash values of different nodes that are only in the first and second subsets;
based on the plurality of comparisons, generating an edit script;
wherein the method is performed by one or more computing devices.
1 Assignment
0 Petitions
Accused Products
Abstract
A technique for differencing XML documents is provided. An edit graph is generated for computing the cost of possible edits that may be applied to a first XML document in order to generate a second XML document. A hash value is assigned to nodes included in the axes of the edit graph, where one axis includes nodes in the first XML document and the other axis includes nodes in the second XML document. The hash value may be generated based on a particular node'"'"'s name and attributes, and the hash value of the name and attributes of each child node of the particular node. A technique for patching an XML document is also provided. Events are generated for each node in the input document and for at least one operation specified in the edit script. The edit script is applied to the input document by performing one or more operations specified in the operation events on one or more node events.
52 Citations
22 Claims
-
1. A method comprising the steps of:
-
receiving a hash level indicating a particular depth in a first document and a second document, wherein; the first document comprises a first plurality of nodes, wherein one or more nodes of the first plurality of nodes are at a depth that is greater than the particular depth; and the second document comprises a second plurality of nodes, wherein one or more nodes of the second plurality of nodes are at a depth that is greater than the particular depth; based on the hash level, identifying a first subset, of the first plurality of nodes, that do not include any nodes, in the first plurality of nodes, that are at a depth that is greater than the particular depth, wherein the first subset includes at least two nodes that are at the same depth; based on the hash level, identifying a second subset, of the second plurality of nodes, that do not include any nodes, in the second plurality of nodes, that are at a depth that is greater than the particular depth, wherein the second subset includes at least two nodes that are at the same depth; for each node included in the first and second subsets, computing a hash value based on said each node and one or more descendants of said each node; performing a plurality of comparisons between hash values of different nodes that are only in the first and second subsets; based on the plurality of comparisons, generating an edit script; wherein the method is performed by one or more computing devices. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 17, 18, 19)
-
-
9. A non-transitory machine-readable storage medium storing instructions, which when executed by one or more processors, causes:
-
receiving a hash level indicating a particular depth in a first document and a second document, wherein; the first document comprises the first plurality of nodes, wherein one or more nodes of the first plurality of nodes are at a depth that is greater than the particular depth; and the second document comprises the second plurality of nodes, wherein one or more nodes of the second plurality of nodes are at a depth that is greater than the particular depth; based on the hash level, identifying a first subset, of the first plurality of nodes, that do not include any nodes, in the first plurality of nodes, that are greater than the particular depth, wherein the first subset includes at least two nodes that are at the same depth; based on the hash level, identifying a second subset, of the second plurality of nodes, that do not include any nodes, in the second plurality of nodes, that are greater than the particular depth, wherein the second subset includes at least two nodes that are at the same depth; for each node included in the first and the second subsets, computing a hash value based on said each node and one or more descendants of said each node; performing a plurality of comparisons between hash values of different nodes that are only in the first and second subsets; and based on the plurality of comparisons, generating an edit script. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 20, 21, 22)
-
Specification