Data processing and difference computation for generating addressing information

• US 20040088652A1
• Filed: 07/02/2003
• Published: 05/06/2004
• Est. Priority Date: 07/15/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Koyanagi, Teruo, Abe, Mari, Hori, Masahiro, Nakaike, Takuya, Ono, Kohichi
• Granted Patent: US 7,530,014 B2
• Time in Patent Office: Days
• US Class Current: 715/513
• 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

Methods, apparatus and systems to keep a desired element properly addressed in a structured document in which particular elements are addressed, even if the structured document is modified. In an example embodiment, the invention comprises a difference computation unit for computing a difference between structured documents, and an XPath update unit for generating addressing information from addressing information that addresses a part of a particular structured document based on information on the difference computed by the difference computation unit, the generated addressing information addressing a corresponding part of the other structured document.

Claims

3. A difference computation method comprising controlling a computer to compute a difference between at least two tree-structured data items, comprising the steps of

a first step of reading at least two tree-structured data items to be processed from memory to compare the

at least two tree-structured data items, creating an operation sequence, in which each operation for transforming one of the tree-structured data items into the other tree-structured data item is expressed as a combination of predetermined operations on a component of a tree-structure, and storing the list in memory;

and

a second step of reading the operation sequences from the memory and changing operations in the operation sequence that are interpreted as a movement of a component into an operation of moving the component.

4. A difference computation method according to claim 3, wherein the first step comprises creating an operation sequence in which each operation for transforming the tree-structured data is expressed as a combination of operations of inserting, removing, or modifying a node or a subtree of a tree structure.

20. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing difference computation, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 3.

21. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for difference computation, said method steps comprising the steps of claim 3.

5. An addressing information generation system comprising:

a difference computation unit for computing a difference between structured documents; and

an addressing information generation unit for generating addressing information from addressing information that addresses a part of a particular structured document based on information on the difference computed by the difference computation unit, the generated addressing information addressing a corresponding part of the other structured document.

6. An addressing information generation system according to claim 5, further comprising a document analysis unit for analyzing structures of the structured documents and converting the structures into tree-structured data items,

wherein the difference computation unit computes the difference by comparing the tree-structured data items corresponding to the structured documents converted by the document analysis unit.

7. An addressing information generation system according to claim 6, wherein the difference computation unit computes the difference between the tree-structured data items to track a component of the tree-structured data items that is moved in operations for transforming one of the tree-structured data items into the other tree-structured data item.

8. An addressing information generation system according to claim 5, wherein the addressing information is written in XPath.

9. An addressing information generation system according to claim 8, wherein the addressing information generation unit generates an XPath for the other structured document by regenerating LocationSteps forming an XPath for the particular structured document based on the difference between the structured documents and on the XPath for the particular structured document.

10. A program for controlling a computer so that the computer performs data processing for addressing at least one predetermined element in a structured document, the program causing the computer to perform:

first processing of, when the structured document having the element addressed by predetermined addressing information is modified, inputting the structured document to analyze the modification and storing an analysis result in a memory; and

second processing of reading the analysis result from the memory and updating the addressing information according to the analyzed modification so that the addressing information addresses at least one corresponding element in the modified structured document.

11. A program according to claim 10,

wherein the first processing provided by the program comprises the processing of:

converting an unmodified version and a modified version of the structured document into tree-structured data items; and

computing a difference between the tree-structured data items, and

wherein in the second processing provided by the program, the program causes the computer to update the addressing information based on the difference between the tree-structured data items.

12. A program according to claim 11, wherein in the processing of computing the difference provided by the program, the program causes the computer to compute the difference between the tree-structured data items to track a component of the tree-structured data items that is moved in operations required for transformation between the tree-structured data items transformed from one to the other according to modification of the structured document.

13. A program according to claim 10, wherein in the second processing provided by the program, the program causes the computer to update an XPath describing the addressing information by regenerating LocationSteps forming the XPath based on the difference between the unmodified version and the modified version of the structured document.

14. A program for controlling a computer to compute a difference between at least two tree-structured data items, the program causing the computer to perform:

first processing of reading at least two tree-structured data items to be processed from memory to compare the at least two tree-structured data items, creating an operation sequence, in which each operation for transforming one of the tree-structured data items into the other tree-structured data item is expressed as a combination of predetermined operations, on a component of a tree-structure, and storing the list in memory; and

second processing of reading the operation sequences from the memory and changing operations in the operation sequence that are interpreted as a movement of a component into an operation of moving the component.

15. A program according to claim 14, wherein in the second processing provided by the program, the program causes the computer to add an operation of moving a component of the tree-structured data items to the operation sequences in place of a pair of operations of removing and inserting the component in the operation sequences.

16. A program according to claim 14, wherein in the second processing provided by the program, the program causes the computer to replace, based on a predetermined rule, an operation of modifying a component of the tree-structured data items in the operation sequences with a different operation that involves moving the component.

17. An annotation server for managing annotation data made for an HTML/XML document, the annotation server comprising:

difference computation means for computing, when the HTML/XML document for which the annotation data has been made is modified, a difference between an unmodified version and a modified version of the HTML/XML document; and

XPath update means for updating, based on difference information obtained from computation by the difference computation means, an XPath associating the annotation data with a part of the HTML/XML document.

1. A data processing method comprising controlling a computer to address at least one predetermined element in a structured document, comprising the steps of:

when the structured document having said at least one predetermined element addressed by predetermined addressing information is modified, inputting the structured document to analyze the modification and storing an analysis result in a memory;

reading the analysis result from the memory; and

updating the addressing information according to the analyzed modification so that the addressing information addresses at least one corresponding element or corresponding elements in the modified structured document.

2. A data processing method according to claim 1, wherein the step of updating the addressing information comprises updating the addressing information written in XPath.

18. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing data processing, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 1.

19. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for data processing, said method steps comprising the steps of claim 1.

22. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing addressing information generation, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 5.

22-1. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing management of annotation data made for an HTML/XML document, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 17.