Real-life Applications of Tries
Well first, we need to look at what a Trie is.
Tries are one of many “data structures” in computer science. You may ask, “Well, what is a data structure?”. Data structures in computer science are ways of organizing and managing data. Real-life examples would be a dictionary. We store the words we have in alphabetical order, each entry complete with a word and definition. (We also have dictionaries in computer science but they’re known as a “key” and “value”.) There are many data structures that computer scientists and engineers use.
However, I will be talking about one specific data structure mentioned previously. Tries.
The word “trie” actually is derived from the word “reTRIEval”. Retrieval meaning “to get something back from somewhere”.
Tries are actually precisely that. They help you get words back after you’ve stored them in the trie. However, what makes tries special is its ability to find a value with just a prefix of the whole word.
It’s quite efficient and makes getting items faster. In fact, it’s much faster than hash tables and binary search trees which are other popular data structures used in computer science. To be exact, its time efficiency depends on the length of the word to be retrieved.
We can also print the words back in alphabetical order easily which isn’t as easy to do with some of the other data structures. Prefix search, also known as auto-complete is one of the most popular implementations of tries.
There are many upsides to tries, but there are a few downsides. Although they are fast and time-efficient, they aren’t the most efficient storage/memory-wise. This is due to the fact that each of these nodes actually has all 26 letters branching off. It’s not going to be illustrated in any of the pictures you see for simplicity’s sake, but that’s what’s going on behind the scenes.
The way that data is stored in tries is through nodes as demonstrated here:
Here, we have the list of words that are stored in this specific tree. (listed vertically on the right)
Each node (or the circular spots connected by a line with one another) has one letter. Then, connected by another node is the next letter in the node.
An interesting part of this is that you can reuse the same “trunk” part of the tree with different leaf/terminal nodes at the end.
In the example above, we can see that “true” and “truck” (top 2 words on the right) have 3 letters in common. You can follow “t”, then “r”, then “u”, after which “true” and “truck” split into two paths. Then, to make “true”, you follow the path to the “e”. And for “truck” it’s following the path to “c” and “k”.
What are the applications of tries that we can actually use?
Auto-correct has been one of the most popular uses for this data structure. Your device or the app you use (for example Google docs) uses tries for its predictive typing or auto-correct feature.
As you type and you have this feature turned on, your phone is constantly entering checking, and learning your typing habits. The more you type the word “chicken” for example, the sooner it’ll recognize you’re trying to write “chicken” with fewer letters.
Spell check is another common application of tries. Tries can be used to store words and then, search for specific words through the data structure.
Suggestions for the words you misspelled (the ones that are close) will come up for you to select when the spell-check feature is enabled. It will scan through the trie which has all the definitions contained in it and does so with efficiency.
There are many other applications for tries other than these. Used and implemented properly, tries can be and are one of the most powerful data structures. These make our lives easier and more fluid in ways that we usually overlook.
The next time you search something up on Google and it gives you the auto-complete suggestion you were looking for and saves you a few strokes of the keyboard, you’ll know what data structure to thank.