PruningRadixTrie

PruningRadixTrie - 速度提升1000倍的基数树，用于前缀搜索和自动完成

PruningRadixTrie是一种新颖的数据结构，源自基数树，但速度快了3个数量级。

基数树或Patricia树是一种空间优化的前缀树。
修剪基数树是一种新型基数树算法，允许对基数树进行修剪并提前终止查找。

在许多情况下，我们对给定前缀的所有子项的完整集合并不感兴趣，而只关注前k个最相关的术语。特别是对于短前缀，这会导致查找前10个结果的时间大幅减少。另一方面，对于自动完成功能来说，数百万个建议的完整结果集并不会有任何帮助。

查找加速是通过在每个节点中存储其所有子节点的最大排名来实现的。通过比较这个最大子节点排名与迄今为止检索到的结果的最低排名，我们可以大幅修剪树，并对子节点排名较低的不太有希望的分支提前终止查找。

性能

基准测试

修剪基数树的速度比普通基数树快1000倍。

虽然对于单个用户来说，37毫秒的自动完成可能看起来足够快，但当我们需要同时为数千用户服务时，这就不够用了。在这种情况下，只有依靠比普通基数树快得多的算法，才能在大型词典中进行自动完成查找。

虽然对于拉丁字母表来说，长度为1的前缀可能不太有用，但对于CJK语言来说却很有意义。此外，快速前缀搜索算法还有许多其他应用领域，不仅限于逐字词完成：前缀可以由任意项目组成，例如查询完成中的整个词语，或长路线序列中的城镇。

词典

Terms.txt包含600万个从英语维基百科中提取的一元和二元组，使用词频计数进行排名。但你可以使用任何语言和领域的频率词典。

博客文章

修剪基数树 - 超级基数树
 速度提升1000倍的拼写纠正算法
 SymSpell vs. BK-tree：100倍更快的模糊字符串搜索和拼写检查

应用：

PruningRadixTrie非常适合大型词典中的自动完成、查询完成或任何其他前缀搜索。虽然对于单个用户来说，37毫秒的自动完成可能看起来足够快，但如果我们需要同时为数千用户服务，情况就完全不同了。在这种情况下，只有依靠比普通基数树快得多的算法，才能在大型词典中进行自动完成查找。

使用方法：

创建对象

PruningRadixtrie pruningRadixTrie = new PruningRadixtrie();

**AddTerm：**将术语和术语频率计数插入修剪基数树。相同术语的频率计数会累加。

pruningRadixTrie.AddTerm("microsoft", 1000);

**GetTopkTermsForPrefix：**从修剪基数树中检索给定前缀的前k个最相关术语。

string prefix="micro";
int topK=10;
var results = pruningRadixTrie.GetTopkTermsForPrefix(prefix, topK, out long termFrequencyCountPrefix);
foreach ((string term,long termFrequencyCount) in results) Console.WriteLine(term+" "+termFrequencyCount);

**ReadTermsFromFile：**从磁盘反序列化修剪基数树以实现持久性。

pruningRadixTrie.ReadTermsFromFile("terms.txt");

**WriteTermsToFile：**将修剪基数树序列化到磁盘以实现持久性。

pruningRadixTrie.WriteTermsToFile("terms.txt");

移植版本

以下是第三方对其他编程语言的移植或重新实现。我本人未测试这些版本是否为精确移植、无错误、提供相同结果或与原始算法一样快。

Go
https://github.com/olympos-labs/pruning-radix-trie

Java
https://github.com/benldr/JPruningRadixTrie

Python
https://github.com/otto-de/PyPruningRadixTrie

Rust
https://github.com/peterall/pruning_radix_trie

PruningRadixTrie由SeekStorm - 高性能搜索即服务和搜索API贡献