SUGGESTING SPELLING CORRECTIONS FOR PERSONAL NAMES

• US 20120136650A1
• Filed: 11/30/2010
• Published: 05/31/2012
• Est. Priority Date: 11/30/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Udupa, Uppinakuduru Raghavendra, Kumar, Shaishav
• Granted Patent: US 8,438,011 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

Personal name spelling correction suggestion technique embodiments are presented which provide suggestions for alternate spellings of a personal name. This involves creating a personal name directory which can be queried to suggest spelling corrections for personal names. A hash function that maps any personal name in a particular language and misspellings thereof to similar binary codewords is used to produce one or more binary codewords for each personal name in the directory. The same hash function is used to produce one or more binary codewords from a personal name presented in a query. The personal name directory is employed to identify up to a prescribed number of personal names, each of which has one or more associated binary codewords that are similar to one or more of the binary codewords produced from the personal name query. The identified personal names are suggested as alternate names for the query personal name.

Claims

1. A computer-implemented process for creating a personal name directory which can be queried to suggest spelling corrections for personal names, comprising:

using a computer to perform the following process actions;

computing a hash function that maps any personal name in a particular language and misspellings thereof to similar binary codewords; and

for each personal name in a directory of personal names in said particular language, using said hash function to produce one or more binary codewords and associating the said codeword or codewords with the personal name.

2. The process of claim 1, wherein the process action of computing the hash function that maps any personal name in a particular language and misspellings thereof to similar binary codewords, comprises the action of:

inputting a set of training personal names in said particular language for training purposes;

segmenting each training personal name into constituent tokens, wherein each token corresponds to a word in the personal name comprising a continuous string of characters unbroken by a space and whose characters are consistent with the types of characters employed in personal names in said particular language;

for each possible pairing of the tokens derived from the training personal names, computing a similarity measure that is indicative of a degree of similarity between the tokens in the pair under consideration; and

computing a hash function that maps similar tokens to similar binary codewords using said pairs of tokens, wherein said computation comprises finding a hash function wherein the summation of the product of the similarity measure computed for a pair of tokens and the distance between the codewords produced by the hash function for that pair of tokens, over all possible pairings of the tokens derived from the training personal names, is minimized.

3. The process of claim 2, wherein the process actions of computing a similarity measure that is indicative of a degree of similarity between the tokens in the pair under consideration and computing a hash function that maps similar tokens to similar binary codewords using said pairs of tokens, comprises the actions of:

representing each token as a vector of features;

computing a similarity measure that is indicative of a degree of similarity between the featurized tokens in the pair of featurized tokens under consideration; and

computing a hash function that maps similar featurized tokens to similar binary codewords using said pairs of featurized tokens.

4. The process of claim 2, wherein the process action of computing the hash function that maps similar tokens to similar binary codewords, comprises an action of characterizing the computation of the hash function as an optimization equation whose relaxation can be solved using a generalized Eigenvalue technique.

5. The process of claim 1, wherein the process action of computing the hash function that maps any personal name in a particular language and misspellings thereof to similar binary codewords, comprises the action of:

inputting a set of training personal names in said particular language;

segmenting each training personal name into constituent tokens, wherein each token corresponds to a word in the personal name comprising a continuous string of characters unbroken by a space and whose characters are consistent with the types of characters employed in personal names in said particular language;

for each token derived from of the training personal names, inputting one or more equivalents of the token in another language or languages, wherein each of said equivalents input for a token is in a language that is different from any other input equivalent of the token, and wherein the language or languages of the one or more equivalents are the same for every token;

computing a hash function that maps any token in the particular language and misspellings thereof to similar binary codewords using said tokens derived from the training personal names and said one or more equivalents of each of the tokens.

6. The process of claim 5, wherein the process action of computing the hash function that maps any token in the particular language and misspellings thereof to similar binary codewords using said tokens derived from the training personal names and said one or more equivalents of each of the tokens, comprises the actions of:

representing each token as a vector of features;

representing the equivalent or equivalents of each token as a vector of features; and

computing a hash function that maps the featurized version of any token in the particular language and featurized versions of misspellings of that token to similar binary codewords using said featurized tokens derived from of the training personal names and said one or more featurized equivalents of each of the tokens.

