Method and apparatus for extracting relevant data

• US 7,103,838 B1
• Filed: 04/04/2002
• Issued: 09/05/2006
• Est. Priority Date: 08/18/2000
• Status: Active Grant

• Current Assignee: Aurea Software Incorporated (ESW Capital, LLC)
• Original Assignee: FirstRain, Inc. (Ignite Technologies Incorporated)
• Inventors: Yu, Xiang, Singh, Jaswinder Pal, Wang, Randolph, Krishnamurthy, Arvind
• Primary Examiner(s): Ali, Mohammad
• Application Number:
  US10/117,783
• Time in Patent Office: 1,615 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205, 715/530, 715/511
• US Class Current: 715/202
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines
• 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

The present invention relates to a method and apparatus for extracting relevant data. A first and a second set of data are accessed. The first set includes selected data. An edit sequence is determined between the first and the second sets, including considering at least repetitions for inclusion in the edit sequence. Corresponding data of the second set have a correspondence to the selected data are found at least partly by determining the edit sequence. A first and a second tree of data are accessed. The first tree includes selected data. An edit sequence is determined between the first and the second trees, including considering at least repetitions for inclusion in the edit sequence. Corresponding data of the second tree have a correspondence to the selected data are found at least partly by determining the edit sequence.

Claims

1. A method of extraction, comprising:

accessing at least a first set of data of a first document, the first document including markup language, wherein the first set of data includes a first selected subset and a second selected subset, such that the second selected subset of data is a subset of the first selected subset of data, the first selected subset at least partly specifying document data, the second selected subset at least partly specifying document data;

accessing at least a second set of data of a second document, the second document including markup language;

determining a first edit sequence between at least part of the first set of data and at least part of the second set of data, the first edit sequence including any of insertions, deletions, substitutions, matches, and repetitions, including;

considering at least repetitions for inclusion in the first edit sequence between at least part of the first set of data and at least part of the second set of data;

finding a first corresponding subset of the second set of data, the first corresponding subset having a correspondence to the first selected subset, the correspondence at least partly found by determining the first edit sequence;

determining a second edit sequence between at least part of the first set of data and at least part of the second set of data, the first set of data including at least part of the first selected subset, the second set of data including at least part of the first corresponding subset, the second edit sequence including any of insertions, deletions, substitutions, matches, and repetitions, including;

considering at least repetitions for inclusion in the second edit sequence between at least part of the first set of data and at least part of the second set of data, the first set of data including at least part of the first selected subset; and

finding a second corresponding subset of the second set of data, the second corresponding subset having a correspondence to the second selected subset, the correspondence at least partly found by determining the second edit sequence;

wherein subsequent sets of data of documents are received, the documents including markup language, document data of the subsequent sets of data are determined by finding corresponding data of the subsequent sets of data, the corresponding data of the subsequent sets correspond to the selected data of earlier sets of data, the corresponding data of the subsequent sets are identified as selected data of the subsequent sets of data, the selected data of the subsequent sets of data at least partly specifying document data, and at least one of selected data of the earlier sets and the selected data of the subsequent data at least partly determine corresponding data of later sets of data, the earlier sets of data are received earlier than the subsequent sets of data, and the later sets of data are received later than the subsequent sets of data.

2. The method of claim 1, wherein at least one of the first edit sequence and the second edit sequence includes none of insertions, deletions, substitutions, matches, and repetitions.

3. The method of claim 1, wherein at least one of the first edit sequence and the second edit sequence includes at least one of one or more insertions, one or more deletions, one or more substitutions, one or more matches, and one or more repetitions.

4. The method of claim 1, wherein at least one of the first edit sequence and the second edit sequence is at least partly determined by calculating a total cost, and each of one or more of insertions, deletions, substitutions, matches, and repetitions is associated with one or more costs.

5. The method of claim 4, wherein the one or more costs are at least partly set to encourage the edit sequence to include one or more matches between at least some markup language from the selected data of the first document and at least some markup language from the second document, the markup language including text-based content and tags.

6. The method of claim 4, wherein a first cost is associated with a first match at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second match at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are set to encourage the first match more than the second match.

