If you are a programmer, you should already know the basic
data structures taught to us in class such as arrays, linked lists, trees,
sets, stacks, and queues and if you’re quite experienced, then you probably
also know when and why to use the different data structures. One data structure
that is often neglected by most is the trie. Some people may ask, “What is a trie?”
or say something along the lines of “Trie? Are you just making stuff up right
now?” The reality is that most people have probably seen a trie before. Another
name for a trie is prefix tree. If that doesn’t help you with thinking of
something that relates to this data structure, you’ve seen tries in word games!
The trie is a specialized data structure that requires much
more memory compared to trees and list. It can be very effective in addressing
performance optimization even though there is a limited alphabet and high redundancy.
The reason why the data structure was named trie is because comes from
retrieval. When using the trie, it is safe to assume all words are lowercase,
that there are only letters from a-z, there may be inflected forms of words such
as plurals, conjugated verbs, and composite words.
The next time you might be thinking of creating a game
involving words, you should definitely think of using a trie. I think it is a
very useful data structure in the long run if you want efficiency with the
limited type of words because it’ll help with figuring out the combinations
needed. For anyone who wants more information or an example of an
implementation I would suggest chapter 5 of Robert Sedgewick’s book
“Algorithms, 4th edition” and taking a look at Princeton’s companion website.
Hey Justin,
ReplyDeleteGreat post! I had no idea what the heck a tier was before reading your blog post. Great informative post about a often overlooked data structure in programming. It was interesting reading about the different uses of this type of data structure and how it can be applied in the real world. I like how you gave everyone a link to check out some sample code using the tier data structure.
Keep up the good work!
Jeffrey Su
Hi Justin,
ReplyDeleteBe honest, I don't know anything about Trier before reading this article. Now, it becomes one part of my knowledge of data structures. Thanks for giving me the chance to learn new data structure. You tell readers Trier step by step. This way can attract people to read it ahead.
No thing is perfect. The Trier is one. It is very effective in some ways, at the same time, it needs more memory. I think it will be further improved in future. Or, with the development of technology, the memory will not be engineers/scientists' worry. Then Trier will be applied more widely.
Hello, Justin Tieu. This is my second comment if I recall correctly, and I was very pleased to read your post again on data structure. I indeed didn't know what trie data structure was and you just taught me what it is. I searched about it and it is also called a radix tree. The references you provided are very helpful for being informative. Also, I hear your voice in your blog posts. Keep up with your great work!
ReplyDeleteHey Justin, I did not know that a tier data structure existed before reading this. I can see why this structure is often overlooked by programmers. It really does seems to take up a lot of memory if implemented incorrectly. It is something I think I will look into on my own time to try to understand it better. At the time of writing it seems that the picture you choose to accompany this post is broken. You might want to look into that.
ReplyDelete