Проверка, содержит ли строка одну из нескольких тысяч подстрок

Question

Я собираюсь просмотреть данные в твиттере в режиме реального времени и попытаться извлечь твиты, в которых упоминаются, например, названия фильмов. Предполагая, что у меня есть список из ~ 7000 жестко закодированных названий фильмов, с которыми я бы хотел ознакомиться, как лучше всего выбрать соответствующие твиты? Этот проект находится в зачаточном состоянии, поэтому я открыт для любого поиска любого решения (т. Е. Не зависит от языка). Любая помощь будет с благодарностью.

Обновление: Мне было бы любопытно, если бы кто-нибудь имел представление о том, как Yahoo! Placemaker API, решает эту проблему. Может принимать текстовую строку и возвращать геокодированный результат JSON для всех местоположений, упомянутых в нем.

Answer 1

Вы можете попробовать Быстрый алгоритм Ву и Манбера для поиска по нескольким шаблонам .

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

Лин, Лин и Лай: Гибридный алгоритм обратного хеширования и автоматического отслеживания для сканирования на вирусы (вариант Wu-Manber; статья находится за платным доступом IEEE).

Ча, Морару и др.: SplitScreen: включение эффективного, распределенного обнаружения вредоносных программ

Answer 2

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

Но так как кажется, что у вас короткие строки с известным шаблоном, вы сможете использовать что-то довольно простое. Сохраните набор заголовков, которые вам нужны, в хеш-таблице или дереве. Извлеките "string1" и "string2" из каждого твита с помощью регулярных выражений и проверьте, содержатся ли они в наборе.

Answer 3

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

Answer 4

Для одновременного поиска большого числа возможных целей может быть полезен алгоритм Рабина-Карпа .

Answer 5

После того, что предложил Эриксон, наиболее выполнимый поиск - это (лучше в вашем примере), а затем проверка одного из 7000 терминов.Вместо этого вы можете сузить набор, создав 7000 поисков по запросу «[фильм] лучше чем», а затем отфильтровав вручную второй фильм, но вы, вероятно, довольно быстро достигнете предела скорости поиска .

Вы можете ускорить поиск, используя специальный поисковый сервис, такой как Solr, вместо разбора текста.Возможно, вы сможете быстро извлекать заголовки, используя какой-либо сервис обработки естественного языка ( OpenCalais ?), Но это лучше подходит для пакетной обработки.