6 Trie, Radix Trie: Efficient Strings Search
This chapter covers
How many times have you sent a text, an email or twitted in a hurry, just to realize, a second later, that you had a typo? For me, it was too many times! Lately, however, we started to have a precious ally by default on our side in email clients, and browsers in general: spell-checkers! If you’d like to know more about how they work and how to implement them efficiently, this chapter is the right place to start.
In chapter 3 we have described balanced trees, which offer the best compromise when it comes to containers, and are ideal to efficiently store dynamically-changing data on which we need to perform frequent searches: in appendix C we have discussed and compared the options we have for containers providing fast lookup, fast insertion or fast removal, and trees offer the best tradeoff between all the operations.
Balanced trees, in particular, guarantee logarithmic running time in the worst-case for all the main operations.
In the general case, when we don’t know anything about the data we need to store and (later) search, this is really the best we can hope.