Determining section information of a digital volume

• US 8,549,008 B1
• Filed: 11/12/2008
• Issued: 10/01/2013
• Est. Priority Date: 11/13/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wang, Xuefu, Manmatha, Raghavan, Pang, Bo
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Black, Linh
• Application Number:
  US12/269,421
• Time in Patent Office: 1,784 Days
• Field of Search: 707709-711, 707/741, 707/758
• US Class Current: 707/741
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A system, method, and computer program determines section information of a digital volume. Digital volumes include digital representations of human-readable content, such as digitized books. Phrases are extracted from a table of contents of a digital volume. Matching phrases that at least approximately match the extracted phrases are identified in the body of the digital volume. A best matching phrase is determined for each extracted phrase based on the ordering of the extracted phrases and the matching phrases, and based on match scores indicating the quality of the matches. Section information is generated, including section headings and section start locations based on the best matching phrases. The digital volume is presented to users with links from the table of contents to the section headings on the section start pages. The section information is also used to enhance searching of the digital volume by users.

Claims

1. A computer-implemented method for determining section information of a digital volume, the method comprising:

determining pages of the digital volume containing a table of contents by applying a classifier to the digital volume, the classifier adapted to use machine learning to recognize references to sections in a body of the digital volume and identify pages of the digital volume containing the section references as the pages containing the table of contents;

and generating a score estimating an accuracy of a classification of a page as containing the table of contents;

extracting phrases from the table of contents of the digital volume;

identifying matching phrases in the body of the digital volume, the matching phrases at least approximately matching the extracted phrases;

determining best matching phrases from the identified matching phrases, the best matching phrases comprising a matching phrase corresponding to each extracted phrase, the determining based at least in part on the ordering of the extracted phrases and the identified matching phrases;

generating section information, the section information comprising section headings and section start locations, the section headings comprising the best matching phrases, and the section start locations indicating starting locations of the sections in the digital volume, the section start locations comprising the locations of the best matching phrases in the digital volume; and

storing the section information.

2. The computer-implemented method of claim 1, wherein identifying matching phrases in the body of the digital volume further comprises:

indexing words of the digital volume to create a word index;

identifying lookup words from the extracted phrases;

looking up the lookup words in the word index to determine matching words, the matching words being exact or approximate matches of the lookup words; and

identifying matching phrases in the body of the digital volume based at least in part on the matching words.

3. The computer-implemented method of claim 1, wherein identifying matching phrases in the body of the digital volume further comprises:

determining match scores associated with the matching phrases, the match scores based at least in part on the similarity of the words in the extracted phrases and the corresponding matching phrases,

and wherein determining best matching phrases from the identified matching phrases is based at least in part on the match scores.

4. The computer-implemented method of claim 3, wherein the match scores are based at least in part on the font or layout of the matching phrases in the digital volume.

5. The computer-implemented method of claim 1, further comprising:

presenting the digital volume to a user, the presented digital volume including user-selectable links from the extracted phrases in the table of contents to corresponding section headings at the corresponding section start locations in the generated section information.

6. The computer-implemented method of claim 1, further comprising:

determining search results from the digital volume responsive to a search query; and

weighting search results containing section headings in the generated section information more heavily than other search results.

7. The computer-implemented method of claim 1, further comprising:

combining nearly adjacent best matching phrases into a section heading and combining corresponding extracted phrases into a section reference.

8. The computer-implemented method of claim 1, wherein the order of the best matching phrases in the body of the digital volume is approximately the same as the order of the extracted phrases in the table of contents.

26. The computer-implemented method of claim 1, wherein the classifier identifies the pages containing the table of contents based at least in part on text of the pages and a layout of the pages of the digital volume.

27. The computer-implemented method of claim 1, wherein the classifier identifies the pages containing the table of contents based at least in part on identifying pages having lines ending in numbers.

9. A computer system for determining section information of a digital volume, the system comprising:

a non-transitory computer-readable storage medium storing executable computer program modules comprising;

a classifier module for determining pages of the digital volume containing a table of contents by applying a classifier to the digital volume, the classifier adapted to use machine learning to recognize references to sections in a body of the digital volume and identify pages of the digital volume containing the section references as the pages containing the table of contents;

and generating a score estimating an accuracy of a classification of a page as containing the table of contents;

a phrase extraction module for extracting phrases from the table of contents of the digital volume, the digital volume comprising a plurality of sections;

a phrase matching module for identifying matching phrases in the body of the digital volume, the matching phrases at least approximately matching the extracted phrases; and

a match selection module for;

determining best matching phrases from the identified matching phrases, the best matching phrases comprising a matching phrase corresponding to each extracted phrase, the determining based at least in part on the ordering of the extracted phrases and the identified matching phrases;

generating section information, the section information comprising section headings and section start locations, the section headings comprising the best matching phrases, and the section start locations indicating starting locations of the sections in the digital volume, the section start locations comprising the locations of the best matching phrases in the digital volume; and

storing the section information; and

a processor for executing the computer program modules stored in the computer-readable storage medium.

10. The computer system of claim 9, wherein identifying matching phrases in the body of the digital volume further comprises:

