METHOD OF SPELL-CHECKING SEARCH QUERIES

• US 20130346434A1
• Filed: 09/30/2011
• Published: 12/26/2013
• Est. Priority Date: 04/09/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: SHAZEER, Noam
• Granted Patent: US 8,621,344 B1
• Time in Patent Office: Days
• US Class Current: 707/759
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A computer-implemented method for determining whether a target text-string is correctly spelled is provided. The target text-string is compared to a corpus to determine a set of contexts which each include an occurrence of the target text-string. Using heuristics, each context of the set is characterized based on occurrences in the corpus of the target text-string and a reference text-string. Contexts are characterized as including a correct spelling of the target text-string, an incorrect spelling of the reference text-string, or including an indeterminate usage of the target text-string. A likelihood that the target text-string is a misspelling of the reference text-string is computed as a function of the quantity of contexts including a correct spelling of the target text-string and the quantity of contexts including an incorrect spelling of a reference text-string. In one application, the target text-string is received in a search query, the search executed following a spell-check.

Claims

1-36. -36. (canceled)

37. A method comprising:

receiving a search query that includes a query term;

identifying, from a corpus of documents, text patterns that each include the query term occurring adjacent to one or more other query terms;

determining a first quantity of occurrences of the text patterns that each include the query term occurring adjacent to the one or more other terms, in the corpus of documents;

determining a second quantity of occurrences of text patterns that each include a heterographic homophone of the query term occurring adjacent to the one or more other terms, in the corpus of documents; and

determining, by one or more computers, whether to revise the received search query to include the heterographic homophone of the query term, based on comparing the first quantity and the second quantity.

64. The method of claim 37, wherein determining whether to revise is further based on determining that the first quantity exceeds a threshold value.

65. The method of claim 37, wherein determining whether to revise is further based on determining that the first quantity does not exceed the threshold value, and that the second quantity exceeds the threshold value.

66. The method of claim 37, wherein determining whether to revise comprises determining not to revise when a ratio of the first quantity to the second quantity exceeds a threshold value.

67. The method of claim 37, wherein determining whether to revise comprises determining to revise when the second quantity exceeds a first threshold value, and a ratio of the second quantity to the first quantity exceeds a second threshold value.

68. The method of claim 37, wherein determining whether to revise comprises determining not to revise when a ratio of the first quantity to a sum of the first quantity and the second quantity exceeds a threshold value.

69. The method of claim 37, wherein determining whether to revise comprises determining not to revise when a ratio of the second quantity to a sum of the first quantity and the second quantity is less than a threshold value.

70. The method of claim 37, wherein the corpus of documents is a first corpus of documents, and wherein the method further comprises:

determining a third quantity of occurrences of the received search query in a second corpus of documents, wherein the first corpus of documents includes less misspellings than the second corpus of documents,

wherein the received search query is selected when a ratio of the first quantity to the third quantity exceeds a threshold value.

71. The method of claim 37, wherein the corpus of documents is a first corpus of documents, and wherein the method further comprises:

determining a third quantity of occurrences of the received search query in a second corpus of documents, wherein the first corpus of documents includes less misspellings than the second corpus of documents,

determining a fourth quantity of occurrences of the modified search query in the second corpus of documents, wherein the received search query is selected when a ratio of the first quantity to the third quantity exceeds a ratio of the second quantity to the fourth quantity.

90. The method of claim 37, wherein determining whether to revise is based on a ratio comprising the first quantity and the second quantity.

38-63. -63. (canceled)

72. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

receiving a search query that includes a query term;

identifying, from a corpus of documents, text patterns that each include the query term occurring adjacent to one or more other query terms;

determining a first quantity of occurrences of the text patterns that each include the query term occurring adjacent to the one or more other terms, in the corpus of documents;

determining a second quantity of occurrences of text patterns that each include a heterographic homophone of the query term occurring adjacent to the one or more other terms, in the corpus of documents; and

determining, by one or more computers, whether to revise the received search query to include the heterographic homophone of the query term, based on comparing the first quantity and the second quantity.

