JS: Implementing Auto-complete
Have you always wondered, how auto completion works, well it is super complex in real life with machine learning and a whole bunch of stuff happening in the backend which I obviously cannot build all by myself! 😛
So, I decided to build a pretty similar working prototype which searches an English word dictionary of about 102k words (because that’s all I could find 😥) to produce auto-completion suggestions..
You might be seeing that, there is no correlation among the words obviously because there is no machine learning being used, but the main goal here to be able to complete the unfinished word (independently i.e irrespective of what was typed before).
Well, more than completion I was more curious about how the back-text (the transparent ghost text that completes your query) worked and how would I blend my word suggestion into the input box itself.
List of words from here. Repository consisting of the words here.
In order to get better suggestions, I have used a popularity measure based on the frequency of usage of English words found here. (repository here). The only problem is, it hosts only about 10k words, which is not very bad!
Prerequisites before proceeding ahead to the code section:
- Knowledge of JavaScript ES6 syntax (classes, async/await)
- Trie data structure
- Adding event listeners to DOM
- Knowledge about debounce. If not read here.
Now, we’re good to go ahead and code this out!
Step 1: Data structure
Which data structure do we choose and why? Considering our corpus of words can be really huge (only about 102k for now) a linear search for prefixes won’t be feasible and would disrupt the user experience of your application.
A well-known data structure used for searching and matching strings is a Trie Tree. An important thing to note here would be to monitor the space constraint because in the worst-case considering our words only have lowercase a to z character can consume about :
O(26 * average_length_of_words * number_of_words)
[depending on the implementation of your trie]
But, the upside is the time complexity can be fairly low — equal to the length of the query string itself.
O(length_of_query)
Let’s code this out:
We shall create Trie class consisting of methods to add new words and produce suggestions.
Let’s look at the method to add new words:
Let’s look at the structure more closely:
Consider the words ant & and added to the tree, this is how it’ll look :
Next, we need a method to find a word in the tree:
Next, we shall use the above find function in-order to produce suggestions:
We need to traverse the search space where our suggestions lie and recursively build the word. We can use a depth-first search to simply traverse over each node and keep concatenating the letters.
We can keep a control on the number of child nodes to traverse on the first node using the CHILDREN argument, to prevent from traversing a very large space as the search space could be very large for huge word corpuses.
That’s all about coding our data structure, let us now use it display suggestions!
Let us use this basic HTML to render the input box:
I haven’t included the styles here (you can see the fiddle here to view the entire source code).
NOTE:
The filenames in the above gists are not be taken literally, we only have 2 files — index.html and index.js all the JS code goes in this file itself.
Now, in our file index.js which also contains our Trie class, we shall add event listeners to handle input into our search bar.
Moving on, assuming you are aware of what debounce is (in short — our main() function is called when the user isn’t typing for 250ms).
Reason for adding a debounce to our main() method:
The main() method is responsible for pulling out the suggestions every time there is a change in the search bar text, but the user would only want the suggestion to appear when the user waits for the short (200–250ms) time while typing. This not only improves the user experience but also reduces unnecessary functions calls to the main() method.
Let’s look at the main() function:
Here, popularity is a measure of the frequency of the words in general for example the word the usually has more frequency than xylophone right?
So, the method getBestMatch() just loops through the suggestions and picks the word with the highest frequency.
Lets us understand the code with a diagram:
You can see here, ghost which is the suggestion is nothing but a span element placed at the distance equal to the content width of your query!
How do you get the width used by the content?
Have another div with is invisible somewhere in the DOM into which you can write the content of the query and measure the clientWidth !
HTML:
<div id='fake-div' class='div'></div>JS:
const $fakeDiv = document.getElementById('fake-div');const query = e.target.textContent.toLowerCase();
$fakeDiv.innerText = query;CONTENT WIDTH = $fakeDiv.clientWidth
Simple right! Now just place the ghost $span at the right position…
Since, the ghost $span needs to look similar to the text input in the $input div, we need to mimic few of the CSS properties of $input div and to get the CSS properties of the $input div we can do this :
Now, to set the style.left of the $span we just do :
LINE 33 : (main.js) GIST$span.style.left = r.left + $fakeDiv.clientWidth + 'px';
Just one thing left to do now! Fill in the input bar if the user wants to use the given suggestion, i.e if the user presses the RIGHT ARROW key.
Great! You made it to the end of this blog! Please note, I might have skipped on a few things such as fetching data from the URLs given and focused more on the topic concerned, you can find them in the link to the source code below.
You can play with the source code here.
And as always, let me know in the comments if you find anything incorrect or if there is anything you’d like to add! Cheers! 🍻
