Tagged: autocomplete

Building a prefix trie

Prefix trie‘s are cool data structures that let you compress a dictionary of words based on their shared prefix. If you think about it, this makes a lot of sense. Why store abs, abbr, and abysmal when you only need to store a,b,b,r,s,y,s,m,a,l. Only storing what you have to (based on prefix) in this example gives you a 70% compression ratio! Not too bad, and it would only get better the more words you added.

The classical way of dealing with prefix tries is to store the suffixes using a map, but for fun I tried something different and used a list.

Data

The main data structure I had was like this

type Key a = [a]

data Trie key = Node (Maybe key) [Trie key] Bool deriving (Show, Eq, Read)

So a trie is really just a node that has a list of other tries … Read more