Найти вхождения огромного списка фраз в тексте

Ответ 1

Чтобы получить разумную скорость при сопоставлении шаблонов 80k, вам определенно нужна некоторая предварительная обработка шаблонов, алгоритмы с одним выстрелом, такие как Boyer-Moore, не помогут.

Вероятно, вам также понадобится выполнить работу в скомпилированном коде (предположите расширение C), чтобы получить разумную пропускную способность. Что касается предварительной обработки шаблонов - один из вариантов - это государственные машины, такие как Aho-Corasick или какой-то общий конечный преобразователь. Следующий вариант - это что-то вроде индекса на основе suffix array, а последний, который приходит мне на ум, - это инвертированный индекс.

Если ваши совпадения являются точными, а шаблоны соответствуют границам слов, есть вероятность, что хорошо реализованное слово или inverted index ключом слово-ngram будет достаточно быстрым даже в чистом Python. Индекс не является полным решением, он скорее даст вам несколько кандидатских фраз, которые вам нужно проверить с помощью обычного сопоставления строк для полного соответствия.

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

Что касается реальных реализаций - flashtext, упомянутый в другом ответе здесь, кажется, является разумным чистым решением Python, если вы в порядке с ограничением полной фразы.

В противном случае вы можете получить разумные результаты с помощью универсальных библиотек регулярных выражений с несколькими шаблонами: одним из самых быстрых должен быть гиперверс Intel - есть даже некоторые рудиментарные привязки python.

Другим вариантом является Google RE2 с привязками Python от Facebook. Вы хотите использовать RE2::Set в этом случае.

Ответ 2

У меня была почти идентичная проблема с моей собственной страницей чата. Я хотел бы добавить ссылку на несколько ключевых слов (с небольшими вариациями), которые присутствовали в тексте. У меня было всего около 200 phrases хотя бы проверить.

Я решил попробовать использовать стандартное регулярное выражение для проблемы, чтобы понять, как быстро это будет. Основным узким местом было построение регулярного выражения. Я решил предварительно скомпилировать это и нашел, что время матча было очень быстрым для более коротких текстов.

В следующем подходе используется список phrases, в каждом из которых есть phrase и link. Сначала он создает словарь обратного поиска:

{'phrase to match' : 'link_url', 'another phrase' : 'link_url2'}

Затем он компилирует регулярное выражение в следующем виде, это позволяет совпадениям, которые содержат различное количество пробелов между словами:

(phrase\s+to\s+match|another\s+phrase)

Затем для каждого фрагмента текста (например, 2000 слов каждый) он использует finditer() для получения каждого соответствия. Объект match дает вам .span() давая начальное и конечное расположение соответствующего текста, а group(1) дает согласованный текст. Поскольку текст может иметь дополнительные пробелы, re_whitespace сначала применяется для его удаления и возвращает его в форму, хранящуюся в reverse словаре. При этом можно автоматически найти требуемую link:

import re

texts = ['this is a phrase   to    match', 'another phrase this  is']
phrases = [{'phrase': 'phrase to match', 'link': 'link_url'}, {'phrase': 'this is', 'link': 'link_url2'}]

reverse = {d['phrase']:d['link'] for d in sorted(phrases, key=lambda x: x['phrase'])}
re_whitespace = re.compile(r'\s+')
re_phrases = re.compile('({})'.format('|'.join(d['phrase'].replace(' ', r'\s+') for d in phrases)))

for text in texts:
    matches = [(match.span(), reverse[re_whitespace.sub(' ', match.group(1))]) for match in re_phrases.finditer(text)]
    print(matches)

Что бы отображать совпадения для двух текстов, как:

[((0, 7), 'link_url2'), ((10, 30), 'link_url')]
[((15, 23), 'link_url2')]

Чтобы проверить, как это масштабируется, я протестировал его, импортировав список английских слов из nltk и автоматически создав 80,000 двух-шести словосочетаний вместе с уникальными ссылками. Затем я приурочил его к двум достаточно длинным текстам:

import re
import random
from nltk.corpus import words
import time

english = words.words()

def random_phrase(l=2, h=6):
    return ' '.join(random.sample(english, random.randint(l, h)))


texts = ['this is a phrase   to    match', 'another phrase this  is']
# Make texts ~2000 characters
texts = ['{} {}'.format(t, random_phrase(200, 200)) for t in texts]

phrases = [{'phrase': 'phrase to match', 'link': 'link_url'}, {'phrase': 'this is', 'link': 'link_url2'}]
#Simulate 80k phrases
for x in range(80000):
    phrases.append({'phrase': random_phrase(), 'link': 'link{}'.format(x)})

construct_time = time.time()    

reverse = {d['phrase']:d['link'] for d in phrases}
re_whitespace = re.compile(r'\s+')
re_phrases = re.compile('({})'.format('|'.join(d['phrase'].replace(' ', r'\s+') for d in sorted(phrases, key=lambda x: len(x['phrase'])))))

print('Time to construct:', time.time() - construct_time)
print()

for text in texts:
    start_time = time.time()
    print('{} characters - "{}..."'.format(len(text), text[:60]))
    matches = [(match.span(), reverse[re_whitespace.sub(' ', match.group(1))]) for match in re_phrases.finditer(text)]
    print(matches)
    print('Time taken:', time.time() - start_time)        
    print()

Это займет ~ 17 секунд, чтобы построить регулярное выражение и обратный поиск (который требуется только один раз). Затем это занимает около 6 секунд на текст. Для очень короткого текста требуется ~ 0,06 секунды на текст.

Time to construct: 16.812477111816406

2092 characters - "this is a phrase   to    match totaquine externize intoxatio..."
[((0, 7), 'link_url2'), ((10, 30), 'link_url')]
Time taken: 6.000027656555176

2189 characters - "another phrase this  is political procoracoidal playstead as..."
[((15, 23), 'link_url2')]
Time taken: 6.190425715255737

Это, по крайней мере, даст вам представление о сравнении.

Ответ 3

Возможно, вам стоит попробовать flashtext.
По словам автора, это намного быстрее, чем Regex.

Автор даже опубликовал статью для этой библиотеки.

Я лично пробовал эту библиотеку для одного из моих проектов, по-моему, его API довольно дружелюбен и полезен.

Надеюсь, поможет.

Ответ 4

Вы должны попробовать алгоритм поиска строк/шаблонов. Самый известный алгоритм для вас - это Aho-Corasick, для него есть библиотека python (в верхней части поиска Google)

Большинство алгоритмов сопоставления шаблонов/строкового поиска потребуют от вас конвертировать ваш "пакет слов/фраз" в trie.

Ответ 5

Модуль pyparsing - инструмент python для извлечения информации из текста - поможет вам с написанием фразового соответствия. Он возвращает все совпадения и диапазон индексов каждого совпадения фразы, которую вы можете описать с помощью BNF (форма Бэксу-Наур) (т.е. грамматика). По моему опыту, он прост в использовании (2), выразительный с точки зрения моделей, которые вы можете определить, и впечатляюще быстро.

from pyparsing import Word, alphas
greet = Word( alphas ) + "," + Word( alphas ) + "!" # <-- grammar defined here
hello = "Hello, World!"
print (hello, "->", greet.parseString( hello ))

Используйте scanString для возврата индекса соответствия:

for item in greet.scanString(hello):
    print(item)

>>> ((['Hello', ',', 'World', '!'], {}), 0, 13)

Если вы собрали список фраз, используя pyparsing в качестве словаря формы

phrase_list = {phrase_defined_with_pyparsing: phrase_name}

то ваша грамматика может быть гигантским оператором OR с помеченными фразами.

import pyparsing as pp
your_grammar = pp.Or([phrase.setResultsName(phrase_name) for phrase, phrase_name in phrase_list.items()])
all_matches = your_grammar.scanString(big_document)

