Patent Document ID: 7882119
Application ID: 11315458

Base Claim:
1. A document alignment method comprising: inputting source leaves of a source document in first tree structured format, the first tree structured format comprising nodes which are ultimately connected with the source leaves by paths, text content of the source document being distributed among the source leaves; inputting target leaves of a target document in second tree structured format, the second tree structured format comprising nodes which are ultimately connected with the target leaves by paths, text content of the target document being distributed among the target leaves; assigning a cost to each of a plurality of matches based on text content of the leaves, each match comprising elements selected from the group consisting of: a source leaf and a target leaf, an unmatched source leaf, and an unmatched target leaf; identifying a set of matches for which a total cost is minimal, wherein each of the input source and target leaves is in at least one of the identified matches; identifying, from the set of identified matches, groups of matches wherein each match in the group has a leaf in common; identifying, from the groups, probable matches in which more than one target leaf is matched with at least one source leaf and probable matches where more than one source leaf is matched with a target leaf; outputting an alignment between leaves of the target document and leaves of the source document which includes the probable matches.

---

Claim 21:
21. The method of claim 1 , wherein the identifying of the set of matches for which a total cost is minimal comprises: inputting a matrix with cost values which are a function of a measure of similarity for the content of pairs of leaves, the pairs of leaves each including a leaf of a source document and a leaf of a target document, each of the leaves including document content; computing a minimum edit distance for the matrix based on the input cost values, whereby each leaf from the source document is aligned with a leaf of the target document or with no leaf of the target document and each leaf from the target document is aligned with a leaf of the source document or with no leaf of the source document; and from the matrix alignments, identifying candidate matches in which a leaf of at least one of the source and target documents matches a combination of leaves of the other of the source and target documents; refining the candidate matches to identify the probable matches; and the output alignment of the leaves of the first document with the leaves of the second document includes matches of at least some of the leaves of the first document with at least some of the leaves of the second document.