Method and apparatus for merging electronic documents containing markup language

• US 7,185,277 B1
• Filed: 10/24/2003
• Issued: 02/27/2007
• Est. Priority Date: 10/24/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jones, Brian, Bernstein, Ethan Joseph, Sawicki, Marcin
• Primary Examiner(s): Bashore; William
• Assistant Examiner(s): RIES, LAURIE ANNE
• Application Number:
  US10/693,347
• Time in Patent Office: 1,222 Days
• Field of Search: 715/513, 715/530
• US Class Current: 715/210
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/194 Calculation of difference between files

Abstract

A method and apparatus are provided for merging two electronic documents, one or both of which contain markup language. The source document and the destination document are compared to identify the matching blocks and the difference blocks. Each of the matching blocks containing a markup language tag for which only a start tag or an end tag has been matched are identified. The identified blocks are then split so that the matched markup language tags are no longer matched. All matching blocks are also split that contain a markup language tag for which either the start tag or the end tag has been matched to a different tag in the other document. Any matching blocks containing markup language tags that would create overlapping tags when merged are then split. The matching and difference blocks are then merged into a merged document in an order that ensures that all markup language tags contained in the merged document are well formed.

Claims

1. A method for merging a source document into a destination document to create a merged document, wherein the source document or the destination document or both contain one or more markup language tags having a start tag or an end tag or both a start tag and an end tag, the method comprising:

comparing the source document and the destination document to identify one or more matching blocks and one or more difference blocks;

splitting all matching blocks that contain a markup language tag for which only a start tag or an end tag has been matched so that the matched markup language tags are no longer matched;

splitting all matching blocks that contain a markup language tag for which either the start tag or the end tag has been matched to a different tag in the other document so that the matched markup language tags are no longer matched;

splitting any matching blocks containing markup language tags that would create overlapping tags when merged; and

merging the matching and difference blocks so that all markup language tags contained in the merged document are well formed by;

copying, for each matching block, text from one of the following;

the source document and the destination document, in the matching block into the merged document,

copying, for each difference block, the text from one of the following;

the source document and the destination document, in the difference block into the merged document if the difference block respectively contains text only from one of the following;

the source document and the destination document, and

copying, for each difference block, the text from the source document and the destination document in the difference block into the merged document if the difference block contains text from both the source document and the destination document wherein the text from the source document is copied to a first section of the merged document and the text from the destination document is copied to a second section of the merged document.

2. The method of claim 1, wherein splitting any matching blocks containing markup language tags that would create overlapping tags when merged comprises for each difference block:

determining whether a markup language tag from the source document has a start tag but not an end tag in the difference block;

in response to determining that the difference block contains a start tag but not an end tag, locating the furthest difference block containing the matching end tag of such a tag in the source document;

identifying an inner range of matching and difference blocks as each of the blocks between the current difference block and the furthest difference block;

identifying an outer range of matching and difference blocks as the current difference block and the furthest difference block and each of the matching and difference blocks in between;

identifying each markup language tag that has a start tag within the inner range and an end tag outside the outer range and, for each identified markup language tag, discarding all matching blocks within the inner range prior to the start tag; and

identifying each markup language tag that has an end tag within the inner range and a start tag outside the outer range and, for each identified markup language tag, discarding all matching blocks within the inner range after the end tag.

3. The method of claim 2, wherein merging the matching and difference blocks so that all markup language tags contained in the merged document are well formed further comprises, for each difference block:

creating a label for each markup language tag that has only either a start tag or an end tag in the difference block, the label comprising a non-zero integer identifying the number of blocks to the difference block containing the matching start or end tag;

creating a sub-block for each distinct label, each sub-block containing the markup language tags and text from either the source or destination document having a corresponding label;

arranging in order each of the sub-blocks, with negative labels first and then positive labels in decreasing order; and

copying text into the merged document from each sub-block, text from the source document being copied just prior to or just after text from the sub-block in the destination document.

4. The method of claim 3, wherein text is copied from each sub-blocks into the merged document in the arranged order.

5. The method of claim 4, wherein text in the sub-block from the source document is copied just prior to text from the sub-block from the destination document if the sub-block has a negative label.

6. The method of claim 5, wherein text in the sub-block from the source document is copied just after text in the sub-block from the destination document if the sub-block has a positive label.

7. The method of claim 6, wherein comparing the source document and the destination document to identify one or more matching blocks and one or more difference blocks comprises:

matching a markup language tag in the source document to a markup language tag in the destination document only if each aspect of the markup language tag in the source document is identical to each aspect of the markup language tag in the destination document.

8. A computer-readable medium which stores a set of instructions which when executed performs a method for merging a source document into a destination document to create a merged document, wherein the source document or the destination document or both contain one or more markup language tags having a start tag or an end tag or both a start tag and an end tag, the method executed by the set of instructions comprising:

comparing the source document and the destination document to identify one or more matching blocks and one or more difference blocks;

splitting all matching blocks that contain a markup language tag for which only a start tag or an end tag has been matched so that the matched markup language tags are no longer matched;

splitting all matching blocks that contain a markup language tag for which either the start tag or the end tag has been matched to a different tag in the other document so that the matched markup language tags are no longer matched;

splitting any matching blocks containing markup language tags that would create overlapping tags when merged; and

merging the matching and difference blocks so that all markup language tags contained in the merged document are well formed by interleaving text from the source document and the destination document into the merged document wherein well formed comprises that each start tag in the markup language tags must have a corresponding end tag and each end tag in the markup language tags must have a corresponding start tag.

