trie下载 - trie源码下载

trie

其他源码

v0.0.1

下载

特里树

Go 中 Trie 数据结构的实现。它提供了比通常的 Trie 前缀搜索更多的功能，并且旨在用于自动完成。

演示

可以在 shivamMg.github.io/trie 尝试 WebAssembly 演示。

特征

键是[]string而不是string ，从而支持更多用例 - 例如 []string{the Quick Brown Fox} 可以是键，其中每个单词都是 Trie 中的一个节点
支持Put键和Delete键
支持前缀搜索 - 例如搜索nation可能会返回nation 、 nation 、 nationism 、 nationist等。
支持编辑距离搜索（又名 Levenshtein 距离） - 例如搜索小麦可能会返回相似的单词，如小麦、作弊、热、什么等。
搜索结果的顺序是确定的。它遵循插入顺序。

示例

tri := trie.New()// 放置键（[]string）和值（任意）tri.Put([]string{"the"}, 1)tri.Put([]string{"the", " Quick", "brown", "fox"}, 2)tri.Put([]string{"the", "quick", "sports", "car"}, 3)tri.Put([]string{"这”， "green", "tree"}, 4)tri.Put([]string{"an", "apple", "tree"}, 5)tri.Put([]string{"an", "umbrella"} , 6)tri.Root().Print()// 输出（以 ($) 结尾的完整 trie）:// ^// ├─ ($)// │ ├─ fast// │ │ ├─ 棕色// │ │ │ └─ 狐狸($)// │ │ └─ 运动// │ │ └─ 汽车($)// │ └─ 绿色// │ └─ 树($)// └─ an// ├─ 苹果// │ └─ 树 ($)// └─ 雨伞 ($) 结果:= tri.Search([]string{"the", "quick"})for _, res := 范围结果.Results { fmt.Println(res.Key, res.Value)
}// 输出（基于前缀的搜索）:// [快速的棕色狐狸] 2// [快速的跑车] 3key := []string{"the", "tree"}results = tri.Search(key , trie.WithMaxEditDistance(2), // 编辑可以插入、删除、替换trie.WithEditOps())for _, res := range results.Results { fmt.Println(res.Key, res.EditDistance) // EditDistance 是转换为[树]所需的编辑次数}//输出（结果距[树]不超过2次编辑）:// [the] 1// [绿色树] 1// [一棵苹果树] 2// [一把雨伞] 2result := results.Results[2]fmt.Printf("将 %v 转换为 %v:n", result.Key, key)printEditOps(result.EditOps)// 输出（将结果转换为 [树] 所需的编辑操作）:// 将 [一棵苹果树] 转换为 [树]:// - 删除“an”// - 将“apple”替换为“the”// - 不编辑“tree”results = tri.Search(key, trie.WithMaxEditDistance(2), trie.WithTopKLeastEdited(), trie.WithMaxResults(2))for _, res := 范围结果.Results { fmt.Println(res.Key, res.Value, res.EditDistance)
}// 输出（前 2 个最少编辑的结果）:// [the] 1 1// [the green tree] 4 1