ELECTRONIC TABLE OF CONTENTS ENTRY CLASSIFICATION AND LABELING SCHEME

• US 20090144277A1
• Filed: 12/03/2007
• Published: 06/04/2009
• Est. Priority Date: 12/03/2007
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: GALIC, SASA, DRESEVIC, BODIN, LUKACEVIC, DEJAN, RADAKOVIC, BOGDAN, TRUTNER, OREN, UZELAC, ALEKSANDAR
• Application Number:
  US11/949,501
• Publication Number:
  US 20090144277A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines

Abstract

Computer-storage media, computerized methods and systems for classifying character strings within electronic documents are provided. Initially, textual data, which includes one or more character strings, is extracted from an electronic version of a document, typically scanned from a physical document utilizing optical character recognition. The textual data is received at a table-of-contents (TOC) engine that extracts semantic information from the textual data. Sub-engines within the TOC engine analyze the semantic information to determine at least one appropriate classification for character strings within the textual data. Labels selected from a predetermined set of TOC-architecture labels are appended to the character strings according to the appropriate classification. The character strings, and labels appended thereto, are stored in association with each other generating an electronic document file that includes enriched textual data.

Claims

1. One or more computer-storage media having computer-executable instructions embodied thereon that, when executed, perform a method for classifying character strings of a table-of-contents (TOC) portion of an electronic document, the method comprising:

receiving textual data extracted from the electronic document, the textual data comprising one or more character strings of the TOC portion of the electronic document;

extracting semantic information from the textual data of the identified TOC portion;

executing a classification procedure to determine at least one appropriate classification for the one or more character strings of the TOC portion by analyzing the semantic information;

appending one or more labels, selected from a predetermined set of TOC-architecture labels, to the one or more character strings according to the at least one appropriate classification; and

storing the one or more labels in association with the one or more character strings.

2. The one or more computer-storage media of claim 1, wherein the textual data further comprises at least one of:

position values, on a page of the electronic document, associated with the one or more character strings;

or layout characteristics, and shape characteristics, of the one or more characters strings.

3. The one or more computer-storage media of claim 2, wherein the classification procedure further comprises:

identifying one or more TOC entries within the TOC portion of the electronic document, the one or more TOC entries comprising one or more character strings; and

determining structural attributes of the one or more TOC entries based on the semantic information.

4. The one or more computer-storage media of claim 3, wherein the classification procedure further comprises:

determining whether the one or more TOC entries include a reference character string that targets a section of the electronic document;

if a reference character sting is provided, comparing page content within the section to the one or more character strings associated with the one or more TOC entries; and

verifying the accuracy of the identification of the one or more TOC entries upon determining that the page content corresponds with the associated one or more character strings.

5. The one or more computer-storage media of claim 2, wherein extracting semantic information from the textual data of the identified TOC portion comprises organizing the one or more character strings into groups upon recognizing the shape characteristics and the layout characteristic of the one or more character strings.

6. The one or more computer-storage media of claim 1, wherein the classification procedure comprises:

performing one or more categorization tests that utilize the extracted semantic information, wherein each of the one or more categorization tests relates to a respective label in the predetermined set of TOC-architecture labels; and

calculating at least one score based on results of each of the one or more categorization tests, wherein the score indicates a correlation between the respective label and the one or more character strings.

7. The one or more computer-storage media of claim 6, wherein performing the one or more categorization tests comprises:

executing one or more evaluation passes of the one or more character strings; and

adjusting the score incrementally based upon results of each of the one or more evaluation passes.

8. The one or more computer-storage media of claim 7, wherein the one or more evaluation passes comprise matching the semantic information associated with the one or more character strings against predefined layout characteristics and shape characteristics.

9. The one or more computer-storage media of claim 7, wherein adjusting the score incrementally is facilitated by a scoring function, the scoring function comprising:

score[n+1]=(score[n]*mulF)+addF,

wherein;

n indicates the iterative number of evaluation passes performed;

the multiplicative coefficient is mulF;

the additive coefficient is addF; and

score[n] represents a value of the score upon performing n number of evaluation passes;

