Trie
Recently I’ve been working on a Trie implementation and I was a surprised and delighted from the simplicity of the data structure.
The first time I came across the Trie data structure, I was looking to solve a problem where a typeahead field had a really large dictionary to query and would choke every time the search was triggered. After stumbling upon John Resig’s JavaScript implementation I wanted to see how it would translate in Go.
So without further ado, I’d like to share with what I found interresting about the Go version.
The data type
type Node map[rune]Node
Using self-referential type definition we are able to describe our tree nodes with nothing more than just built-in types.
Building an index
Some parts are omitted from the following example but this is where the magic happens.
func (node Node) Insert(s string) {
for _, r := range s {
if node[r] == nil {
node[r] = New()
}
node = node[r]
}
node.End()
}
Notice how we walk down the tree for every rune in the string with node = node[r]
.
You’ve probably noticed the node.End()
near the end. This inserts an invalid UTF8 character at the current node marking the end of a word.
Search
Searching is as simple as walking down the tree matching each letter in the search term to a key in each node. When we reach the end of the search term we have found a match, so the string indexed by the current node plus the strings from all its child nodes should be returned as results to the query.
func (node Node) Search(s string) (res []string) {
for i, r := range s {
if _, ok := node[r]; ok {
node = node[r]
}
if i == len(s)-utf8.RuneLen(r) {
return append(res, node.All(s)...)
}
}
return res
}
The code is available on GitHub and the API docs at the usual place. I would love to hear your feedback. Enjoy!
Originally published at https://alexkappa.com on January 3, 2015.