Small form factor web browsing

• US 20040103371A1
• Filed: 11/27/2002
• Published: 05/27/2004
• Est. Priority Date: 11/27/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Wang, Ming-Yu, Chen, Yu, Zhang, Hong Jiang
• Granted Patent: US 7,203,901 B2
• Time in Patent Office: Days
• US Class Current: 715/513
• 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 data structure comprising a web page partitioned into one or more sub-pages each containing a hierarchy of one or more logical blocks, each said logical block being a function of a semantic structure of the markup language of the web page, wherein the hierarchy of the one or more logical blocks of each said sub-page does not correspond to one markup language tree tag.

2. The data structure as defined in claim 1, further comprising:

a thumbnail image of the web page having partitions corresponding to the one or more sub-pages; and

a hyperlink to each said sub-page from a corresponding said partition of the thumbnail image of the web page.

3. The data structure as defined in claim 1, wherein the web page is an HTML document and the data structure further comprises an XPath and an XPointer to store the correspondence between the content in the HTML document and the respective place of each of the one or more logical blocks in the hierarchy of each said sub-page.

4. The data structure as defined in claim 3, further comprising an external XML file for storage of the one or more sub-pages.

5. The data structure as defined in claim 1, wherein each said sub-page has a width less than a predetermined number of pixels.

6. The data structure as defined in claim 1, wherein each said sub-page includes:

any corresponding style information for the corresponding contents thereof;

any hyperlinks to locations within the sub-page (intra-sub-page hyperlinks); and

any hyperlinks to locations on a different said sub-page (inter-sub-page hyperlinks).

7. An XML data structure comprising:

an HTML document representing a web page that is partitioned into one or more sub-pages each containing a hierarchy of one or more logical blocks, each said logical block being a function of a semantic structure of the HTML document, wherein the hierarchy of the one or more logical blocks of each said sub-page does not correspond to one HTML tree tag;

a thumbnail image of the web page having partitions corresponding to the one or more sub-pages;

a hyperlink to each said sub-page from a corresponding said partition of the thumbnail image of the web page; and

an XPath and an XPointer to store the correspondence between the content in the HTML document and the respective place of each of the one or more logical blocks in the hierarchy of each said sub-page.

8. The XML data structure as defined in claim 7, wherein each said sub-page includes any corresponding style information from the HTML document for the corresponding contents thereof.

9. A method comprising:

analyzing a markup language tag tree of a web page to identify peripheral regions around the periphery of the web page and any body regions between the peripheral regions;

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

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

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

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

identifying visual boundaries of the web page from the projection values on each said axis;

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

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

the logical blocks within each said peripheral and body region;

the peripheral regions;

the body regions; and

the visual boundaries.

10. The method as defined in claim 9, wherein the periphery regions comprise header, footer, left, and right regions.

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

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 the 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;

each said markup language tag region has a height and width;

N=a base threshold+F(x);

F(x)=a/(b*x+c);

x=height/width; and

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

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

13. The method as defined in claim 11, wherein:

the base threshold is about=160;

a is about 40,

b is about 20; and

c is about 1.

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

the markup language is HTML;

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

the respective XPath and the XPointer indicators store the correspondence between each said logical block and the content therein.

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

16. The method as defined in claim 9, 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>

.

17. The method as defined in claim 9, 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 said basic semantic unit having a shape.

18. The method as defined in claim 17, 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 the markup language Document Object Model (DOM) tree; and

arranging all the basic nodes in the markup language DOM tree in the order of the 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 the node sequence of the basic node 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 the frequency of the number of times that each said pattern appears in each said symbol string; and

selecting the pattern in each said symbol string with the 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 said symbol string that is adjacent to the selected pattern;

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

BR>

tag, space characters, a <

TD>

tag that contains space characters only, the <

MAP>

tag that contains space characters only, and the <

SCRIPT>

tag that contains space characters only.

19. The method as defined in claim 17, 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;

the tag <

A>

;

the <

MARQUEE>

tag;

the <

SELECT>

tag;

the <

MAP>

tag;

the text nodes; and

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

20. The method as defined in claim 9, 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 said sub-page.

21. The method as defined in claim 9, wherein the generating of the plurality of sub-pages further comprises, for a small form factor device having a screen with a height and a width, selecting for each said sub-page one or more said logical blocks from among those contiguous said logical blocks within each said peripheral and body region that have a width not greater than the width of the screen.

