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

摘要

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.

主权项

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; anda 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.