7. The process of claim 5, wherein the process action of computing the hash function that maps any token in the particular language and misspellings thereof to similar binary codewords using said tokens derived from the training personal names and said one or more equivalents of each of the tokens, comprises an action of characterizing the computation of the hash function as an optimization equation whose relaxation can be solved using a generalized Eigenvalue technique.

8. The process of claim 1, wherein the process action of using said hash function to produce one or more binary codewords and associating the codeword or codewords with the personal name, for each personal name in a directory of personal names in said particular language, comprises the actions of:

segmenting each personal name in the personal name directory into constituent tokens, wherein each token corresponds to a word in the personal name comprising a continuous string of characters unbroken by a space and whose characters are consistent with the types of characters employed in personal names in said particular language;

identifying a set of unique tokens from the constituent tokens of the personal names from the personal name directory;

generating an index which for each token in the set of unique tokens identifies all the personal names in the personal name directory that have that token as one of its constituent tokens;

applying said hash function to each unique token to produce a binary codeword representation thereof; and

associating the binary codeword produced for each unique token with that token in said index.

9. The process of claim 8, wherein the process action of applying said hash function to each unique token to produce a binary codeword representation thereof, comprises the actions of:

representing each unique token as a vector of features; and

applying said hash function to each featurized unique token to produce the binary codeword representation thereof.

10. A computer-implemented process for providing one or more suggested spelling corrections for a personal name included in a personal name query, comprising:

inputting a personal name query comprising a personal name in a particular language;

using a hash function to produce one or more binary codewords from the personal name in the personal name query, wherein said hash function maps any personal name in a particular language and misspellings thereof to similar binary codewords;

employing a personal name directory to identify up to a prescribed number of personal names in the personal name directory, each of which has one or more of the associated binary codewords that are similar to one or more of the binary codewords produced from the personal name query;

designating the identified personal names as potential personal name corrections; and

suggesting one or more of the potential personal name corrections as alternate names for the personal name from the personal name query.

11. The process of claim 10, wherein said hash function was used to respectively produce and associate one or more binary codewords with each personal name in the personal name directory in said particular language, said producing and associating comprising,

segmenting each personal name in the personal name directory into constituent tokens, wherein each token corresponds to a word in the personal name comprising a continuous string of characters unbroken by a space and whose characters are consistent with the types of characters employed in personal names in said particular language,

identifying a set of unique tokens from the constituent tokens of the personal names from the personal name directory;

generating an index which for each token in the set of unique tokens identifies all the personal names in the personal name directory that have that token as one of its constituent tokens;

applying said hash function to each unique token to produce a binary codeword representation thereof; and

associating the binary codeword produced for each unique token with that token in said index, and wherein the process action of using said hash function to produce one or more binary codewords from the personal name in the personal name query, comprises the actions of;

segmenting the personal name from the query into constituent tokens, wherein each token corresponds to a word in the personal name comprising a continuous string of characters unbroken by a space and whose characters are consistent with the types of characters employed in personal names in said particular language;

identifying unique tokens within the constituent tokens segmented from the personal name query that are a member of said set of unique tokens; and

applying said hash function to each identified unique token from the personal name query to produce a binary codeword for each of the identified unique tokens.

12. The process of claim 11, wherein the process action of applying said hash function to each identified unique token from the personal name query to produce a binary codeword for each of the identified unique tokens, comprises the actions of:

representing each identified unique token from the personal name query as a vector of features; and

applying said hash function to each featurized unique token from the personal name query to produce a binary codeword for each of the featurized unique tokens.

13. The process of claim 11, wherein the process action of employing a personal name directory to identify up to a prescribed number of personal names in the personal name directory each of which has one or more of its associated binary codewords that are similar to one or more of the binary codewords produced from the personal name query, comprises the actions of:

for each binary codeword associated with the personal name query,

respectively computing said distance measure between the personal name query codeword and each codeword computed for a unique token derived from the personal name directory,

identifying codewords computed for a unique token derived from the personal name directory that have a computed distance measure from the personal name query codeword that is less than said prescribed distance threshold;

for each unique token corresponding to a one of the identified codewords, respectively computing a token level similarity measure between that token and each token associated with the personal name query;

ranking the unique tokens corresponding to the identified codewords based on their computed similarity measure;

retaining a prescribed number of the top ranking unique tokens;

identifying the personal names in the personal name directory that comprise any of the retained top ranking unique tokens and designate each of these personal names as a candidate personal name;

