Word Toptimizer

Question

for s_index, s in enumerate(sentences):
        s_tokens = s.split()
        if (local_q_set.intersection(set(s_tokens)) == local_q_set):
            q_results.append(s_index)

Приведенный выше фрагмент кода является основным алгоритмом, который я использовал для поиска релевантных предложений в массивных текстовых данных, которые включают все токены в запросе. Например, для запроса «счастливое яблоко» он находит все предложения, включающие ровно один или несколько из всех заданных токенов (то есть «счастливый» и «яблоко»). Мой метод очень прост: найдите общие пересекающиеся множества и посмотрите, совпадают ли они. Тем не менее, я не получаю достаточно производительности. Если кто-то видел оптимизацию для такой проблемы, я был бы очень признателен за любое направление или ссылку на идею - спасибо за время заранее

Answer 1

Есть несколько вещей, которые вы можете сделать, чтобы повысить производительность последовательного поиска, но реальное повышение получит индексирование токенов.

set.difference

Использованиеnot local_q_set.difference(s_tokens) вместо сравнения пересечения с исходным набором может быть несколько быстрее.

Фильтр регулярных выражений

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

import re
tokens     = re.compile("|".join(local_q_set))
tokenCount = len(local_q_set)
for s_index, s in enumerate(sentences):
    s_tokens = tokens.findall(s)
    if len(s_tokens) < tokenCount or local_q_set.difference(s.split()):
       continue
    q_results.append(s_index) 

Фильтр с использованием оператора in

Вы также можете использоватьпростой оператор in для проверки наличия токенов вместо регулярного выражения (это должно быть быстрее, когда в запросе мало токенов):

result = []
tokenSet = set(queryTokens)
for index, sentence in enumerate(sentences):
     if any( token not in sentence for token in queryTokens) \
     or tokenSet.difference(sentence.split()):
         continue
     result.append(index)

Кэширование наборов слов предложений

Чтобы улучшить последовательный поиск при выполнении нескольких запросов к одному и тому же списку предложений, вы можете создать кэш наборов слов, соответствующихк предложениям.Это избавит от необходимости разбора предложений при их поиске соответствия.

cachedWords = []

queryTokens = ["happy","apple"]

queryTokenSet = set(queryTokens)
if not cachedWords:
    cachedWords = [ set(sentence.split()) for sentence in sentences ]
result = [ index for index,words in enumerate(cachedWords) if not queryTokenSet.difference(words) ]

Индексирование токенов

Если вы собираетесь выполнить много запросов кВ этом же списке предложений будет более эффективно создать отображение между токенами и индексами предложений.Вы можете сделать это, используя словарь, а затем получить результаты запроса напрямую, пересекая индексы предложений запрашиваемых токенов:

tokenIndexes = dict()
for index,sentence in enumerate(sentences):
    for token in sentence.lower().split():
        tokenIndexes.setdefault(token,[]).append(index)

def tokenSet(token): return set(tokenIndexes.get(token,[]))

queryTokens = ["happy","apple"]

from functools import reduce
result = reduce(set.intersection , (tokenSet(token) for token in queryTokens) )

Это позволит вам экономически эффективно реализовывать сложные запросы с использованием операторов множеств.Например:

import re

querySring = " happy & ( apple | orange | banana ) "
result = eval(re.sub("(\w+)",r"tokenSet('\1')", querySring)) 

# re.sub(...) transforms the query string into " tokenSet('happy') & ( tokenSet('apple') | tokenSet('orange') | tokenSet('banana') ) "

Тесты производительности:

Я провел несколько тестов производительности (обнаружив два токена в одном предложении из 80 000):

original algorithm: 105 ms           1x
set.difference:      88 ms         1.2x
regular expression:  60 ms         1.8x
"in" operator:       43 ms         2.4x
caching word sets:   23 ms         4.6x (excluding 187ms to build cache)
token indexing:       0.0075 ms  14000x (excluding 238ms to build tokenIndexes)

Итак, если вы собираетесь выполнять несколько запросов к одним и тем же предложениям при индексировании токена, вы получите ответы в 14 тысяч раз быстрее, когда будет создан словарь tokenIndexes.