wherein the value of the score is reevaluated, utilizing the scoring function, incident to the completion of each of the one or more evaluation passes.

10. The one or more computer-storage media of claim 9, wherein the multiplicative coefficient and the additive coefficient are assigned numerical values based on the significance of the predefined layout characteristics and shape characteristics utilized in each of the one or more evaluation passes.

11. The one or more computer-storage media of claim 10, wherein the numerical values of the multiplicative coefficient and the additive coefficient are automatically trained according to a machine-learning framework to improve the accuracy of correlation between the respective label and an actual classification of the one or more character strings.

12. The one or more computer-storage media of claim 6, wherein the classification procedure further comprises comparing the at least one score calculated based on the results of each of the one or more categorization tests to determine which respective label in the predetermined set of TOC-architecture labels correlates to the one or more character strings.

13. A computer system for determining a structure of a table-of-contents (TOC) portion of an electronic document, the system comprising:

a converter component for receiving textual data extracted from the TOC portion the electronic document, the textual data comprising one or more TOC entries;

a TOC engine for classifying one or more elements within the one or more TOC entries of the electronic document, the TOC engine comprising;

a featurizer tool for extracting semantic information from the textual data; and

a word-label sub-engine for determining at least one appropriate classification for the one or more elements by analyzing the semantic information, and for appending one or more labels, selected from a predetermined set of architecture labels, to the one or more elements according to the at least one appropriate classification; and

a merge engine for storing the one or more labels in association with the one or more elements.

14. The computer system of claim 13, further comprising one or more antecedent layout engines for deriving format information from the electronic document based on an analysis of the textual data, the format information including an identification of the TOC portion of the electronic document.

15. The computer system of claim 14, further comprising an engine-interface manager for conveying the format information between the one or more antecedent layout engines and the TOC engine, wherein the word-label sub-engine of the TOC engine utilizes the format information when executing the classification procedure.

16. The computer system of claim 13, wherein the merge engine is further configured to attach an internal link to the one or more TOC entries, wherein an Internet user is directed to a targeted section of the electronic document upon selection of the internal link.

17. The computer system of claim 13, the TOC engine further comprising one or more classification sub-engines that determine structural attributes of the one or more TOC entries based on the extracted semantic information.

18. The computer system of claim 17, wherein the structural attributes comprises an indication of a number of lines of page content that each of the one or more TOC include, an indication of whether each of the one or more TOC entries reference an introductory section or a main-body section of the electronic document;

and an indication of a level-of-depth value.

19. The computer system of claim 13, wherein appending one or more labels, selected from a predetermined set of architecture labels, to the one or more elements according to the at least one appropriate classification comprises selecting from a predetermined set of at least one of table-of-content architecture labels, bibliography architecture labels, or index architecture labels.

20. A computerized method for classifying character strings within electronic documents, the method comprising:

receiving textual data extracted from an electronic document, the textual data comprising one or more character strings, wherein the textual data comprises position values, layout characteristics, and shape characteristics, associated with the one or more characters strings;

deriving semantic information from the textual data, wherein deriving semantic information comprises organizing the one or more character strings into groups upon recognizing the shape characteristics and the layout characteristic of the one or more character strings;

performing one or more categorization tests that utilize the derived semantic information, wherein each of the one or more categorization tests relates to a respective label in a predetermined set of architecture labels, wherein performing the one or more categorization tests comprises;

executing one or more evaluation passes on the one or more character strings, wherein the one or more evaluation passes comprise matching the semantic information associated with the one or more character strings against predefined layout characteristics and predefined shape characteristics; and

incrementally adjusting a temporary score, associated with the one or more character strings, based upon results of each of the one or more evaluation passes, wherein adjusting the temporary score is facilitated by a scoring function that receives results determined by the one or more evaluation passes;

calculating at least one character-string score based on results determined by each of the one or more categorization tests and the temporary score;

appending one or more labels to the one or more character strings according to the at least one character-string score; and

serializing the one or more labels in association with the one or more character strings; and

training the scoring function according to a correlation between the one or more labels and an actual classification of the one or more character strings.