Patent Document ID: 8429526
Application ID: 11401610

Base 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.

---

Claim 8:
8. The method of claim 1 , wherein performing the plurality of comparisons comprises: generating a distance matrix for a plurality of subtrees in the first document, wherein: the root of said each subtree of the plurality of subtrees is above the depth indicated by the hash level; a first axis of each distance matrix includes child nodes of the root node of a different subtree in the first document; a second axis of said each distance matrix includes child nodes of the root node of a particular subtree in the second document that corresponds to said different subtree in the first document; for each node in each distance matrix, computing a second hash value based on said each node and descendants of said each node; for each distance matrix, based on the hash value computed for said each node, generating a plurality of proposed paths through said each distance matrix; and for each distance matrix, selecting, based on one or more criteria, a proposed path from the plurality of proposed paths; and wherein the edit script is based on the proposed path for each distance matrix.