1. A method comprising, by one or more computing devices: receiving, from a client system of a user of an online social network, a search query comprising one or more n-grams, wherein the n-grams comprise one or more misspelled n-grams; identifying, for each misspelled n-gram, one or more variant-tokens; calculating, for each identified variant-token of a misspelled n-gram, a feature value indicating a likelihood of the variant-token being a correctly spelled n-gram of the misspelled n-gram, wherein the feature value is based at least on the identified variant-token, the misspelled n-gram, and one or more variant-tokens corresponding to one or more n-grams preceding the misspelled n-gram; generating a plurality of unique combinations of the n-grams and variant-tokens, wherein each unique combination comprises a variant-token corresponding to each misspelled n-gram; calculating a sequence-score for each unique combination based at least in part on the calculated feature values of the variant-tokens of the unique combination, wherein the sequence-score for each unique combination indicates a suitability of the unique combination for correcting the search query; and generating one or more corrected queries, each corrected query comprising a unique combination having a sequence-score greater than a threshold sequence-score; and sending, to the client system of the user for display in response to receiving the search query, one or more of the corrected queries.
1. A method comprising, by one or more computing devices: receiving, from a client system of a user of an online social network, a search query comprising one or more n-grams, wherein the n-grams comprise one or more misspelled n-grams; identifying, for each misspelled n-gram, one or more variant-tokens; calculating, for each identified variant-token of a misspelled n-gram, a feature value indicating a likelihood of the variant-token being a correctly spelled n-gram of the misspelled n-gram, wherein the feature value is based at least on the identified variant-token, the misspelled n-gram, and one or more variant-tokens corresponding to one or more n-grams preceding the misspelled n-gram; generating a plurality of unique combinations of the n-grams and variant-tokens, wherein each unique combination comprises a variant-token corresponding to each misspelled n-gram; calculating a sequence-score for each unique combination based at least in part on the calculated feature values of the variant-tokens of the unique combination, wherein the sequence-score for each unique combination indicates a suitability of the unique combination for correcting the search query; and generating one or more corrected queries, each corrected query comprising a unique combination having a sequence-score greater than a threshold sequence-score; and sending, to the client system of the user for display in response to receiving the search query, one or more of the corrected queries. 8. The method of claim 1 , wherein the calculated sequence-score for each unique combination is based at least in part on a calculated sum of the calculated feature values of the variant-tokens of the unique combination.