Document alignment systems for legacy document conversions

• US 7,882,119 B2
• Filed: 12/22/2005
• Issued: 02/01/2011
• Est. Priority Date: 12/22/2005
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chidlovskii, Boris, Bergholz, Andre
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Ruiz; Angelica
• Application Number:
  US11/315,458
• Publication Number:
  US 20070150443A1
• Time in Patent Office: 1,867 Days
• Field of Search: 707/2, 707/102, 707/103.Y, 707/103.R, 715/234, 715/236, 715/237, 715/239
• US Class Current: 707/758
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database

Abstract

A method for aligning documents which may be in different XML formats includes inputting source and target leaves of a source and documents in first and second tree structured formats and assigning a cost to each of a plurality of matches. Each match may include a source leaf and a target leaf or be an unmatched source or target leaf. Matches are identified for which a total cost is minimal, wherein each of the leaves is in at least one of the identified matches. From the identified matches, groups of two or more matches are identified which have a leaf in common. From the groups, probable matches are identified in which more that one target leaf is matched with at least one source leaf or more than one source leaf is matched with a target leaf. An alignment between leaves of the target document and leaves of the source document is output which includes the probable matches.

Claims

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.

2. The document alignment method of claim 1, wherein at least one of the first and second tree structured formats is an extended mark up language format.

3. The document alignment method of claim 1, wherein the target document is in a semantically richer extended mark up language format than the source document.

4. The document alignment method of claim 1, wherein each assigned cost is a function of a similarity measure for the elements in the pair.

7. The document alignment method of claim 1, wherein each assigned cost is a function of a similarity measure for the elements in the pair.

8. The document alignment method of claim 7, further comprising:

determining the similarity measure for each of the matches in which a leaf of the target document is matched with a leaf of the source document, including computing at least one of;

a length of the leaf with the shortest content minus the minimum edit distance between the two contents;

if the content of one leaf is a substring of the other one, the length of the former, otherwise 0;

a sum of the lengths of words common to the two leaves; and

for each portion of the first leaf which has a matching portion in the second leaf, determining a length of the portion and summing the determined lengths, optionally modified by imposing at least one constraint whose violation leads to a similarity of 0.

9. The document alignment method of claim 7, wherein each cost is also a function of a length of a shorter of the two leaves.

10. The method of claim 1, wherein when two elements have no greater than a threshold number of characters in common, a maximum cost value is assigned.

11. The method of claim 1, wherein the identifying matches for which a total cost is minimal includes computing a minimum edit distance for a matrix in which the costs of the matches are arranged according to a sequence in which the source leaves and target leaves are arranged in their respective documents.

12. The method of claim 1, wherein the identifying of 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 includes:

merging a pair of a group with another pair where the similarity between the elements of one of the pairs is 0.

13. The method of claim 1, wherein the identifying of 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 includes determining whether the group as a whole has a higher similarity than the elements from which the group is derived.

14. The method of claim 1, further comprising,

annotating leaves of at least one of the source document and the target document with an attribute, the attribute identifying a matching leaf from the other of the source document and the target document.

16. The method of claim 1, wherein the target document has substantially the same content as the source document.

17. The method of claim 1, wherein the source document is a natural language document and the target document is a natural language document in the same language and wherein the source and target leaves include text in the natural language.

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.

22. The method of claim 21, wherein a maximum cost value is assigned to unmatched pairs in which a target leaf has no corresponding source leaf or a source leaf has no corresponding target leaf.

23. The method of claim 1, wherein each assigned cost is a function of a similarity measure for the elements in the pair and wherein each cost is also a function of a length of a shorter of the two leaves.

24. The method of claim 1, wherein the assigning a cost to each of the plurality of matches is not based on the tree structure of the source and target documents.

5. 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, each source leaf comprising text content;

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, each target leaf comprising text content;

subdividing the leaves of the source document and the leaves of the target document into blocks, each block including a set of the source leaves and a set of the target leaves;

for each block, assigning a cost to each of a plurality of matches, each match comprising a pair of elements selected from the group consisting of a source leaf and a target leaf, an unmatched source leaf, and an unmatched target leaf from the same block;

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; and

outputting an alignment between leaves of the target document and leaves of the source document which includes the probable matches.

6. The document alignment method of claim 5, further comprising:

within each of the blocks, identifying any matches wherein a similarity measure between a leaf of the source document and a leaf of the target document exceeds a threshold value; and

subdividing the leaves of the source document and the leaves of the target document into partitions bounded by the identified matches wherein the similarity measure between the leaf of the source document and the leaf of the target document exceeds a threshold value.

25. The method of claim 5, wherein the leaves of the source and target documents are subdivided into an equal number of blocks.

26. The method of claim 5, wherein the leaves of the source and target documents are subdivided into a number of blocks which is from about ⅕

to about 1/200 times a number of leaves in the source or target document.

15. A supervised learning method comprising:

learning a transformation which converts a source document to a target document using source and target documents aligned by a method comprising;

inputting source leaves of a source document in first tree structured format, each source leaf comprising text content;

inputting target leaves of a target document in second tree structured format, each target leaf comprising text content;

assigning a cost to each of a plurality of matches based on leaf text content, each match consisting of one of the group consisting of;

a source leaf and a target leaf,

an unmatched source leaf, and

an unmatched target leaf;

identifying matches for which a total cost is minimal, wherein each of the leaves is in at least one of the identified matches;

identifying, from the 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.

18. A document alignment apparatus comprising:

an input device for inputting source leaves of a source document in first tree structured format, the first tree structured format comprising nodes which are ultimately connected with source leaves by paths, and 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 source document being distributed among the source leaves and text content of the target document being distributed among the target leaves;

memory for storing the input source and target leaves;

a processing module which assigns a cost to each of a plurality of matches based on leaf text content and not on the tree structure of the source and target documents, each match being selected from the group consisting of;

a source leaf and a target leaf,

an unmatched source leaf, and

an unmatched target leaf;

a processing module which identifies matches for which a total cost is minimal, wherein each of the leaves is in at least one of the identified matches;

a processing module which identifies, from the identified matches, groups of matches wherein each match in the group has a leaf in common;

a processing module which identifies, 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; and

an output device for outputting an alignment between leaves of the target document and leaves of the source document which includes the identified probable matches.

19. The document alignment apparatus of claim 18, further comprising:

a processing module for subdividing the source and target document into blocks, each block comprising a plurality of target leaves and a plurality of target leaves.

20. The document alignment apparatus of claim 18, further comprising:

a processing module for annotating leaves of at least one of the source and target documents with attributes.