73. The system of claim 72, wherein determining whether to revise is further based on determining that the first quantity exceeds a threshold value.

74. The system of claim 72, wherein determining whether to revise is further based on determining that the first quantity does not exceed the threshold value, and the second quantity exceeds a threshold value.

75. The system of claim 72, wherein determining whether to revise comprises determining not to revise the received search query when a ratio of the first quantity to the second quantity exceeds a threshold value.

76. The system of claim 72, wherein determining whether to revise comprises determining not to revise the search query when the first quantity exceeds a first threshold value, and a ratio of the first quantity to the second quantity exceeds a second threshold value.

77. The system of claim 72, wherein determining whether to revise comprises determining not to revise the received search query when a ratio of the first quantity to a sum of the first quantity and the second quantity exceeds a threshold value.

78. The system of claim 72, wherein determining whether to revise comprises determining not to revise when a ratio of the second quantity to a sum of the first quantity and the second quantity is less than a threshold value.

79. The system of claim 72, wherein the corpus of documents is a first corpus of documents, and the operations further comprise:

accessing a second corpus of documents; and

determining a third quantity of occurrences of the received search query in the second corpus of documents, where the first corpus of documents includes less misspellings than the second corpus of documents,

wherein the received search query is selected when a ratio of the first quantity to the third quantity exceeds a threshold value.

80. The system of claim 72, wherein the corpus of documents is a first corpus of documents, and the operations further comprise:

determining a third quantity of occurrences of the received search query in a second corpus of documents, wherein the first corpus of documents includes less misspellings than the second corpus of documents,

determining a fourth quantity of occurrences of the modified search query in the second corpus of documents,

wherein the received search query is selected when a ratio of the first quantity to the third quantity exceeds a ratio of the second quantity to the fourth quantity.

81. A non-transitory computer-readable storage device storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

receiving a search query that includes a query term;

identifying, from a corpus of documents, text patterns that each include the query term occurring adjacent to one or more other query terms;

determining a first quantity of occurrences of the text patterns that each include the query term occurring adjacent to the one or more other terms, in the corpus of documents;

determining a second quantity of occurrences of text patterns that each include a heterographic homophone of the query term occurring adjacent to the one or more other terms, in the corpus of documents; and

determining, by one or more computers, whether to revise the received search query to include the heterographic homophone of the query term, based on comparing the first quantity and the second quantity.

82. The device of claim 81, wherein determining whether to revise is further based on determining that the first quantity does not exceed the threshold value, and the second quantity exceeds a threshold value.

83. The device of claim 81, wherein determining whether to revise comprises determining not to revise when a ratio of the first quantity to the second quantity exceeds a threshold value.

84. The device of claim 81, wherein determining whether to revise comprises determining not to revise when the first quantity exceeds a first threshold value, and a ratio of the first quantity to the second quantity exceeds a second threshold value.

85. The device of claim 81, wherein determining whether to revise comprises determining not to revise when a ratio of the first quantity to a sum of the first quantity and the second quantity exceeds a threshold value.

86. The device of claim 81, wherein determining whether to revise comprises determining not to revise when a ratio of the first quantity to a sum of the first quantity and the second quantity exceeds a threshold value.

87. The device of claim 81, wherein determining whether to revise comprises determining not to revise when a ratio of the second quantity to a sum of the first quantity and the second quantity is less than a threshold value.

88. The device of claim 81, the operations further comprising:

accessing a second corpus of documents; and

determining a third quantity of occurrences of the received search query in a second corpus of documents, where the first corpus of documents includes less misspellings than the second corpus of documents, where the received search query is selected when a ratio of the first quantity to the third quantity exceeds a threshold value.

89. The device of claim 81, wherein the corpus of documents is a first corpus of documents, and wherein the operations further comprise:

determining a third quantity of occurrences of the received search query in a second corpus of documents, where the first corpus of documents includes less misspellings than the second corpus of documents; and

determining a fourth quantity of occurrences of the modified search query in the second corpus of documents,

wherein the received search query is selected when a ratio of the first quantity to the third quantity exceeds a ratio of the second quantity to the fourth quantity.