7. The method of claim 4, wherein a first cost is associated with a first insertion at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second insertion at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are different.

8. The method of claim 4, wherein a first cost is associated with a first deletion at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second deletion at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are different.

9. The method of claim 4, wherein a first cost is associated with a first substitution at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second substitution at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are different.

10. The method of claim 4, wherein a first cost is associated with a first repetition at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second repetition at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are different.

11. The method of claim 4, wherein a first cost is associated with a first text-based content substitution such that a first length of substituting text-based content is substantially equal to a first length of substituted text-based content, a second cost is associated with a second text-based content substitution such that a second length of substituting text-based content is substantially different from a second length of substituted text-based content, and the first cost and the second cost are set to discourage the second text-based content substitution more than the first text-based content substitution.

12. The method of claim 4, wherein markup language includes at least text-based content and tags, and the one or more costs are at least partly set to discourage substitutions of text-based content for one or more tags.

13. The method of claim 4, wherein markup language includes at least text-based content and tags, and the one or more costs are at least partly set to discourage substitutions of one or more tags for text-based content.

14. The method of claim 4, wherein a first cost is associated with preserving a first tag with unchanged attributes, a second cost is associated with preserving a second tag with one or more changed attributes, and the first cost and the second cost are set to discourage preserving the second tag more than preserving the first tag.

15. The method of claim 1, wherein document data is at least partly from the first document.

16. The method of claim 1, wherein document data is at least partly from the second document.

17. The method of claim 1, wherein the second document is received if the second document is different from the first document.

18. The method of claim 1, wherein the markup language includes at least HTML (Hypertext Markup Language).

19. The method of claim 1, wherein the markup language includes at least one of XML, a subset of XML, and a specialization of XML (eXtensible Markup Language).

20. The method of claim 1, wherein the markup language includes at least WML (Wireless Markup Language).

21. The method of claim 1, wherein the markup language includes at least one of SGML, a subset of SGML, and a specialization of SGML (Standard Generalized Markup Language).

22. The method of claim 1, wherein the markup language includes at least text-based content and tags, the tags detailing one or more of structure of content, semantics of content, and formatting information about text-based content.

23. The method of claim 1, further comprising:

if two or more corresponding data are found, then;

selecting larger selected data, at least part of the larger selected data including a larger subtree in a first tree representation of the first set of data, the larger subtree including the selected data;

determining a third edit sequence between at least part of the first set of data and at least part of a second tree representation of the second set of data, the first set of data including at least part of the larger selected data, the third edit sequence including any of insertions, deletions, and substitutions, including;

considering at least repetitions for inclusion in the third edit sequence between at least part of the first set of data and at least part of the second tree representation of the second set of data;

finding corresponding data of the second set of data, the corresponding data having a correspondence to the larger selected data, the correspondence at least partly found by determining the third edit sequence; and

finding corresponding data of the second set of data, the corresponding data having a correspondence to the selected data, the correspondence at least partly found by determining the third edit sequence.

24. The method of claim 1, wherein one or more of the first set of data and the second set of data is represented at least partly by a tree.

25. The method of claim 24, wherein the edit sequence includes repetitions of subtrees of at least the first tree.

26. The method of claim 24, wherein the edit sequence includes at least two repetitions, the at least two repetitions based on at least one subtree of the first tree, and the at least two repetitions appears in the second tree, and the at least two repetitions include at least a first repetition and a second repetition, and the first repetition has at least one difference from the second repetition.

27. The method of claim 26, wherein each of the at least two repetitions is obtainable from the at least one subtree of the first tree by some sequence of one or more insertions, deletions, substitutions and matches.

28. The method of claim 24, wherein the edit sequence includes at least one of one or more insertions of nodes, one or more insertions of subtrees, one or more deletions of subtrees, one or more deletions of subtrees, one or more substitutions of nodes, one or more substitutions of subtrees, one or more repetitions of nodes, and one or more repetitions of subtrees.

29. The method of claim 1, wherein one or more of the first set of data and the second set of data is represented at least partly by a set of linearized tokens.

30. The method of claim 1, wherein the first document and the second document represent different documents.

31. The method of claim 1, wherein the first document and the second document represent a same document.