22. The method as defined in claim 9, wherein the generating of the plurality of sub-pages further comprises, selecting for each said sub-page one or more said logical blocks from among those contiguous said logical blocks within each said peripheral and body region that have a height not greater than the height of the screen.

23. The method as defined in claim 9, wherein the generating of the plurality of sub-pages further comprises:

selecting, for each said sub-page, one or more contiguous said logical blocks within each said peripheral and body region having a width less than a predetermined width;

extracting the corresponding contents of the markup language for each selected said logical block;

inserting the extracted said corresponding contents into the respective said sub-page, including;

any corresponding style information for the extracted said corresponding contents;

any intra-sub-page hyperlinks; and

any inter-sub-page hyperlinks.

24. The method as defined in claim 23, wherein said any corresponding style information for the extracted said corresponding contents is extracted by:

for a cascading style sheet;

collecting the corresponding style information from the <

HEADER>

tag using the <

STYLE>

tag or the <

LINK>

tag; and

copying the <

HEADER>

tag of the web page to each said sub-page;

for a style inheritance;

tracing along the parent link of each of the basic nodes in the corresponding markup language; and

collecting all the style information of each parent tag of each said basic node, wherein the style information from ancestor nodes and the node itself are merged as child nodes with higher priority over ancestor nodes.

25. One or more computer-readable media having computer-readable instructions thereon which, when executed by one or more processors, cause the one or more processors to implement the method of claim 9.

26. One or more computer-readable media having computer-readable instructions thereon which, when executed by one or more processors, cause the one or more processors to perform a method comprising:

extracting high level structure information about a web page using markup language tag tree selection rules to define high level boundaries;

extracting low level structure information within each said high level structure information by;

identifying explicit visual boundaries from the properties of the tags of the markup language tag tree;

identifying visual units by boundary detection from the markup language tag tree corresponding to each said high level structure information; and

projecting each visual unit perpendicularly to an axis to identify implicit boundaries between the visual units; and

storing the high level boundaries, the implicit boundaries, and the extracted high and low level structure information of the web page.

27. The one or more computer-readable media as defined in claim 26, wherein the identifying visual units further comprises:

collecting basic nodes from the markup language tag tree corresponding to each said high level structure information;

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 said identified visual unit for implicit boundary detection.

28. The one or more computer-readable media as defined in claim 26, wherein the method further comprises, for a predetermined display screen having a width, identifying a plurality of sub-pages of the web page using the high level boundaries, the implicit boundaries, and the extracted high and low level structure information of the web page, wherein each said sub-page has a width not greater than the width of the predetermined display screen.

29. The one or more computer-readable media as defined in claim 28, wherein the method further comprises:

forming a thumbnail image of the web page having partitions corresponding to the one or more sub-pages;

forming a hyperlink to each said sub-page from a corresponding said partition of the thumbnail image of the web page; and

storing the sub-pages, the thumbnail image, and the hyperlinks using an annotation mechanism.

30. The one or more computer-readable media as defined in claim 29, wherein the method further comprises, for the contents each said sub-page, extracting any style information from the markup language tag tree of the web page for inclusion in the sub-page.

31. A method comprising:

using a markup language tag tree of the web page to extract regions of the web page including a header, a footer, left and right side bar regions, and one or more body regions encompassed by the header region, the footer region, the left side bar region, and the right side bar region;

identifying visual boundaries within each said region by;

the properties of the tags of the markup language tag tree;

projecting normal to an axis each shape represented by one or more semantic units of the tags of the markup language tag tree in each region; and

determining the additional visual boundaries from the projection values on the axis.

32. The method as defined in claim 31, wherein the one or more semantic units of the tags of the markup language tag tree in each region is found by clustering the leaf markup language tags in a pattern detection algorithm.

33. The method as defined in claim 31, further comprising:

for a predetermined display screen, identifying a plurality of sub-pages of the web page using the identified visual boundaries and the regions, where each said sub-page has a width not greater than the width of the predetermined display screen;

forming a thumbnail image of the web page having partitions corresponding to the one or more sub-pages;

forming a hyperlink to each said sub-page from a corresponding said partition of the thumbnail image of the web page; and

storing the sub-pages, the thumbnail image, and the hyperlinks using an annotation mechanism.

34. The method as defined in claim 33, further comprising, for the contents each said sub-page, extracting any style information from the markup language tag tree of the web page for inclusion in the sub-page.

35. One or more computer-readable media having computer-readable instructions thereon which, when executed by one or more processors, cause the one or more processors to implement the method of claim 31.

