Autocomplete
Answers before you finish typing.
Type two letters into a search box, and suggestions appear instantly. That has to take less than a tenth of a second, or it feels broken. A language model is far too slow for that. So what's behind it? A simple tree of letters.
- Two letters, instant suggestions
- Under a tenth of a second
- A tree of letters
A trie
A trie stores words as paths through letters. Words that begin the same way share the same path, which saves a lot of space. Each word stores a count of how often people search for it. To complete a prefix, we walk down the tree to it, then gather everything below it, and sort by popularity. Run it. For r e, we get refund, return, and review. Type one more letter, f, and the list narrows down immediately. The time that it takes depends only on the length of what you typed, not on the size of the catalogue.
class Trie:
def __init__(self):
self.kids, self.count = {}, 0
def add(self, word, n=1):
node = self
for ch in word:
node = node.kids.setdefault(ch, Trie())
node.count += n
def complete(self, prefix, k=3):
node = self
for ch in prefix:
if ch not in node.kids:
return []
node = node.kids[ch]
found = []
def walk(n, s):
if n.count:
found.append((n.count, s))
for c, kid in n.kids.items():
walk(kid, s + c)
walk(node, prefix)
return [w for _, w in sorted(found, reverse=True)[:k]]
t = Trie()
for word, n in [("refund", 90), ("refresh", 5), ("reference", 12), ("return", 70), ("review", 40)]:
t.add(word, n)
print(t.complete("re"))
print(t.complete("ref"))['refund', 'return', 'review'] ['refund', 'reference', 'refresh']
Summary
Tries give you instant suggestions. Next, a harder question. How do you score language itself?
Key takeaways- Shared prefixes share paths
- Sort by popularity
- Speed doesn't depend on catalogue size