Method and apparatus for iterative merging of documents

• US 20040205539A1
• Filed: 09/07/2001
• Published: 10/14/2004
• Est. Priority Date: 09/07/2001
• Status: Abandoned Application

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Arora, Akhil K., Ong, Herbert T., Mak, Mingchi Stephen
• Application Number:
  US09/949,127
• Publication Number:
  US 20040205539A1
• Time in Patent Office: Days
• US Class Current: 715/511
• CPC Class Codes: G06F 40/194 Calculation of difference between files

Abstract

The present invention is a technique to iteratively merge two or more documents. The documents represent different versions of an original document. After obtaining the documents, the differences between the versions are determined. In one embodiment, the present invention uses a Longest Common Subsequence algorithm to determine modifications necessary to merge the changes made to one document into the other document. The documents are analyzed at various levels of analysis. Thus, segments of a word processing document are analyzed for differences in paragraphs while other segments are analyzed for differences in words. In one embodiment of the present invention, a conflict resolution block resolves conflicts arising from a merge process involving three or more documents. The modifications are merged back into a single document.

Claims

1. A method for the merging of documents, comprising:

obtaining a first document;

obtaining a second document;

compiling a list of modifications, comprising, comparing said first and second documents at a first level of analysis; and

comparing said first and second documents at a second level of analysis, if a difference exists at said first level of analysis;

updating a list of modifications; and

applying said list of modifications to said first document.

2. The method of claim 1, wherein a modification on said list of modifications comprises a record having a modification action and a modification location.

3. The method of claim 2, wherein said modification action is an addition, a deletion, or a change.

4. The method of claim 3, wherein said compiling further comprises:

selecting a modification locus when said modification action is said change;

determining a longest common subsequence of said modification locus in said first document and said second document at a second level of analysis.

5. The method of claim 4, further comprising:

obtaining a third document.

6. The method of claim 5, wherein said compiling further comprises:

determining a longest common subsequence of said first document and said third document at said first level of analysis; and

resolving one or more merge conflicts between one or more modifications necessitated by said second document and said third document.

7. The method of claim 5, wherein said third document is a markup language document.

8. The method of claim 7, wherein said markup language is XML.

9. The method of claim 1, wherein said first and second documents are markup language documents.

10. The method of claim 9, wherein said markup language is XML.

11. A computer program product comprising:

a computer usable medium having computer readable program code embodied therein configured to merge documents, said computer program product comprising;

computer readable code configured to cause a computer to obtain a first document;

computer readable code configured to cause a computer to obtain a second document;

computer readable code configured to cause a computer to compile a list of modifications, comprising, comparing said first and second documents at a first level of analysis; and

comparing the said first and second documents at a second level of analysis, if a difference exists at said first level of analysis;

computer readable code configured to cause a computer to update a list of modifications; and

computer readable code configured to cause a computer to apply said list to said first document.

12. The computer program product of claim 11 wherein a modification on said list of modifications comprises a record including a modification action and a modification location.

13. The computer program product of claim 12 wherein said modification action is an addition, a deletion, or a change.

14. The computer program product of claim 13 wherein said computer readable code configured to cause a computer to compile a list of modifications further comprises:

computer readable code configured to cause a computer to select a modification locus when said modification action is said change;

computer readable code configured to cause a computer to determine a longest common subsequence in said modification locus of said first document and said second document at a second level of analysis.

15. The computer program product of claim 14, wherein said computer readable code configured to cause a computer to merge two or more documents further comprises:

computer readable code configured to cause a computer to obtain a third document.

16. The computer program product of claim 15 wherein said computer readable code configured to cause a computer to compile a list of modifications further comprises:

computer readable code configured to cause a computer to determine a longest common subsequence of said first document and said third document at said first level of analysis; and

computer readable code configured to cause a computer to resolve one or more merge conflicts between one or more modifications necessitated by said second document and said third document.

17. The computer program product of claim 15 wherein said third document is a markup language document.

18. The computer program product of claim 17, wherein said markup language is XML.

19. The computer program product of claim 11 wherein said first and second documents are markup language documents.

20. The computer program product of claim 19, wherein said markup language is XML.

21. A system for merging of documents, comprising:

a first document;

a second document;

a list of modifications means for comparing said first and second documents at a first level of analysis;

means for comparing said first and second documents at a second level of analysis, if a difference exists at said first level of analysis; and

means for updating and applying said list of modifications to said first document.

22. The system of claim 21, wherein a modification on said list of modifications comprises a record having a modification action and a modification location.

23. The system of claim 22, wherein said modification action is an addition, a deletion, or a change.

24. The system of claim 23, wherein said compiling further comprises:

a modification locus means for selection, when said modification action is said change;

a longest common subsequence means for determining said modification locus in said first document and said second document at a second level of analysis.

25. The system of claim 24, further comprising:

a third document.

26. The system of claim 25, further comprising:

a longest common subsequence means for determining in said first document and said third document at said first level of analysis; and

one or more merge conflicts means for resolving between one or more modifications necessitated by said second document and said third document.

27. The system of claim 25, wherein said third document is a markup language document.

28. The system of claim 27, wherein said markup language is XML.

29. The system of claim 21, wherein said first and second documents are markup language documents.

30. The system of claim 29, wherein said markup language is XML.