How to effortlessly implement an autocomplete data structure in JavaScript (Using a Trie).
Have you ever wondered how Google knows the next word or sentence you will type in the search bar? Oh yes! they have good algorithms and have collected enough data and everybody knows that. But at the core of such user-friendly features in most of the search bars lies a very powerful yet data structure called a Trie. A Trie (Keyword Tree) is a tree data structure that stores strings and can be used in machine learning, web crawling, and most commonly, the autocomplete feature which we shall implement right away.
How to implement a Trie for autocomplete
Before we get into the implementation, I assume you are familiar with;-
- JavaScript Objects and how to manipulate them
- JavaScript Data Structures and basic methods
- Basic knowledge and terminologies of a tree data structure
Once you are sure of those three, we can delve into this without much strain (I’ve also tried making the code blocks ‘dirty’ with comments for easy interpretation).
There are two important things we are going to consider in this whole implementation;
- the node
- Trie Structure
- The node
Since a Trie is a tree data structure, it obviously must have a node. Each node represents a letter of any word that will be stored in the Trie. As of our implementation, the node will track the current letter, previous letter, next letters, position (whether it is the last node or not), and a function that joins all the previous letters before that node (to form a word if possible).
from the illustration above, it will have no previous letters on creating a new node since it is a root node (first node in the tree), and no preceding letters until we add words. We then create the getword()
method inside the TrieNode
object
finally, our complete node will look like the one in the illustration below
The Trie Implementation
After we have created the node structure of our tree, we can now implement the Trie. To achieve our basic autocomplete task, we shall have one property and three methods;-
root
this property will create the first node of the treeinsert
; this method will create or insert a new word in our Trie ‘dictionary’.contains
; this method will check if a word exists in our ‘dictionary’.find
; this method will use prefixes to predict words that can be formed with the given prefix. (the words must be available in the dictionary of course.)
We start with the insert
method since we cannot make use of the Trie when it lacks a ‘dictionary’
from the above illustration, iterating through each letter gives us the ability to create a node for each letter. Also, since our nextLetters
property is an object, there are various ways we can access the values of the keys (in this case the letters) and I opted for nextLetters[current_letter]
. To explain how we are accessing the next letters a little further, here is a snippet.
If the word I am going to insert is cat
, we iterate through each letter singly as 'c'
, 'a'
, and 't'
. The object for these letters will look like this;
nextLetters = {
c: 'c',
a: 'a',
t: 't'
}
to access the letter 'a'
and make any comparisons or effects to it, we can say;
nextLetters.a // return 'a'
OR
nextLetters[a] // returns 'a' if we use a loop
So basically that is how we are trying to access and manipulate letters in the above methods and the next two methods.
Next, we implement the contains
method that checks whether a word exists
If a word exists, it will return true, otherwise false. We can use this method to confirm if our words were inserted into the ‘dictionary’.
And lastly find
, the method that makes the whole basic importance of this Trie Data structure. The find
method has two parts. First, we check our prefixes and move the node to the last letter of the prefix. If the prefix is exerc
, we must make sure our current node is c
because it will be used as a reference. This is how we do it.
The findAllWords()
the function will be a recursive function that will use the current node of the prefix
as a reference point to traverse all the children
of that node and then return an array with all the possible words.
Basically, the function takes in two arguments, the node
and and array
. First, it checks whether the node represents the last letter of a word. If it is, it will be used by the getword()
function the get the corresponding word which will be pushed to the array list of possible words. If it's not, we use a for...in
loop to traverse through the node's children so that we access the next node and build the word recursively.
Once all child nodes are visited, the find
method will return an array of possible words. And then our Trie will be done. To make some tests, we can implement a trie and do some sampling.
So that’s it. you can find the complete code here. If this was helpful don’t forget the claps.