У меня есть около 10 000 слов, используемых в качестве набора инвертированных индексов примерно для 500 000 документов. Оба нормализованы, поэтому индекс представляет собой сопоставление целых чисел (идентификатор слова) с набором целых чисел (идентификаторы документов, содержащих это слово).
В моем прототипе в качестве очевидного типа данных используется набор Python.
Когда я ищу документ, я нахожу список из N искомых слов и соответствующих им N наборов. Я хочу вернуть набор документов на пересечении этих N наборов.
Метод Python «intersect» реализован как попарная редукция. Я думаю, что параллельный поиск отсортированных множеств может быть лучше, если библиотека предлагает быстрый способ получить следующую запись после 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 и аналогичным записям для других массивов Judy.
Этот алгоритм, динамически адаптирующийся к данным, должен отдавать предпочтение наборам с низким количеством совпадений. Для типа данных, с которыми я работаю, это дало 5 -10% увеличение производительности.))
