Small form factor web browsing

• US 7,873,901 B2
• Filed: 08/18/2006
• Issued: 01/18/2011
• Est. Priority Date: 11/27/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chen, Yu, Ma, Wei-Ying, Wang, Ming-Yu, Zhang, Hong Jiang
• Primary Examiner(s): NGUYEN, CHAU T
• Application Number:
  US11/465,718
• Publication Number:
  US 20060282444A1
• Time in Patent Office: 1,614 Days
• Field of Search: 715205-207, 715232-234, 715/243, 715/247, 715/253, 715/238, 715/251
• US Class Current: 715/234
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents

Abstract

A large web page is analyzed and partitioned into smaller sub-pages so that a user can navigate the web page on a small form factor device. The user can browse the sub-pages to find and read information in the content of the large web page. The partitioning can be performed at a web server, an edge server, at the small form factor device, or can be distributed across one or more such devices. The analysis leverages design habits of a web page author to extract a representation structure of an authored web page. The extracted representation structure includes high level structure using several markup language tag selection rules and low level structure using visual boundary detection in which visual units of the low level structure are provided by clustering markup language tags. User viewing habits can be learned to display favorite parts of a web page.

Claims

1. A method comprising:

analyzing, on a computer, a markup language tag tree of a web page to identify peripheral regions around periphery of the web page and any body regions between the peripheral regions, wherein the peripheral regions comprise header, footer, left, and right regions, the left and right regions are defined, respectively, as being the left and right one third of the web page; and

the header and footer regions are defined, respectively, as being in an upper N and lower N pixels of the web page, wherein;

each of the header and footer regions contains one or more markup language tag regions; and

each markup language tag region has a height and width;

N is a dynamic threshold for the header region determined by a base threshold added to a function of the height of the tag region divided by the width of the tag region;

within the markup language tag tree defining each peripheral and body region;

identifying a first set of visual boundaries from properties of the tags of the markup language tag tree; and

detecting patterns in leaf markup language tags of the markup language tag tree to find one or more basic semantic units each having a shape;

projecting the shape of each basic semantic unit normal to perpendicular axes;

identifying a second set of visual boundaries of the web page from the projection values on each perpendicular axis;

within the markup language tag tree that defines each peripheral and body region, identifying each logical block that is adjacent to any of the first set or the second set of identified visual boundaries; and

storing, using an annotation mechanism, a representation of the web page including;

the logical blocks within each peripheral and body region;

the peripheral regions;

the body regions; and

the visual boundaries.

2. The method as defined in claim 1, wherein:

the header and footer regions are further defined by;

the function of the height of the tag region divided by the width of the tag region, F(x)=a/(b*x+c);

wherein x=height/width; and

the base threshold, a, b and c are constants.

3. The method as defined in claim 2, wherein the width and height of the left and right regions are defined, respectively, as being about 240 pixels and about 150 pixels.

4. The method as defined in claim 2, wherein:

the base threshold is about=160;

a is about 40,

b is about 20; and

c is about 1.

5. The method as defined in claim 1, wherein:

the markup language is HTML;

the annotation mechanism uses XPath and XPointer indicators to recognize a corresponding place of each logical block within each peripheral and body region in a original markup language document of the web page; and

the respective XPath and the XPointer indicators store the correspondence between each logical block and the content therein, enabling the content of the logical block to be extracted.

6. The method as defined in claim 1, wherein the stored representation of the peripheral regions, the body regions, and the visual boundaries are contained in an external XML file.

7. The method as defined in claim 1, wherein for the identifying visual boundaries from the properties of the tags of the markup language tag tree, the tags of the markup language tag tree are selected from the group consisting <

HR>

, <

DIV>

, <

TABLE>

, <

TD>

, and <

IMG>

.

8. The method as defined in claim 1, wherein the detecting patterns in the leaf markup language tags to find a basic semantic unit having a shape further comprises:

collecting basic nodes from the markup language tag tree;

classifying the collected basic nodes;

grouping similar classifications of the collected basic nodes into symbol strings;

detecting and merging adjacent similar patterns in the symbol strings of the classified collected basic nodes to form new symbol strings; and

determining each non-blank symbol in each remaining symbol string to be one basic semantic unit having a shape.

9. The method as defined in claim 8, wherein:

the markup language is HTML;

the collecting basic nodes from the markup language tag tree further comprises;

collecting all of the basic nodes in a markup language Document Object Model (DOM) tree; and

arranging all the basic nodes in the markup language DOM tree in an order of a markup language document sequence;

the classifying the collected basic nodes further comprises classifying the collected basic nodes into categories on basis of text font, size, color and tag properties;

the grouping similar classifications of the collected basic nodes into symbol strings further comprises representing the basic nodes in the same category by a symbol, whereby a node sequence of the basic nodes is changed into a symbol string;

the detecting and merging adjacent similar patterns in the symbol strings of the classified collected basic nodes to form new symbol strings further comprises;

