эффективный алгоритм поиска совпадения матрицы фраз

Question

У меня есть список L около 40 000 фраз и документ объемом около 10 миллионов слов. я хочу проверить, какая пара этих фраз co происходит в окне из 4 слов. Например, рассмотрим L = [«коричневая лиса», «ленивая собака»]. В документе содержатся слова: «Быстрая коричневая лиса прыгает через ленивую собаку». Я хочу посмотреть, сколько раз коричневый лис и ленивая собака появляется в окне из четырех слов и хранит это в файле. У меня следующий код для этого:

content=open("d.txt","r").read().replace("\n"," "); 
for i in range(len(L)): 
for j in range(i+1,len(L)): 
    wr=L[i]+"\W+(?:\w+\W+){1,4}"+L[j] 
    wrev=L[j]+"\W+(?:\w+\W+){1,4}"+L[i] 
    phrasecoccur=len(re.findall(wr, content))+len(re.findall(wrev,content)) 
    if (phrasecoccur>0): 
    f.write(L[i]+", "+L[j]+", "+str(phrasecoccur)+"\n") 

По существу, для каждой пары фраз в списке L, я проверяю в содержании документа, что сколько раз появляются эти фразы в окне 4 слов. Однако этот метод является вычислительно неэффективным, когда список L довольно большой, например, 40K элементов. Есть ли лучший способ сделать это?

Answer 1

Развивая ответ Иоиля, ваш итератор может быть что-то вроде этого:

def doc_iter(doc): 
    words=doc[0:4] 
    yield words 
    for i in range(3,len(doc)): 
    words=words[1:] 
    words.append(doc[i]) 
    yield words 

положить ваши фразы в Словаре и использовать итератор по документу, проверяя фразы на каждой итерации. Это должно дать вам производительность между O (n) и O (n * log (n)).

Answer 2

Вы можете использовать что-то похожее на Aho-Corasick string matching algorithm. Создайте конечный автомат из списка фраз. Затем начните подавать слова в конечный автомат. Всякий раз, когда происходит совпадение, конечный автомат сообщает вам, какая фраза соответствует и на каком номере слова. Так что ваш выход будет что-то вроде:

"brown fox", 3 
"lazy dog", 8 
etc. 

Вы можете захватить все выходные и после процесса его, или вы можете обрабатывать матчи, как они найдены.

Для создания конечного автомата (несколько секунд для 40 000 фраз) требуется немного времени, но после этого он линейный по числу входных токенов, количеству фраз и количеству совпадений.

Я использовал что-то похожее на совпадение 50 миллионов видеороликов YouTube с несколькими миллионами названий песен и имен художников в базе данных MusicBrainz. Отлично. И очень быстро.

Answer 3

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

import re 

class Matcher(object): 
    def __init__(self, phrases): 
     phrase_pattern = "|".join("(?:{})".format(phrase) for phrase in phrases) 
     gap_pattern = r"\W+(?:\w+\W+){0,4}?" 
     full_pattern = "({0}){1}({0})".format(phrase_pattern, gap_pattern) 

     self.regex = re.compile(full_pattern) 

    def match(self, doc): 
     return self.regex.findall(doc) # or use finditer to generate match objs 

Вот как вы можете использовать его:

>>> L = ["brown fox", "lazy dog"] 
>>> matcher = Matcher(L) 
>>> doc = "The quick brown fox jumps over the lazy dog." 
>>> matcher.match(doc) 
[('brown fox', 'lazy dog')] 

Это решение имеет несколько ограничений. Во-первых, он не обнаруживает перекрывающиеся пары фраз. Итак, в примере, если вы добавили фразу "jumps over" в список фраз, вы все равно получите только одну пару с совпадением, ("brown fox", "jumps over"). Он пропустит как ("brown fox", "lazy dog"), так и ("jumps over", "lazy dog"), так как они содержат одни и те же слова.