32. The method of claim 1, wherein the first document and the second document represent different versions of a same document.

33. The method of claim 1, wherein at least one of the first edit sequence and the second edit sequence includes a tree-based edit sequence.

34. The method of claim 1, wherein at least one of determining the first edit sequence and determining the second edit sequence comprises:

determining at least one edit sequence of forward and backward edit sequences between at least part of a first tree representation of the first set of data and at least part of a second tree representation of the second set of data;

performing at least one of

     1) and

     2);

1a) pruning a relevant subtree from at least part of the first tree representation, the relevant subtree at least partly determined from the forward and backward edit sequences;

1b) determining a pruned edit sequence between the pruned relevant subtree and at least part of the second tree representation;

2a) pruning a relevant subtree from at least part of the second tree representation, the relevant subtree at least partly determined from the forward and backward edit sequences;

2b) determining a pruned edit sequence between at least part of the first tree representation and the pruned relevant subtree; and

finding corresponding data of the second set of data, the corresponding data having a correspondence to the selected data, the correspondence at least partly found by determining the pruned edit sequence.

35. A method of extracting relevant data, comprising:

accessing at least a first set of data of a first document, the first document including markup language, wherein the first set of data includes selected data of the first document, the selected data at least partly specifying document data;

accessing at least a second set of data of a second document, the second document including markup language;

determining a first edit sequence between at least part of the first set of data and at least part of the second set of data, the first edit sequence including any of insertions, deletions, substitutions, matches and repetitions, including;

considering at least repetitions for inclusion in the first edit sequence between at least part of the first set of data and at least part of the second set of data;

finding corresponding data of the second set of data, the corresponding data having a correspondence to the selected data, the correspondence at least partly found by determining the first edit sequence;

if two or more corresponding data are found, then;

selecting larger selected data, at least part of the larger selected data including a larger subtree in a tree representation of the first set of data, the larger subtree including the selected data;

determining a second edit sequence between at least part of the first set of data and at least part of the second set of data, the first set of data including at least part of the larger selected data, the second edit sequence including any of insertions, deletions, substitutions, matches and repetitions, including;

considering at least repetitions for inclusion in the second edit sequence between at least part of the first set of data and at least part of the second set of data;

finding corresponding data of the second set of data, the corresponding data having a correspondence to the larger selected data, the correspondence at least partly found by determining the second edit sequence; and

finding corresponding data of the second set of data, the corresponding data having a correspondence to the selected data, the correspondence at least partly found by determining the second edit sequence;

wherein subsequent sets of data of documents are received, the documents including markup language, document data of the subsequent sets of data are determined by finding corresponding data of the subsequent sets of data, the corresponding data of the subsequent sets correspond to the selected data of earlier sets of data, the corresponding data of the subsequent sets are identified as selected data of the subsequent sets of data, the selected data of the subsequent sets of data at least partly specifying document data, and at least one of selected data of the earlier sets and the selected data of the subsequent data at least partly determine corresponding data of later sets of data, the earlier sets of data are received earlier than the subsequent sets of data, and the later sets of data are received later than the subsequent sets of data.

36. The method of claim 35, wherein document data is at least partly from the first document.

37. The method of claim 35, wherein document data is at least partly from the second document.

38. The method of claim 35, wherein the second document is received if the second document is different from the first document.

39. The method of claim 35, wherein the markup language includes at least HTML (Hypertext Markup Language).

40. The method of claim 35, wherein the markup language includes at least one of XML, a subset of XML, and a specialization of XML (extensible Markup Language).

41. The method of claim 35, wherein the markup language includes at least WML (Wireless Markup Language).

42. The method of claim 35, wherein the markup language includes at least one of SGML, a subset of SGML, and a specialization of SGML (Standard Generalized Markup Language).

43. The method of claim 35, wherein the markup language includes at least text-based content and tags, the tags detailing one or more of structure of content, semantics of content, and formatting information about text-based content.

44. The method of claim 35, wherein the first document and the second document represent different documents.

45. The method of claim 35, wherein the first document and the second document represent a same document.

46. The method of claim 35, wherein the first document and the second document represent different versions of a same document.

47. A method of extraction, comprising:

accessing at least a first set of data of a first document, the first document including markup language, wherein the first set of data includes selected data, the selected data at least partly specifying document data;

accessing at least a second set of data of a second document, the second document including markup language;

determining document data of the second set of data, by finding corresponding data of the second set of data, the corresponding data having a correspondence to the selected data of the first set of data, the correspondence at least partly determined by a first edit sequence between at least part of the first set of data and at least part of the second set of data, the first edit sequence including any of insertions, deletions, substitutions, matches, and repetitions, including;

considering at least repetitions for inclusion in the first edit sequence between at least part of the first set of data and at least part of the second set of data;

identifying the corresponding data of the second set of data as selected data of the second set of data, the selected data at least partly specifying document data;

accessing at least a third set of data of a third document, the third document including markup language; and

determining document data of the third set of data, by finding corresponding data of the third set of data, the corresponding data having a correspondence to at least one of the selected data of the first set of data and the selected data of the second set of data, the correspondence at least partly determined by a second edit sequence between at least part of the third set of data and at least one of at least part of the first set of data and at least part of the second set of data, the second edit sequence including any of insertions, deletions, substitutions, matches, and repetitions, including;

considering at least repetitions for inclusion in the second edit sequence between at least part of the third set of data and at least one of at least part of the first set of data and at least part of the second set of data;

wherein subsequent sets of data of documents are received, the documents including markup language, document data of the subsequent sets of data are determined by finding corresponding data of the subsequent sets of data, the corresponding data of the subsequent sets correspond to the selected data of earlier sets of data, the corresponding data of the subsequent sets are identified as selected data of the subsequent sets of data, the selected data of the subsequent sets of data at least partly specifying document data, and at least one of selected data of the earlier sets and the selected data of the subsequent data at least partly determine corresponding data of later sets of data, the earlier sets of data are received earlier than the subsequent sets of data, and the later sets of data are received later than the subsequent sets of data.

48. The method of claim 47, wherein at least one of the first edit sequence and the second edit sequence includes none of insertions, deletions, substitutions, matches, and repetitions.

49. The method of claim 47, wherein at least one of the first edit sequence and the second edit sequence includes at least one of one or more insertions, one or more deletions, one or more substitutions, one or more matches, and one or more repetitions.

50. The method of claim 47, wherein at least one of the first edit sequence and the second edit sequence is at least partly determined by calculating a total cost, and each of one or more of insertions, deletions, substitutions, matches, and repetitions is associated with one or more costs.

51. The method of claim 50, wherein the one or more costs are at least partly set to encourage the edit sequence to include one or more matches between at least some markup language from the selected data of the first document and at least some markup language from the second document, the markup language including text-based content and tags.

52. The method of claim 50, wherein a first cost is associated with a first match at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second match at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are set to encourage the first match more than the second match.

53. The method of claim 50, wherein a first cost is associated with a first insertion at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second insertion at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are different.

54. The method of claim 50, wherein a first cost is associated with a first deletion at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second deletion at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are different.

55. The method of claim 50, wherein a first cost is associated with a first substitution at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second substitution at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are different.

56. The method of claim 50, wherein a first cost is associated with a first repetition at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second repetition at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are different.

57. The method of claim 50, wherein a first cost is associated with a first text-based content substitution such that a first length of substituting text-based content is substantially equal to a first length of substituted text-based content, a second cost is associated with a second text-based content substitution such that a second length of substituting text-based content is substantially different from a second length of substituted text-based content, and the first cost and the second cost are set to discourage the second text-based content substitution more than the first text-based content substitution.

58. The method of claim 50, wherein markup language includes at least text-based content and tags, and the one or more costs are at least partly set to discourage substitutions of text-based content for one or more tags.

59. The method of claim 50, wherein markup language includes at least text-based content and tags, and the one or more costs are at least partly set to discourage substitutions of one or more tags for text-based content.

60. The method of claim 50, wherein a first cost is associated with preserving a first tag with unchanged attributes, a second cost is associated with preserving a second tag with one or more changed attributes, and the first cost and the second cost are set to discourage preserving the second tag more than preserving the first tag.

61. The method of claim 47, wherein document data is at least partly from the first document.