counting up frequency of a number of times that each similar pattern appears in each symbol string; and

selecting a pattern in each symbol string with a highest frequency, wherein the selected pattern has a length, and if the length of the selected pattern;

is greater than 1, grouping the selected pattern into a new symbol string; and

is equal to 1, merging each symbol string that is adjacent to the selected pattern;

any blank symbols in any of the remaining symbol strings are selected from the group consisting of <

BR>

tag, space characters, a <

TD>

tag that contains space characters only, a <

MAP>

tag that contains space characters only, and a <

SCRIPT>

tag that contains space characters only.

10. The method as defined in claim 8, wherein:

the markup language is HTML; and

the basic nodes from the markup language tag tree are selected from the group consisting of;

all the leaf tags of the markup language tag tree;

a <

A>

tag;

a <

MARQUEE>

tag;

a <

SELECT>

tag;

a <

MAP>

tag;

one or more text nodes; and

any tag where a text node is the only child of the tag.

11. The method as defined in claim 1, further comprising generating from the stored representation of the web page:

a plurality of sub-pages; and

a local index page that contains hyperlinks pointing to each sub-page.

12. A computer-readable storage device including computer instructions executable on a computer to perform the acts comprising:

analyzing a markup language tag tree of a web page to identify peripheral regions around periphery of the web page and any body regions between the peripheral regions, wherein the peripheral regions comprise header, footer, left, and right regions, the left and right regions are defined, respectively, as being the left and right one third of the web page; and

the header and footer regions are defined, respectively, as being in an upper N and lower N pixels of the web page, wherein;

each of the header and footer regions contains one or more markup language tag regions; and

each markup language tag region has a height and width;

N is a dynamic threshold for the header region determined by a base threshold added to a function of the height of the tag region divided by the width of the tag region;

within the markup language tag tree defining each peripheral and body region;

identifying a first set of visual boundaries from properties of the tags of the markup language tag tree; and

detecting patterns in leaf markup language tags of the markup language tag tree to find one or more basic semantic units each having a shape;

projecting the shape of each basic semantic unit normal to perpendicular axes;

identifying a second set of visual boundaries of the web page from the projection values on each perpendicular axis;

within the markup language tag tree that defines each peripheral and body region, identifying each logical block that is adjacent to any of the first set or the second set of identified visual boundaries; and

storing, using an annotation mechanism, a representation of the web page including;

the logical blocks within each peripheral and body region;

the peripheral regions;

the body regions; and

the visual boundaries.

13. The computer-readable storage device as defined in claim 12, wherein the header and footer regions are further defined by:

the function of the height of the tag region divided by the width of the tag region, F(x)=a/(b*x+c);

wherein x=height/width; and

the base threshold, a, b and c are constants.

14. The computer-readable storage device as defined in claim 13, wherein the width and height of the left and right regions are defined, respectively, as being about 240 pixels and about 150 pixels.

15. The computer-readable storage device as defined in claim 13, wherein:

the base threshold is about =160;

a is about 40,

b is about 20; and

c is about 1.

16. The computer-readable storage device as defined in claim 12, wherein the detecting patterns in the leaf markup language tags to find a basic semantic unit having a shape further comprises:

collecting basic nodes from the markup language tag tree;

classifying the collected basic nodes;

grouping similar classifications of the collected basic nodes into symbol strings;

detecting and merging adjacent similar patterns in the symbol strings of the classified collected basic nodes to form new symbol strings; and

determining each non-blank symbol in each remaining symbol string to be one basic semantic unit having a shape.

17. The computer-readable storage device as defined in claim 16, wherein:

the markup language is HTML;

the collecting basic nodes from the markup language tag tree further comprises;

collecting all of the basic nodes in markup language Document Object Model (DOM) tree; and

arranging all the basic nodes in the markup language DOM tree in an order of a markup language document sequence;

the classifying the collected basic nodes further comprises classifying the collected basic nodes into categories on the basis of text font, size, color and tag properties;

the grouping similar classifications of the collected basic nodes into symbol strings further comprises representing the basic nodes in the same category by a symbol, whereby a node sequence of the basic nodes is changed into a symbol string;

the detecting and merging adjacent similar patterns in the symbol strings of the classified collected basic nodes to form new symbol strings further comprises;

counting up a frequency of a number of times that each similar pattern appears in each symbol string; and

selecting a pattern in each symbol string with a highest frequency, wherein the selected pattern has a length, and if the length of the selected pattern;

is greater than 1, grouping the selected pattern into a new symbol string; and

is equal to 1, merging each symbol string that is adjacent to the selected pattern;

any blank symbols in any of the remaining symbol strings are selected from the group consisting of a <

BR>

tag, space characters, a <

TD>

tag that contains space characters only, a <

MAP>

tag that contains space characters only, and a <

SCRIPT>

tag that contains space characters only.