Поиск всех совпадений из большого набора строк в меньшей строке
У меня есть большой набор слов и фраз (лексикон или словарь), который включает в себя подстановочные знаки. Мне нужно найти все экземпляры этих слов и фраз в гораздо меньшей строке (~150 символов на данный момент).
Сначала я хотел запустить операцию в обратном порядке; то есть проверить, существует ли каждое слово в моей меньшей строке в Лексиконе, что может быть реализовано в виде хэш-таблицы. Проблема в том, что некоторые из этих значений в моем лексиконе не являются отдельными словами, а многие являются символами подстановки (например, substri*).
Я думаю об использовании алгоритма Рабина-Карпа, но я не уверен, что это лучший выбор.
Какой эффективный алгоритм или метод для выполнения этой операции?
Пример данных:
Словарь содержит сотни слов и потенциально может расширяться. Эти слова могут заканчиваться подстановочными знаками (звездочками). Вот несколько случайных примеров:
- хорошо
- плохой
- освобождена *
- небрежное *
- большая потеря
Текст, который мы анализируем (на данный момент) - это короткие, неформальные (грамматически) английские высказывания. Основным примером текста (опять же, на данный момент) будет Twitter Tweet. Они ограничены примерно 140 символами. Например:
Just got the Google nexus without a contract. Hands down its the best phone
I've ever had and the only thing that could've followed my N900.
Хотя может быть полезно отметить, что мы выполняем очень простой анализ настроений по этому тексту; наша техника анализа настроений не моя забота. Я просто перевожу существующее решение в систему обработки в реальном времени, и мне нужно выполнить некоторые оптимизации.
7 ответов
Я думаю, что это отличный пример использования алгоритма сопоставления строк Aho-Corasick, который специально разработан для поиска всех совпадений большого набора строк в одной строке. Он выполняется в две фазы - первая фаза, в которой создается соответствующий автомат (который может быть сделан заранее и требует только линейного времени), и вторая фаза, в которой автомат используется для поиска всех совпадений (для которой требуется только линейное время)., плюс время, пропорциональное общему количеству матчей). Алгоритм также может быть адаптирован для поддержки поиска по шаблону.
Надеюсь это поможет!
Один ответ, который я хотел выбросить, был алгоритм поиска Бойера-Мура. Это алгоритм, который использует grep. Grep, вероятно, один из самых быстрых доступных инструментов поиска. Кроме того, вы можете использовать что-то вроде GNU Parallel для параллельного запуска grep, тем самым реально ускоряя алгоритм.
Кроме того, вот хорошая статья, которая может показаться вам интересной.
Вы все еще можете использовать свою оригинальную идею проверки каждого слова в тексте по словарю. Тем не менее, чтобы эффективно его запустить, вам нужно проиндексировать словарь, чтобы сделать поиск действительно быстрым. Уловка, используемая в системах поиска информации, заключается в хранении так называемого индекса пермутерм ( http://nlp.stanford.edu/IR-book/html/htmledition/permuterm-indexes-1.html).
В основном, что вы хотите сделать, это сохранить в словаре каждую возможную перестановку слов (например, для дома):
house$
ouse$h
use$ho
...
e$hous
Затем этот индекс можно использовать для быстрой проверки по шаблонным запросам. Если, например, у вас есть ho*e, вы можете посмотреть в индексе пермутерства термин, начинающийся с e$ho и вы быстро найдете совпадение с домом.
Сам поиск обычно выполняется с помощью некоторой логарифмической стратегии поиска (бинарный поиск или b-деревья) и, таким образом, обычно очень быстр.
Пока шаблоны для полных слов: вы не хотите or соответствовать storage; пробелы и знаки препинания - это якоря совпадений, тогда простой способ - это преобразовать лексику во вход генератора сканера (например, вы могли бы использовать flex), сгенерировать сканер, а затем запустить его над своим вводом.
Генераторы сканера предназначены для идентификации появления токенов на входе, где каждый тип токена описывается регулярным выражением. Flex и подобные программы быстро создают сканеры. Flex по умолчанию обрабатывает до 8 тысяч правил (в вашем случае лексикон), и это можно расширить. Сгенерированные сканеры работают за линейное время и на практике работают очень быстро.
Внутренне регулярные выражения токенов преобразуются в стандартный конвейер "теоремы Клини": сначала в NFA, затем в DFA. DFA затем преобразуется в свою уникальную минимальную форму. Это кодируется в таблице HLL, которая отправляется внутри оболочки, которая реализует сканер, ссылаясь на таблицу. Это то, что делает flex, но возможны и другие стратегии. Например, DFA можно перевести на goto код, в котором состояние DFA неявно представляется указателем инструкции во время выполнения кода.
Причина такого пробела заключается в том, что сканеры, созданные такими программами, как Flex, обычно неспособны идентифицировать перекрывающиеся совпадения: strangers не может соответствовать обоим strangers а также range, например.
Вот гибкий сканер, который соответствует приведенному вами примеру лексики:
%option noyywrap
%%
"good" { return 1; }
"bad" { return 2; }
"freed"[[:alpha:]]* { return 3; }
"careless"[[:alpha:]]* { return 4; }
"great"[[:space:]]+"loss" { return 5; }
. { /* match anything else except newline */ }
"\n" { /* match newline */ }
<<EOF>> { return -1; }
%%
int main(int argc, char *argv[])
{
yyin = argc > 1 ? fopen(argv[1], "r") : stdin;
for (;;) {
int found = yylex();
if (found < 0) return 0;
printf("matched pattern %d with '%s'\n", found, yytext);
}
}
И запустить его:
$ flex -i foo.l
$ gcc lex.yy.c
$ ./a.out
Good men can only lose freedom to bad
matched pattern 1 with 'Good'
matched pattern 3 with 'freedom'
matched pattern 2 with 'bad'
through carelessness or apathy.
matched pattern 4 with 'carelessness'
Это не дает точного ответа на вопрос об алгоритме, но посмотрите библиотеку re2. В Python, Ruby и других языках программирования есть хорошие интерфейсы. По моему опыту, это слепо быстро и устраняет довольно похожие узкие места в моем коде с небольшим суетой и практически без дополнительного кода с моей стороны.
Единственная сложность связана с перекрытием шаблонов. Если вы хотите, чтобы шаблоны начинались с границ слов, вы должны иметь возможность разбить словарь на набор регулярных выражений r_1, r_2, ..., r_k формы \b(foobar|baz baz\S*|...) где каждая группа в r_{i+1} имеет префикс в r_i, Затем вы можете оценить короткое замыкание, так как если r_{i+1} соответствует тогда r_i Должно быть подобрано.
Если вы не реализуете свой алгоритм в высокооптимизированном C, я бы поспорил, что этот подход будет быстрее, чем любой из (алгоритмически превосходных) ответов где-либо еще в этой теме.
Позвольте мне получить это прямо. У вас есть большой набор запросов и одна маленькая строка, и вы хотите найти экземпляры всех этих запросов в этой строке.
В этом случае я предлагаю вам проиндексировать этот маленький документ как сумасшедший, чтобы ваше время поиска было как можно короче. Ад. При таком размере документа я бы даже подумал о том, чтобы делать небольшие мутации (для сопоставления с подстановочными знаками и т. Д.) И индексировал бы их.
У меня была очень похожая задача. Вот как я это решил, производительность невероятна http://www.foibg.com/ijita/vol17/ijita17-2-p03.pdf