Generating context-based spell corrections of entity names

• US 8,402,032 B1
• Filed: 03/24/2011
• Issued: 03/19/2013
• Est. Priority Date: 03/25/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Brunsman, Lawrence J., Lerner, Uri N., Tong, Simon, Devin, Matthieu
• Primary Examiner(s): LE, DEBBIE M
• Application Number:
  US13/071,378
• Time in Patent Office: 726 Days
• Field of Search: 707/748, 707/750, 707/711
• US Class Current: 707/748
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for correcting entity names. One method includes receiving texts and deriving a plurality of name-context pairs from the texts. The method further includes calculating a context consistency measure for each name-context pair and storing context-entity name data representing the name-context pairs. Another method includes identifying an entity name and one or more context terms from a query and generating candidate names for the entity name. The method further includes determining a score for each of the candidate names, selecting a number of top scoring candidate names, and using the selected candidate names to respond to the query.

Claims

1. A system comprising:

one or more computers including one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations comprising;

receiving texts from each of a plurality of text sources, wherein each text source provides a text;

deriving a plurality of name-context pairs from the texts, wherein each name-context pair comprises an entity name included in the text from a text source and a context term included in the text from the text source, wherein each entity name is one or more terms used to refer to a respective entity and each context term is a term that appears in text associated with the entity name;

calculating a context consistency measure for each distinct name-context pair, wherein the context consistency measure for a particular name-context pair is an estimate of a probability that, if the entity name of the particular name-context pair appears in text, the context term of the particular name-context pair will also appear in the text; and

storing context-entity name data, wherein the context-entity name data is searchable data that represents one or more of the distinct name-context pairs and the context consistency measure for each of the one or more name-context pair.

2. The system of claim 1, wherein the context-entity name data maps each context term in the name-context pairs to a list of entity names and the context consistency measure for each entity name.

3. The system of claim 1, wherein the text sources comprise documents.

4. The system of claim 1, wherein the text sources comprise query sessions.

5. The system of claim 1, wherein the context term of each name-context pair is identified from a window of text associated with the entity name of the name-context pair.

6. The system of claim 5, wherein the window of text includes a specified number of terms before and after the entity name in the text from which the entity name is identified and the title of the document.

7. The system of claim 1, wherein:

the operations further comprise determining a respective popularity score for each entity name in the plurality of name-context pairs; and

the context-entity name data associates the entity names with the respective popularity scores.

8. The system of claim 7, wherein the popularity score for an entity name is related to how often the entity name appears in the texts.

9. The system of claim 8, wherein the popularity score is derived from a number of times the entity name appears in the texts and a total number of times any entity name in the plurality of name-context pairs appears in the texts.

10. The system of claim 8, wherein the popularity score is derived by dividing a number of the texts in which the entity name appears by a number of the texts from the plurality of text sources in which any entity name in the plurality of name-context pairs appears.

11. The system of claim 1, wherein the operations further comprise:

generating a score for each of the name-context pairs; and

excluding, from the context-entity name data, name-context pairs having a score that is less than a threshold.

12. The system of claim 11, wherein the score for a name-context pair is derived from the context consistency measure for the name-context pair and an average context consistency measure for the context and all entity names in the distinct name-context pairs.

13. The system of claim 12, wherein the score for a name-context pair is further derived from a number of times the entity name and the context term of the name-context pair appear in queries submitted to a search engine during a period of time.

14. The system of claim 11, wherein:

a first name-context pair is derived from texts from multiple text sources; and

the operations further comprise modifying the score for the first name-context pair to reflect a similarity of the texts from which the first name-context pair was derived.

15. The system of claim 14, wherein the operations further comprise:

determining a fingerprint bucket for each text from which the first name-context pair is derived;

analyzing a distribution of the fingerprint buckets to determine that the distribution is skewed from a normal distribution; and

modifying the score by discounting the score.

16. The system of claim 1, wherein each entity name has one or more parts and the context-entity name data further associates each entity name with a respective canonical form of each part of the entity name.

17. The system of claim 1, wherein each entity name has one or more parts and the context-entity name data further associates one or more of the entity names with one or more related name parts for one or more parts of the entity name.

18. The system of claim 1, wherein the related text for the text from a text source comprises the text from the text source.

19. The system of claim 1, wherein each entity name is a name of a respective person.

20. A computer-implemented method, comprising:

receiving texts from each of a plurality of text sources, wherein each text source provides a text;

deriving a plurality of name-context pairs from the texts, wherein each name-context pair comprises an entity name included in the text from a text source and a context term included in the text from the text source, wherein each entity name is one or more terms used to refer to a respective entity and each context term is a term that appears in text associated with the entity name;

calculating a context consistency measure for each distinct name-context pair, wherein the context consistency measure for a particular name-context pair is an estimate of a probability that, if the entity name of the particular name-context pair appears in text, the context term of the particular name-context pair will also appear in the text; and

storing context-entity name data, wherein the context-entity name data is searchable data that represents one or more of the distinct name-context pairs and the context consistency measure for each of the one or more name-context pair.

21. The method of claim 20, wherein the context-entity name data maps each context term in the name-context pairs to a list of entity names and the context consistency measure for each entity name.

22. The method of claim 20, wherein the text sources comprise documents.

23. The method of claim 20, wherein the text sources comprise query sessions.

24. The method of claim 20, wherein the context term of each name-context pair is identified from a window of text associated with the entity name of the name-context pair.

25. The method of claim 24, wherein the window of text includes a specified number of terms before and after the entity name in the text from which the entity name is identified and the title of the document.

