У меня есть около 10000 слов, используемых в качестве набора перевернутых индексов для около 500000 документов. Оба нормализуются, поэтому индекс представляет собой отображение целых чисел (идентификатора слова) на набор целых чисел (идентификаторов документов, которые содержат слово).
Мой прототип использует набор Python в качестве очевидного типа данных.
Когда я выполняю поиск документа, я нахожу список из N поисковых слов и их соответствующих N наборов. Я хочу вернуть набор документов на пересечении этих N наборов.
Метод пересечения Python реализован как парное сокращение. Я думаю, что мне лучше справиться с параллельным поиском отсортированных наборов, если библиотека предлагает быстрый способ получить следующую запись после i .
Я давно искал что-то подобное. Несколько лет назад я написал PyJudy , но я больше не поддерживаю его и знаю, сколько потребуется работы, чтобы довести его до стадии, когда мне снова будет удобно. Я предпочел бы использовать чужой хорошо проверенный код, и я бы хотел, чтобы он поддерживал быструю сериализацию / десериализацию.
Я не могу найти ни одного, или, по крайней мере, ни одного с привязками Python. Существует avltree , который делает то, что я хочу, но, поскольку даже объединение парных множеств занимает больше времени, чем я хочу, я подозреваю, что хочу, чтобы все мои операции выполнялись на C / C ++.
Знаете ли вы о каких-либо библиотеках radix / patricia / critbit tree, написанных как расширения C / 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 и аналогичным записям для других массивов Джуди.
Этот алгоритм динамически адаптируется к данным, должен преимущественно отдавать предпочтение наборам с низким количеством попаданий. Для типа данных, с которыми я работаю, производительность увеличилась на 5-10% .)
)