Method and Apparatus for Extraction

• US 20060242145A1
• Filed: 06/28/2006
• Published: 10/26/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: Pal, Jaswinder, Yu, Xiang, Wang, Randolph, Krishnamurthy, Arvind
• Granted Patent: US 7,934,152 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 pertains to the field of computer software. More specifically, the present invention relates to one or more of the definition, extraction, delivery, and hyper-linking of clips, for example web clips.

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

finding one or more sets of corresponding data of the second set of data, each of one or more sets of corresponding data having a strength of correspondence to the selected data of the first set of data;

if two or more sets of corresponding data are found, then

     1) if one of the corresponding sets of data has a substantially higher strength of correspondence than strengths of correspondence of the other corresponding sets of data, assigning a high measure of quality to the selection of the selected data, and

     2) assigning a low measure of quality to the selection of the selected data, if at least one of;

2a) none of the corresponding sets of data has a substantially higher strength of correspondence than strengths of correspondence of the other corresponding sets of data, and 2b) if strengths of correspondence of all corresponding sets of data are low.

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

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

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

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

6. 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).

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

8. 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).

9. 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.

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

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

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

13. 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;

finding one or more sets of corresponding data of the second set of data, each of one or more sets of corresponding data having a strength of correspondence to the selected data of the first set of data, the strength of correspondence at least partly determined by an edit sequence between at least part of the second set of data and at least part of the first set of data, the edit sequence including any of insertions, deletions, substitutions, matches, and repetitions, including;

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

if two or more sets of corresponding data are found, then

     1) if one of the corresponding sets of data has a substantially higher strength of correspondence than strengths of correspondence of the other corresponding sets of data, assigning a high measure of quality to the selection of the selected data, and

     2) if none of the corresponding sets of data has a substantially higher strength of correspondence than strengths of correspondence of the other corresponding sets of data, assigning a low measure of quality to the selection of the selected data.

14. The method of claim 13, wherein the edit sequence includes none of insertions, deletions, substitutions, matches, and repetitions.

15. The method of claim 13, wherein the 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.

16. The method of claim 13, wherein the 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.

17. The method of claim 16, 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.

18. The method of claim 16, 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.

19. The method of claim 16, 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.

20. The method of claim 16, 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.

21. The method of claim 16, 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.

22. The method of claim 16, 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.

23. The method of claim 16, 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.

24. The method of claim 16, 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.

25. The method of claim 16, 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.

26. The method of claim 16, 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.

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

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

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

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

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

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

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

34. The method of claim 13, 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.

35. The method of claim 13, 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 second 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 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 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 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.

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

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

38. The method of claim 36, 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.

39. The method of claim 38, 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.

40. The method of claim 36, 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.

41. The method of claim 13, 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.

42. The method of claim 13, wherein the first document and the second document represent different documents.

43. The method of claim 13, wherein the first document and the second document represent a same document.

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

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

46. The method of claim 13, 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.

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;

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

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

if two or more sets of corresponding data are found, then

     1) if one of the corresponding sets of data has a substantially higher strength of correspondence than strengths of correspondence of the other corresponding sets of data, assigning a high measure of quality to the selection of the selected data, and

     2) if none of the corresponding sets of data has a substantially higher strength of correspondence than strengths of correspondence of the other corresponding sets of data, assigning a low measure of quality to the selection of the selected data.

48. The method of claim 47, wherein the tree-based edit sequence includes none of insertions, deletions, substitutions, matches, and repetitions.

49. The method of claim 47, wherein the 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.

50. The method of claim 47, wherein the 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.

51. The method of claim 50, 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.

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 the second document is received if the second document is different from the first document.

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

65. 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).

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

67. 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).

68. 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.

69. 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 second 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 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 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 second 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 second tree-based edit sequence.

70. 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.

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

72. The method of claim 70, 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.

73. The method of claim 72, 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.

74. The method of claim 70, 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.

75. 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.

76. The method of claim 47, wherein the first document and the second document represent different documents.

77. The method of claim 47, wherein the first document and the second document represent a same document.

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

79. The method of claim 47, 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.