26. The method of claim 20, further comprising determining a respective popularity score for each entity name in the plurality of name-context pairs, wherein the context-entity name data associates the entity names with the respective popularity scores.

27. The method of claim 26, wherein the popularity score for an entity name is related to how often the entity name appears in the texts.

28. The method of claim 27, wherein the popularity score is derived from a number of times the entity name appears in the texts and a total number of times any entity name in the plurality of name-context pairs appears in the texts.

29. The method of claim 27, wherein the popularity score is derived by dividing a number of the texts in which the entity name appears by a number of the texts from the plurality of text sources in which any entity name in the plurality of name-context pairs appears.

30. The method of claim 20, further comprising:

generating a score for each of the name-context pairs; and

excluding, from the context-entity name data, name-context pairs having a score that is less than a threshold.

31. The method of claim 30, wherein the score for a name-context pair is derived from the context consistency measure for the name-context pair and an average context consistency measure for the context and all entity names in the distinct name-context pairs.

32. The method of claim 31, wherein the score for a name-context pair is further derived from a number of times the entity name and the context term of the name-context pair appear in queries submitted to a search engine during a period of time.

33. The method of claim 30, wherein:

a first name-context pair is derived from texts from multiple text sources; and

the operations further comprise modifying the score for the first name-context pair to reflect a similarity of the texts from which the first name-context pair was derived.

34. The method of claim 33, further comprising:

determining a fingerprint bucket for each text from which the first name-context pair is derived;

analyzing a distribution of the fingerprint buckets to determine that the distribution is skewed from a normal distribution; and

modifying the score by discounting the score.

35. The method of claim 20, wherein each entity name has one or more parts and the context-entity name data further associates each entity name with a respective canonical form of each part of the entity name.

36. The method of claim 20, wherein each entity name has one or more parts and the context-entity name data further associates one or more of the entity names with one or more related name parts for one or more parts of the entity name.

37. The method of claim 20, wherein the related text for the text from a text source comprises the text from the text source.

38. The method of claim 20, wherein each entity name is a name of a respective person.

39. A computer storage medium storing instructions that, when executed by data processing apparatus, cause the one or more computers to perform operations comprising:

receiving texts from each of a plurality of text sources, wherein each text source provides a text;

deriving a plurality of name-context pairs from the texts, wherein each name-context pair comprises an entity name included in the text from a text source and a context term included in the text from the text source, wherein each entity name is one or more terms used to refer to a respective entity and each context term is a term that appears in text associated with the entity name;

calculating a context consistency measure for each distinct name-context pair, wherein the context consistency measure for a particular name-context pair is an estimate of a probability that, if the entity name of the particular name-context pair appears in text, the context term of the particular name-context pair will also appear in the text; and

storing context-entity name data, wherein the context-entity name data is searchable data that represents one or more of the distinct name-context pairs and the context consistency measure for each of the one or more name-context pair.

40. The computer storage medium of claim 39, wherein the context-entity name data maps each context term in the name-context pairs to a list of entity names and the context consistency measure for each entity name.

41. The computer storage medium of claim 39, wherein the text sources comprise documents.

42. The computer storage medium of claim 39, wherein the text sources comprise query sessions.

43. The computer storage medium of claim 39, wherein the context term of each name-context pair is identified from a window of text associated with the entity name of the name-context pair.

44. The computer storage medium of claim 43, wherein the window of text includes a specified number of terms before and after the entity name in the text from which the entity name is identified and the title of the document.

45. The computer storage medium of claim 39, wherein:

the operations further comprise determining a respective popularity score for each entity name in the plurality of name-context pairs; and

the context-entity name data associates the entity names with the respective popularity scores.

46. The computer storage medium of claim 45, wherein the popularity score for an entity name is related to how often the entity name appears in the texts.

47. The computer storage medium of claim 46, wherein the popularity score is derived from a number of times the entity name appears in the texts and a total number of times any entity name in the plurality of name-context pairs appears in the texts.

48. The computer storage medium of claim 46, wherein the popularity score is derived by dividing a number of the texts in which the entity name appears by a number of the texts from the plurality of text sources in which any entity name in the plurality of name-context pairs appears.

49. The computer storage medium of claim 39, wherein the operations further comprise:

generating a score for each of the name-context pairs; and

excluding, from the context-entity name data, name-context pairs having a score that is less than a threshold.

50. The computer storage medium of claim 49, wherein the score for a name-context pair is derived from the context consistency measure for the name-context pair and an average context consistency measure for the context and all entity names in the distinct name-context pairs.

51. The computer storage medium of claim 50, wherein the score for a name-context pair is further derived from a number of times the entity name and the context term of the name-context pair appear in queries submitted to a search engine during a period of time.

52. The computer storage medium of claim 49, wherein:

a first name-context pair is derived from texts from multiple text sources; and

the operations further comprise modifying the score for the first name-context pair to reflect a similarity of the texts from which the first name-context pair was derived.

53. The computer storage medium of claim 52, wherein the operations further comprise:

determining a fingerprint bucket for each text from which the first name-context pair is derived;

analyzing a distribution of the fingerprint buckets to determine that the distribution is skewed from a normal distribution; and

modifying the score by discounting the score.

54. The computer storage medium of claim 39, wherein each entity name has one or more parts and the context-entity name data further associates each entity name with a respective canonical form of each part of the entity name.

55. The computer storage medium of claim 39, wherein each entity name has one or more parts and the context-entity name data further associates one or more of the entity names with one or more related name parts for one or more parts of the entity name.

56. The computer storage medium of claim 39, wherein the related text for the text from a text source comprises the text from the text source.

57. The computer storage medium of claim 39, wherein each entity name is a name of a respective person.