Method and system for providing query suggestions based on personalized spelling correction

1. A method, implemented on a machine having at least one processor, storage, and a communication platform connected to a network for providing a query suggestion, the method comprising:

receiving a request for query suggestions with respect to a query prefix input by a user, wherein the query prefix includes a misspelled portion;

obtaining personal data of the user for identifying at least one spelling correction candidate for the query prefix, the personal data including a list of item candidates;

generating one or more spelling correction candidates based on the personal data and the query prefix, wherein each of the one or more spelling correction candidates represents a possible spelling correction of the query prefix, wherein the one or more spelling correction candidates are generated by:

determining a set of matching item candidates based on one or more versions of the query prefix and the list of item candidates, wherein each of the one or more versions is determined by shortening the query prefix by one or more characters until a predetermined threshold condition is met, wherein the one or more spelling correction candidates comprise the set of matching candidate items;

determining one or more query suggestions for the query prefix based on the one or more spelling correction candidates; and

providing the one or more query suggestions as a response to the request.

2. The method of claim 1 , wherein the personal data include information related to at least one of: a personal contact list of the user; a personal search history of the user; a personal online chat history of the user; personal emails of the user; or a personal calendar input of the user.

3. The method of claim 1 , wherein determining the set of matching item candidates comprises:

generating the list of item candidates including one or more item candidates based on the personal data of the user;

matching the query prefix with the one or more item candidates to determine one or more matched item candidates, wherein:

shortening the query prefix comprises truncating the query prefix to obtain a truncated query prefix, the truncated query prefix being one of the one or more versions of the query prefix, and the one or more characters that the query prefix are based on a predetermined direction and a predetermined step;

matching the truncated query prefix with the one or more item candidates to determine one or more additional matched item candidates; and

repeating the steps of truncating and matching until the predetermined threshold condition is met, the predetermined threshold condition comprising a number of matched item candidates reaching a predetermined threshold, wherein the set of matching item candidates is obtained responsive to the number of matched item candidates reaching the predetermined threshold, and wherein the one or more spelling correction candidates are generated based on the set of matching candidate items.

4. The method of claim 1 , wherein determining the one or more query suggestions comprises:

partitioning each of the one or more spelling correction candidates to generate a candidate prefix based on the query prefix;

determining an edit distance between the query prefix and each candidate prefix, wherein the edit distance is represented by a minimum number of possible edits to change the candidate prefix to the query prefix;

obtaining a predetermined threshold related to the edit distance; and

selecting one or more candidate prefixes based on their respective edit distances and the predetermined threshold.

5. The method of claim 4 , wherein determining the one or more query suggestions further comprises:

aligning text between the query prefix and each of the selected one or more candidate prefixes;

segmenting the aligned texts of the query prefix and each selected candidate prefix into N-grams;

obtaining a pre-calculated transformation probability for misspelling a N-gram in the query prefix with a corresponding N-gram in each selected candidate prefix from a database;

calculating a misspelling likelihood associated with each selected candidate prefix based on the pre-calculated transformation probabilities;

retrieving a misspelling likelihood threshold; and

selecting the one or more query suggestions from the selected one or more candidate prefixes based on their respective associated misspelling likelihoods and the misspelling likelihood threshold.

6. The method of claim 5 , further comprising:

generating at least one knowledge-based query suggestion based on the query prefix;

determining a score for each of the at least one knowledge-based query suggestion and the one or more query suggestions;

modifying the score for each of the one or more query suggestions based on its associated misspelling likelihood; and

ranking the at least one knowledge-based query suggestion and the one or more query suggestions based on their respective scores and modified scores to generate a ranked list of query suggestions, wherein the one or more query suggestions provided as the response is further based on the ranked list of query suggestions.

7. The method of claim 1 , further comprising:

generating at least one knowledge-based query suggestion based on the query prefix; and

providing both the at least one knowledge-based query suggestion and the one or more query suggestions as the response to the request, wherein the one or more query suggestions are to be presented in a different format than that of the at least one knowledge-based query suggestion, and a presentation of the at least one knowledge-based query suggestion and the one or more query suggestions to the user is based on the personal data.

8. A system having at least one processor, storage, and a communication platform connected to a network for providing a query suggestion, comprising:

a query suggestion request parser configured for receiving a request for query suggestions with respect to a query prefix input by a user, wherein the query prefix includes a misspelled portion;

a personal data retriever configured for obtaining personal data of the user for identifying at least one spelling correction candidate for the query prefix, the personal data including a list of item candidates;

a spelling correction candidate generator configured for generating one or more spelling correction candidates based on the personal data and the query prefix, wherein each of the one or more spelling correction candidates represents a possible spelling correction of the query prefix, wherein the one or more spelling correction candidates are generated by:

determining a set of matching item candidates based on one or more versions of the query prefix and the list of item candidates, wherein each of the one or more versions is determined by shortening the query prefix by one or more characters until a predetermined threshold condition is met, wherein the one or more spelling correction candidates comprise the set of matching candidate items;

a spelling correction candidate evaluator configured for determining one or more query suggestions for the query prefix based on the one or more spelling correction candidates; and

a query suggestion integrator configured for providing the one or more query suggestions as a response to the request.

9. The system of claim 8 , wherein the personal data include information related to at least one of: a personal contact list of the user; a personal search history of the user; a personal online chat history of the user; personal emails of the user; or a personal calendar input of the user.

10. The system of claim 8 , wherein determining the set of matching item candidates comprises:

generating the list of item candidates including one or more item candidates based on the personal data of the user;

matching the query prefix with the one or more item candidates to determine one or more matched item candidates, wherein: shortening the query prefix comprises truncating the query prefix to obtain a truncated query prefix, the truncated query prefix being one of the one or more versions of the query prefix, and the one or more characters that the query prefix are based on a predetermined direction and a predetermined step;

matching the truncated query prefix with the one or more item candidates to determine one or more additional matched item candidates; and

repeating the steps of truncating and matching until the predetermined threshold condition is met, the predetermined threshold condition comprising a number of matched item candidates reaching a predetermined threshold, wherein the set of matching item candidates is obtained responsive to the number of matched item candidates reaching the predetermined threshold, and wherein the one or more spelling correction candidates are generated based on the set of matching candidate items.

11. The system of claim 8 , wherein determining the one or more query suggestions comprises:

partitioning each of the one or more spelling correction candidates to generate a candidate prefix based on the query prefix;

determining an edit distance between the query prefix and each candidate prefix, wherein the edit distance is represented by a minimum number of possible edits to change the candidate prefix to the query prefix;

obtaining a predetermined threshold related to the edit distance; and

selecting one or more candidate prefixes based on their respective edit distances and the predetermined threshold.

12. The system of claim 11 , wherein determining the one or more query suggestions further comprises:

aligning text between the query prefix and each of the selected one or more candidate prefixes;

segmenting the aligned texts of the query prefix and each selected candidate prefix into N-grams;

obtaining a pre-calculated transformation probability for misspelling a N-gram in the query prefix with a corresponding N-gram in each selected candidate prefix from a database;

calculating a misspelling likelihood associated with each selected candidate prefix based on the pre-calculated transformation probabilities;

retrieving a misspelling likelihood threshold; and

selecting the one or more query suggestions from the selected one or more candidate prefixes based on their respective associated misspelling likelihoods and the misspelling likelihood threshold.

13. The system of claim 12 , further comprising:

a knowledge based query suggestion generator configured for generating at least one knowledge-based query suggestion based on the query prefix, wherein the query suggestion integrator is further configured for:

determining a score for each of the at least one knowledge-based query suggestion and the one or more query suggestions;

modifying the score for each of the one or more query suggestions based on its associated misspelling likelihood; and

ranking the at least one knowledge-based query suggestion and the one or more query suggestions based on their respective scores and modified scores to generate a ranked list of query suggestions, wherein the one or more query suggestions provided as the response is further based on the ranked list of query suggestions.

14. The system of claim 8 , further comprising:

a knowledge based query suggestion generator configured for generating at least one knowledge-based query suggestion based on the query prefix, wherein the query suggestion integrator is further configured for:

providing both the at least one knowledge-based query suggestion and the one or more query suggestions as the response to the request, wherein the one or more query suggestions are to be presented in a different format than that of the at least one knowledge-based query suggestion, and a presentation of the at least one knowledge-based query suggestion and the one or more query suggestions to the user is based on the personal data.

