Существуют ли какие-либо деревья radix/patricia/critbit для Python?

У меня около 10 000 слов, используемых в виде набора инвертированных индексов примерно для 500 000 документов. Оба нормированы, поэтому индекс представляет собой отображение целых чисел (word id) в набор целых чисел (идентификаторы документов, которые содержат слово).

Мой прототип использует Python как очевидный тип данных.

Когда я выполняю поиск документа, я нахожу список N поисковых слов и их соответствующих N наборов. Я хочу вернуть набор документов в пересечении тех N наборов.

Метод "пересекаться" Python реализуется как попарное восстановление. Я думаю, что я могу сделать лучше с параллельным поиском отсортированных наборов, если библиотека предлагает быстрый способ получить следующую запись после i.

Я искал что-то подобное в течение некоторого времени. Несколько лет назад я писал PyJudy, но я больше не поддерживаю его, и я знаю, сколько работы потребуется, чтобы довести его до стадии, m удобно с ним снова. Я предпочел бы использовать чей-то еще проверенный код, и я бы хотел, чтобы он поддерживал быструю сериализацию/десериализацию.

Я не могу найти ни одного или, по крайней мере, не с помощью связок Python. Существует avltree, который делает то, что я хочу, но так как даже слияние парных мутов занимает больше времени, чем я хочу, я подозреваю, что хочу все мои операции выполняются на C/С++.

Знаете ли вы какие-либо библиотеки дерева radix/patricia/critbit, написанные как расширения C/С++ для Python?

В противном случае, какая самая подходящая библиотека, которую я должен обернуть? Сайт Judy Array не обновлялся через 6 лет, а 1.0.5 выпущен в мае 2007 года. (Хотя он строит чисто так, возможно, это Просто работает.)

(Изменить: чтобы уточнить, что я ищу из 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% увеличение производительности). )

Ответы

Ответ 1

Да, есть некоторые, , хотя я не уверен, что они подходят для вашего прецедента:, но, похоже, ни один из них не является тем, что вы просили.

BioPython имеет реализацию Trie в C.

А, вот приятное обсуждение, включая тесты: http://bugs.python.org/issue9520

Другие (некоторые очень устаревшие) реализации:

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

py-radix - это реализация структура данных дерева оснований для хранения и поиска IPv4 и IPv6 сетевые префиксы.

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

Выполнение Python Патрисия дерево

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

Реализация дерева префикса (trie).

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

patricia.py: реализация Python PATRICIA trie (Практический алгоритм для получения информации, закодированной в Буквенно-цифровой).

Ответ 2

Недавно я добавил поддержку итерации datrie, вы можете попробовать.