Retrieval of prefix completions by way of walking nodes of a trie data structure

• US 9,158,758 B2
• Filed: 01/09/2012
• Issued: 10/13/2015
• Est. Priority Date: 01/09/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Hsu, Bo-June
• Primary Examiner(s): Waldron, Scott A
• Application Number:
  US13/345,750
• Publication Number:
  US 20130179419A1
• Time in Patent Office: 1,373 Days
• Field of Search: 707/797
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

Technologies pertaining to providing completions to proffered prefixes are disclosed herein. A suggested completion to a proffered prefix is retrieved by walking nodes of a trie data structure, wherein a node includes one or more characters that are used to extend a character sequence represented by its parent. Each node in the trie data structure is assigned a score, wherein the score maps to a best score assigned to its descendants. The nodes of the trie data structure are sorted based upon score, and the nodes are walked based upon scores assigned thereto.

Claims

1. A method executed by a computer processor, the method comprising:

receiving a prefix that comprises at least one character; and

using the prefix, executing a search over a computer-implemented trie data structure to retrieve a suggested completion for the prefix, the trie data structure comprising;

a root node;

a plurality of leaf nodes that are child nodes of the root node, the leaf nodes corresponding to a respective plurality of completions to potential prefixes, each leaf node in the plurality of leaf nodes having a respective score assigned thereto that is indicative of historic frequency of use of its corresponding completion; and

a plurality of intermediate nodes, wherein each intermediate node is a descendant node of the root node and an ancestor node to at least one leaf node, the intermediate nodes corresponding to a respective plurality of extensions to the potential prefixes, and wherein each intermediate node is assigned a respective score that maps to a highest score assigned to a respective leaf node from amongst all leaf nodes that are child nodes of the respective intermediate node, wherein the suggested completion for the prefix is retrieved by walking nodes of the trie data structure based upon the respective scores assigned thereto.

2. The method of claim 1, wherein the plurality of leaf nodes and the plurality of intermediate nodes are sorted in the trie data structure based upon the respective scores assigned thereto.

3. The method of claim 2, wherein the search is executed over the computer-implemented trie data structure to retrieve a plurality of suggested completions, the plurality of suggested completions retrieved by walking nodes of the trie data structure from an intermediate node corresponding to the prefix.

4. The method of claim 1, wherein executing the search over the trie data structure comprises:

identifying an intermediate node in the trie data structure that corresponds to the prefix, wherein the intermediate node has a plurality of immediate child nodes that have scores assigned thereto; and

adding less than all the immediate child nodes to a priority queue when retrieving the completion of the prefix.

5. The method of claim 4, wherein adding less than all the immediate child nodes to the priority queue when retrieving the completion of the prefix comprises:

adding a first node from the plurality of immediate child nodes of the intermediate node to a priority queue based upon a score assigned thereto;

retrieving the first node from the priority queue;

subsequent to retrieving the first node from the priority queue, adding a second node from the plurality of immediate child nodes of the intermediate node to the priority queue based upon a score assigned thereto; and

retrieving the prefix completion subsequent to retrieving the first node from the priority queue.

6. The method of claim 1, wherein at least one intermediate node in the trie data structure comprises a multiple character extension to the prefix.

7. The method of claim 1, wherein scores assigned to the leaf nodes are encodings of original scores corresponding to completions, wherein the original scores are encoded by way of differential encoding.

8. The method of claim 7, wherein the scores are encoded by way of variable byte encoding, such that different numbers of bytes are employed to represent different scores for different nodes in the trie data structure.

9. The method of claim 1, wherein nodes in the trie data structure are stored in memory such that sibling nodes are stored consecutively in memory and in depth-first order.

10. The method of claim 9, wherein each intermediate node comprises a pointer to its child node with a lowest score assigned thereto from amongst all scores assigned to its children.

11. The method of claim 10, wherein a pointer in an intermediate node is encoded by way of differential encoding.

12. The method of claim 11, wherein the completion is reconstructed from a plurality of extensions to the prefix by way of traversing pointers in nodes of the trie data structure.

13. The method of claim 1, wherein a leaf node comprises a pointer to another leaf node in the trie data structure.

14. A system, comprising:

at least one processor; and

memory that comprises a plurality of components that are executed by the at least one processor, the plurality of components comprises;

a receiver component that receives a prefix set forth by a user; and

a returner component that returns a suggested completion for the prefix responsive to receiving the prefix, the returner component selecting the suggested completion from amongst a plurality of potential completions by walking nodes of a trie data structure based upon scores respectively assigned to the nodes that are indicative of probabilities that the completions will be selected, the trie data structure comprising;

a plurality of leaf nodes, wherein each of the leaf nodes is representative of a respective potential completion, and wherein each of the leaf nodes is assigned a score that is indicative of a respective probability that the completion will be selected; and

at least one intermediate node that is a parent to the plurality of leaf nodes, the at least one intermediate node representative of a potential extension to the prefix and being assigned a score that equals a score assigned to a leaf node in the plurality of leaf nodes, the leaf node in the plurality of leaf nodes being representative of a most probable potential completion from amongst potential completions represented by the plurality of leaf nodes.

15. The system of claim 14, wherein the prefix is a query prefix set forth to a search engine by the user and the suggested completion is a query completion.

16. The system of claim 14, wherein the prefix is proffered to a URL field of a browser, and wherein the suggested completion is a URL to a web page.

17. The system of claim 14, wherein the plurality of leaf nodes are ordered beneath the intermediate node based upon scores assigned to the plurality of leaf nodes.

18. The system of claim 14, wherein at least one leaf node in the plurality of leaf nodes comprises a pointer to another leaf node, the another leaf node being representative of an alteration to a completion represented by the at least one leaf node.

19. The system of claim 14, wherein the trie data structure comprises a plurality of intermediate nodes, each of the intermediate nodes having a plurality of child nodes, and wherein sibling nodes in the trie data structure are stored in memory adjacent to one another, and wherein nodes in the trie structure are stored in the memory in depth-first order.

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

receiving a prefix set forth by a user, the prefix comprising a plurality of alphanumerical characters;

executing a search over a trie data structure responsive to receiving the prefix, wherein the trie data structure comprises;

an intermediate node, the intermediate node comprising at least one character that is a potential extension to the prefix and a pointer, the intermediate node having a first score assigned thereto; and

a plurality of leaf nodes that are children of the intermediate node, the leaf nodes representing potential completions of the prefix, each of the leaf nodes assigned a respective score that is indicative of probability of a respective potential completion, wherein a first leaf node in the plurality of leaf nodes that is representative of a most probable potential completion is assigned the first score, wherein the pointer in the intermediate node points to the first leaf node, and wherein the plurality of leaf nodes are ordered in memory of a computing device based upon the scores assigned thereto; and

returning the most desirable probable completion as a suggested completion to the prefix.