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.
This is version 2 of the package, which you can retrieve using go get
:
go get github.com/beevik/prefixtree/v2
The following code adds strings and associated data (in this case an integer) to a prefix tree.
tree := prefixtree.New[int]()
tree.Add("apple", 10)
tree.Add("orange", 20)
tree.Add("apple pie", 30)
tree.Add("lemon", 40)
tree.Add("lemon meringue pie", 50)
The following code searches the prefix tree generated by the previous example and outputs the results.
fmt.Printf("%-18s %-8s %s\n", "prefix", "value", "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",
} {
value, err := tree.FindValue(prefix)
fmt.Printf("%-18s %-8v %v\n", prefix, value, err)
}
Output:
prefix value error
------ ----- -----
a 0 prefixtree: prefix ambiguous
appl 0 prefixtree: prefix ambiguous
apple 10 <nil>
apple p 30 <nil>
apple pie 30 <nil>
apple pies 0 prefixtree: prefix not found
o 20 <nil>
oran 20 <nil>
orange 20 <nil>
oranges 0 prefixtree: prefix not found
l 0 prefixtree: prefix ambiguous
lemo 0 prefixtree: prefix ambiguous
lemon 40 <nil>
lemon m 50 <nil>
lemon meringue 50 <nil>
pear 0 prefixtree: prefix not found