9. The computer-readable medium of claim 8, wherein splitting any matching blocks containing markup language tags that would create overlapping tags when merged comprises for each difference block:

determining whether a markup language tag from the source document has a start tag but not an end tag in the difference block;

in response to determining that the difference block contains a start tag but not an end tag, locating the furthest difference block containing the matching end tag of such a tag in the source document;

identifying an inner range of matching and difference blocks as each of the blocks between the current difference block and the furthest difference block;

identifying an outer range of matching and difference blocks as the current difference block and the furthest difference block and each of the matching and difference blocks in between;

identifying each markup language tag that has a start tag within the inner range and an end tag outside the outer range and, for each identified markup language tag, discarding all matching blocks within the inner range prior to the start tag; and

identifying each markup language tag that has an end tag within the inner range and a start tag outside the outer range and, for each identified markup language tag, discarding all matching blocks within the inner range after the end tag.

10. The computer-readable medium of claim 9, wherein merging the matching and difference blocks so that all markup language tags contained in the merged document are well formed further comprises, for each difference block:

creating a label for each markup language tag that has only either a start tag or an end tag in the difference block, the label comprising a non-zero integer identifying the number of blocks to the difference block containing the matching start or end tag;

creating a sub-block for each distinct label, each sub-block containing the markup language tags and text from either the source or destination document having a corresponding label;

arranging in order each of the sub-blocks, with negative labels first and then positive labels in decreasing order; and

copying text into the merged document from each sub-block, text from the source document being copied just prior to or just after text from the sub-block in the destination document.

11. The computer-readable medium of claim 10, wherein text is copied from each sub-blocks into the merged document in the arranged order.

12. The computer-readable medium of claim 11, wherein text in the sub-block from the source document is copied just prior to text from the sub-block from the destination document if the sub-block has a negative label.

13. The computer-readable medium of claim 12, wherein text in the sub-block from the source document is copied just after text in the sub-block from the destination document if the sub-block has a positive label.

14. The computer-readable medium of claim 13, wherein comparing the source document and the destination document to identify one or more matching blocks and one or more difference blocks comprises matching a markup language tag in the source document to a markup language tag in the destination document only if each aspect of the markup language tag in the source document is identical to each aspect of the markup language tag in the destination document.

15. A system for merging a source document into a destination document to create a merged document, wherein the source document or the destination document or both contain one or more markup language tags having a start tag or an end tag or both a start tag and an end tag, the system comprising:

a memory storage for maintaining a database; and

a processing unit coupled to the memory storage, wherein the processing unit is operative to;

compare the source document and the destination document to identify one or more matching blocks and one or more difference blocks;

split all matching blocks that contain a markup language tag for which only a start tag or an end tag has been matched so that the matched markup language tags are no longer matched;

split all matching blocks that contain a markup language tag for which either the start tag or the end tag has been matched to a different tag in the other document so that the matched markup language tags are no longer matched;

split any matching blocks containing markup language tags that would create overlapping tags when merged; and

merge the matching and difference blocks so that all markup language tags contained in the merged document are well formed by interleaving text from the source document and the destination document into the merged document wherein well formed comprising the matching and the difference blocks merged in an order such that no overlapping tags are present in the merged document wherein the processing unit being operative to merge the matching and difference blocks so that all markup language tags contained in the merged document are well formed comprises the processing unit is operative to;

process each matching block and difference block in order,

copy, for each matching block, text from the source or destination document in the matching block into the merged document, and

copy, for each difference block, the text from the source or destination document in the difference block into the merged document if the difference block contains text only from either the source or destination document.

16. The system of claim 15, wherein the processing unit is being operative to split any matching blocks containing markup language tags that would create overlapping tags when merged comprises, for each difference block, the processing unit is operative to:

determine whether a markup language tag from the source document has a start tag but not an end tag in the difference block;

in response to determining that the difference block contains a start tag but not an end tag, locate the furthest difference block containing the matching end tag of such a tag in the source document;

identify an inner range of matching and difference blocks as each of the blocks between the current difference block and the furthest difference block;

identify an outer range of matching and difference blocks as the current difference block and the furthest difference block and each of the matching and difference blocks in between;

identify each markup language tag that has a start tag within the inner range and an end tag outside the outer range and, for each identified markup language tag, discarding all matching blocks within the inner range prior to the start tag; and

identify each markup language tag that has an end tag within the inner range and a start tag outside the outer range and, for each identified markup language tag, discarding all matching blocks within the inner range after the end tag.

17. The system of claim 16, wherein the processing unit being operative to merge the matching and difference blocks so that all markup language tags contained in the merged document are well formed further comprises, for each difference block, the processing unit is operative to:

create a label for each markup language tag that has only either a start tag or an end tag in the difference block, the label comprising a non-zero integer identifying the number of blocks to the difference block containing the matching start or end tag;

create a sub-block for each distinct label, each sub-block containing the markup language tags and text from either the source or destination document having a corresponding label;

arrange in order each of the sub-blocks, with negative labels first and then positive labels in decreasing order; and

copy text into the merged document from each sub-block, text from the source document being copied just prior to or just after text from the sub-block in the destination document.

18. The system of claim 17, wherein text is copied from each sub-blocks into the merged document in the arranged order.

19. The system of claim 18, wherein text in the sub-block from the source document is copied just prior to text from the sub-block from the destination document if the sub-block has a negative label.

20. The system of claim 19, wherein text in the sub-block from the source document is copied just after text in the sub-block from the destination document if the sub-block has a positive label.