Automatic metadata identification

• US 8,510,312 B1
• Filed: 09/28/2007
• Issued: 08/13/2013
• Est. Priority Date: 09/28/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Thibaux, Romain, Vincent, Luc, Uhlik, Christopher Richard, Wang, Xuefu, Manmatha, Raghavan
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US11/864,197
• Time in Patent Office: 2,146 Days
• Field of Search: None
• US Class Current: 707/748
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

A system identifies metadata associated with a document by capturing text of a document and comparing the text of the document with a collection of metadata records. Sets of matches between the text of the document and at least one record in the collection of metadata records may be identified, where each set of matches corresponds to a metadata record in the collection of metadata records. Metadata records corresponding to each set of matches may be scored. At least one of the metadata records may be identified based on the scores of the metadata records. The at least one identified metadata record may be associated with the document.

Claims

1. A method performed by one or more processors associated with one or more network devices, the method comprising:

capturing text of a document;

comparing the text of the document to content of each of a plurality of metadata records, each of the plurality of metadata records storing information associated with a particular one of a plurality of documents that differs from the document;

selecting, based on comparing the text of the document to the content, one or more of the plurality of metadata records, where, for each of the selected metadata records, a portion of the associated content corresponds to at least a portion of the text of the document;

scoring each of the selected metadata records, including calculating a score representing a correspondence between the text of the document and the content of the respective one of the selected metadata records, where scoring each of the selected metadata records further includes;

calculating a first probability associated with a likelihood of one or more common phrases, that appear in both the text of the document and the content of the one of the selected metadata records, also appearing in the contents of the plurality of metadata records,

calculating a second probability associated with a likelihood of the one or more common phrases appearing in text of the plurality of documents, and

scoring the one of the selected metadata records based on the first probability and second probability;

ranking the selected metadata records based on scoring the selected metadata records; and

storing an association between the document and a particular number of highest ranking ones of the selected metadata records.

2. The method of claim 1, where capturing the text includes:

capturing an image of the document, and

converting the image to the text.

3. The method of claim 1, where comparing the text of the document to the content of each of the plurality of metadata records includes:

identifying a copyright page included in the text of the document; and

statistically comparing text of the identified copyright page to the content of each of the plurality of metadata records, and

where, for one of the selected metadata records, at least a portion of the text of the copyright page corresponds to at least a portion of the content of the one of the selected metadata records.

4. The method of claim 1, where comparing the text of the document to the content of each of the plurality of metadata records comprises:

identifying phrases in the text of the document, where each of the phrases includes one or more words; and

comparing the identified phrases, in the text of the document, to the content of each of the plurality of metadata records.

5. The method of claim 4, where selecting the one or more of the plurality of metadata records further comprises:

forming, for each of the selected metadata records, a first list that includes the one or more of the phrases corresponding to the content of the one of the selected metadata records.

6. The method of claim 5, where scoring the selected metadata records further comprises:

counting occurrences, of each of the identified phrases, in the plurality of documents;

counting occurrences, of each of the identified phrases, in the plurality of metadata records;

calculating, for each of the identified phrases and as the first probability, a probability of finding the one of the identified phrases in a randomly selected one of the plurality of documents based on counting the occurrences, of each of the identified phrases, in the plurality of documents;

calculating, for each of the identified phrases and as the second probability, a probability of finding the one of the identified words and phrases in a randomly selected one of the plurality of metadata records based on counting the occurrences, of each of the identified phrases, in the plurality of metadata records; and

scoring the first list for each of the selected metadata records based on the calculated first probability and the second probability.

7. The method of claim 6, where scoring the first set for each of the selected metadata records further comprises:

summing logarithms of the calculated probabilities of finding each of the phrases in the first set.

8. The method of claim 5, where identifying the first set for each of the selected metadata records further comprises:

identifying a maximal matching phrases set occurring for each of the selected metadata records, where the maximal matching phrases set includes entries in the first set that do not include phrases that are included within other entries in the first set; and

scoring the maximal matching phrases set occurring for each of the selected metadata records.

9. The method of claim 8, where identifying the maximal matching phrases set further comprises:

generating a list of phrases in the first set;

sorting the generated list of phrases in order of increasing length, such that a sub-phrase, that includes one or more words, is listed before a parent phrase that includes the sub-phrase and one or more additional words that are not included in the sub-phrase;

generating a first list of records that include the sub-phrase;

generating a second list of records that include the parent phrase;

removing, from the first list of records that include the sub-phrase, the records that are included in the second list of records that include the parent phrase; and

identifying the set of maximal matching phrases based on the remaining records in each of the first list of records and the second list of records.

10. The method of claim 8, where scoring the maximal matching phrases set further comprises:

summing logarithms of calculated probabilities of finding each phrase, in the maximal matching phrases set.

11. The method of claim 1, where comparing the text of the document to the content of each of the plurality of metadata records further comprises:

identifying selected words or phrases in the text of the document, where a number of the selected words or phrases in the document is less than a total number of words or phrases in the document; and

comparing the selected words or phrases to the content of each of the plurality of metadata records.

12. The method of claim 11, where identifying the selected words or phrases in the document further comprises:

generating a list of words or phrases in the document;

calculating, for each word or phrase in the document and as the second probability, a probability of finding the word or phrase in a randomly selected one of a plurality of documents;

calculating a maximum possible score for each word or phrase in the document based on the calculated probability of finding the word or phrase in a randomly selected one of the plurality of documents;

sorting the list of words or phrases, in decreasing order, based on the maximum possible scores; and

traversing down the sorted list to identify the selected words or phrases in the document.

13. The method of claim 12, further comprising:

determining whether a score has been calculated for a top-most word or phrase in the sorted list of words or phrases;

selecting the top-most word or phrase as a selected word or phrase when the score has been calculated for the top-most word or phrase;

removing the top-most word or phrase from the sorted list;

determining whether a particular total number of selected words or phrases has been selected from the list of words or phrases in the document; and

when the total number of selected words or phrases have not been selected from the list of words or phrases in the document;

determining whether the score has been calculated for a remaining top-most word or phrase in the sorted list of words or phrases,

selecting the remaining top-most word or phrase as a selected word or phrase when the score has been calculated for the remaining top-most word or phrase, and

removing the remaining top-most word or phrase from the sorted list.

14. The method of claim 13, further comprising:

calculating the score for the top-most word or phrase in the sorted list in response to determining that the score has not been calculated for the top-most word or phrase in the sorted list;

replacing the maximum possible score for the top-most word or phrase in the sorted list with the calculated score;

re-sorting the list of words or phrases based on the calculated score for the top-most word or phrase in the sorted list; and

determining whether the score has been calculated for a top-most word or phrase in the re-sorted list of words or phrases.

15. The method of claim 14, where calculating the score for the top-most word or phrase in the sorted list further comprises:

calculating a probability of finding the top-most word or phrase in a randomly selected one of the plurality of plurality of documents;

calculating a probability of finding the top-most word or phrase in a randomly selected one of the plurality of metadata records; and

calculating the score, for the top-most word or phrase, based on;

calculating the probability of finding the top-most word or phrase in a randomly selected one of the plurality of documents, and

calculating the probability of finding the top-most word or phrase in a randomly selected one of the plurality of metadata records.

16. The method of claim 15, further comprising:

determining that the listing of words or phrases includes a sub-phrase of the top-most word or phrase; and

re-calculating the maximum possible score for the identified sub-phrase based on the probability of finding the top-most word or phrase in a randomly selected one of the plurality of metadata records,

where re-sorting the list of words or phrases is further based on re-calculating the maximum possible score for the identified sub-phrase.

17. The method of claim 15, further comprising:

determining that the top-most word or phrase does not occur in at least a particular number of the plurality of metadata records; and

removing the top-most word or phrase from the list of words or phrases in response to determining that the top-most word or phrase does not occur in at least the particular number of the plurality of metadata records.

18. The method of claim 1, where storing the association between the document and the particular number of the highest ranking ones of the selected metadata records further comprises:

storing a link to the text of the document in the plurality of metadata records.

19. The method of claim 1, where storing the association between the document and the particular number of the highest ranking ones of the selected metadata records further-comprises:

storing a portion of the text of the document in the plurality of metadata records.

20. A system, comprising:

one or more processors to;

capture an image of a document;

recognize, based on the image, text of the document;

compare the text of the document to content of each of a plurality of metadata records associated with a plurality of captured documents that differ from the document;

identify sets of matching phrases that occur in both the text of the document and the content of one or more of the metadata records;

calculate a probability of finding each phrase in the set of matching phrases in the plurality of captured documents;

calculate a probability of finding each phrase in the set of matching phrases in the plurality of metadata records;

score each set of matching phrases based on the calculated probability of finding each of the phrases, in the set of matching phrases, in the plurality of captured documents, and the calculated probability of finding each of the phrases in the set of matching phrases in the plurality of metadata records; and

link at least one selected metadata record, from the plurality of metadata records, to the document based on the scoring of the sets of matching phrases.

21. The system of claim 20, where the one or more processors, when identifying the sets of matching phrases, are further to:

identify sets of maximal matching phrases, where none of the maximal matching phrases, in one of the sets of maximal matching phrases,

is a sub-phrase of another of the maximal matching phrases in the one of the sets of maximal matching phrases.

22. A system, comprising:

a first memory to store metadata records;

a second memory to store text of at least one page of a document; and

a processor to;

identify sets of matching phrases included in both the text of the at least one page of the document and the stored metadata records, where each of the sets of matching phrases is associated with one of the metadata records,

score each of the sets of matching phrases based on probabilities of each of the matching phrases, included in the respective set of matching phrases, appearing, respectively, in a randomly selected one of the stored metadata records and in a randomly selected one of a plurality of documents associated with the stored metadata records, where the plurality of documents differ from the document,

