Method and system for analyzing the logical structure of a document

• US 5,669,007 A
• Filed: 02/28/1995
• Issued: 09/16/1997
• Est. Priority Date: 06/16/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Tateishi, Yuka
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/395,559
• Time in Patent Office: 931 Days
• Field of Search: 395/779, 395/761, 395/773-778, 395/784, 395/600, 395/800, 382/113, 382/173, 382/176, 382/180, 382/224, 382/240, 382/272, 382/276, 358/403, 358/453, 358/466
• US Class Current: 715/210
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1444 Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields

Abstract

An input document is matched with predetermined patterns on a line-by-line basis, whereby it can be assigned a plurality of pairs of attributes and costs. When the process for the whole document is completed, in accordance with a rule specifying the combination of attributes between the adjacent lines, the nodes of a graph are generated, the nodes are linked with each other, and costs are given to the node and links. There is a plurality of paths for traveling the graph from the root node to the final node, and each of them means the interpretation of a possible logical structure of the document. By summing the costs for the traveled nodes and links, a total cost value can be associated with each path, and by prioritizing by this total cost value, a plurality of logical structure interpretations can be sequentially shown from the most plausible path (logical structure interpretation). A chosen logical structure is tagged as required.

Claims

1. In a method for analyzing the logical structure of a document stored in readable form in a computer system in processing by said computer system,

a method for analyzing the logical structure of a document comprising the steps of:

(a) reading said document into the memory region of said computer system on a line-by-line basis;

(b) determining an attribute of said line comprising a start of a list, a continuation of a list, and the attributes of an ordinary line which is read into said memory region in accordance with a predetermined line attribute determination criterion to allow for the determination of a plurality of attributes and associate with teach determination a cost value representing a measure for the validity of the determination;

(c) in response to the completion of the attribute determination for all of the lines of said document, generating a starting node and then, for the first line of said document, generating as many nodes as the number of attribute determinations of said first line, and, in accordance with a predetermined attribute-based node linking rule, linking said starting node with the nodes generated for said first line;

(d) for the next line, generating as many nodes as the number of attribute determinations of said next line and in accordance with a predetermined node linking rule based on said attributes and cost value linking through links the nodes generated for the line preceding said next line with the nodes generated for said next line, and giving costs to said generated nodes and links;

(e) sequentially performing said step (d) until reaching the last line to construct a directed graph directed from said starting node to the ending node;

(f) traveling said directed graph from said starting node while summing the costs for the nodes and links en route to find a plurality of paths reaching the ending node; and

(g) ranking said plurality of paths found based on the sum of the costs associated with said individual paths.

2. A method for analyzing the logical structure of a document at set forth in claim 1 wherein said attribute determination is performed by matching with a plurality of predetermined regular retrieval patterns.

3. A method for analyzing the logical structure of a document as set forth in claim 1 wherein said step (b) further comprises a step of giving a level representing the depth of a list.

4. A method for analyzing the logical structure of a document as set forth in claim 3, comprising a step of following one path of the graph found in said step (g) and, while individually tagging in accordance with the attributes and levels of the nodes on said path, outputting a line associated with said nodes.

5. A method for analyzing the logical structure of a document as set forth in claim 4 wherein said tags are those based on the BookMaster'"'"'s rule.

6. In a system for analyzing the logical structure of a document stored in readable form in a computer system in processing by said computer,

a system for analyzing the logical structure of a document comprising:

(a) a memory means for storing a document in a form readable by said computer system on a line-by-line basis;

(b) a reading means for reading out said document from said memory means on a line-by-line basis;

(c) a text format analyzing means having a plurality of patterns and a pair of at least one attribute and a cost value associated with said individual patterns, having a pattern expression dictionary in which at least two or more pairs of an attribute and a cost value are associated with one pattern, and applying said plurality of patterns to the individual lines of said document read out by said reading means and in response to the occurrence of pattern matching, associating and storing all of the pairs of the attributes and cost values associated with the pattern for which said matching has occurred;

(d) a graph generating means for performing the node generation of a graph and the linking between the nodes in accordance with said attributes and cost values and previously having a rule for giving costs to said nodes and internode links, and in response to the completion of the processing for all of the lines of said document by said text format analyzing means, applying said rule from the first line of said document to link the nodes generated for the preceding line with the nodes generated for the next line, thereby generating a directed graph;

(e) a graph analyzing means for traveling said generated directed graph from the starting node until reaching the ending node while summing the costs given to said nodes and links to find a plurality of paths, and ranking said paths found based on the cost values calculated for them; and

(f) a means for giving tags indicating the logical structure of the document based on said ranked paths of the graph.

7. A system for analyzing the logical structure of a document as set forth in claim 6 wherein said tags are those based on the BookMaster'"'"'s rule.

8. A system for analyzing the logical structure of a document as set forth in claim 6 wherein said pattern matching includes a pattern matching based on a regular expression.

