Autocomplete Style Prefix Lookup

algorithm, prefix-tree, python, trie

Solution

Yes, we can use a trie. The most frequent names for a trie node are either (1) the name at that trie node or (2) a most frequent name for a child of the trie node. Here's some Python code to play with.

from collections import defaultdict


class trie:
    __slots__ = ('children', 'freq', 'name', 'top5')

    def __init__(self):
        self.children = defaultdict(trie)
        self.freq = 0
        self.name = None
        self.top5 = []

    def __getitem__(self, suffix):
        node = self
        for letter in suffix:
            node = node.children[letter]
        return node

    def computetop5(self):
        candidates = []
        for letter, child in self.children.items():
            child.computetop5()
            candidates.extend(child.top5)
        if self.name is not None:
            candidates.append((self.freq, self.name))
        candidates.sort(reverse=True)
        self.top5 = candidates[:5]

    def insert(self, freq, name):
        node = self[name]
        node.freq += freq
        node.name = name


root = trie()
with open('letter_s.txt') as f:
    for line in f:
        freq, name = line.split(None, 1)
        root.insert(int(freq.strip()), name.strip())
root.computetop5()
print(root['St'].top5)

Problem

Original source