Каждое совпадение представляет собой кортеж, который помечен (через setResultsName) и имеет индексный диапазон.

Ответ 6

Предполагая, что список фраз изменяется со временем и становится больше, я бы рекомендовал использовать программное обеспечение, которое уже делает, что вам нужно. Например, elasticsearch, он с открытым исходным кодом и имеет клиент Python. Если вы используете такой сервис в фоновом режиме, это решает все, что вам нужно, и, возможно, больше, чем вы когда-либо могли себе представить. И это действительно не так сложно реализовать.

Ответ 7

У вас гораздо больше данных шаблонов, чем текстовых данных. Инвертировать проблему: сопоставить шаблоны с текстом.

Для целей этого я бы предположил, что текст может быть разумно обозначен в словах (или что-то словоподобное). Я бы также предположил, что фразы, даже если они не могут быть обозначены как таковые (например, потому что они являются регулярными выражениями), тем не менее обычно содержат слова, и (большую часть времени) должны соответствовать хотя бы одному из слов, которые они содержат,

Вот эскиз решения, которое состоит из трех частей:

1. Токенизировать и индексировать шаблоны (один раз) - это создает карту шаблонов, содержащих каждый токен

2. Обозначьте текстовые и фильтрующие шаблоны, чтобы найти кандидатов, которые могут соответствовать тексту.

3. Проверка шаблонов кандидатов и выполнение замещений

Вот код:

import re
import random
# from nltk.corpus import words
import time

""" Prepare text and phrases, same as in Martin Evans answer """

# english = words.words()
with open('/usr/share/dict/american-english') as fh:
    english = [ x.strip() for x in fh.readlines() ]


def random_phrase(l=2, h=6):
    return ' '.join(random.sample(english, random.randint(l, h)))


texts = ['this is a phrase to match', 'another phrase this is']
# Make texts ~2000 characters
texts = ['{} {}'.format(t, random_phrase(200, 200)) for t in texts]

phrases = [{'phrase': 'phrase to match', 'link': 'link_url'}, {'phrase': 'this is', 'link': 'link_url2'}]
#Simulate 80k phrases
for x in range(80000):
    phrases.append({'phrase': random_phrase(), 'link': 'link{}'.format(x)})

""" Index the patterns """

construct_time = time.time()    

reverse = {d['phrase']:d['link'] for d in phrases}
re_phrases = [ re.compile(d['phrase'].replace(' ', r'\s+')) for d in phrases ]
re_whitespace = re.compile(r'\s+')

def tokenize(str):
    return str.split()

index = {}

for n in range(len(phrases)):
    tokens = tokenize(phrases[n]['phrase'])
    for token in tokens:
        if not token in index:
            index[token] = []
        index[token].append(n)

print('Time to construct:', time.time() - construct_time)
print()

for text in texts:
    start_time = time.time()
    print('{} characters - "{}..."'.format(len(text), text[:60]))

    """ Filter patterns to find candidates that *could* match the text """
    tokens = tokenize(text)
    phrase_ns = []

    for token in tokens:
        if not token in index:
           continue
        for n in index[token]:
            phrase_ns.append(n)

    phrase_ns = list(set(phrase_ns))

    """ Test the candidate patterns and perform substitutions """
    for n in phrase_ns:
        match = re.search(re_phrases[n], text)
        if match:
            print(match.span(), reverse[match.group()])
    print('Time taken:', time.time() - start_time)        
    print()

В моей среде эта версия создает индекс за 16,2 секунды и выполняет сопоставление в 0,0042 и 0,0037 секунды (против 4,7 секунды для простой версии регулярного выражения, ускорение ~ 1000 раз). Точная производительность зависит от статистических свойств текста и фраз, конечно, но это почти всегда будет огромной победой.

Бонус: если фраза должна соответствовать нескольким словам (токенам), вы можете добавить ее только в индексную запись для одного наименее общего токена, который должен соответствовать, для другого огромного ускорения.