Social-based spelling correction for online social networks
In one embodiment, a method includes, receiving, from a client system of a user, a search query including n-grams. The method includes associating each n-gram with verticals based on an analysis of the n-grams by language models. The method includes determining, for each n-gram, if a bloom filter for a vertical associated with the n-gram indicates, based on sub-bloom filters of the bloom filter, the n-gram does exist or does not exist in a set of object names associated with the vertical. Each sub-bloom filter is associated with a subset of the set of object names and indicates the n-gram does exist or does not exist in its subset of object names. The method includes sending, to the client system, an indication that an n-gram of the n-grams is misspelled if a bloom filter indicates the n-gram does not exist in the set of object names associated with the vertical.
1. A method comprising, by one or more computing systems:
receiving, from a client system of a user, a search query comprising one or more n-grams;
associating, by a segmentation component, each n-gram with one or more verticals, the associating of the n-gram being based on an analysis of the n-grams by one or more language models;
determining, by a misspelled classifier component, for each n-gram, if a bloom filter for a vertical associated with the n-gram indicates, based on a plurality of sub-bloom filters of the bloom filter, the n-gram does exist or does not exist in a set of object names present in an index of objects in the vertical of the one or more verticals, each sub-bloom filter being associated with a subset of the set of object names and each sub-bloom filter indicating the n-gram does exist or does not exist in the respective subset of object names; and
sending, to the client system of the user, an indication that one or more of the n-grams is misspelled if a bloom filter for a vertical of the one or more verticals associated with the respective n-gram indicates the n-gram does not exist in the set of object names present in the index of objects in the vertical.
2. The method of claim 1 , wherein the one or more language models are selected based on social information associated with the user.
3. The method of claim 1 , wherein each vertical of the one or more verticals is a data store storing objects of a particular object type.
4. The method of claim 1 , wherein at least one vertical of the one or more verticals is a data store storing objects of two or more object types.
5. The method of claim 1 , wherein each bloom filter and sub-bloom filter uses a hash function to determine whether the n-gram is a member of the set or subsets, respectively, of object names.
6. The method of claim 1 , wherein a set of object names for a bloom filter or a subset of object names for a sub-bloom filter comprises object names associated with previous search queries or object names associated with corrected search queries.
7. The method of claim 1 , wherein determining if the bloom filter for the vertical associated with the n-gram indicates the n-gram does exist or does not exist in the set of object names comprises determining, by the bloom filter, a likelihood that the n-gram is a member of the set of object names.
8. The method of claim 7 , wherein determining, by the bloom filter, the likelihood that the n-gram is a member of the set of object names comprises determining, by each sub-bloom filter of the plurality of sub-bloom filters, a likelihood that the n-gram is a member of the subset of object names associated with the respective sub-bloom filter.
9. The method of claim 1 , further comprising:
identifying, for each n-gram that does not exist in the set of object names, one or more variant-tokens based at least on the bloom filter for the vertical associated with the n-gram and the set of object names present in the index of objects in the vertical; and
generating one or more unique combinations of the n-grams of the search query and variant-tokens, wherein each unique combination comprises a variant-token corresponding to each n-gram that does not exist in a set of object names present in an index of objects in a vertical associated with the n-gram.
10. The method of claim 9 , wherein identifying one or more variant-tokens is further based on a language model associated with the user.
11. The method of claim 9 , wherein generating one or more unique combinations of the n-grams and variant-tokens comprises:
calculating a token score for each identified variant-token based on at least a language model, an error-correction model, and a bloom filter comprising a plurality of sub-bloom filters, wherein the language model, the error-correction model, and the bloom filter are associated with the vertical associated with the n-gram corresponding to the identified variant-token, and wherein the token score indicates if the identified variant-token exists in the language model, error-correction model, and the set of object names present in the index of objects in the vertical; and
wherein each variant-token used in a unique combination has a token score greater than a threshold token score.
12. The method of claim 9 , wherein generating one or more unique combinations of the n-grams and variant-tokens comprises:
calculating a combination score for each unique combination based on whether the bloom filter indicates, based on the plurality of sub-bloom filters of the bloom filter, the unique combination does exist or does not exist in the set of object names present in the index of objects in a vertical associated with an n-gram or variant-token of the unique combination; and
selecting one or more of the unique combinations having a combination score greater than a threshold combination score.
13. The method of claim 12 , wherein calculating the combination score for each unique combination is further based on one or more of:
an indication of a valid grammar construct for the unique combination;
an indication of whether the unique combination is associated with a database of previously identified lexicons associated with the vertical associated with the search query; or
a measure of interactions with the unique combination by one or more users of an online social network.
14. The method of claim 9 , further comprising:
calculating a confidence score for each unique combination based at least in part on the search query and whether the bloom filter for a vertical associated with an n-gram or variant-token of each unique combination indicates the unique combination does exist or does not exist in a set of object names present in an index of objects in the vertical.
15. The method of claim 14 , wherein calculating the confidence score for each unique combination is further based on whether the unique combination is relevant to a delivery of advertisements to the user of the online social network.
16. The method of claim 14 , wherein calculating the confidence score for each unique combination is further based on a number of times the unique combination has appeared as a search query in the past.
17. The method of claim 14 , further comprising:
identifying objects matching each unique combination having a confidence score greater than a threshold confidence score; and
sending, to the client system of the user, instructions for generating a search-results interface comprising one or more references to one or more of the identified objects, respectively.
18. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:
receive, from a client system of a user, a search query comprising one or more n-grams;
associate, by a segmentation component, each n-gram with one or more verticals, the associating of the n-gram being based on an analysis of the n-grams by one or more language models;
determine, by a misspelled classifier component, for each n-gram, if a bloom filter for a vertical associated with the n-gram indicates, based on a plurality of sub-bloom filters of the bloom filter, the n-gram does exist or does not exist in a set of object names present in an index of objects in the vertical of the one or more verticals, each sub-bloom filter being associated with a subset of the set of object names and each sub-bloom filter indicating the n-gram does exist or does not exist in the respective subset of object names; and
send, to the client system of the user, an indication that one or more of the n-grams is misspelled if a bloom filter for a vertical of the one or more verticals associated with the respective n-gram indicates the n-gram does not exist in the set of object names present in the index of objects in the vertical.
19. A system comprising: one or more processors; and a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to:
receive, from a client system of a user, a search query comprising one or more n-grams;
associate, by a segmentation component, each n-gram with one or more verticals, the associating of the n-gram being based on an analysis of the n-grams by one or more language models;
determine, by a misspelled classifier component, for each n-gram, if a bloom filter for a vertical associated with the n-gram indicates, based on a plurality of sub-bloom filters of the bloom filter, the n-gram does exist or does not exist in a set of object names present in an index of objects in the vertical of the one or more verticals, each sub-bloom filter being associated with a subset of the set of object names and each sub-bloom filter indicating the n-gram does exist or does not exist in the respective subset of object names; and
send, to the client system of the user, an indication that one or more of the n-grams is misspelled if a bloom filter for a vertical of the one or more verticals associated with the respective n-gram indicates the n-gram does not exist in the set of object names present in the index of objects in the vertical.