python - 有没有用于 Python 的 radix/patricia/​​critbit 树？

Question

我有大约 10,000 个单词用作大约 500,000 个文档的一组倒排索引。两者都已标准化，因此索引是整数(单词 ID)到一组整数(包含该单词的文档的 ID)的映射。

我的原型(prototype)使用 Python 的集合作为明显的数据类型。

当我搜索文档时，我找到了 N 个搜索词及其对应的 N 个集合的列表。我想返回 N 组交集中的文档集。

Python 的“相交”方法是作为成对归约实现的。我认为我可以通过并行搜索排序集来做得更好，只要该库提供一种快速方法来获取 i 之后的下一个条目。

一段时间以来，我一直在寻找类似的东西。多年前我写了PyJudy但我不再维护它，而且我知道需要做多少工作才能让它恢复到让我再次适应它的状态。我宁愿使用别人经过良好测试的代码，而且我想要一个支持快速序列化/反序列化的代码。

我找不到任何 Python 绑定(bind)，或者至少找不到。有 avltree它可以满足我的要求，但由于即使是成对集合合并也需要比我想要的更长的时间，我怀疑我想用 C/C++ 完成所有操作。

您知道任何 radix/patricia/​​critbit 树库是为 Python 编写的 C/C++ 扩展吗？

否则，我应该包装的最合适的库是什么？ 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% increase in performance .))

Answer 1

是的，有一些， 虽然我不确定它们是否适合您的用例: 但似乎没有一个是您要求的。

BioPython在 C 中有一个 Trie 实现。

啊，这是一个很好的讨论，包括基准测试:http://bugs.python.org/issue9520

其他(一些非常陈旧的)实现:

http://pypi.python.org/pypi/radix

py-radix is an implementation of a radix tree data structure for the storage and retrieval of IPv4 and IPv6 network prefixes.

https://bitbucket.org/markon/patricia-tree/src

A Python implementation of patricia-tree

http://pypi.python.org/pypi/trie

A prefix tree (trie) implementation.

http://pypi.python.org/pypi/logilab-common/0.50.3

patricia.py : A Python implementation of PATRICIA trie (Practical Algorithm to Retrieve Information Coded in Alphanumeric).