62. The method of claim 47, wherein document data is at least partly from the second document.

63. The method of claim 47, wherein document data is at least partly from the third document.

64. The method of claim 47, wherein the second document is received if the second document is different from the first document.

65. The method of claim 47, wherein the markup language includes at least HTML (Hypertext Markup Language).

66. The method of claim 47, wherein the markup language includes at least one of XML, a subset of XML, and a specialization of XML (eXtensible Markup Language).

67. The method of claim 47, wherein the markup language includes at least WML (Wireless Markup Language).

68. The method of claim 47, wherein the markup language includes at least one of SGML, a subset of SGML, and a specialization of SGML (Standard Generalized Markup Language).

69. The method of claim 47, wherein the markup language includes at least text-based content and tags, the tags detailing one or more of structure of content, semantics of content, and formatting information about text-based content.

70. The method of claim 47, further comprising:

if two or more corresponding data are found, then;

selecting larger selected data, at least part of the larger selected data including a larger subtree in a first tree representation of the first set of data, the larger subtree including the selected data;

determining a third edit sequence between at least part of the first set of data and at least part of a second tree representation of the second set of data, the first set of data including at least part of the larger selected data, the third edit sequence including any of insertions, deletions, substitutions, matches, and repetitions, including;

considering at least repetitions for inclusion in the third edit sequence between at least part of the first set of data and at least part of the second tree representation of the second set of data;

finding corresponding data of the second set of data, the corresponding data having a correspondence to the larger selected data, the correspondence at least partly found by determining the third edit sequence; and

finding corresponding data of the second set of data, the corresponding data having a correspondence to the selected data, the correspondence at least partly found by determining the third edit sequence.

71. The method of claim 47, wherein one or more of the first set of data and the second set of data is represented at least partly by a tree.

72. The method of claim 71, wherein the edit sequence includes repetitions of subtrees of at least the first tree.

73. The method of claim 71, wherein the edit sequence includes at least two repetitions, the at least two repetitions based on at least one subtree of the first tree, and the at least two repetitions appears in the second tree, and the at least two repetitions include at least a first repetition and a second repetition, and the first repetition has at least one difference from the second repetition.

74. The method of claim 73, wherein each of the at least two repetitions is obtainable from the at least one subtree of the first tree by some sequence of one or more insertions, deletions, substitutions and matches.

75. The method of claim 71, wherein the edit sequence includes at least one of one or more insertions of nodes, one or more insertions of subtrees, one or more deletions of subtrees, one or more deletions of subtrees, one or more substitutions of nodes, one or more substitutions of subtrees, one or more repetitions of nodes, and one or more repetitions of subtrees.

76. The method of claim 47, wherein one or more of the first set of data and the second set of data is represented at least partly by a set of linearized tokens.

77. The method of claim 47, wherein at least two of the first document, the second document, and the third document represent different documents.

78. The method of claim 47, wherein at least two of the first document, the second document, and the third document represent a same document.

79. The method of claim 47, wherein at least two of the first document, the second document, and the third document represent different versions of a same document.

80. The method of claim 47, wherein at least one of the first edit sequence and the second edit sequence includes a tree-based edit sequence.

81. The method of claim 47, wherein determining the edit sequence comprises:

determining at least one edit sequence of forward and backward edit sequences between at least part of a first tree representation of the first set of data and at least part of a second tree representation of the second set of data;

performing at least one of

     1) and

     2);

1a) pruning a relevant subtree from at least part of the first tree representation, the relevant subtree at least partly determined from the forward and backward edit sequences;

1b) determining a pruned edit sequence between the pruned relevant subtree and at least part of the second tree representation;

2a) pruning a relevant subtree from at least part of the second tree representation, the relevant subtree at least partly determined from the forward and backward edit sequences;

2b) determining a pruned edit sequence between at least part of the first tree representation and the pruned relevant subtree; and

finding corresponding data of the second set of data, the corresponding data having a correspondence to the selected data, the correspondence at least partly found by determining the pruned edit sequence.

82. A method of extraction, comprising:

accessing at least a first set of data of a first document, the first document including markup language, wherein the first set of data includes selected data, the selected data at least partly specifying document data;