36. A method comprising:

analyzing a markup language tag tree of a web page to identify;

peripheral regions of the web page including header, footer, left, and right regions; and

one or more body regions adjacent to at least one said peripheral region;

within the markup language tag tree that defines each said peripheral and body region;

identifying visual boundaries given in the properties of the tags of the markup language tag tree; and

identifying blank areas by;

analyzing one or more functions on the basis of a layout structure of each said function by;

configuring each said function into a rectangle;

projecting each rectangle normally onto each of perpendicular axes; and

determining one or more separators that are each normal to the axes as a function of the sum of the projections on each axis.

37. The method as defined in claim 36, further comprising, for a predetermined width of a display screen, identifying a plurality of sub-pages of the web page each having a width not greater than the predetermined width of the display screen and using:

the peripheral regions of the web page including header, footer, left, and right regions;

the one or more body regions adjacent to at least one said peripheral region;

the visual boundaries identified in the properties of the tags of the markup language tag tree; and

the one more separators.

38. The method as defined in claim 37, further comprising:

forming a thumbnail image of the web page having partitions corresponding to the one or more sub-pages;

forming a hyperlink to each said sub-page from a corresponding said partition of the thumbnail image of the web page; and

storing the sub-pages, the thumbnail image, and the hyperlinks using an annotation mechanism.

39. The method as defined in claim 38, further comprising, for the contents each said sub-page, extracting any style information from the markup language tag tree of the web page for inclusion in the sub-page.

40. The method as defined in claim 36, wherein the identifying blank areas further comprises:

processing the markup language tag tree defining each said peripheral and body region to identify therein one or more objects each having one or more properties relating to at least one function thereof; and

analyzing each said object in each said peripheral and body region by;

grouping the object into a shape that contains one or more properties relating to at least one function;

separating each said shape from the other shapes by a separator, wherein each said shape is a rectangle having sides parallel or normal to that of the other rectangles and to the separators;

inserting blanks between the shapes;

projecting each of the shapes onto two perpendicular axes;

quantifying the projections along each said axis; and

identifying each said separator as being normal to each section along each said axis where the quantity of the projections is less than a predetermined threshold.

41. One or more computer-readable media having computer-readable instructions thereon which, when executed by one or more processors, cause the one or more processors to implement the method of claim 36.

42. A computer architecture for use in adapting web content for display on a small form factor device having a display screen with a width, the architecture comprising:

a high level structure analysis module for receiving a web page and analyzing a markup language tag tree of a markup language document representing the web page to identify;

peripheral regions of the web page including header, footer, left, and right regions; and

any body regions enclosed by the peripheral regions;

a low level structure analysis module for analyzing the markup language tag tree defining each said peripheral and body region to;

identify visual boundaries from the properties of the tags of the markup language tag tree;

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

project the shape of each said basic semantic unit normal to perpendicular axes; and

identify visual boundaries of the web page from the projection values on each said axis;

a logical block analysis module for identifying within each said peripheral and body region, from the corresponding tags of the markup language tag tree, each logical block that is adjacent to any of the identified visual boundaries, wherein each said logical block is a function of a semantic structure of a markup language document representing the web page; and

a content adaptation module configured to;

partition the visual boundaries and the logical blocks within each said peripheral and body region into one or more sub-pages each containing a hierarchy of the logical blocks and having a width not greater than the width of the display screen of the small form factor device, each said logical block being a function of a semantic structure of the markup language document representing the web page, wherein the hierarchy of the one or more logical blocks of each said sub-page does not correspond to one tree tag of the markup language;

form a thumbnail image of the web page having partitions corresponding to the one or more sub-pages; and

form a hyperlink to each said sub-page from a corresponding said partition of the thumbnail image of the web page.

43. The architecture as defined in claim 42, wherein the markup language document is an HTML document, and the architecture further comprises a storage module for storing in an XML file having stored therein:

the content of the HTML document corresponding to;

the logical blocks within each said peripheral and body region;

the visual boundaries;

the thumbnail image of the web page having partitions corresponding to the one or more sub-pages;

each said hyperlink to each said sub-page from a corresponding said partition of the thumbnail image of the web page; and

a correspondence between the content in the HTML document and the respective place of each of the one or more logical blocks in the hierarchy of each said sub-page by;

an XPath; and

an XPointer.

