Python中有没有基数树/帕特里夏树/临界位树？

Question

我有大约10,000个单词，这些单词用来创建一个反向索引，关联到大约500,000个文档。所有的单词和文档都经过标准化处理，所以这个索引实际上是一个整数的映射（单词的ID）到一组整数（包含这个单词的文档ID）。

我的原型程序使用了Python的集合（set）作为数据类型，这样很明显。

当我搜索一个文档时，我会找到N个搜索词和它们对应的N个集合。我想要返回这些N个集合的交集，也就是同时包含这些单词的文档集合。

Python的“交集”方法是通过成对比较来实现的。我觉得我可以通过对排序后的集合进行并行搜索来做得更好，只要这个库能提供一种快速获取某个位置后一个条目的方法。

我已经寻找这样的东西有一段时间了。几年前我写过一个叫PyJudy的项目，但我现在不再维护它，我知道要让它达到我满意的状态需要多少工作。我更愿意使用别人经过充分测试的代码，并且希望这个代码支持快速的序列化和反序列化。

我找不到这样的库，或者至少没有找到带有Python绑定的。虽然有一个avltree，它能满足我的需求，但由于即使是成对的集合合并也比我想要的慢，我怀疑我希望所有操作都在C/C++中完成。

你知道有没有用C/C++编写的、可以作为Python扩展的基数树/帕特里夏树/临界位树库吗？

如果没有，那我应该包装哪个最合适的库？Judy Array网站已经有6年没有更新了，最后一次发布是2007年5月的1.0.5版本。（虽然它可以正常构建，所以也许它就是可以用的。）

（编辑：为了澄清我想要的API，我想要类似这样的东西：

def merge(document_sets):
    probe_i = 0
    probe_set = document_sets[probe_i]
    document_id = GET_FIRST(probe_set)

    while IS_VALID(document_id):
        # See if the document is present in all sets
        for i in range(1, len(document_sets)):
            # dynamically adapt to favor the least matching set
            target_i = (i + probe_i) % len(document_sets)
            target = document_sets[target_i]
            if document_id not in target_set:
                probe_i = target_id
                probe_set = document_sets[probe_i]
                document_id = GET_NEXT(probe_set, document_id)
                break
        else:
            yield document_id

我在寻找一个实现GET_NEXT()的方法，用来返回给定条目之后的下一个条目。这对应于Judy1N和其他Judy数组的类似条目。

这个算法会根据数据动态调整，优先考虑命中率低的集合。对于我处理的数据类型，这带来了5-10%的性能提升。）

性能优化数据结构集合交集反向索引基数树帕特里夏树临界位树 C/C++扩展

Python中有没有基数树/帕特里夏树/临界位树？

2 个回答

撰写回答