ONLINE SPELLING CORRECTION/PHRASE COMPLETION SYSTEM

• US 20120246133A1
• Filed: 03/23/2011
• Published: 09/27/2012
• Est. Priority Date: 03/23/2011
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hsu, Bo-June, Wang, Kuansan, Duan, Huizhong
• Application Number:
  US13/069,526
• Publication Number:
  US 20120246133A1
• Time in Patent Office: Days
• US Class Current: 707/706
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

Online spelling correction/phrase completion is described herein. A computer-executable application receives a phrase prefix from a user, wherein the phrase prefix includes a first character sequence. A transformation probability is retrieved responsive to receipt of the phrase prefix, wherein the transformation probability indicates a probability that a second character sequence has been transformed into a first character sequence. A search is then executed over a trie to locate a most probable phrase completion based at least in part upon the transformation probability.

Claims

1. A computer-executable method that facilitates performing in-line spelling correction, the method comprising:

receiving a first character sequence from a user, wherein the first character sequence is a potentially misspelled portion of a phrase;

responsive to receiving the first character sequence, retrieving transformation probability data from a first data structure in a computer-readable data repository, wherein the transformation probability data is indicative of a probability that a second character sequence transformed into the first character sequence, wherein the second character sequence is a properly spelled portion of the phrase;

subsequent to retrieving the transformation probability data, searching over a second data structure in the computer-readable data repository for a completion of the phrase based at least in part upon the transformation probability data; and

providing at least one completion of the phrase to the user subsequent to receiving the first character sequence but prior to receiving additional characters from the user.

2. The method of claim 1, wherein the second data structure comprises an n-gram language model.

3. The method of claim 1, wherein the second data structure comprises a trie that maps phrases to probabilities.

4. The method of claim 3, wherein the trie comprises a plurality of nodes and a plurality of paths, wherein each node is representative of a character sequence and a path between two nodes extends the character sequence, and wherein each node in the trie has a largest probability among possible words or phrases that include a respective character sequence stored in relation thereto.

5. The method of claim 4, wherein the searching is undertaken across multiple paths in the trie to locate a threshold number of most probable words or phrases in combination with the transformation probability corresponding to the first character sequence.

6. The method of claim 5, further comprising utilizing beam pruning to limit a number of paths that is searched over during the act of searching.

7. The method of claim 1 configured for execution by a search engine, wherein the first character sequence is a portion of a query.

8. The method of claim 1 configured for execution by a word processing application.

9. The method of claim 1, wherein the completion of the phrase comprises multiple words that have yet to be provided by the user.

10. The method of claim 1, further comprising:

computing a risk that the completion of the phrase is not germane to informational retrieval intent of the user;

comparing the risk with a threshold value; and

providing the completion of the phrase to the user only if the risk is below the threshold value.

11. The method of claim 1, wherein a number of characters in at least one of the first character sequence or the second character sequence of a transformation unit is greater than one.

12. A system comprising a plurality of components that are executable by a processor, the components comprising:

a receiver component that receives a character sequence from a user, wherein the character sequence is intended by the user to be a portion of a particular word;

a search component that;

accesses a first data structure in a data repository, wherein the first data structure comprises a translation probability that indicates a probability that a second character sequence is a translation of the first character sequence;

searches over a plurality of possible word or phrase completions in a second data structure, wherein the possible word or phrase completions have a probability assigned thereto;

retrieves at least a most probable word or phrase completion from the plurality of possible word or phrase completions based at least in part upon the translation probability, wherein the most probable word or phrase completion comprises the particular word; and

outputs the most probable word or phrase completion to the user as a suggested word or phrase correction/completion.

13. The system of claim 12 being comprised by a search engine.

14. The system of claim 12 being comprised by an operating system.

15. The system of claim 12 being comprised by one of a word processing application or a web browser.

16. The system of claim 12, wherein the second data structure is a trie that comprises a plurality of nodes that are representative of character sequences and a plurality of paths between nodes that are representative of continuations of the character sequences, and wherein leaf nodes in the trie represent the possible word or phrase completions.

17. The system of claim 16, wherein each node in the trie has a probability assigned thereto, wherein a probability assigned to a node is a highest probability from amongst all leaf nodes that are coupled to the node.

18. The system of claim 12, wherein the search component utilizes an A* search algorithm to search over the plurality of possible word or phrase completions in the second data structure.

19. The system of claim 12, wherein the search component is configured to compute a risk value corresponding to the most probable word or phrase and only outputs the most probable word or phrase to the user if the risk value is below a threshold, wherein the risk value is indicative of a risk that the most probable word or phrase fails to correspond to intentions of the user.

20. A non-transitory computer-readable medium comprising instructions that, when executed by a processor, cause the processor to perform acts comprising:

receiving a partial query from a user, wherein the partial query comprises a first character sequence;

responsive to receiving the partial query, retrieving a transformation probability from a first data structure that indicates a probability that a second character sequence is a transformation of the first character sequence;

subsequent to retrieving the transformation probability, executing an A* search algorithm over a trie based at least in part upon the transformation probability, wherein the trie comprises a plurality of nodes and paths, wherein leaf nodes in the trie represent possible query completions and internal nodes represent character sequences that are portions of query completions, and wherein each internal node in the trie has a probability assigned thereto that is indicative of a most probable query completion given a character sequence that corresponds to a respective internal node; and

outputting a query correction/completion based at least in part upon the A* search.