Automatic visual segmentation of webpages

• US 8,255,793 B2
• Filed: 01/08/2008
• Issued: 08/28/2012
• 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: Chakrabarti, Deepayan, Mital, Manav Ratan, Hajela, Swapnil, Velipasaoglu, Emre
• Primary Examiner(s): STORK, KYLE R
• Application Number:
  US11/971,160
• Publication Number:
  US 20090177959A1
• Time in Patent Office: 1,694 Days
• Field of Search: 715/234, 715/240, 715/241, 715/243, 715/246, 715/247, 715/254, 715/273
• 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 webpage into semantic units, comprising computer-executed steps of:

estimating a target optimal number that represents how many semantic units should be associated with said webpage;

identifying what fraction of said webpage is occupied by a rendered area associated with a node of a DOM tree corresponding to said webpage;

determining whether the fraction multiplied by said target optimal number is below a threshold number; and

in response to determining that said fraction multiplied by said target optimal number is below the threshold number, merging a first semantic unit associated with said node with a second semantic unit associated with a second node into a single semantic unit;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, 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 said threshold number; and

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

3. The method of claim 1, further comprising:

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

4. The method of claim 1, further comprising:

wherein said node and said second node are siblings.

5. The method of claim 1, further comprising:

wherein said node and said second node are not siblings.

12. A non-transitory computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes performance of the method recited in claim 1.

13. A non-transitory computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes performance of the method recited in claim 2.

14. A non-transitory computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes performance of the method recited in claim 3.

15. A non-transitory computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes performance of the method recited in claim 4.

16. A non-transitory computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes performance of the method recited in claim 5.

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

estimating a target optimal number that represents how many semantic units should be associated with said webpage;

identifying what fraction of said webpage is occupied by a rendered area on said webpage, wherein said rendered area corresponds to a semantic unit;

determining whether the fraction multiplied by said target optimal number exceeds a threshold number; and

in response to determining that said fraction multiplied by said target optimal number exceeds said threshold number, dividing said semantic unit into a plurality of semantic units;

wherein the method is performed by one or more computing devices.

7. The method of claim 6, further comprising:

wherein dividing is performed by recursively dividing said semantic unit.

8. The method of claim 6, further comprising:

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

9. The method of claim 6, further comprising:

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

10. The method of claim 6, further comprising:

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

11. The method of claim 6, further comprising:

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

17. A non-transitory computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes performance of the method recited in claim 6.

18. A non-transitory computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes performance of the method recited in claim 7.

19. A non-transitory computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes performance of the method recited in claim 8.

20. A non-transitory computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes performance of the method recited in claim 9.

21. A non-transitory computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes performance of the method recited in claim 10.

22. A non-transitory computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes performance of the method recited in claim 11.