44. The architecture as defined in claim 43, further comprising a style module for extracting, for the contents of each said sub-page, any style information from the HTML document of the web page for inclusion in the sub-page.

45. A system comprising:

an interconnected network;

a small form factor client, having a display screen of a predetermined width and being in communication with the interconnected network, for performing the acts comprising;

transmitting a request for all or a portion of a web page to the interconnected network;

receiving a transmission via the interconnected network, wherein the transmission includes the requested all or the portion of the web page; and

displaying the received all or the portion of the web page;

a server, in communication with the small form factor client through the interconnected network, for performing the acts comprising;

using a markup language tag tree of the web page to extract regions of the web page including a header, a footer, left and right side bar regions, and one or more body regions adjacent to one of said header, footer, left or right side bar regions;

identifying visual boundaries within each said region by;

the properties of the tags of the markup language tag tree;

projecting normal to an axis each shape represented by one or more semantic units of the tags of the markup language tag tree in each region; and

determining the additional visual boundaries from the projection values on the axis;

identifying a plurality of sub-pages of the web page using the identified visual boundaries and the regions, where each said sub-page has a width not greater than the predetermined width of the display screen;

forming a thumbnail image of the web page having;

a width not greater than the width of the display screen of the small form factor device; and

partitions corresponding to the one or more sub-pages;

forming a hyperlink to each said sub-page from a corresponding said partition of the thumbnail image of the web page;

storing the sub-pages of the web page, the thumbnail image, and the hyperlinks using an annotation mechanism;

receiving the request for the web page from the small form factor client; and

transmitting a transmission to the small form factor device on the interconnected network that includes at least one selection from the group consisting of;

the thumbnail image of the web page; and

one of the sub-pages.

46. The system as defined in claim 45, wherein:

the identifying a plurality of sub-pages of the web page further comprises, for the contents each said sub-page, extracting any style information from the markup language tag tree of the web page for inclusion in the sub-page; and

the displaying the received all or the portion of the web page further comprises processing of the extracted style information included in the sub-page.

47. The system as defined in claim 45, wherein:

the received all or the portion of the web page displayed by the small form factor device includes the thumbnail image of the web page;

the small form factor client performs further acts comprising;

receiving input that includes one said hyperlink to a corresponding sub-page;

transmitting a second request for the sub-page of the web page to the interconnected network;

receiving a second transmission via the interconnected network, wherein the transmission includes the requested sub-page; and

displaying the received requested sub-page;

the server performs further acts comprising;

receiving the request for the sub-page of the web page from the small form factor client;

retrieving the requested sub-page from the stored sub-pages; and

transmitting the second transmission to the small form factor device on the interconnected network that includes the requested sub-page.

48. The system as defined in claim 45, wherein the transmitting a transmission to the small form factor device on the interconnected network further comprises selecting content for the transmission based upon prior requests received from the small form factor.

49. One or more computer-readable media embodying the system of claim 45.

50. An apparatus comprising:

means for partitioning a markup language document representing a web page into one or more sub-pages; and

means for deriving from the markup language document of the web page a hierarchy of one or more logical blocks for each said sub-page, wherein;

each said logical block of each said sub-page is a function of a semantic structure of the markup language; and

the hierarchy of the one or more logical blocks of each said sub-page does not correspond to one markup language tree tag;

means for generating a thumbnail image of the web page having partitions corresponding to the one or more sub-pages; and

means for associating a hyperlink to each said sub-page from a corresponding said partition of the thumbnail image of the web page.

51. The apparatus as defined in claim 50, wherein:

the markup language document is an HTML document; and

the apparatus further comprises means for storing in a data structure;

the one or more sub-pages;

the hierarchy of one or more logical blocks for each said sub-page;

the thumbnail image of the web page having partitions corresponding to the one or more sub-pages;

the hyperlink to each said sub-page from the corresponding said partition of the thumbnail image of the web page; and

an XPath and an XPointer to store the correspondence between the content in the HTML document and the respective place of each of the one or more logical blocks in the hierarchy of each said sub-page.

52. The apparatus as defined in claim 50, wherein the data structure comprised an external XML file.

53. The apparatus as defined in claim 50, wherein each said sub-page has a width less than a predetermined number of pixels.

54. The apparatus as defined in claim 50, wherein each said sub-page includes:

any corresponding style information for the corresponding contents thereof;

any hyperlinks to locations within the sub-page (intra-sub-page hyperlinks); and

any hyperlinks to locations on a different said sub-page (inter-sub-page hyperlinks).