select at least one of the stored metadata records, associated with the sets of matching phrases, based on the scoring of each of the sets of matching phrases, and

store information to associate the document with the at least one selected metadata record in the first memory or the second memory.

23. The system of claim 22, where each of the sets of matching phrases:

includes maximal phrases, and

does not include sub-phrases of the maximal phrases included in the respective one of the sets of matching phrases.

24. The system of claim 22, further comprising:

a document capture system to;

perform optical character recognition on an image of the document to recognize text of the document, and

extract the text of the at least one page of the document from the text of the document.

25. A non-transitory computer-readable memory device that stores instructions executable by at least one processor, the computer-readable memory device comprising:

one or more instructions for receiving text of a document;

one or more instructions for identifying a particular page of the document based on the text of the document;

one or more instructions for identifying one or more of a plurality of metadata records, based on a comparison between text of the particular page and information in the plurality of metadata records;

one or more instructions for scoring each of the identified metadata records based on probabilities of one or more common phrases, that appear in both the text of the document and content of the respective identified metadata record, also appearing, respectively, in a randomly selected one of the plurality of metadata records and in a randomly selected one of a plurality of documents associated with the plurality of metadata records, where the plurality of documents differ from the document;

one or more instructions for selecting at least one highest scoring identified metadata record of the identified metadata records; and

one or more instructions for associating, based on the scoring, the selected at least one of the identified metadata records with the document.

26. The non-transitory computer-readable memory device of claim 25, where the one or more instructions for identifying the one or more of the plurality of metadata records comprises:

one or more instructions for identifying words and phrases in the text of document;

one or more instructions for comparing the identified words and phrases, in the text of the document, to each of the plurality of metadata records;

one or more instructions for choosing at least one of the plurality of metadata records, where each of the chosen metadata records includes at least one of the words and phrases identified in the text of the document; and

one or more instructions for identifying one or more of the words or phrases occurring for each of the chosen metadata records.

27. The non-transitory computer-readable memory device of claim 26, where one or more instructions for scoring each of the identified metadata records includes:

one or more instructions for counting occurrences, of each of the identified words and phrases, in the plurality of documents;

one or more instructions for counting occurrences, of each of the identified words and phrases, in the plurality of metadata records;

one or more instructions for calculating, for each of the identified words and phrases, a probability of finding the one of the identified words and phrases in a randomly selected one of the documents in the plurality of documents;

one or more instructions for calculating, for each of the identified words and phrases, a probability of finding the one of the identified words and phrases in a randomly selected one of the plurality of metadata records; and

one or more instructions for scoring one of the identified words and phrases based on the probability of finding the one of the identified words and phrases in the randomly selected one of the documents in the plurality of documents and based on the probability of finding the one of the identified words and phrases in the randomly selected one of the plurality of metadata records.

28. The non-transitory computer-readable memory device of claim 25, where the one or more instructions for identifying the one or more of the plurality of metadata records comprises:

one or more instructions for identifying selected words or phrases in the document, where a number of the selected words or phrases in the document is less than a total number of words or phrases in the document,

where the one or more instructions for identifying the selected words or phrases in the document includes;

one or more instructions for generating a list of words or phrases in the document,

one or more instructions for calculating, for each word or phrase in the document, a probability of finding the word or phrase in a randomly selected one of a plurality of documents that differ from the document,

one or more instructions for calculating a maximum possible score for each word or phrase in the document based on the calculated probability of finding the word or phrase in the randomly selected one of the plurality of documents,

one or more instructions for sorting the list of words or phrases, in decreasing order, based on the maximum possible scores, and

one or more instructions for traversing down the sorted list to identify the selected words or phrases in the document; and

one or more instructions for comparing the selected words or phrases to information in the plurality of metadata records.

29. The non-transitory computer-readable memory device of claim 28, where the one or more instructions for traversing down the sorted list to identify the selected words or phrases in the document includes:

one or more instructions for selecting a particular number of top-most words or phrases in the sorted list of words or phrases, where the one or more instructions for selecting the particular number of top-most words or phrases includes;

one or more instructions identifying one or more of the particular number of top-most words or phrases for which an actual score has not been calculated,

one or more instructions for recalculating the score for the one or more of the particular number of top-most words or phrases for which a score has not been calculated,

one or more instructions for re-sorting the list based on recalculating, and

one or more instructions for selecting the particular number of top-most words or phrases in the re-sorted list of words or phrases.

30. The non-transitory computer-readable memory device of claim 29, where the one or more instructions for recalculating the score comprises:

one or more instructions for determining whether the list of words or phrases includes a sub-phrase of the top-most word or phrase; and

one or more instructions for re-calculating the maximum possible score for the identified sub-phrase based on the probability of finding the top-most word or phrase in a randomly selected one of the plurality of metadata records.