Method and apparatus for extraction

• US 7,934,152 B2
• Filed: 06/28/2006
• Issued: 04/26/2011
• 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): Hong; Stephen S
• Assistant Examiner(s): Robinson; Marshon
• Application Number:
  US11/427,299
• Publication Number:
  US 20060242145A1
• Time in Patent Office: 1,763 Days
• Field of Search: 715/242, 715/238, 715/234, 715/202, 715/243
• US Class Current: 715/234
• 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 extracting a clip of a web page on a remote computer system, the method comprising:

prior to the extraction, receiving, in a computer system, selection of a view, wherein the view comprises definition of the clip of the web page including markup language;

storing data from a portion of the web page defining the view in a view repository database;

automatically accessing from the view repository database, at least the data from the portion of the web page defining the view;

automatically accessing, over a computer network, new data from the web page, which has changed, on the remote computer system from which the clip of the web page is to be extracted;

in an extraction engine in a computer system, finding one or more sets of corresponding data of the new data from the web page which has changed, each of one or more sets of corresponding data of the new data from the web page which has changed having a strength of correspondence to the data, accessed from the view repository database, from the portion of the web page defining the view;

determining whether (a) two or more sets of corresponding data of the new data from the web page which has changed are found and (b) whether one of the corresponding sets of data of the new data from the web which has changed has a substantially higher strength of correspondence to the data accessed from the view repository database, from the portion of the web page defining the view, than strengths of correspondence of the other corresponding sets of data of the new data from the web page from which has changed;

if two or more sets of corresponding data of the new data from the web page which has changed are found, then

     1) if one of the corresponding sets of data of the new data from the web which has changed has a substantially higher strength of correspondence to the data accessed from the view repository database, from the portion of the web page defining the view, than strengths of correspondence of the other corresponding sets of data of the new data from the web page from which has changed, then assigning a high measure of quality to the selection of the corresponding data having a higher strength of correspondence to the data accessed from the view repository database, from the portion of the web page defining the view, and

     2) assigning a low measure of quality to the selection of the corresponding data of the new data from the web page which has changed, if at least one of;

2a) none of the corresponding sets of data of the new data from the web page which has changed has a substantially higher strength of correspondence than strengths of correspondence of the other corresponding sets of data of the new data from the web page which has changed, and 2b) if strengths of correspondence of all corresponding sets of data of the new data from the web page which has changed are low;

if the high measure of quality is assigned to one of the corresponding sets of data of the new data from the web page which has changed, then extracting the corresponding set of data from the web page which has changed, as the clip of the web page having the defined clip of the web page;

transmitting, over a computer network to an electronic display device, the extracted corresponding set of new data from the web page which has changed, as the clip of the web page having the defined clip of the web page, whereby a graphical display of the electronic display device renders the extracted corresponding set of new data, as the clip of the web page having the defined clip of the web page.

2. A method of extracting a clip of a web page on a remote computer system, the method comprising:

prior to the extraction, receiving, in a computer system, selection of a view, wherein the view comprises definition of the clip of the web page including markup language;

storing data from a portion of the web page defining the view in a view repository database;

automatically accessing from the view repository database, at least the data from the portion of the web page defining the view;

automatically accessing, over a computer network, new data from the web page, which has changed, on the remote computer system from which the clip of the web page is to be extracted;

in an extraction engine in a computer system, finding one or more sets of corresponding data of the new data from the web page which has changed, each of one or more sets of corresponding data of the new data from the web page which has changed having a strength of correspondence to the data, accessed from the view repository database from the portion of the web page defining the view, the strength of correspondence at least partly determined by an edit sequence between at least part of the new data from the web page which has changed and at least part of the data, accessed from the view repository database, from the portion of the web page defining the view, 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 new data from the web page which has changed and at least part of the data accessed from the view repository database, from the portion of the web page defining the view; and

if two or more sets of corresponding data of the new data from the web page which has changed are found, then

     1) if one of the corresponding sets of data of the new data from the web which has changed has a substantially higher strength of correspondence to the data accessed from the view repository database, from the portion of the web page defining the view than strengths of correspondence of the other corresponding sets of data of the new data from the web page from which has changed, then assigning a high measure of quality to the selection of the corresponding data having a higher strength of correspondence to the data accessed from the view repository database, from the portion of the web page defining the view, 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 of the new data from the web page which has changed, assigning a low measure of quality to the selection of the selected data of the new data from the web page which has changed;

