EXTRACTION OF ANCHOR EXPLANATORY TEXT BY MINING REPEATED PATTERNS

• US 20070239710A1
• Filed: 03/31/2006
• Published: 10/11/2007
• 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
• Granted Patent: US 7,627,571 B2
• Time in Patent Office: Days
• 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 computer system for identifying explanatory text for a display page, comprising:

a find repeated patterns component that identifies repeated patterns of elements within a display page, a repeated pattern having a reference to a referenced display page along with text associated with the reference; and

an extract text component that extracts from a repeated pattern the text associated with the reference, wherein the extracted text represents explanatory text for the referenced display page.

2. The computer system 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 computer system 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 computer system of claim 3 wherein the reference explanatory text nodes are similar when they are within a threshold edit distance.

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

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

7. The computer system 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 computer system of claim 6 wherein the extract text component extracts explanatory text associated with a reference in a dominant reference node.

9. The computer system of claim 1 including a summarization component that generates a summary of a display page from the explanatory text extracted from the extract text component.

10. The computer system 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.

11. The computer system of claim 10 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.

12. A computer-readable medium containing instructions for controlling a computer system to identify explanatory text for a referenced web page from a referencing web page, by a method comprising:

identifying repeated patterns of elements within the referencing web page, an element of a repeated pattern having a reference to a web page along with text surrounding the reference; and

for each occurrence of a repeated pattern,

identifying a dominant reference to a web page; and

extracting the text surrounding the dominant reference as explanatory text for the referenced web page.

13. The computer-readable medium of claim 12 wherein the elements of the referencing web page are hierarchically organized as nodes and wherein 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 surrounding text.

14. The computer-readable medium of claim 13 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 that are within a threshold edit distance.

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

16. The computer-readable medium of claim 12 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.

17. The computer-readable medium of claim 12 including generating a summary of the referenced web page from the extracted text that surrounds references to the referenced web page.

18. A computer system for identifying explanatory text for a referenced web page from a referencing web page, comprising:

a component that identifies repeated patterns of elements within the referencing web page, an occurrence of a repeated pattern having a reference to a web page along with text surrounding the reference;

a component that identifies a dominant reference for each repeated pattern; and

a component that extracts text surrounding the dominant reference as explanatory text for the referenced web page.

19. The computer system of claim 18 wherein the occurrences of a repeated pattern have a similarity that is within a similarity threshold that varies based on whether an occurrence contains a block element.

20. The computer system of claim 18 wherein elements of the referencing web page are hierarchically organized as nodes and wherein 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 surrounding 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 similar.