prefixtree
The prefixtree package implements a simple prefix trie data structure. The tree enables rapid searching for strings that uniquely match a given prefix. The implementation allows the user to associate data with each string, so it can act as a sort of flexible key-value store where searches succeed with the shortest unambiguous key prefix.
See http://godoc.org/github.com/beevik/prefixtree for godoc-formatted API documentation.
Example: Building a prefix tree
The following code adds strings and associated data (an integer) to a prefix tree.
tree := prefixtree.New()
tree.Add("apple", 10)
tree.Add("orange", 20)
tree.Add("apple pie", 30)
tree.Add("lemon", 40)
tree.Add("lemon meringue pie", 50)Example: Searching the prefix tree
The following code searches the prefix tree generated by the previous example and outputs the results.
fmt.Printf("%-18s %-8s %s\n", "prefix", "data", "error")
fmt.Printf("%-18s %-8s %s\n", "------", "----", "-----")
for _, prefix := range []string{
"a",
"appl",
"apple",
"apple p",
"apple pie",
"apple pies",
"o",
"oran",
"orange",
"oranges",
"l",
"lemo",
"lemon",
"lemon m",
"lemon meringue",
"pear",
} {
data, err := tree.Find(prefix)
fmt.Printf("%-18s %-8v %v\n", s, data, err)
}Output:
prefix data error
------ ---- -----
a <nil> prefixtree: prefix ambiguous
appl <nil> prefixtree: prefix ambiguous
apple 10 <nil>
apple p 30 <nil>
apple pie 30 <nil>
apple pies <nil> prefixtree: prefix not found
o 20 <nil>
orang 20 <nil>
orange 20 <nil>
oranges <nil> prefixtree: prefix not found
l <nil> prefixtree: prefix ambiguous
lemo <nil> prefixtree: prefix ambiguous
lemon 40 <nil>
lemon m 50 <nil>
lemon meringue 50 <nil>
pear <nil> prefixtree: prefix not found