Before diving straight into the practical data structures for front-end applications, let’s first understand what is a front-end Application? And why is it important?
What is Front-end Application?
The front-end as the name suggests is the part of your application or website with which the user interacts directly is called frontend. Each and everything you visit on website or either any app on your smartphone e.g. WhatsApp, Instagram everything you do on these is frontend while other things like how these things are working behind for e.g. messaging/posting images/ chatting is all backend.
Let’s try to see with an image below:
What is Data Structures?
As the topic is about the importance or use of data structures for frontend application, so what is Data Structures?
According to Wikipedia, In computer science, a data structure is a data organisation, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.
But as a user, we don’t get to see the big part of the application/website i.e. backend because there’s no interaction with the backend for the user. So you don’t get to see what’s actually happening in the backend.
Let me show you below with the help of picture what I mean?
Well that’s not the case always. It’s just a meme because professional developers work effortlessly to make your app smooth or working in every possible condition but the picture gives us an idea that how backend looks and what a user gets to see when he visit some website or uses an app.
What is Trie Data Structures?
Now let’s come back to our topic of discussion, Practical Data Structures for frontend Applications: When to use Tries. But before talking about it first discuss what are tries?
In very simple words, Tries (also known as radix trees or prefix trees) are tree-based data structures that are typically used to store associative arrays where the keys are usually strings.
Tries are interesting for many reasons. One important thing that makes tries different from trees is that nodes in the tree do not store keys. Instead, they each store parts of keys. On traversing the trie down from the root node to a leaf allows you to build the key as you progress. Also, it’s not necessary that there should be a value at every node. Even values are typically only associated with leaf nodes.
For example, below in the image, there is a representation of a trie that contains the following associative array. Always keep in mind that an associative array is an abstract data type, so a trie is one way to implement that ADT(Abstract Data Type).
Now the important thing is why to use Tries? And why it’s important for our front-end application is because:
- Whenever we store the keys in BST (Binary search tree), a well-balanced BST will take time proportional to M * log N, where M is the length of the maximum string and N denotes the number of keys in the tree. Using Trie, searching for the key can be done in O(M) time.
- Insert and search operation costs O(key-length), however, the memory requirements of Trie is O(ALPHABET-SIZE * key-length * N) where N is a number of keys in Trie.
If you’re not confident about trie and want to read about the implementation then read here Using Trie in Data Structures.
Use of Tries in Frontend Applications –
Alright, this seems to be pretty useful now the question comes what and how can we use it to implement something in our application. Well we can use Tries to implement the following in our front-end application:-
- Spell Checkers
- Browser History
- Longest Prefix Matching
Let’s discuss one by one that how can we use tries for these then later we’ll compare if it’s helpful for us or not?
- Auto Complete:
As we know, Autocomplete, or word completion, is a feature in which an application predicts the rest of a word a user is typing. In Android smartphones, this is called predictive text. In GUI (graphical user interfaces) or any compiler, Whenever the user press the tab key then a suggestion or the down arrow key to accept one of several.
AutoComplete feature helps in improving or speeding the interactions between a user and the application, especially when it accurately predicts the word a user intends to use after the first few characters have been typed. AutoComplete feature is more accurate or we can say precisely when there is a limited number of possible words or when some words are more commonly used.
But as we know there’s always a scope of optimisation. So one of the most important fields of research in the present is to create or find optimum artificial intelligence algorithms that efficiently and is helpful in predicting the words based upon the user experience and usage.
Need of Trie for Auto-complete
- Trie helps in the alphabetical ordering of the data by keys.
- Trie data structure is the fastest for suggestions in auto-complete. Even if we talk about the worst case, Trie is O(n) times faster than it’s an alternate option which is an imperfect hash table algorithm where n is the length of the string. Also, a Trie data structure helps in overcoming the problem of key collisions in imperfect hash tables which cause a reduction in accuracy.
- Searching for suggestions using Trie helps us in getting the pointers to get to a node that represents the string user has entered. One more thing is when we traverse a tree data structure using the DFS (Depth-first search) algorithm, one can enlist all suggestable strings that complete the user input.
Various software applications of auto complete
1. Web Browser: In web browsers, Autocomplete is implemented in both the search box of the search engine which uses browser history for suggestions as well as the address bar where typing the full address of website takes time and it’s really hectic that you have to use but in this case here auto complete learns from the history of the user, it means it will only remember only if you have ever visited that website before.
2. Email: Email uses feature of autocomplete mainly for filling out email address of recipients based on mail history and even in the body of the mail.
Many email service providers like Gmail now also supports the auto complete on content strings using artificial intelligence algorithms now a days whenever you write an email then it gives you suggestion based on the content you’re writing.
3. Search Engines: Autocomplete helps user with suggestions based on most relevant details and also based on the user history, So user will not have to type same thing agai. They follow the auto suggest/incremental search algorithm.
There are also many advanced algorithms which are used including the language independent Levenshtein Algorithm.
5. Command-Line Interpreters: They use the list of commands the user can use to auto-fill the commands. You can easily do it by using the Tab key and it will show you suggestions there and even when you will press the upward key on the keyboard it will give you previous history like if you want to go that again.
Most popular CLI having autocompleted feature include bash for Linux and PowerShell for Windows and many more so it gives you flexibility and ease so that you won’t have to write the whole thing.
- Spell Checkers/ Auto- Correct
Well I know you must have felt like this when your phone does to you. But don’t worry it helps you mostly whenever you’re wrong grammatically but it’s not the case always because as a writer when I write trust me I do a lot of mistakes but there are Google Docs. Grammarly helps me in correcting my grammar either I’m writing a blog or sending a mail to someone.
Auto-correct is a three-step process
- It checks for the word you’re typing in the data dictionary
- Then it displays you the potential suggestions
- Suggestions shown to you are sorted on priority basis
Basically, we can say that the Trie data structure is really helpful in storing the data dictionary and algorithms for searching the words from the dictionary and provides you with the list of valid words for the suggestion.
3. Longest Prefix Matching
The longest Prefix Matching algorithm is also known as Maximum Prefix length match, is used by the routing devices in IP (Internet Protocol) networking. Like how it works in simple words is first it’ll select an entry from the routing table which is based on the history of previous packets transferred on the network.
Radix Trie Implementation in BSD Kernel is the earliest IP Lookup Technique for employing the Trie data structure.
For optimizing the network routes there is a need for contiguous masking which bounds the complexity of the worst case for lookup time to O(n), where n is the length of the URL address in bits. To minimising the time for the lookup process, Multiple Bit Trie Schemes were developed that performed the lookups of multiple bits faster.
4. Browser History
As we know that whenever we visit any website on any browser either Chrome, Firefox, Safari and Internet Explorer. All of them keep track of the history of websites visited by the user.
With the help of history and no. of visits to the specific websites as a key value, and organise it on Trie data structure, the user is given suggestions of the website when he types anything on the search-bar then all suggestions related to that keyword or matching with that string is shown to the user.
Now we have seen a couple of examples in which tries will help in implementing or making our frontend application faster. But another thing that comes to mind is whether we need to use tries or not? Let’s discuss each point one by one whether we need to use tries or not?
- Does using this trie structure give me performance gains? Are the performance gains worth it?
- Is this structure easier to use — or, at least, no more difficult?
- Does use this trie structure helps in providing my data with more semantics? Does it make my code easier to understand?
- How much of an impact will this structure have on my build size? Is this increase in build size worth it?
The criteria we’ll use to contrast Tries and Arrays is:
- Performance (run time and load time)
- Ease of use, and readability
- Build size (Arrays add no extra code. We’ll analyse the Trie)
Frequently Asked Questions
O(n), where n is the key length.
Requires more memory to store the strings and slower than hash table.
Trie is an excellent data structures and one thing we get to know from this article is that when you have an application that does a lot of searching. Tries are easy to use — and they’re fast. It’s really helpful in improvising the frontend application.
But also one thing is that it has its own advantages and it’s own disadvantages like, preferring a Trie over an Array has some performance costs, such as:
- Trie Initialisation: Because of this, it is recommended that you defer the initialisation of a Trie because there might be the case user don’t visit that section so don’t initialise until after the page has loaded).
- Larger bundle size.
If you’re confident about tries then why don’t you give a hand on solving one problem on CodeStudio and if you are stuck somewhere then don’t forget to watch the video from Maximum XOR Pair Using Trie – YouTube.
By Yogesh Kumar