Method and expert system for deducing document structure in document conversion

• US 7,313,754 B2
• Filed: 03/14/2003
• Issued: 12/25/2007
• Est. Priority Date: 03/14/2003
• Status: Expired due to Term

• Current Assignee: Texterity Incorporated (GTxcel, Inc)
• Original Assignee: Texterity Incorporated (GTxcel, Inc)
• Inventors: McLure, Petra, Scholz, Carl, Whitney, Ronald
• Primary Examiner(s): HUYNH, THU V
• Application Number:
  US10/388,685
• Publication Number:
  US 20040181746A1
• Time in Patent Office: 1,747 Days
• Field of Search: 715/500, 715522-523, 715/530, 715/513, 345/764, 345/809
• US Class Current: 715/234
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/154 Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets
• CPC Class Codes: G06F 40/169 Annotation, e.g. comment data or footnotes

Abstract

An expert system for more efficiently and accurately deducing document structure from document formatting, the expert system including a conversion engine for converting an unstructured file to a structured file, and a verification engine, responsive to the output of the conversion engine, for generating and displaying a representation of the structured file annotated with a visual depictions of the classified components thereof so that the annotations can be modified and/or classifications can be added and/or classifications can be suggested, and/or rules for classification can be suggested and the structured file reprocessed by the conversion engine.

Claims

1. An expert system for more efficiently and accurately deducing document structure from document formatting, the expert system comprising:

a conversion engine for converting an unstructured file to a structured file, the conversion engine configured to locate document formatting including frequency of usage, repetitions and locations of text, spacing of text and style of text in the unstructured file to initially deduce document structure from the document formatting; and

a verification engine, responsive to the output of the conversion engine, for generating and displaying a visual representation file of the structured file annotated with visual depictions of the classified components of the structured file on a display device so that the annotations with the visual depictions of the classified components can be modified, classifications of the components can be added and classifications of the components can be suggested by an example, and

the structured file reprocessed by the conversion engine which to further deduce the document structure, uses the initially deduced document structure, the annotations that are modified, the classifications that are added, the classifications that are suggested, a rule that is derived from the examples provided via the verification engine and all occurrences in the structured file that match the derived rule, the conversion engine and the verification engine operating iteratively until an operator indicates the structured file annotated with visual depictions is correct.

2. The expert system of claim 1 in which the representation file is a graphics based page description language file annotated with visual depictions of the classified components of a document.

3. The expert system of claim 2 in which, after the annotated graphics based page description language file is modified, it is input to the conversion engine.

4. The expert system of claim 1 in which the conversion engine is programmed to:

convert a graphics based page description language file to a flat file representation of all metrics known about each character and image of the graphics based page description language file;

group all said metrics in an intermediate mark-up language file; and

create an output mark-up language file including components of the document classified into their respective component parts and relationships.

5. The expert system of claim 4 in which the graphics based page description language file is a PDF file, the flat file is a comma separated value file, the intermediate mark-up language file is a GPML file, and the output file is an XML file.

6. The expert system of claim 1 in which the conversion engine includes a rules engine including a set of rules.

7. The expert system of claim 6 further including a feedback channel wherein an annotated graphics based page description language file modified using the verification engine is compared with the original annotated graphics base page description language file and, based on the comparison, the conversion engine is programmed to change the operation of the rules of the rules engine.

8. The expert system of claim 1 in which the conversion engine is programmed to output outputs selected from the following group:

a word list including the coordinates of each word on a page, a table of contents, scaleable vector graphic images, a cascading style sheet, and an ADOBE e-Book.

9. The system of claim 1 in which the structured file annotated with visual depictions is modified to classify the annotations as a plurality of header level components of the structured file.

10. The system of claim 9 in which the plurality of header levels include H1, H2, H3, H4, H5, and H6.

11. The system of claim 10 in which the H1 header level classifies a “

Part”

of the structured file.

12. The system of claim 11 in which the H1 header level is classified by selecting an H1 icon and drawing a box about the annotated visual depictions which represent the “

Part”

of the structured file.

13. The system of claim 12 in which the H1 icon and the box are colored red and the H1 icon includes the text “

H1”

.

14. The system of claim 10 in which the H2 header level classifies a “

Chapter”

of the structured file.

15. The system of claim 14 in which the H2 header level is classified by selecting an H2 icon and drawing a box about the annotated visual depictions which represent the “

Chapter”

of the structured file.

16. The system of claim 15 in which the H2 icon and the box are colored blue and the icon includes the text “

H2”

.

17. The system of claim 10 in which the H3 header level classifies a “

Subchapter”

of the structured file.

18. The system of claim 17 in which the H3 header level is classified by selecting an H3 icon and drawing a box about the annotated visual depictions which represent the “

Subchapter”

of the structured file.

19. The system of claim 18 in which the H3 icon and the box are colored green and the icon includes the text “

H3”

.

20. The system of claim 10 in which the H4 header level classifies a “

Sub-subchapter”

of the structured file.

21. The system of claim 20 in which the H4 header level is classified by selecting an H4 icon and drawing a box about the annotated visual depictions which represent the “

Sub-subchapter”

of the structured file.

22. The system of claim 21 in which the icon and the box are colored fuchsia and the H4 icon includes the text “

H4”