accessing at least a second set of data of a second document, the second document including markup language;

determining document data of the second set of data, by finding corresponding data of the second set of data, the corresponding data having a correspondence to the selected data of the first set of data, the correspondence at least partly determined by a first tree-based edit sequence between at least part of the first set of data and at least part of the second set of data, the first tree-based edit sequence including any of insertions, deletions, substitutions, matches, and repetitions, including;

considering at least repetitions for inclusion in the first tree-based edit sequence between at least part of the first set of data and at least part of the second set of data;

identifying the corresponding data of the second set of data as selected data of the second set of data, the selected data at least partly specifying document data;

accessing at least a third set of data of a third document, the third document including markup language; and

determining document data of the third set of data, by finding corresponding data of the third set of data, the corresponding data having a correspondence to at least one of the selected data of the first set of data and the selected data of the second set of data, the correspondence at least partly determined by a second tree-based edit sequence between at least part of the third set of data and at least one of at least part of the first set of data and at least part of the second set of data, the second tree-based edit sequence including any of insertions, deletions, substitutions, matches, and repetitions, including;

considering at least repetitions for inclusion in the second tree-based edit sequence between at least part of the third set of data and at least one of at least part of the first set of data and at least part of the second set of data;

wherein subsequent sets of data of documents are received, the documents including markup language, document data of the subsequent sets of data are determined by finding corresponding data of the subsequent sets of data, the corresponding data of the subsequent sets correspond to the selected data of earlier sets of data, the corresponding data of the subsequent sets are identified as selected data of the subsequent sets of data, the selected data of the subsequent sets of data at least partly specifying document data, and at least one of selected data of the earlier sets and the selected data of the subsequent data at least partly determine corresponding data of later sets of data, the earlier sets of data are received earlier than the subsequent sets of data, and the later sets of data are received later than the subsequent sets of data.

83. The method of claim 82, wherein at least one of the first tree-based edit sequence and the second tree-based edit sequence includes none of insertions, deletions, substitutions, matches, and repetitions.

84. The method of claim 82, wherein at least one of the first tree-based edit sequence and the second tree-based edit sequence includes at least one of one or more insertions, one or more deletions, one or more substitutions, one or more matches, and one or more repetitions.

85. The method of claim 82, wherein at least one of the first tree-based edit sequence and the second tree-based edit sequence is at least partly determined by calculating a total cost, and each of one or more of insertions, deletions, substitutions, matches, and repetitions is associated with one or more costs.

86. The method of claim 85, wherein the one or more costs are at least partly set to encourage the tree-based edit sequence to include one or more matches between at least some markup language from the selected data of the first document and at least some markup language from the second document, the markup language including text-based content and tags.

87. The method of claim 85, wherein a first cost is associated with a first match at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second match at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are set to encourage the first match more than the second match.

88. The method of claim 85, wherein a first cost is associated with a first insertion at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second insertion at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are different.

89. The method of claim 85, wherein a first cost is associated with a first deletion at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second deletion at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are different.

90. The method of claim 85, wherein a first cost is associated with a first substitution at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second substitution at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are different.

91. The method of claim 85, wherein a first cost is associated with a first repetition at a first distance from a root of a tree representation of some set of data, a second cost is associated with a second repetition at a second distance from a root of a tree representation of some set of data, the first distance is less than the second distance, and the first cost and the second cost are different.

92. The method of claim 85, wherein a first cost is associated with a first text-based content substitution such that a first length of substituting text-based content is substantially equal to a first length of substituted text-based content, a second cost is associated with a second text-based content substitution such that a second length of substituting text-based content is substantially different from a second length of substituted text-based content, and the first cost and the second cost are set to discourage the second text-based content substitution more than the first text-based content substitution.

93. The method of claim 85, wherein markup language includes at least text-based content and tags, and the one or more costs are at least partly set to discourage substitutions of text-based content for one or more tags.

94. The method of claim 85, wherein markup language includes at least text-based content and tags, and the one or more costs are at least partly set to discourage substitutions of one or more tags for text-based content.

95. The method of claim 85, wherein a first cost is associated with preserving a first tag with unchanged attributes, a second cost is associated with preserving a second tag with one or more changed attributes, and the first cost and the second cost are set to discourage preserving the second tag more than preserving the first tag.

