tag: trie

After writing a trie I wanted to better understand its performance, so I wrote some benchmarks against various other Go implementations for storing UK postcodes. At some point since the new year I entirely replaced the implementation from my last post with one that more closely matches the “pure” trie described at the start of TAOCP 6.3; i.e. a table of nodes, consisting of a list of entries, where each node entry can be either a link to another node, or a key (that is, an entire string stored in the trie)....

A trie (pronounced either “tree” or “try”) is a data structure typically used to store a set of strings in a way that allows looking up by prefix efficiently - i.e. unlike a hashmap where the keys are randomly ordered - this makes it a reasonable choice for an autocompletion system. A possible advantage over binary trees is that the keys are not stored in full in each node - so if you have a large number of strings which often have overlapping prefixes (e.g. “cat”, “cats”, “catastrophe”) then you may be able to save memory. ...