identifying a prescribed number of the candidate personal names from the personal name directory that most closely match the personal name from the query, wherein a personal name from the directory is deemed to most closely match a query personal name whenever a personal name similarity score computed using the token level similarity measures computed between the tokens of the candidate personal name and personal name from the query is one of said prescribed number of the top ranking candidate personal names based on the personal name similarity scores; and

for each of the identified prescribed number of the candidate personal names from the personal name directory that most closely match the personal name from the query,

ascertaining if the personal name similarity score computed for the candidate personal name exceeds a prescribed personal name similarity threshold, and

designating each candidate personal name whose personal name similarity score is ascertained to exceed the prescribed personal name similarity threshold as potential personal name corrections.

14. The process of claim 13, wherein the process action of respectively computing said distance measure between the personal name query codeword and each codeword computed for a unique token derived from the personal name directory, comprises computing a Hamming distance between the personal name query codeword and each codeword computed for a unique token derived from the personal name directory.

15. The process of claim 13, wherein the process action of, for each unique token corresponding to a one of the identified codewords, respectively computing a token level similarity measure between that token and each token associated with the personal name query, comprises an action of employing a logistic function applied over multiple distance measures to compute the token level similarity measure.

16. The process of claim 15, wherein the multiple distance measures between tokens comprise a normalized Damerau-Levenshtein edit distance measure between the tokens and a Hamming distance between codewords corresponding to the tokens.

17. The process of claim 13, wherein the process action of computing the personal name similarity score between the tokens of a candidate personal name and personal name from the query, comprises the action of:

constructing a weighted bipartite graph comprising a node for each token of the candidate personal name and for each token of the personal name from the query, and an edge weight assigned between each possible pair of nodes in the graph that is equal to a token-level similarity measure computed between the tokens associated with the pair of nodes;

computing a value of the maximum weighted bipartite matching for the graph; and

dividing the maximum weighted bipartite matching value by the absolute value of the difference between the number of tokens in the candidate personal name and the number of tokens in the query personal name, plus one, to produce the personal name similarity score for the candidate personal name.

18. A computer-implemented process for suggesting spelling corrections for personal names, comprising:

using a computer to perform the following process actions;

computing a hash function that maps any personal name in a particular language and misspellings thereof to similar binary codewords;

for each personal name in a directory of personal names in said particular language, using said hash function to produce one or more binary codewords and associating the said codeword or codewords with the personal name;

inputting a personal name query comprising a personal name in said particular language;

using said hash function to produce one or more binary codewords from the personal name in the personal name query;

identifying up to a prescribed number of personal names in the personal name directory each of which has one or more of its associated binary codewords that are similar to one or more of the binary codewords produced from the personal name query and designating the identified personal names as potential personal name corrections; and

suggesting one or more of the potential personal name corrections as alternate names for the personal name from the personal name query.

19. The process of claim 18, wherein the process action of computing the hash function that maps any personal name in a particular language and misspellings thereof to similar binary codewords, comprises the action of:

inputting a set of training personal names in said particular language for training purposes;

segmenting each training personal name into constituent tokens, wherein each token corresponds to a word in the personal name comprising a continuous string of characters unbroken by a space and whose characters are consistent with the types of characters employed in personal names in said particular language;

for each possible pairing of the tokens derived from the training personal names, computing a similarity measure that is indicative of a degree of similarity between the tokens in the pair under consideration; and

computing a hash function that maps similar tokens to similar binary codewords using said pairs of tokens, wherein said computation comprises finding a hash function wherein the summation of the product of the similarity measure computed for a pair of tokens and the distance between the codewords produced by the hash function for that pair of tokens, over all possible pairings of the tokens derived from the training personal names, is minimized.

20. The process of claim 18, wherein the process action of computing the hash function that maps any personal name in a particular language and misspellings thereof to similar binary codewords, comprises the action of:

inputting a set of training personal names in said particular language;

segmenting each training personal name into constituent tokens, wherein each token corresponds to a word in the personal name comprising a continuous string of characters unbroken by a space and whose characters are consistent with the types of characters employed in personal names in said particular language;

for each token derived from of the training personal names, inputting one or more equivalents of the token in another language or languages, wherein each of said equivalents input is in a language that is different any other input equivalents of the token, and wherein the language or languages of the one or more equivalents are the same for every token;

computing a hash function that maps any token in the particular language and misspellings thereof to similar binary codewords using said tokens derived from the training personal names and said one or more equivalents of each of the tokens.