System and method for identifying document structure and associated metainformation

• US 7,937,338 B2
• Filed: 04/30/2008
• Issued: 05/03/2011
• Est. Priority Date: 04/30/2008
• Status: Active Grant

• Current Assignee: Wrp IP Management, LLC
• Original Assignee: International Business Machines Corporation
• Inventors: Byrd, Roy J., Coden, Anni R., Cheng, Keh-Shin F., Teiken, Wilfried, Boguraev, Branimir K., Tanenblatt, Michael A.
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): Bharadwaj; Kalpana
• Application Number:
  US12/112,944
• Publication Number:
  US 20090276378A1
• Time in Patent Office: 1,098 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 40/117 Tagging; Marking up details of markup languages G06F40/143; Designating a block; Setting of attributes style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors

Abstract

A system and method for processing documents by utilizing the textual content and layout of the documents, including visual indicators, to more efficiently and reliably process the documents across various document types. The system and method identifies visually distinguishable elements within the document, such as section and sub-section boundary indicators, to mark, divide and label the boundaries and content type such that the sections are more clearly identifiable and easily processed. The system and method uses known elements, including section heading types, keywords, section type classifiers, sub-section heading constructs, stop words, and the like to adaptively identify and process a broad range of document types. The system and method continually refines and updates these known elements and allows users to discover and define new elements for further refinement and updating.

Claims

1. A computer-implemented method, comprising:

receiving at least one document;

identifying sections and associated section types within said at least one document;

identifying sub-sections within said at least one document;

defining new section types and new sub-section heading constructs when sections having known section types are identified; and

learning new section heading keywords when sections having known section types are identified, wherein learning new section heading keywords comprises;

receiving new section headings;

receiving at least one stop word;

filtering said at least one stop word from new section headings and ingesting new section heading keywords; and

outputting section heading keywords.

2. The method according to claim 1, wherein said at least one document includes a collection of documents of different types and formats.

3. The method according to claim 1, wherein identifying sections and associated section types within said at least one document further comprises:

identifying document section heading candidates based on known visual indicators;

identifying document section types based on known section type keywords;

establishing whether section types can be determined,

if section types can be determined then performing the following;

processing the section content based on the section type, and

outputting the processed document; and

if section types cannot be determined then performing the following;

identifying section types based on known section type classifiers, and

establishing whether section types can be determined;

if section types can be determined then performing the following;

 

outputting the section headings and types to a database,

 

processing the section content based on the section type, and

 

outputting the processed document; and

if section types cannot be determined then performing the following;

 

outputting the sections having undetermined section types to a database.

4. The method according to claim 3, wherein identifying document section heading candidates includes:

segmenting said at least one document into regions based on visual indicators;

assigning weights to each visual indicator based on the distinguishing ability of the visual indicator;

computing a confidence value for each region; and

selecting regions having high confidence values as section candidates.

5. The method according to claim 1, wherein identifying sub-sections within said at least one document further comprises:

receiving document sections having undetermined section types;

receiving known sub-section heading constructs;

determining whether known sub-section heading constructs exist in the section having undetermined section types,

if known sub-section heading constructs exist then performing the following;

processing said sub-section heading constructs,

processing said sub-section content as a main section, and

outputting the processed document, and

if no known sub-section heading constructs exist then performing the following;

processing the content as a main section, and

outputting the sections having undetermined section types to a database.

6. The method according to claim 1, wherein defining new section types and new sub-section heading constructs comprises:

receiving sections with unknown types;

discovering and defining new section types or new sub-section heading constructs; and

outputting new section types and sub-section heading constructs to respective databases.

7. The method according to claim 6, wherein said new section types and sub-section heading constructs include section keywords, section type classifiers, sub-section heading constructs and stop words.

8. A system, comprising:

a document input unit;

a processing unit coupled to said document input unit, said processing unit includes;

means for identifying document section heading candidates based on known visual indicators;

means for identifying document section types based on known section type keywords;

means for establishing whether section types can be determined and performing the following;

if section types can be determined,

processing the section content based on the section type, and

outputting the processed document;

if section types cannot be determined,

identifying section types based on known section type classifiers;

means for establishing whether section types can be determined and performing the following;

if section types can be determined,

outputting the section headings and types to a database,

processing the section content based on the section type, and

outputting the processed document; and

if section types cannot be determined,

outputting the sections having undetermined section types to a database;

a storage unit coupled to said processing unit; and

a document output unit coupled to said output unit.

9. A system according to claim 8, wherein said processing unit further includes:

means for segmenting documents into regions based on visual indicators;

