AUTOMATIC VISUAL SEGMENTATION OF WEBPAGES

• US 20090177959A1
• Filed: 01/08/2008
• Published: 07/09/2009
• Est. Priority Date: 01/08/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Mital, Manav Ratan, CHAKRABARTI, DEEPAYAN, Hajela, Swapnil, Velipasaoglu, Emre
• Granted Patent: US 8,255,793 B2
• Time in Patent Office: Days
• US Class Current: 715/234
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/131 Fragmentation of text files, e.g. creating reusable text-blocks; Linking to fragments, e.g. using XInclude; Namespaces
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]

Abstract

To provide valuable information regarding a webpage, the webpage must be divided into distinct semantically coherent segments for analysis. A set of heuristics allow a segmentation algorithm to identify an optimal number of segments for a given webpage or any portion thereof more accurately. A first heuristic estimates the optimal number of segments for any given webpage or portion thereof. A second heuristic coalesces segments where the number of segments identified far exceeds the optimal number recommended. A third heuristic coalesces segments corresponding to a portion of a webpage with much unused whitespace and little content. A fourth heuristic coalesces segments of nodes that have a recommended number of segments below a certain threshold into segments of other nodes. A fifth heuristic recursively analyzes and splits segments that correspond to webpage portions surpassing a certain threshold portion size.

Claims

1. A method to divide a portion of a webpage into semantic units, comprising computer-executed steps of:

based on visual aspects of said portion of said webpage, estimating an optimal number of semantic units that said portion of said webpage may be divided into;

based, at least in part on said optimal number, dividing said portion of said webpage into semantic units; and

storing into volatile or non-volatile memory data that indicates the semantic units into which said portion of said webpage is divided.

2. The method of claim 1, further comprising:

wherein said portion of said webpage equals said webpage.

3. The method of claim 1, further comprising:

wherein estimating further comprises examining a size of said portion of said webpage.

4. The method of claim 1, further comprising:

wherein estimating further comprises using a predefined number of semantic units as said optimal number of semantic units.

5. The method of claim 1, further comprising:

wherein said portion of said webpage corresponds to a node on a DOM tree that corresponds to said webpage.

6. The method of claim 1, further comprising:

wherein estimating further comprises considering where on said webpage that said portion of said webpage is located.

7. The method of claim 1, further comprising:

wherein estimating further comprises analyzing an entire website that said webpage is a part of.

26. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

27. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

28. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

29. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

30. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

31. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

32. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

8. A method to divide a webpage into semantic units, comprising computer-executed steps of:

determining a first number that represents how many semantic units are currently associated with a subtree that extends from a first node of a DOM tree corresponding to said webpage;

estimating a second number that represents how many semantic units should be associated with said subtree;

performing a comparison between the first number and the second number; and

in response to the comparison, coalescing into a single semantic unit two or more semantic units currently associated with said subtree.

9. The method of claim 8, further comprising:

wherein coalescing is performed in response to determining that said first number exceeds said second number by a predetermined amount.

10. The method of claim 8, further comprising:

wherein coalescing is performed in response to determining that said first number is greater than said second number.

33. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

34. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

35. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

11. A method to divide a webpage into semantic units, comprising computer-executed steps of:

estimating a size of a rendered area on said webpage corresponding to a node of a DOM tree corresponding to said webpage;

analyzing rendered contents of said rendered area on said webpage; and

based at least in part on said size and said rendered contents, coalescing into a single semantic unit, (a) a semantic unit currently associated with said node, and (b) one or more semantic units.

12. The method of claim 11, further comprising:

wherein coalescing is performed in response to determining that said rendered contents of said rendered area on said webpage is composed mostly of whitespace.

13. The method of claim 11, further comprising:

wherein coalescing is performed in response to determining that a subtree of one or more child nodes of said node of said DOM tree is associated with a number of semantic units beyond a threshold number of semantic units.

14. The method of claim 11, further comprising:

wherein coalescing is performed in response to determining that child nodes of said node of said DOM tree correspond to a second rendered area on said webpage,

wherein said second rendered area is contained within said rendered area; and

wherein said second rendered area is below a threshold area size.

36. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

37. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

38. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.

39. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14.

15. A method to divide a webpage into semantic units, comprising computer-executed steps of:

estimating a number that represents how many semantic units should be associated with a node of a DOM tree corresponding to said webpage;

deciding that said number is below a threshold number; and

in response to deciding, merging a first semantic unit associated with said node with a second semantic unit associated with a second node into a single semantic unit.

16. The method of claim 15, further comprising:

wherein merging is performed by;

searching for said second node in said DOM tree;

estimating a second number that represents how many semantic units should be associated with said second node,

wherein said second number is greater than or equal to one; and

merging said first semantic unit and said second semantic unit into said single semantic unit.

17. The method of claim 15, further comprising:

wherein a subtree of said second node is associated with only one semantic unit.

18. The method of claim 15, further comprising:

wherein said node and said second node are siblings.

19. The method of claim 15, further comprising:

wherein said node and said second node are not siblings.

40. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 15.

41. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 16.

42. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 17.

43. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 18.

44. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 19.

20. A method to divide a webpage into semantic units, comprising computer-executed steps of:

estimating a size of a rendered area on said webpage, wherein said rendered area corresponds to a semantic unit;

determining that said size exceeds a threshold size; and

in response to determining that said size exceeds a threshold size, dividing said semantic unit into a plurality of semantic units.

21. The method of claim 20, further comprising:

wherein dividing is performed by recursively dividing said semantic unit.

22. The method of claim 20, further comprising:

wherein dividing is performed by looking for a significant whitespace between rendered elements on said webpage.

23. The method of claim 20, further comprising:

wherein dividing further comprises examining whether a significant whitespace is vertical or horizontal.

24. The method of claim 20, further comprising:

wherein dividing further comprises examining one or more properties of rendered elements on said webpage on either side of a significant whitespace.

25. The method of claim 20, further comprising:

wherein dividing is performed by applying an optimal segments number estimation heuristic.

45. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 20.

46. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 21.

47. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 22.

48. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 23.

49. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 24.

50. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 25.