indexing words of the digital volume to create a word index;

identifying lookup words from the extracted phrases;

looking up the lookup words in the word index to determine matching words, the matching words being exact or approximate matches of the lookup words; and

identifying matching phrases in the body of the digital volume based at least in part on the matching words.

11. The computer system of claim 9, wherein identifying matching phrases in the body of the digital volume further comprises:

determining match scores associated with the matching phrases, the match scores based at least in part on the similarity of the words in the extracted phrases and the corresponding matching phrases,

and wherein determining best matching phrases from the identified matching phrases is based at least in part on the match scores.

12. The computer system of claim 11, wherein the match scores are based at least in part on the font or layout of the matching phrases in the digital volume.

13. The computer system of claim 9, further comprising:

a presentation module for presenting the digital volume to a user, the presented digital volume including user-selectable links from the extracted phrases in the table of contents to corresponding section headings at the corresponding section start locations in the generated section information.

14. The computer system of claim 9, further comprising:

a search module for;

determining search results from the digital volume responsive to a search query; and

weighting search results containing section headings in the generated section information more heavily than other search results.

15. The computer system of claim 9, further comprising:

a post-processing module for combining nearly adjacent best matching phrases into a section heading and combining corresponding extracted phrases into a section reference.

16. The computer system of claim 9, wherein the order of the best matching phrases in the body of the digital volume is approximately the same as the order of the extracted phrases in the table of contents.

17. A computer program product having a non-transitory computer-readable storage medium having executable computer program instructions recorded thereon, the computer program instructions when executed by a processor causing the computer to determine section information of a digital volume, comprising:

a classifier module for determining pages of the digital volume containing a table of contents by applying a classifier to the digital volume, the classifier adapted to use machine learning to recognize references to sections in a body of the digital volume and identify pages of the digital volume containing the section references as the pages containing the table of contents;

and generating a score estimating an accuracy of a classification of a page as containing the table of contents;

a phrase extraction module for extracting phrases from the table of contents of the digital volume, the digital volume comprising a plurality of sections;

a phrase matching module for identifying matching phrases in the body of the digital volume, the matching phrases at least approximately matching the extracted phrases; and

a match selection module for;

determining best matching phrases from the identified matching phrases, the best matching phrases comprising a matching phrase corresponding to each extracted phrase, the determining based at least in part on the ordering of the extracted phrases and the identified matching phrases;

generating section information, the section information comprising section headings and section start locations, the section headings comprising the best matching phrases, and the section start locations indicating starting locations of the sections in the digital volume, the section start locations comprising the locations of the best matching phrases in the digital volume; and

storing the section information.

18. The computer program product of claim 17, wherein identifying matching phrases in the body of the digital volume further comprises:

indexing words of the digital volume to create a word index;

identifying lookup words from the extracted phrases;

looking up the lookup words in the word index to determine matching words, the matching words being exact or approximate matches of the lookup words; and

identifying matching phrases in the body of the digital volume based at least in part on the matching words.

19. The computer program product of claim 17, wherein identifying matching phrases in the body of the digital volume further comprises:

determining match scores associated with the matching phrases, the match scores based at least in part on the similarity of the words in the extracted phrases and the corresponding matching phrases,

and wherein determining best matching phrases from the identified matching phrases is based at least in part on the match scores.

20. The computer program product of claim 19, wherein the match scores are based at least in part on the font or layout of the matching phrases in the digital volume.

21. The computer program product of claim 17, further comprising:

a presentation module for presenting the digital volume to a user, the presented digital volume including user-selectable links from the extracted phrases in the table of contents to corresponding section headings at the corresponding section start locations in the generated section information.

22. The computer program product of claim 17, further comprising:

a search module for;

determining search results from the digital volume responsive to a search query; and

weighting search results containing section headings in the generated section information more heavily than other search results.

23. The computer program product of claim 17, further comprising:

a post-processing module for combining nearly adjacent best matching phrases into a section heading and combining corresponding extracted phrases into a section reference.

24. The computer program product of claim 17, wherein the order of the best matching phrases in the body of the digital volume is approximately the same as the order of the extracted phrases in the table of contents.

25. A computer-implemented method of determining a location of a section within a digital volume, the method comprising:

determining a portion of the digital volume containing a table of contents by applying a classifier to the digital volume, the classifier adapted to use machine learning to recognize references to sections in a body of the digital volume and identify portions of the digital volume containing the section references as the portion containing the table of contents;

and generating a score estimating an accuracy of a classification of a page as containing the table of contents;

extracting ordered text phrases from the identified portion of the digital volume determined to contain the table of contents, the ordered text phrases referencing a plurality of sections in the body of the digital volume;

identifying ordered text phrases in the body of the digital volume that at least approximately match the extracted text phrases;

determining an identified text phrase that best matches an extracted text phrase responsive at least in part to a match score indicating a quality of a match between the identified text phrase and the extracted text phrase and an ordering constraint determined based on an order of the extracted text phrases and an order of the identified text phrases;

generating section information indicating that a location of the identified best-matching text phrase is a starting location of a section in the body of the digital volume referenced by the extracted text phrase; and

storing the section information.