96. The method of claim 82, wherein document data is at least partly from the first document.

97. The method of claim 82, wherein document data is at least partly from the second document.

98. The method of claim 82, wherein document data is at least partly from the third document.

99. The method of claim 82, wherein the second document is received if the second document is different from the first document.

100. The method of claim 82, wherein the markup language includes at least HTML (Hypertext Markup Language).

101. The method of claim 82, wherein the markup language includes at least one of XML, a subset of XML, and a specialization of XML (extensible Markup Language).

102. The method of claim 82, wherein the markup language includes at least WML (Wireless Markup Language).

103. The method of claim 82, wherein the markup language includes at least one of SGML, a subset of SGML, and a specialization of SGML (Standard Generalized Markup Language).

104. The method of claim 82, wherein the markup language includes at least text-based content and tags, the tags detailing one or more of structure of content, semantics of content, and formatting information about text-based content.

105. The method of claim 82, further comprising:

if two or more corresponding data are found, then;

selecting larger selected data, at least part of the larger selected data including a larger subtree in a first tree representation of the first set of data, the larger subtree including the selected data;

determining a third tree-based edit sequence between at least part of the first set of data and at least part of a second tree representation of the second set of data, the first set of data including at least part of the larger selected data, the third tree-based edit sequence including any of insertions, deletions, substitutions, matches, and repetitions, including;

considering at least repetitions for inclusion in the third tree-based edit sequence between at least part of the first set of data and at least part of the second tree representation of the second set of data;

finding corresponding data of the second set of data, the corresponding data having a correspondence to the larger selected data, the correspondence at least partly found by determining the third tree-based edit sequence; and

finding corresponding data of the second set of data, the corresponding data having a correspondence to the selected data, the correspondence at least partly found by determining the third tree-based edit sequence.

106. The method of claim 82, wherein one or more of the first set of data and the second set of data is represented at least partly by a tree.

107. The method of claim 106, wherein the edit sequence includes repetitions of subtrees of at least the first tree.

108. The method of claim 106, wherein the edit sequence includes at least two repetitions, the at least two repetitions based on at least one subtree of the first tree, and the at least two repetitions appears in the second tree, and the at least two repetitions include at least a first repetition and a second repetition, and the first repetition has at least one difference from the second repetition.

109. The method of claim 108, wherein each of the at least two repetitions is obtainable from the at least one subtree of the first tree by some sequence of one or more insertions, deletions, substitutions and matches.

110. The method of claim 106, wherein the edit sequence includes at least one of one or more insertions of nodes, one or more insertions of subtrees, one or more deletions of subtrees, one or more deletions of subtrees, one or more substitutions of nodes, one or more substitutions of subtrees, one or more repetitions of nodes, and one or more repetitions of subtrees.

111. The method of claim 82, wherein one or more of the first set of data and the second set of data is represented at least partly by a set of linearized tokens.

112. The method of claim 82, wherein at least two of the first document, the second document, and the third document represent different documents.

113. The method of claim 82, wherein at least two of the first document, the second document, and the third document represent a same document.

114. The method of claim 82, wherein at least two of the first document, the second document, and the third document represent different versions of a same document.

115. The method of claim 82, wherein determining the tree-based edit sequence comprises:

determining at least one tree-based edit sequence of forward and backward edit sequences between at least part of a first tree representation of the first set of data and at least part of a second tree representation of the second set of data;

performing at least one of

     1) and

     2);

1a) pruning a relevant subtree from at least part of the first tree representation, the relevant subtree at least partly determined from the forward and backward edit sequences;

1b) determining a pruned tree-based edit sequence between the pruned relevant subtree and at least part of the second tree representation;

2a) pruning a relevant subtree from at least part of the second tree representation, the relevant subtree at least partly determined from the forward and backward edit sequences;

2b) determining a pruned tree-based edit sequence between at least part of the first tree representation and the pruned relevant subtree; and

finding corresponding data of the second set of data, the corresponding data having a correspondence to the selected data, the correspondence at least partly found by determining the pruned tree-based edit sequence.