.

23. The system of claim 10 in which the H5 header level classifies an operator defined element of the structured file.

24. The system of claim 23 in which the H5 header level is classified by selecting an H5 icon and drawing a box about the annotated visual depictions which represent an operator defined part of the structured file.

25. The system of claim 24 in which H5 the icon and the box are colored aqua and the H5 icon includes the text “

H5”

.

26. The system of claim 10 in which the H6 header level classifies an operator defined element of the structured file.

27. The system of claim 26 in which the H6 header level is classified by selecting an H6 icon and drawing a box about the annotated visual depictions which represent an operator defined element of the structured file.

28. The system of claim 27 in which the H6 icon and the box are colored white and the icon includes the text “

H6”

.

29. The system of claim 1 in which the structured file annotated visual with depictions is modified to add or suggest classification of running header components at the top of every page of the structured file.

30. The system of claim 29 in which the running header is classified by selecting a header/footer icon and drawing a box about the annotated visual depictions which represent the running header of the structured file.

31. The system of claim 30 in which the header/footer icon and the box are colored orange and the icon includes the depiction of page with a header and footer.

32. The system of claim 1 in which the structured file annotated visual with depictions is modified to add or suggest classification of running footer components at the bottom of every page of the structured file.

33. The system of claim 32 in which the running footer is classified by selecting a header/footer icon and drawing a box about annotated visual depictions which represent the running header of the structured file.

34. The system of claim 1 further including a plurality of icons for activating the conversion engine and verification engine.

35. The system of claim 34 further including a “

New”

icon to initialize and create a hint file so that an operator can define hints.

36. The system of claim 34 further including an “

Execute”

icon to execute a hinting process.

37. The system of claim 34 further including a “

New TC”

icon to create a hint file containing hintable objects file.

38. The system of claim 34 further including a “

Reset”

icon to clear all local and intermediate files of the system.

39. The system of claim 34 further including an “

Undo Hints”

icon to undo the results of a last hint cycle.

40. The system of claim 34 further including a “

Change Elements”

icon to change existing elements of the structured annotated graphics based page description file from one class of elements to another class of elements.

41. The system of claim 34 further including a “

Change Encoding”

icon to activate a dialog box wherein an operator can correct unicode mapping of the structured annotated graphics based page description file.

42. The system of claim 34 further including an “

Edit Rules File”

icon to activate a dialog box for an operator to configure a match for a particular hint element.

43. The system of claim 34 in which the dialog box is provided to select particular attributes of the structured annotated graphics based page description file.

44. The system of claim 43 in which the dialog box selects size, slant, weight, underline, strikethrough, adornment, color, baseline, font name, small caps, case, PDF-x-overlap, PDF-y-overlap, left-align, right-align, top-align, and bottom-align.

45. The system of claim 34 further including a “

Body-Start”

icon to mark the beginning of a text body of the structured annotated graphics based page description file.

46. The system of claim 34 further including a “

Body-End”

icon to mark the end of a body of the structured annotated graphics based page description file.

47. A method for more efficiently and accurately deducing document structure from document formatting, the method comprising:

a) converting an unstructured file to a structured file wherein the components of the structured file are classified, the step of converting including locating document formatting that include frequency of usage, repetitions and locations of text, spacing of text and style of text in the unstructured file to initially deduce document structure from the document formatting;

b) generating and displaying a visual representation file of the structured file annotated with visual depictions of the classified components thereof;

c) at least one of the steps of modifying the annotated visual depictions, adding classifications of the components, and suggesting classifications of the components by an example associated with step a); and

d) repeating steps a), b), and c) until no further modifications, additions or suggestions are made, step a) further including deducing the document structure by using the initially deduced document structure, the annotated visual depictions that are modified, the classifications that are added, the classifications that are suggested, a rule that is derived from the example, and all occurrences that match the derived rule.

48. The method of claim 47 further including the step of creating an output file based on the structured file and the modifications and/or additions and/or suggestions made in steps c) and d).

49. The method of claim 47 in which the displayed representation is a graphics based page description language file annotated with visual depictions of the classified components of the document and in which step c) includes modifying the annotated graphics based page description language file.

50. The method of claim 47 in which step a) includes:

a1) converting a graphics based page description language file to a flat file representation of all metrics known about each character and image of the graphics based page description language file;

a2) grouping all said metrics in an intermediate mark-up language file; and

a3) creating an output mark-up language file including components of the document classified in to their respective component parts and relationships.

51. The method of claim 50 in which step d) includes repeating steps a2) and a3).

52. The method of claim 50 in which step d) further includes repeating step a1), a2) and a3).

53. The method of claim 50 in which the graphics based description language file is a PDF file, the flat file is a comma separated value file, the intermediate mark-up language file is a GPML file, and the output file is an XML file.

54. The method of claim 47 in which step a) includes the operation of a rules engine including a set of rules.

55. The method of claim 54 further including the step of comparing the annotations displayed with the modified annotations, and, based on the comparison, amending the operation of the rules of the rules engine.

56. The method of claim 47 further including the step of outputting, based on the structured file, outputs selected from the following group:

a word list including the coordinates of each word on a page, a table of contents, scaleable vector graphic images, a cascading style sheet, and an ADOBE e-Book in PDF format.