Extraction of anchor explanatory text by mining repeated patterns

• US 7,627,571 B2
• Filed: 03/31/2006
• Issued: 12/01/2009
• Est. Priority Date: 03/31/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Zhang, Lei, Jing, Feng, Deng, Kefeng
• Primary Examiner(s): Alam; Shahid A
• Assistant Examiner(s): Bromell; Alexandria Y
• Application Number:
  US11/278,289
• Publication Number:
  US 20070239710A1
• Time in Patent Office: 1,341 Days
• Field of Search: 707/6, 715/200, 704/221
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and system for identifying explanatory text for a referenced web page based on a reference to the referenced web page contained in a repeated pattern of a referencing web page is provided. An anchor explanatory text (“AET”) system uses the hierarchical organization of the web page to identify a repeated pattern of hierarchical elements that contain references to other display pages. After the AET system identifies a repeated pattern, it identifies the dominant reference or anchor within each occurrence of the pattern. The AET system uses the explanatory text surrounding a dominant anchor as a description of the referenced web page.

Claims

1. A computing device with a computer-readable storage medium with instructions for identifying explanatory text for a display page, the computer-readable storage medium comprising:

a find repeated patterns component that identifies repeated patterns of elements within a display page by comparing elements of the display page to other elements of the display page, a repeated pattern having an anchor along with text associated, the anchor being an element that includes a reference to a referenced display page, wherein patterns of elements are considered to be repeated when the patterns have the same number of elements and the patterns have an edit distance that is within a threshold;

a find dominant anchor component that finds a dominant anchor within a repeated pattern by

when the repeated pattern includes multiple anchors,

when only one anchor of the repeated pattern contains a block element and has text associated with the anchor, designating that anchor as the dominant anchor; and

when more than one anchor of the repeated pattern contains a block element and has text associated with the anchor, designating no anchor as the dominant anchor;

an extract text component that extracts from a repeated pattern the text associated with the dominant anchor, wherein the extracted text represents explanatory text for the referenced display page; and

wherein

a summarization component generates a summary of a display page from the explanatory text extracted by the extract text component.

2. The computing device of claim 1 wherein a display page is represented as a tag tree with nodes representing elements and the find repeated patterns component identifies a reference explanatory text node as a collection of adjacent, sibling nodes with a subtree of one node containing a reference node with associated text.

3. The computing device of claim 2 wherein the find repeated patterns component identifies a reference explanatory text region as a collection of adjacent, sibling reference explanatory text nodes that have the same length and are similar.

4. The computing device of claim 3 wherein the reference explanatory text nodes are similar when they are within a threshold edit distance.

5. The computing device of claim 4 wherein the threshold edit distance varies based on the number of block nodes within the reference explanatory text nodes.

6. The computing device of claim 2 wherein the extract text component identifies a dominant reference node for each reference explanatory text node.

7. The computing device of claim 6 wherein a reference explanatory text node has a dominant reference node when it has only one reference node that is a block node with a unique subtree structure.

8. The computing device of claim 6 wherein the extract text component extracts explanatory text associated with a reference in a dominant reference node.

9. The computing device of claim 1 wherein a display page is represented as a tag tree with nodes representing elements and the find repeated patterns component identifies a reference explanatory text node as a collection of adjacent, sibling nodes with a subtree of one node containing a reference node with associated text and identifies a reference explanatory text region as a collection of adjacent, sibling reference explanatory text nodes that have the same length and are within a threshold edit distance that varies based on the number of block nodes within the reference explanatory text nodes.

10. The computing device of claim 9 wherein the extract text component identifies a dominant reference node for each reference explanatory text node as its only reference node that is a block node with a unique subtree structure and extracts text associated with a reference in a dominant reference node as explanatory text.

11. A method performed by a computer executing instructions of a computer program for identifying explanatory text for a display page, the method comprising:

identifying repeated patterns of elements within a display page by comparing elements of the display page to other elements of the display page, a repeated pattern having an anchor along with text associated, the anchor being an element that includes a reference to a referenced display page, wherein patterns of elements are considered to be repeated when the patterns have the same number of elements and the patterns have an edit distance that is within a threshold;

finding a dominant anchor within a repeated pattern by

when the repeated pattern includes multiple anchors,

when only one anchor of the repeated pattern contains a block element and has text associated with the anchor, designating that anchor as the dominant anchor; and

when more than one anchor of the repeated pattern contains a block element and has text associated with the anchor, designating no anchor as the dominant anchor;

extracting from a repeated pattern the text associated with the dominant anchor, wherein the extracted text represents explanatory text for the referenced display page; and

generating a summary of a display page based on the extracted explanatory text.

12. The method of claim 11 wherein a display page is represented as a tag tree with nodes representing elements and the identifying of repeated patterns identifies a reference explanatory text node as a collection of adjacent, sibling nodes with a subtree of one node containing a reference node with associated text.

13. The method of claim 12 wherein the identifying of repeated patterns identifies a reference explanatory text region as a collection of adjacent, sibling reference explanatory text nodes that have the same length and are similar.

14. The method of claim 13 wherein the reference explanatory text nodes are similar when they are within a threshold edit distance.

15. The method of claim 14 wherein the threshold edit distance varies based on the number of block nodes within the reference explanatory text nodes.

16. The method of claim 12 wherein the extracting of text identifies a dominant reference node for each reference explanatory text node.

17. The method of claim 16 wherein a reference explanatory text node has a dominant reference node when it has only one reference node that is a block node with a unique subtree structure.

18. The method of claim 16 wherein the extracting of text extracts explanatory text associated with a reference in a dominant reference node.

19. The method of claim 11 wherein a display page is represented as a tag tree with nodes representing elements and the identifying of repeated patterns identifies a reference explanatory text node as a collection of adjacent, sibling nodes with a subtree of one node containing a reference node with associated text and identifies a reference explanatory text region as a collection of adjacent, sibling reference explanatory text nodes that have the same length and are within a threshold edit distance that varies based on the number of block nodes within the reference explanatory text nodes.

20. The method of claim 19 wherein the extracting of text identifies a dominant reference node for each reference explanatory text node as its only reference node that is a block node with a unique subtree structure and extracts text associated with a reference in a dominant reference node as explanatory text.