Document re-authoring systems and methods for providing device-independent access to the world wide web

• US 6,857,102 B1
• Filed: 01/29/1999
• Issued: 02/15/2005
• Est. Priority Date: 04/07/1998
• Status: Expired due to Fees

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Girgensohn, Andreas, Schilit, William N., Bickmore, Timothy W., Sullivan, Joseph W.
• Primary Examiner(s): Hong, Stephen S.
• Assistant Examiner(s): HUYNH, THU V
• Application Number:
  US09/239,295
• Time in Patent Office: 2,209 Days
• Field of Search: 707/501, 707/500, 707/513, 707/511, 707/516, 707/530, 707/501.1, 715/501.1, 715/513, 715/530, 715/523
• US Class Current: 715/205
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/151 Transformation
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149

Abstract

An automatic re-authoring system and method re-author a document originally designed for display on a desktop computer screen for display on a smaller display screen, such as those used with a PDA or a cellular telephone. The automatic re-authoring system and method input a document to be re-authored and re-authoring parameters, such as display screen size, default font and the like. The automatic re-authoring system and method convert the document into a number of pages, where each page is fully displayable with only at most a minimal amount of scrolling on the display screen of the PDA or cellular phone. At each stage of the re-authoring, a number of different transformations are applied to the original document or a selected re-authored page. The selected re-authored page is the best page resulting from the previous re-authoring stage. The best page at each stage is determined based on the re-authoring parameters and the content of the document being re-authored.

Claims

1. A method for automatically re-authoring a document, comprising:

parsing the document;

transforming the parsed document, using one of a plurality of transforms, into a transformed document;

generating an evaluation value from the transformed document;

determining if the evaluation value meets at least one evaluation criterion;

if the evaluation value for the transformed document does not meet the at least one criterion, repeating the transforming, generating and determining steps using a different one of the plurality of transforms; and

if the evaluation value for the transformed document meets the at least one criterion, outputting the transformed document.

2. The method of claim 1, wherein outputting the transformed document comprises transmitting the transformed document to a display device.

3. The method of claim 2, wherein the display device has a display area that is less than the display area of a desktop monitor.

4. The method of claim 1, wherein parsing the document comprises generating an abstract syntax tree from the document.

5. The method of claim 4, wherein transforming the parsed document comprises transforming the abstract syntax tree into at least one transformed abstract syntax tree.

6. The method of claim 1, wherein transforming the parsed document comprises:

selecting a transform from the plurality of transforms;

determining if the selected transform can properly be applied to the parsed document;

if the selected transform can properly be applied, transforming the parsed document into the transformed document using the selected transform; and

if the selected transform cannot properly be applied, repeating the selecting and determining steps for a different one of the plurality of transforms.

7. The method of claim 6, wherein determining if the selected transform can properly be applied to the parsed document comprises determining if the selected transform is inconsistent with a previously-applied transform.

8. The method of claim 6, wherein determining if the selected transform can properly be applied to the parsed document comprises determining if the parsed document meets application criteria for the selected transform.

9. The method of claim 6, wherein transforming the parsed document into the transformed document using the selected transform comprises at least one of outlining sections of the document, removing content from the document, reducing a size of at least one image within the document and summarizing text within the document.

10. The method of claim 1, wherein, if no transform results in a transformed document that has an evaluation value that meets the at least one evaluation criterion, the method further comprises:

selecting the transformed document having the evaluation value that most closely meets the evaluation value; and

repeating the transforming, generating and determining steps on the selected transformed document using an additional transform.

11. The method of claim 1, wherein transforming the document into the transformed document comprises at least one of outlining sections of the document, removing contentless portions from the document;

removing content from the document, reducing a size of at least one image within the document and summarizing text within the document.

12. The method of claim 11, wherein outlining sections of the document comprises:

identifying sections within the document

identifying a section header and a document portion for each section;

placing each identified document portion into a separate subpage;

removing the identified document portions from the parsed document to form a transformed document containing only the identified sections headers;

converting each of the identified section headers into a link to the corresponding subpage; and

linking the separate subpages together and to the transformed document.

13. The method of claim 12, wherein identifying the sections comprises identifying text blocks within the document.

14. The method of claim 13, wherein identifying the section header and document portion within the text block comprises selecting a representative text string of the text block as the section header and the text block as the document portion.

15. The method of claim 14, wherein the text string is at least a portion of a first sentence of the text block.

16. The method of claim 14, wherein the text string is section header of the text block.

17. The method of claim 11, wherein removing contentless portions from the document comprises replacing sequences of page breaks or paragraph breaks with a single page break or paragraph break.