means for assigning weights to said visual indicators based on the distinguishing ability to the visual indicator;

means for computing a confidence value for each region; and

means for selecting regions having high confidence values as section or sub-section heading candidates.

10. A system according to claim 8, wherein said processing unit further includes:

means for receiving document sections having undetermined section types;

means for receiving known sub-section heading constructs;

means for determining whether known sub-section heading constructs exist in the section having undetermined section types and performing the following;

if known sub-section heading constructs exist,

processing said sub-section heading constructs,

processing said sub-section content as a main section, and

outputting the processed document, and

if no known sub-section heading constructs exist,

processing the content as a main section, and

outputting the sections having undetermined section types to a database.

11. A system according to claim 8, wherein defining new section types and new sub-section heading constructs comprises:

means for receiving sections with unknown types;

means for discovering and defining new section types or new sub-section heading constructs; and

means for outputting new section types and sub-section heading constructs to respective databases.

12. The system according to claim 11, wherein said new section types and sub-section heading constructs include section keywords, section type classifiers, sub-section heading constructs and stop words.

13. A computer program product comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

receive at least one document;

identify sections and associated section types within said at least one document;

identify sub-sections within said at least one document;

define new section types and new sub-section heading constructs; and

learn new section heading keywords, wherein when learning new section heading keywords the computer readable program further causes the computer to;

receive new section headings;

receive at least one stop word;

filter said at least one stop words from new section headings and ingesting new section heading keywords; and

output section heading keywords.

14. A computer program product according to claim 13, wherein the computer readable program further causes the computer to:

identify document section heading candidates based on known visual indicators;

identify document section types based on known section type keywords;

establish whether section types can be determined,

if section types can be determined then causing the computer to;

process the section content based on the section type, and

output the processed document; and

if section types cannot be determined then causing the computer to;

identify section types based on known section type classifiers, and

establish whether section types can be determined;

if section types can be determined then causing the computer to;

 

output the section headings and types to a database,

 

process the section content based on the section type, and

 

output the processed document; and

if section types cannot be determined then causing the computer to;

 

output the sections having undetermined section types to a database.

15. A computer program product according to claim 14, wherein when identifying document section heading candidates the computer readable program further causes the computer to:

segment said at least one document into regions based on visual indicators;

assign weights to each visual indicator based on the distinguishing ability of the visual indicator;

compute a confidence value for each region; and

select regions having high confidence values as section candidates.

16. A computer program product according to claim 13, wherein when identifying sub-sections within said documents the computer readable program further causes the computer to:

receive document sections having undetermined section types;

receive known sub-section heading constructs;

determine whether known sub-section heading constructs exist in the section having undetermined section types and further causing the computer to;

if known sub-section heading constructs exist,

process said sub-section heading constructs,

process said sub-section content as a main section, and

output the processed document, and

if no known sub-section heading constructs exist,

processing the content as a main section, and

output the sections having undetermined section types to a database.

17. A computer program product according to claim 13, wherein when defining new section types and new sub-section heading constructs the computer readable program further causes the computer to:

receive sections with unknown types;

discover and define new section types or new sub-section heading constructs; and

output new section types and sub-section heading constructs to respective databases.

18. A computer-implemented method, comprising:

receiving at least one document;

identifying sections and associated section types within said at least one document based on known keywords and section type classifiers;

identifying sub-sections within said at least one document based on sub-section heading constructs;

defining new section types and new sub-section heading constructs when sections having unknown section types are identified; and

learning new section heading keywords when known section types are identified by a section type classifier, instead of the existence of known section type keywords, wherein learning new section heading keywords comprises;

receiving new section headings;

receiving at least one stop word;

filtering said at least one stop word from new section headings and ingesting new section heading keywords; and

outputting section heading keywords.

19. The method according to claim 18, wherein identifying sub-sections within said at least one document further comprises:

receiving document sections having undetermined section types;

receiving known sub-section heading constructs;

determining whether known sub-section heading constructs exist in the section having undetermined section types,

if known sub-section heading constructs exist then performing the following;

processing said sub-section heading constructs,

processing said sub-section content as a main section, and

outputting the processed document, and

if no known sub-section heading constructs exist then performing the following;

processing the content as a main section, and

outputting the sections having undetermined section types to a database.

20. The method according to claim 18, wherein defining new section types and new sub-section heading constructs comprises:

receiving sections with unknown types;

discovering and defining new section types or new sub-section heading constructs; and

outputting new section types and sub-section heading constructs to respective databases.

21. The method according to claim 20, wherein said new section types and sub-section heading constructs include section keywords, section type classifiers, sub-section heading constructs and stop words.