if the high measure of quality is assigned to one of the corresponding sets of data of the new data from the web page which has changed, then extracting the corresponding set of data from the web page which has changed, as the clip of the web page having the defined clip of the web page; and

transmitting, over a computer network to an electronic display device, the extracted corresponding set of new data from the web page which has changed, as the clip of the web page having the defined clip of the web page, whereby a graphical display of the electronic display device renders the extracted corresponding set of new data, as the clip of the web page having the defined clip of the web page.

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

4. The method of claim 2, 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.

5. The method of claim 2, 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.

6. The method of claim 5, 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 5, 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 5, 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 5, 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 5, 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 5, 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 5, 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.

13. The method of claim 2, further comprising:

if two or more corresponding data are found, then;

selecting larger new data from the web page which has changed, at least part of the larger new data from the web page which has changed including a larger subtree in a first tree representation of the first set of data, the larger subtree including the new data from the web page which has changed; and

determining a second edit sequence between at least part of the data accessed from the view repository database, from the portion of the web page defining the view and at least part of a second tree representation of the new data from the web page which has changed, the data accessed from the view repository database, from the portion of the web page defining the view including at least part of the larger new data from the web page which has changed, the second edit sequence including any of insertions, deletions, substitutions, matches, and repetitions.

14. The method of claim 2, wherein one or more of the data accessed from the view repository database, from the portion of the web page defining the view and the new data from the web page which has changed is represented at least partly by a tree.

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

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

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

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

19. The method of claim 2, wherein one or more of data accessed from the view repository database, from the portion of the web page defining the view and the new data from the web page which has changed is represented at least partly by a set of linearized tokens.

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

21. The method of claim 2, 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 new data from the web page which has changed, the corresponding data having a correspondence to the data accessed from the view repository database, from the portion of the web page defining the view, the correspondence at least partly found by determining the pruned edit sequence.

22. A method of extracting a clip of a web page on a remote computer system, the method comprising:

prior to the extraction, receiving, in a computer system, selection of a view, wherein the view comprises definition of the clip of the web page including markup language;

storing data from a portion of the web page defining the view in a view repository database;

automatically accessing from the view repository database, at least the data from the portion of the web page defining the view;

automatically accessing, over a computer network, new data from the web page, which has changed, on the remote computer system from which the clip of the web page is to be extracted;

in an extraction engine in a computer system, finding one or more sets of corresponding data of the new data from the web page which has changed, each of one or more sets of corresponding data of the new data from the web page which has changed having a strength of correspondence to the data, accessed from the view repository database, from the portion of the web page defining the view, the strength of correspondence at least partly determined by a tree-based edit sequence between at least part of the new data from the web page which has changed and at least part of the data, accessed from the view repository database, from the portion of the web page defining the view, 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 new data from the web page which has changed and at least part of the data accessed from the view repository database, from the portion of the web page defining the view;

if two or more sets of corresponding data of the new data from the web page which has changed are found, then

     1) if one of the corresponding sets of data of the new data from the web which has changed has a substantially higher strength of correspondence than strengths of correspondence of the other corresponding sets of data of the new data from the web page from which has changed, then assigning a high measure of quality to the selection of the corresponding data having a higher strength of correspondence to the data accessed from the view repository database, from the portion of the web page defining the view, and

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

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

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

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

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

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

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

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

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

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

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

33. The method of claim 22, further comprising:

if two or more corresponding data are found, then;

selecting larger new data from the web page which has changed, at least part of the larger new data from the web page which has changed including a larger subtree in a first tree representation of the first set of data, the larger subtree including the new data from the web page which has changed; and

determining a second tree-based edit sequence between at least part of the data accessed from the view repository database, from the portion of the web page defining the view and at least part of a second tree representation of the new data from the web page which has changed, the data accessed from the view repository database, from the portion of the web page defining the view including at least part of the larger new data from the web page which has changed, the second tree-based edit sequence including any of insertions, deletions, substitutions, matches, and repetitions.

34. The method of claim 22, wherein one or more of the first set of data and the new data from the web page which has changed is represented at least partly by a tree.

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

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

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

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

39. The method of claim 22, wherein one or more of data accessed from the view repository database, from the portion of the web page defining the view and the new data from the web page which has changed is represented at least partly by a set of linearized tokens.

40. The method of claim 22, 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 new data from the web page which has changed, the corresponding data having a correspondence to the data accessed from the view repository database, from the portion of the web page defining the view, the correspondence at least partly found by determining the pruned tree-based edit sequence.

41. A computer system comprising at least a computer, the computer system for extracting a clip of a web page on a remote computer system, the computer system comprising:

a view repository database for storing data from a portion of the web page defining a view, wherein the view comprises definition of the clip of the web page including markup language;

an engine, in a server coupled to the view repository database, that prior to the extraction, receives a selection of the view and stores data from a portion of the web page defining the view in a view repository database;

an engine, in a server coupled to the view repository database, that automatically accesses from the view repository database, at least the data from the portion of the web page defining the view;

an engine, in a server coupled to the view repository database, that automatically accesses, over a computer network, new data from the web page, which has changed, on the remote computer system from which the clip of the web page is to be extracted; and

an extraction engine, in a server coupled to the view repository database, that

finds one or more sets of corresponding data of the new data from the web page which has changed, each of one or more sets of corresponding data of the new data from the web page which has changed having a strength of correspondence to the data, accessed from the view repository database, from the portion of the web page defining the view;

if two or more sets of corresponding data of the new data from the web page which has changed are found, then

     1) if one of the corresponding sets of data of the new data from the web which has changed has a substantially higher strength of correspondence to the data accessed from the view repository database, from the portion of the web page defining the view, than strengths of correspondence of the other corresponding sets of data of the new data from the web page from which has changed, then assigns a high measure of quality to the selection of the corresponding data having a higher strength of correspondence to the data accessed from the view repository database, from the portion of the web page defining the view, and

     2) assigns a low measure of quality to the selection of the corresponding data of the new data from the web page which has changed, if at least one of;

2a) none of the corresponding sets of data of the new data from the web page which has changed has a substantially higher strength of correspondence than strengths of correspondence of the other corresponding sets of data of the new data from the web page which has changed, and 2b) if strengths of correspondence of all corresponding sets of data of the new data from the web page which has changed are low;

if the high measure of quality is assigned to one of the corresponding sets of data of the new data from the web page which has changed, then extracts the corresponding set of data from the web page which has changed, as the clip of the web page having the defined clip of the web page;

transmits, over a computer network to an electronic display device, the extracted corresponding set of new data from the web page which has changed, as the clip of the web page having the defined clip of the web page, whereby a graphical display of the electronic display device renders the extracted corresponding set of new data, as the clip of the web page having the defined clip of the web page.

42. A computer system comprising at least a computer, the computer system for extracting a clip of a web page on a remote computer system, the computer system comprising:

a view repository database for storing data from a portion of the web page defining a view, wherein the view comprises definition of the clip of the web page including markup language;

an engine, in a server coupled to the view repository database, that prior to the extraction, receives a selection of the view and stores data from a portion of the web page defining the view in a view repository database;

an engine, in a server coupled to the view repository database, that automatically accesses from the view repository database, at least the data from the portion of the web page defining the view;

an engine, in a server coupled to the view repository database, that automatically accesses, over a computer network, new data from the web page, which has changed, on the remote computer system from which the clip of the web page is to be extracted; and

an extraction engine, in a server coupled to the view repository database, that

finds one or more sets of corresponding data of the new data from the web page which has changed, each of one or more sets of corresponding data of the new data from the web page which has changed having a strength of correspondence to the data, accessed from the view repository database, from the portion of the web page defining the view, the strength of correspondence at least partly determined by an edit sequence between at least part of the new data from the web page which has changed and at least part of the data, accessed from the view repository database, from the portion of the web page defining the view, 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 new data from the web page which has changed and at least part of the data accessed from the view repository database, from the portion of the web page defining the view; and

if two or more sets of corresponding data of the new data from the web page which has changed are found, then

     1) if one of the corresponding sets of data of the new data from the web which has changed has a substantially higher strength of correspondence to the data accessed from the view repository database, from the portion of the web page defining the view than strengths of correspondence of the other corresponding sets of data of the new data from the web page from which has changed, then assigning a high measure of quality to the selection of the corresponding data having a higher strength of correspondence to the data accessed from the view repository database, from the portion of the web page defining the view, 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 of the new data from the web page which has changed, assigning a low measure of quality to the selection of the selected data of the new data from the web page which has changed;

if the high measure of quality is assigned to one of the corresponding sets of data of the new data from the web page which has changed, then extracts the corresponding set of data from the web page which has changed, as the clip of the web page having the defined clip of the web page; and

transmits, over a computer network to an electronic display device, the extracted corresponding set of new data from the web page which has changed, as the clip of the web page having the defined clip of the web page, whereby a graphical display of the electronic display device renders the extracted corresponding set of new data, as the clip of the web page having the defined clip of the web page.