18. The method of claim 11, wherein removing contentless portions from the document comprises removing formatting from the document.

19. The method of claim 18, wherein removing formatting from the document comprises at least one of removing indenting from the document;

converting text strings of the document to at least one of a single font and font size, removing bullets from the document, removing background space from the document and removing banner images from the document.

20. The method of claim 19, wherein removing banner images from the document further comprises replacing the banner images with corresponding text links.

21. The method of claim 11, wherein reducing a size of at least one image within the document comprises:

identifying at least one image within the document

placing each identified image into a separate subpage;

generating a reduced version of each identified image;

removing each identified image from the document and inserting the reduced version of each removed image to form the transformed document; and

adding, for each removed image, a link into the reduced version of that image to the subpage containing that removed image.

22. The method of claim 1 wherein removing content from the document comprises at least one of removing at least one image from the document and removing at least one table cell from the document.

23. The method of claim 22, wherein removing at least one image from the document comprises one of removing all images from the document, removing all but the first image from the document, and removing all but the first and last images from the document.

24. The method of claim 23, wherein removing all images from the document comprises:

identifying each image in the document;

adding each identified image to a separate subpage; and

replacing each identified image with a link to the corresponding subpage to form the transformed document.

25. The method of claim 24, further comprising linking the separate subpages for each identified image together.

26. The method of claim 24, wherein each link includes one of a text string associated with that identified image and a predetermined icon representing an image.

27. The method of claim 26, wherein the text string associated with that identified image is obtained from hypertext information associated with that identified image.

28. The method of claim 23, wherein removing all images from the document comprises:

identifying each image in the document;

adding each identified image to a separate subpage;

replacing the first identified image with a link to the corresponding subpage to form the transformed document;

removing any other identified images from the transformed page; and

linking the separate subpages together.

29. The method of claim 28, wherein the link includes one of a text string associated with that identified image and a predetermined icon representing an image.

30. The method of claim 9, wherein the text string associated with that identified image is obtained from hypertext information associated with that identified image.

31. The method of claim 23, wherein removing all but the first image from the document comprises:

identifying each image in the document except the first image;

adding each identified image to a separate subpage; and

replacing each identified image with a link to the corresponding subpage to form the transformed document.

32. The method of claim 31, further comprising linking the separate subpages for each identified image together.

33. The method of claim 31, wherein each link includes one of a text string associated with that identified image and a predetermined icon representing an image.

34. The method of claim 33, wherein the text string associated with that identified image is obtained from hypertext information associated with that identified image.

35. The method of claim 23, wherein removing all but the first image from the document comprises:

identifying each image in the document except the first image;

adding each identified image to a separate subpage;

adding a link to one of the separate subpages to the first image to form the transformed document;

removing the identified images from the transformed page; and

linking the separate subpages together.

36. The method of claim 23, wherein removing all but the first and last images from the document comprises:

identifying each image in the document except the first image and the last image;

adding each identified image to a separate subpage; and

replacing each identified image with a link to the corresponding subpage to form the transformed document.

37. The method of claim 36, further comprising linking the separate subpages for each identified image together.

38. The method of claim 36, wherein each link includes one of a text string associated with that identified image and a predetermined icon representing an image.

39. The method of claim 38, wherein the text string associated with that identified image is obtained from hypertext information associated with that identified image.

40. The method of claim 23, wherein removing all but the first and last images from the document comprises:

identifying each image in the document except the first image and the last image;

adding each identified image to a separate subpage;

adding a first link to one of the separate subpages to the first image and a second link to one of the separate subpages to the last image to form the transformed document;

removing the identified images from the transformed page; and

linking the separate subpages together.

41. The method of claim 22, wherein removing at least one table cell from the document comprises:

determining if the table contains any sidebars of links;

if the table contains any sidebars, converting the sidebars into a list of links as a last cell of the table;

identifying all but the first cell of the table;

adding each identified cell to a separate subpage;

replacing the table with the first cell to form the transformed document; and

linking the separate subpages together and to the transformed document.

42. The method of claim 41, wherein, for each cell, adding that cell into a separate subpage comprises:

determining if that cell is a nested table;

if that cell is not a nested table, adding that cell to the separate subpage; and

if that cell is a nested table, repeating the determining, converting, identifying, adding, replacing and linking steps of claim 41.

43. The method of claim 22, wherein removing at least one table cell from the document comprises:

determining if the table contains any sidebars of links;

if the table contains any sidebars, converting the sidebars into a list of links as a last cell of the table;

