Keyboard-based corrections for search queries on online social networks

1. A method comprising, by one or more computing devices of a search engine:

receiving, from a client system of a first user of an online social network, a completed text query submitted to the search engine by the first user using an I/O device associated with the client system, the I/O device comprising a first keyboard layout having a plurality of layers, wherein each of the plurality of layers comprises a particular set of characters, wherein the completed text query comprises N characters having N character positions in a first layer of the plurality of layers of the first keyboard layout;

identifying one or more physical-proximity phrases corresponding to the completed text query based at least in part on a second layer of the plurality of layers of the first keyboard layout, each identified physical-proximity phrase matching one or more n-grams included in a reference corpus, each matching n-gram comprising N characters having N character positions in the second layer of the first keyboard layout;

calculating a confidence score for each of the identified physical-proximity phrases based at least in part on a search history of the first user, wherein the confidence score for each physical-proximity phrase represents a likelihood that the first user intended to include the physical-proximity phrase in the completed text query;

determining one or more corrected text queries, each corrected text query comprising one or more of the physical-proximity phrases having a calculated confidence score greater than a threshold confidence score;

identifying, from a plurality of objects associated with the online social network, responsive to the completed text query, automatically without requiring the first user to select a corrected text query, one or more first objects matching the completed text query and one or more second objects matching at least one of the corrected text queries; and

sending, to the client system of the first user for display, a plurality of search results corresponding to one or more of the identified first objects and one or more of the identified second objects.

2. The method of claim 1 , wherein the I/O device comprises a physical keyboard.

3. The method of claim 1 , wherein the I/O device comprises a touch screen configured to display a soft keyboard.

4. The method of claim 1 , further comprising:

receiving, from the client system of the first user, information about the first keyboard layout.

5. The method of claim 1 , further comprising:

identifying, for each n th character position of the text query, a set of physical-proximity characters comprising a first character that occupies the n th character position of the text query and one or more characters adjacent to the first character on the first keyboard layout; and

generating a plurality of physical-proximity phrases based on the identified physical-proximity characters.

6. The method of claim 1 , wherein, for each of one or more pairs of a first character in the first layer and a second character in the second layer, the first character is located on the first keyboard layout at a position corresponding to that of the second character.

7. The method of claim 5 , wherein, for each of the generated physical-proximity phrases, at each n th character position of character positions 1 through N, the character occupying the n th character position of the physical-proximity phrase is a character selected from the set of physical-proximity characters corresponding to the n th character position.

8. The method of claim 1 , wherein the reference corpus comprises a lexical database.

9. The method of claim 1 , wherein the reference corpus comprises text extracted from a plurality of content objects associated with the online social network.

10. The method of claim 1 , wherein calculating the confidence score for each of the identified physical-proximity phrases is further based on a level of matching between the physical-proximity phrase and the reference corpus.

11. The method of claim 10 , wherein the level of matching between the physical-proximity phrase and the reference corpus is based on a number of times that physical-proximity phrase appears in the reference corpus.

12. The method of claim 10 , wherein the level of matching between the physical-proximity phrase and the reference corpus is based on a number of component n-grams of the physical-proximity phrase that appear in the reference corpus.

13. The method of claim 1 , further comprising:

deriving, based on the search history of the first user, one or more patterns describing a typing behavior of the first user; and

calculating the confidence score for each of the identified physical-proximity phrases further based on one or more of the derived patterns.

14. The method of claim 1 , wherein calculating the confidence score for each of the identified physical-proximity phrases comprises:

determining that a first physical-proximity phrase appears in a list of trending-topic keywords; and

increasing the confidence score for the first physical-proximity phrase based on the determination.

15. The method of claim 1 , wherein calculating the confidence score for each of the identified physical-proximity phrases is further based on an edit distance between the physical-proximity phrase and the text query.

16. The method of claim 1 , further comprising:

determining a number of search results to be displayed based at least in part on the calculated confidence scores of the identified physical proximity phrases.

17. The method of claim 1 , further comprising:

dividing the search results into a first group and one or more second groups associated with the completed text query and the one or more corrected text queries, respectively; and

displaying the search results of the first group and the one or more second groups in a first search-results module and one or more second search-results modules, respectively, wherein the positions of the first search-results module and the one or more second search-results modules are based at least in part on the calculated confidence scores of the identified physical proximity phrases.

18. The method of claim 1 , further comprising:

ranking each of the search results sent to the client system of the first user based at least in part on the calculated confidence scores of the identified physical-proximity phrases; and

displaying the search results based on the ranked search results.

19. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

receive, at a search engine system from a client system of a first user of an online social network, a completed text query submitted to the search engine system by the first user using an I/O device associated with the client system, the I/O device comprising a first keyboard layout having a plurality of layers, wherein each of the plurality of layers comprises a particular set of characters, wherein the completed text query comprises N characters having N character positions in a first layer of the plurality of layers of the first keyboard layout;

identify one or more physical-proximity phrases corresponding to the completed text query based at least in part on a second layer of the plurality of layers of the first keyboard layout, each identified physical-proximity phrase matching one or more n-grams included in a reference corpus, each matching n-gram comprising N characters having N character positions in the second layer of the first keyboard layout;

calculate a confidence score for each of the identified physical-proximity phrases based at least in part on a search history of the first user, wherein the confidence score for each physical-proximity phrase represents a likelihood that the first user intended to include the physical-proximity phrase in the completed text query;

determine one or more corrected text queries, each corrected text query comprising one or more physical-proximity phrases having a calculated confidence score greater than a threshold confidence score;

identify, from a plurality of objects associated with the online social network, responsive to the completed text query, automatically without requiring the first user to select a corrected text query, one or more first objects matching the completed text query and one or more second objects matching at least one of the corrected text queries; and

send, to the client system of the first user for display, a plurality of search results corresponding to one or more of the identified first objects and one or more of the identified second objects.

20. A search engine system comprising: one or more processors; and a non-transitory 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 first user of an online social network, a completed text query submitted to the search engine system by the first user using an I/O device associated with the client system, the I/O device comprising a first keyboard layout having a plurality of layers, wherein each of the plurality of layers comprises a particular set of characters, wherein the completed text query comprises N characters having N character positions in a first layer of the plurality of layers of the first keyboard layout;

identify one or more physical-proximity phrases corresponding to the completed text query based at least in part on a second layer of the plurality of layers of the first keyboard layout, each identified physical-proximity phrase matching one or more n-grams included in a reference corpus, each matching n-gram comprising N characters having N character positions in the second layer of the first keyboard layout;

calculate a confidence score for each of the identified physical-proximity phrases based at least in part on a search history of the first user, wherein the confidence score for each physical-proximity phrase represents a likelihood that the first user intended to include the physical-proximity phrase in the completed text query;

determine one or more corrected text queries, each corrected text query comprising one or more physical-proximity phrases having a calculated confidence score greater than a threshold confidence score;

identify, from a plurality of objects associated with the online social network, responsive to the completed text query, automatically without requiring the first user to select a corrected text query, one or more first objects matching the completed text query and one or more second objects matching at least one of the corrected text queries; and

send, to the client system of the first user for display, a plurality of search results corresponding to one or more of the identified first objects and one or more of the identified second objects.

21. The method of claim 1 , wherein each character having a character position in the first layer corresponds to a different character having the same character position in the second layer.