15. A non-transitory machine-readable medium having information recorded thereon for providing a query suggestion, wherein the information, when read by the machine, causes the machine to perform the following:

receiving a request for query suggestions with respect to a query prefix input by a user, wherein the query prefix includes a misspelled portion;

obtaining personal data of the user for identifying at least one spelling correction candidate for the query prefix, the personal data including a list of item candidates;

generating one or more spelling correction candidates based on the personal data and the query prefix, wherein each of the one or more spelling correction candidates represents a possible spelling correction of the query prefix, wherein the one or more spelling correction candidates are generated by:

determining a set of matching item candidates based on one or more versions of the query prefix and the list of item candidates, wherein each of the one or more versions is determined by shortening the query prefix by one or more characters until a predetermined threshold condition is met, wherein the one or more spelling correction candidates comprise the set of matching candidate items;

determining one or more query suggestions for the query prefix based on the one or more spelling correction candidates; and

providing the one or more query suggestions as a response to the request.

16. The medium of claim 15 , wherein the personal data include information related to at least one of: a personal contact list of the user; a personal search history of the user; a personal online chat history of the user; personal emails of the user; or a personal calendar input of the user.

17. The medium of claim 15 , wherein determining the set of matching item candidates comprises:

generating the list of item candidates including one or more item candidates based on the personal data of the user;

matching the query prefix with the one or more item candidates to determine one or more matched item candidates, wherein:

shortening the query prefix comprises truncating the query prefix to obtain a truncated query prefix, the truncated query prefix being one of the one or more versions of the query prefix, and the one or more characters that the query prefix are based on a predetermined direction and a predetermined step;

matching the truncated query prefix with the one or more item candidates to determine one or more additional matched item candidates; and

repeating the steps of truncating and matching until the predetermined threshold condition is met, the predetermined threshold condition comprising a number of matched item candidates reaching a predetermined threshold, wherein the set of matching item candidates is obtained responsive to the number of matched item candidates reaching the predetermined threshold, and wherein the one or more spelling correction candidates are generated based on the set of matching candidate items.

18. The medium of claim 15 , wherein determining the one or more query suggestions comprises:

partitioning each of the one or more spelling correction candidates to generate a candidate prefix based on the query prefix;

determining an edit distance between the query prefix and each candidate prefix, wherein the edit distance is represented by a minimum number of possible edits to change the candidate prefix to the query prefix;

obtaining a predetermined threshold related to the edit distance; and

selecting one or more candidate prefixes based on their respective edit distances and the predetermined threshold.

19. The medium of claim 18 , wherein determining the one or more query suggestions further comprises:

aligning text between the query prefix and each of the selected one or more candidate prefixes;

segmenting the aligned texts of the query prefix and each selected candidate prefix into N-grams;

obtaining a pre-calculated transformation probability for misspelling a N-gram in the query prefix with a corresponding N-gram in each selected candidate prefix from a database;

calculating a misspelling likelihood associated with each selected candidate prefix based on the pre-calculated transformation probabilities;

retrieving a misspelling likelihood threshold; and

selecting the one or more query suggestions from the selected one or more candidate prefixes based on their respective associated misspelling likelihoods and the misspelling likelihood threshold.

20. The medium of claim 19 , wherein the information, when read by the machine, further causes the machine to perform the following:

generating at least one knowledge-based query suggestion based on the query prefix;

determining a score for each of the at least one knowledge-based query suggestion and the one or more query suggestions;

modifying the score for each of the one or more query suggestions based on its associated misspelling likelihood; and

ranking the at least one knowledge-based query suggestion and the one or more query suggestions based on their respective scores and modified scores to generate a ranked list of query suggestions, wherein the one or more query suggestions provided as the response is further based on the ranked list of query suggestions.

21. The medium of claim 15 , wherein the information, when read by the machine, further causes the machine to perform the following:

generating at least one knowledge-based query suggestion based on the query prefix; and

providing both the at least one knowledge-based query suggestion and the one or more query suggestions as the response to the request, wherein the one or more query suggestions are to be presented in a different format than that of the at least one knowledge-based query suggestion, and a presentation of the at least one knowledge-based query suggestion and the one or more query suggestions to the user is based on the personal data.