identifying each cell of the table;

adding each identified cell to a separate subpage;

replacing the table with a link to one of the separate subpages to form the transformed document; and

linking the separate subpages together.

44. The method of claim 43, wherein, for each cell, adding that cell into a separate subpage comprises:

determining if that cell is a nested table;

if that cell is not a nested table, adding that cell to the separate subpage; and

if that cell is a nested table, repeating the determining, converting, identifying, adding, replacing and linking steps of claim 41.

45. The method of claim 1, wherein transforming the parsed document into a transformed document further comprises generating at least one subpage.

46. The method of claim 45, when a transformed document meets the at least one evaluation criterion, further comprising:

generating an evaluation value for each generated subpage for that transformed document;

determining, for each subpage, if the evaluation value for that subpage meets the at least one evaluation criterion;

for each subpage, if the evaluation value for that subpage does not meet the at least one criterion, performing the transforming, generating and determining steps on that subpage using an additional one of the transforms to generate a transformed subpage; and

for each subpage, if that subpage meets the at least one criterion, identifying that subpage as ready to be output.

47. The method of claim 46, wherein identifying that subpage as ready to be output comprises storing that subpage in an output cache.

48. The method of claim 45, when a transformed subpage meets the at least one evaluation criterion, further comprising:

generating an evaluation value for each generated subpage for that transformed subpage;

determining, for each subpage, if the evaluation value for that subpage meets the at least one evaluation criterion;

for each subpage, if the evaluation value for that subpage does not meet the at least one criterion, performing the transforming, generating and determining steps on that subpage using an additional one of the transforms to generate a transformed subpage; and

for each subpage, if that subpage meets the at least one criterion, identifying that subpage as ready to be output.

49. The method of claim 1, further comprising, after parsing the document:

generating an evaluation value from the document;

determining if the evaluation value meets at least one evaluation criterion;

if the document does not meet the at least one criterion, performing the transforming, generating and determining steps using a first one of the transforms; and

if the document meets the at least one criterion, outputting the document without transforming the document.

50. The method of claim 1, wherein transforming the document comprises:

filtering the document to extract desired portions of the document; and

replacing the document with the extracted portions.

51. A document re-authoring system that automatically re-authors a document, comprising

a parse tree generating circuit;

a document size evaluation circuit; and

a transform circuit.

52. The document re-authoring system of claim 51, wherein the parse tree generating circuit parses the document to generate a parse tree.

53. The document re-authoring system of claim 52, wherein the parse tree is an abstract syntax tree.

54. The document re-authoring system of claim 52, wherein the document size evaluation circuit evaluates the parse tree generated by the parse tree generating circuit to determine if the document meets at least one evaluation criterion.

55. The document re-authoring system of claim 54, wherein, when the document meets the at least one evaluation criterion;

the document is output to a display device that has a display area less than a display area of a desktop monitor.

56. The document re-authoring system of claim 54, wherein, when the document does not meet the at least one evaluation criterion;

the transform circuit transforms the parse tree using a first transform to generate a first transformed parse tree.

57. The document re-authoring system of claim 56, wherein the document size evaluation circuit evaluates the transformed parse tree generated by the transform circuit to determine if a transformed document corresponding to the transformed parse tree meets at least one evaluation criterion.

58. The document re-authoring system of claim 57, wherein, when the transformed document does not meet the at least one evaluation criterion;

the transform circuit transforms the parse tree using a second transform to generate a second transformed parse tree.

59. The document re-authoring system of claim 57, wherein, when the transformed document meets the at least one evaluation criterion;

the transformed document is output to a display device that has a display area less than a display area of a desktop monitor.

60. The document re-authoring system of claim 56, wherein, in response to transforming the parse tree, the transform circuit also generates at least subpage parse tree corresponding to at least one subpage.

61. The document re-authoring system of claim 60, wherein, when the transformed document meets the at least one evaluation criterion;

the document size evaluation circuit evaluates each resulting subpage parse tree generated by the transform circuit from that transformed document to determine if the subpage corresponding to that subpage parse tree meets at least one evaluation criterion.

62. The document re-authoring system of claim 61, wherein, for each resulting subpage parse tree, when the subpage corresponding to that subpage parse tree meets the at least one evaluation criterion;

that subpage is identified as ready to be output to the display device.

63. The document re-authoring system of claim 61, wherein, for each resulting subpage parse tree, when the subpage corresponding to that subpage parse tree does not meet the at least one evaluation criterion;

the transform circuit transforms that subpage parse tree using a second transform to generate a transformed subpage parse tree.