У меня около 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% увеличение производительности). )