9. A system for analyzing the logical structure of a document as set forth in claim 6 wherein said attributes include the start of a list, the continuation of a list, and the attributes of an ordinary line.

10. In a method for analyzing the logical structure of a document printed on paper in a predetermined format by a computer system processing,

a method for analyzing the logical structure of a document comprising the steps of:

(a) optically scanning the paper on which said document is printed, thereby to create a document image which can be processed by said computer system;

(b) analyzing said document image to determine the margins and paragraphs of the document;

(c) performing character column slicing and character recognition based on the determination of the margins and paragraphs of said document, and storing the result in a memory means in a form which can be processed by said computer system on a line-by-line basis for the document;

(d) reading said document on a line-by-line basis into the memory region of said compute system;

(e) determining attributes of line comprising the start of a list, the continuation of a list, and the attributes of an ordinary line read into said memory region in accordance with a predetermined line attribute determination criterion to allow for the determining of a plurality of attributes and associate with each determination a cost value indicating the validity of the determination;

(f) in response to the completion of the attribute determination for all of the lines of said document, generating a starting node and then, for the first line of said document, generating as many nodes as the number of the attribute determinations of said first line, and, in accordance with a predetermined attribute-based node linking rule, linking said starting node with the nodes generated for said first line;

(g) for the next line, generating as many nodes as the number of attribute determinations of said next line, and, in accordance with a predetermined node linking rule based on said attribute and cost value, linking through links the nodes generated for the line preceding said next line with the nodes generated for said next line, and giving costs to said generated nodes and links;

(h) sequentially performing said step (g) until reaching the last line to construct a directed graph directed from said starting node t the ending node;

(i) traveling said directed graph from said starting node while summing the costs for the nodes an links en route to find a plurality of paths reaching the ending node; and

(j) ranking said plurality of paths found based on the sum of the costs associated with said individual paths.

11. A method for analyzing the logical structure of a document as set forth in claim 10 wherein said attribute determination is performed by matching with a plurality of predetermined regular retrieval patterns.

12. A method for analyzing the logical structure of a document as set forth in claim 10 wherein said step (b) further comprises a step of giving a level representing the depth of a list.

13. A method for analyzing the logical structure of a document as set forth in claim 12 wherein there is comprised a step for following one path of the graph found in said step (j) and, while individually tagging in accordance with the attributes and levels on said path, outputting a line associated with said nodes.

14. A method for analyzing the logical structure of a document as set forth in claim 13 wherein said tags are those based on the BookMaster'"'"'s rule.

15. A method for analyzing the logical structure of a document as set forth in claim 10 wherein said step (i) further comprises a step for correcting the cost value of a node based on the margin values associated with a line of the document.

16. A method for analyzing the logical structure of a document as set forth in claim 10 wherein said step (c) further comprises a step for determining a font size for a line, and said step (i) further comprises a step for correcting the cost value of a node based on said font size associated with a line of the document.

17. In a system for analyzing the logical structure of a document printed on paper in a predetermined format by a computer system processing,

a system for analyzing the logical structure of a document comprising:

(a) an image scanner means for optically scanning the paper on which said document is printed, thereby to create a document image which can be processed by said computer system;

(b) a means for analyzing said document image to determine the margins and paragraphs of the document, and storing the result in a form which can be processed by said computer system;

(c) a means for performing character column slicing and character recognition based on the determination of the margins and paragraphs of said document, and storing the result in the memory means in a form which can be processed by said computer system on a line-by-line basis for the document;

(d) a reading means for said document form said memory means on a line-by-line basis;

(e) a text format analyzing means having a plurality of patterns and a pair of at least one attribute and a cost value associated with said individual patterns, having a pattern expression dictionary in which at least tow or more pairs of an attribute and a cost value are associated with at least one pattern, and applying said plurality of patterns to the individual lines of said document read out by said reading means and, in response to the occurrence of a pattern match, associating and storing all of the pairs of attribute and cost values associated with the pattern for which said match has occurred;

(f) a graph generating means for performing the node generation of a graph and the linking between the nodes in accordance with said attributes and cost values and previously having a rule for giving costs to aid nodes and internode links, and, in response to the completion of the processing for all of the liens of said document by said text format analyzing means, applying said rule from the first line of said document to link the nodes generated for the preceding line with the nodes generated for the next line, thereby to generate a directed graph;

(g) a graph analyzing means for traveling said generated directed graph from the starting node until reaching the ending node while summing the costs given to said nodes and links to find a plurality of paths, and ranking said paths found based on the cost values calculated for them; and

(h) means for giving tags indicating the logical structure of the document based on said ranked paths of the graph.

18. A system for analyzing the logical structure of a document as set forth in claim 17 wherein said tags are those based on the BookMaster'"'"'s rule.

19. A system for analyzing the logical structure of a document as set forth in claim 17 wherein said pattern matching includes a pattern matching based on a regular expression.

20. A system for analyzing the logical structure of a document as set forth in claim 17 wherein said attributes include the start of a list, the continuation of a list, and the attributes of an ordinary line.