6 Trie, radix trie: Efficient string search
This chapter covers
- Understanding why working with strings is different
- Introducing trie1 for efficient string search and indexing
- Introducing radix tree2 as a memory-efficient evolution of trie
- Using prefix trees to solve string-related problems
- Leveraging tries to implement an efficient spell-checker
How many times have you sent a text or an email or tweeted in a hurry, only to realize a second later that you made a typo? For me, it was too many times! Lately, however, we’ve had a precious ally 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 ...
Get Advanced Algorithms and Data Structures now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
