README
¶
Trie
Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.
Usage
Create a Trie with:
t := trie.New()
Add Keys with:
// Add can take in meta information which can be stored with the key.
// i.e. you could store any information you would like to associate with
// this particular key.
t.Add("foobar", 1)
Find a key with:
node, ok := t.Find("foobar")
meta := node.Meta()
// use meta with meta.(type)
Remove Keys with:
t.Remove("foobar")
Prefix search with:
t.PrefixSearch("foo")
Fast test for valid prefix:
t.HasKeysWithPrefix("foo")
Fuzzy search with:
t.FuzzySearch("fb")
Contributing
Fork this repo and run tests with:
go test
Create a feature branch, write your tests and code and submit a pull request.
License
MIT
Documentation
¶
Overview ¶
Implementation of an R-Way Trie data structure.
A Trie has a root Node which is the base of the tree. Each subsequent Node has a letter and children, which are nodes that have letter values associated with them.
Index ¶
- type ByKeys
- type Node
- func (n Node) Children() map[rune]*Node
- func (n Node) Depth() int
- func (n Node) Mask() uint64
- func (n Node) Meta() interface{}
- func (parent *Node) NewChild(val rune, path string, bitmask uint64, meta interface{}, term bool) *Node
- func (n Node) Parent() *Node
- func (n *Node) RemoveChild(r rune)
- func (n Node) Terminating() bool
- func (n Node) Val() rune
- type Trie
- func (t *Trie) Add(key string, meta interface{}) *Node
- func (t *Trie) Find(key string) (*Node, bool)
- func (t Trie) FuzzySearch(pre string) []string
- func (t *Trie) HasKeysWithPrefix(key string) bool
- func (t *Trie) Keys() []string
- func (t Trie) PrefixSearch(pre string) []string
- func (t *Trie) Remove(key string)
- func (t *Trie) Root() *Node
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
func (*Node) NewChild ¶
func (parent *Node) NewChild(val rune, path string, bitmask uint64, meta interface{}, term bool) *Node
Creates and returns a pointer to a new child for the node.
func (*Node) RemoveChild ¶
func (Node) Terminating ¶
type Trie ¶
type Trie struct {
// contains filtered or unexported fields
}
func (*Trie) Add ¶
Adds the key to the Trie, including meta data. Meta data is stored as `interface{}` and must be type cast by the caller.
func (Trie) FuzzySearch ¶
Performs a fuzzy search against the keys in the trie.
func (*Trie) HasKeysWithPrefix ¶
func (Trie) PrefixSearch ¶
Performs a prefix search against the keys in the trie.
Source Files