Finishing your thoughts since... you started typing
- 6 minutes read - 1101 wordsTypeahead System
A little background
An autocomplete system, also called typeahead, is a feature often experienced by users while typing in a search bar (or your IDE for that matter). The software suggests the rest of a word or word sequence based on what the user has already typed.
These suggestions can be ranked depending on how often/popular a search is. Remember that gorgeous Versace dress J-Lo wore for the Grammy Awards back in 2000? Everyone googled it - in fact it became the most popular search query at the time and - fun fact - prompted Google engineers to develop the image search! The objective is to make user searches more efficient and reduce the amount of typing required, while keeping the suggestions relevant with current search trends.
Underlying data structure
The prefix tree is particularly adapted for this use case.
A prefix tree has a root node which has up to n children - n size of your charset. If considering purely
the latin alphabet, the root node would have at most 26 children.
Inserting a word consists in creating a node for each character, the next character being a child node of the previous one.
One could think of the word dad represented as the node sequence d–>a–>d, where the last node also indicates
this is the end of a word.
This way, multiple words share the same prefix-path on the tree - which is
exactly what is leveraged when designing a typeahead system.
The below example shows the words ant and and share a common prefix an.
| Insert word | Search word | Search prefix |
|---|---|---|
| O(w) | O(w) | O(w) |
where w is the length of the word.
Below is the implementation of get and insert method.
class Trie_Node:
def __init__(self):
self.children = {}
self.isWord = False
class Trie:
def __init__(self):
self.root = Trie_Node()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children.keys():
node.children[c] = Trie_Node()
node = node.children[c]
node.isWord = True
def get(self, word):
node = self.root
for c in word:
if c not in node.children.keys():
return ['word does not exist']
node = node.children[c]
return node.isWord
And maps?
Yes, maps can be used: for each new word, all the possible prefixes are also inserted in the map. The lookup of a prefix is then reduced to a simple key lookup. The value stored against each key is the list of words sharing this prefix. This method is known as inverted indexing. This solution takes up more space than a prefix tree as duplicate data is stored under different keys. It is also higher maintenance - upcoming post on inverted indexes.
{
"d": ["dog", "donut"],
"do": ["dog", "donut"],
"dog": ["dog"],
"don": ["donut"],
"donu": ["donut"],
"donut": ["donut"],
}
Implementation for typeahead feature
As discussed above, a prefix tree is used for this implementation with its classic insert and
get methods. The number of suggestions returned is configurable using the parameter length
of the Trie class.
In order to keep the suggestions relevant with current search trends, we also maintain a queue of access times for each node.
It is used to
discard older searches based on their configured time to live: that way old searches have no weight in the ranking
of the most popular results.
This access times queue is updated upon both word search and prefix search by the method _remove_old_entries.
Note there are other ways one could consider handling old searches becoming irrelevant with today’s trends; the use of a frequency counter paired with a dampening coefficient could be explored. I did not move forward with this idea as I preferred a clear configuration to cut old searches using the ttl.
From there, the get_suggestions method simply navigates to the node representing the last character of the given prefix.
This node is the root node of the sub-tree we need to explore in order to return all the possible known words.
The list is then sorted and the top k results are returned.
from collections import deque
import time
class Trie_Node:
def __init__(self):
self.children = {}
self.isWord = False
self.accessTimes = deque()
class Trie:
def __init__(self, ttl=300, length=2):
self.root = Trie_Node()
self.ttl = ttl
self.length = length
def insert(self, word):
node = self.root
for c in word:
if c not in node.children.keys():
node.children[c] = Trie_Node()
node = node.children[c]
node.isWord = True
def get(self, word):
node = self.root
for c in word:
if c not in node.children.keys():
return ['word does not exist']
node = node.children[c]
if node.isWord:
curr_time = time.time()
node.accessTimes.append(curr_time)
self._remove_old_entries(node, curr_time, self.ttl)
return node.isWord
def get_suggestions(self, prefix):
node = self.root
for c in prefix:
if c not in node.children.keys():
return ['prefix does not exist']
node = node.children[c]
if not node.children:
return ['prefix has no children']
suggestions = []
self._traverse(node, prefix, suggestions)
suggestions.sort(key=lambda x: x[0], reverse=True)
return [word for freq, word in suggestions[:self.length]]
def _remove_old_entries(self, node, curr_time, time_window):
while node.accessTimes and node.accessTimes[0] < curr_time - time_window:
node.accessTimes.popleft()
def _traverse(self, node, word, suggestions):
if node.isWord:
self._remove_old_entries(node, time.time(), self.ttl)
suggestions.append((len(node.accessTimes), word))
for k, v in node.children.items():
self._traverse(v, word + k, suggestions)
return suggestions
Demo
This demo shows how popular searched words influence the content and order of the returned suggestions.
The default ttl and result length are used: respectively being 5 min and 2.
if __name__ == '__main__':
prefix = Trie()
words = ["cross-country", "crossfit", "cross", "crossroad", "crosswalk", "champagne", "charm", "champion"]
print("Inserting words into trie: " + str(words))
for word in words:
prefix.insert(word)
print("Making crossfit the most popular word, followed by crosswalk - expected returned value [crossfit, crosswalk]")
for i in range(0, 5):
prefix.get('crossfit') # Simulating searches
if i < 3:
prefix.get('crosswalk') # Simulating searches
popular_words = prefix.get_suggestions("cross")
assert "crossfit" in popular_words and "crosswalk" in popular_words, "Hm, this didn't work.."
print("Assertion passed!")
print("Making crossroad the popular word - expected returned value [crossfit, crossroad]")
for i in range(0, 6):
prefix.get('crossroad') # Simulating searches
popular_words = prefix.get_suggestions("cross")
assert "crossfit" in popular_words and "crossroad" in popular_words, "Hm, this didn't work.."
print("Assertion passed!")
print('Initial returned suggestions for champ prefix ' + str(prefix.get_suggestions("cha")))
print('Making charm the most popular word - expected returned value [charm, champagne]')
for i in range(0, 3):
prefix.get('charm') # Simulating searches
popular_words = prefix.get_suggestions("cha")
assert "charm" in popular_words and "champagne" in popular_words, "Hm, this didn't work.."
print("Assertion passed!")
Inserting words into trie: ['cross-country', 'crossfit', 'cross', 'crossroad', 'crosswalk', 'champagne', 'charm', 'champion']
Making crossfit the most popular word, followed by crosswalk - expected returned value [crossfit, crosswalk]
Assertion passed!
Making crossroad the popular word - expected returned value [crossroad, crossfit]
Assertion passed!
Initial returned suggestions for champ prefix ['champagne', 'champion']
Making charm the most popular word - expected returned value [charm, champagne]
Assertion passed!