trie
An implementation of the Trie data structure in Go. It provides more features than the usual Trie prefix-search, and is meant to be used for auto-completion.
Demo
A WebAssembly demo can be tried at shivamMg.github.io/trie.
Features
- Keys are
[]string
instead of string
, thereby supporting more use cases - e.g. []string{the quick brown fox} can be a key where each word will be a node in the Trie - Support for Put key and Delete key
- Support for Prefix search - e.g. searching for nation might return nation, national, nationalism, nationalist, etc.
- Support for Edit distance search (aka Levenshtein distance) - e.g. searching for wheat might return similar looking words like wheat, cheat, heat, what, etc.
- Order of search results is deterministic. It follows insertion order.
Examples
tri := trie.New()
tri.Put([]string{"the"}, 1)
tri.Put([]string{"the", "quick", "brown", "fox"}, 2)
tri.Put([]string{"the", "quick", "sports", "car"}, 3)
tri.Put([]string{"the", "green", "tree"}, 4)
tri.Put([]string{"an", "apple", "tree"}, 5)
tri.Put([]string{"an", "umbrella"}, 6)
tri.Root().Print()
results := tri.Search([]string{"the", "quick"})
for _, res := range results.Results {
fmt.Println(res.Key, res.Value)
}
key := []string{"the", "tree"}
results = tri.Search(key, trie.WithMaxEditDistance(2),
trie.WithEditOps())
for _, res := range results.Results {
fmt.Println(res.Key, res.EditDistance)
}
result := results.Results[2]
fmt.Printf("To convert %v to %v:\n", result.Key, key)
printEditOps(result.EditOps)
results = tri.Search(key, trie.WithMaxEditDistance(2), trie.WithTopKLeastEdited(), trie.WithMaxResults(2))
for _, res := range results.Results {
fmt.Println(res.Key, res.Value, res.EditDistance)
}
References