tchap/go-patricia
GitHub: tchap/go-patricia
一个用 Go 实现的泛型 Patricia Trie（基数树）库，提供高效的前缀匹配和有序键值存储能力。
Stars: 293 | Forks: 60
# go-patricia
[](https://pkg.go.dev/github.com/tchap/go-patricia/v2/patricia)[](https://coveralls.io/r/tchap/go-patricia)
## 关于
一个使用 Go (Golang) 实现的泛型 patricia trie（也称为基数树）。
本库中实现的 patricia trie 支持以以下特定方式快速访问项目：
1. 访问树中保存的所有项目，
2. 访问所有匹配特定前缀的项目（访问子树），或
3. 给定一个字符串，访问所有匹配该字符串某些前缀的项目。
键使用 `[]byte` 类型，值使用 `interface{}`。
`Trie` 不是线程安全的。请自行同步访问。
### 项目状态
显然有一些人正在使用它，因此 API 不会经常更改。
依然欢迎任何关于如何改进本库的想法。
更多的（单元）测试也会很棒...
## 用法
首先从 GitHub 导入该包。
```
import "github.com/tchap/go-patricia/v2/patricia"
```
然后你就可以开始尽情使用了。
```
printItem := func(prefix patricia.Prefix, item patricia.Item) error {
fmt.Printf("%q: %v\n", prefix, item)
return nil
}
// Create a new default trie (using the default parameter values).
trie := NewTrie()
// Create a new custom trie.
trie := NewTrie(MaxPrefixPerNode(16), MaxChildrenPerSparseNode(10))
// Insert some items.
trie.Insert(Prefix("Pepa Novak"), 1)
trie.Insert(Prefix("Pepa Sindelar"), 2)
trie.Insert(Prefix("Karel Macha"), 3)
trie.Insert(Prefix("Karel Hynek Macha"), 4)
// Just check if some things are present in the tree.
key := Prefix("Pepa Novak")
fmt.Printf("%q present? %v\n", key, trie.Match(key))
// "Pepa Novak" present? true
key = Prefix("Karel")
fmt.Printf("Anybody called %q here? %v\n", key, trie.MatchSubtree(key))
// Anybody called "Karel" here? true
// Walk the tree in alphabetical order.
trie.Visit(printItem)
// "Karel Hynek Macha": 4
// "Karel Macha": 3
// "Pepa Novak": 1
// "Pepa Sindelar": 2
// Walk a subtree.
trie.VisitSubtree(Prefix("Pepa"), printItem)
// "Pepa Novak": 1
// "Pepa Sindelar": 2
// Modify an item, then fetch it from the tree.
trie.Set(Prefix("Karel Hynek Macha"), 10)
key = Prefix("Karel Hynek Macha")
fmt.Printf("%q: %v\n", key, trie.Get(key))
// "Karel Hynek Macha": 10
// Walk prefixes.
prefix := Prefix("Karel Hynek Macha je kouzelnik")
trie.VisitPrefixes(prefix, printItem)
// "Karel Hynek Macha": 10
// Delete some items.
trie.Delete(Prefix("Pepa Novak"))
trie.Delete(Prefix("Karel Macha"))
// Walk again.
trie.Visit(printItem)
// "Karel Hynek Macha": 10
// "Pepa Sindelar": 2
// Delete a subtree.
trie.DeleteSubtree(Prefix("Pepa"))
// Print what is left.
trie.Visit(printItem)
// "Karel Hynek Macha": 10
```
## 许可证
MIT，请查看 `LICENSE` 文件。
[](https://www.gittip.com/tchap/
"Gittip 徽章")
标签：EVTX分析, Go, Ruby工具, 基数树, 基础库, 字典树, 数据结构, 日志审计