как распознать набор ключевых слов в тексте

Question

У меня огромный набор ключевых слов. Учитывая текст, я хочу иметь возможность распознавать только те слова, которые встречаются в списке ключевых слов, и игнорировать все остальные слова. Каков наилучший способ приблизиться к этому?

Answer 1

Алгоритм Aho-Corasick - это быстрый алгоритм для распознавания набора строк шаблона в большей исходной строке.Он используется несколькими поисковыми утилитами, наряду со многими антивирусными программами, поскольку он запускается за время O (m + n + z), где n - общий размер всех строк шаблона, которые вы пытаетесь сопоставить, m - длинастрока для поиска, а z - общее количество совпадений.Более того, если вы заранее знаете, какие строки вы ищете, вы можете выполнить O (n) в автономном режиме и сократить время поиска до O (m + z).

Answer 2

Сохраните ваши слова в три .

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

У вас будут небольшие сложности с определением слова. В частности, несловарные символы обычно заканчиваются словом, но есть исключения, такие как don't.

Обратите внимание, что некоторые механизмы регулярных выражений (Perl в любой недавней версии Perl для одного) достаточно умны, чтобы автоматически создавать три и пытаться сопоставить его. Следовательно, есть большая вероятность, что вы можете просто соединить свои слова вместе с конвейерами, добавить их в механизм регулярных выражений и получить хорошую производительность.

Если это не сработает, вы можете создать регулярное выражение, которое кодирует дерево. Например, учитывая список foo, bar, baz, blat, регулярное выражение /\b(foo|b(?:a(?:r|z)|lat))\b/ должно соответствовать этим словам и только этим словам. Вероятно, он не будет делать это так же эффективно, как свернутый вручную C (например, на движке Perl вы столкнетесь с проверками медленных сложных регулярных выражений, и он, скорее всего, сделает несколько глупых возвратов, которые ему не нужны) ) но это будет на много меньше работы, чтобы собрать вместе.

Answer 3

1. Поместите ваши ключевые слова в структуру данных, которая позволяет легко искать. Например, хеш-таблица или двоичное дерево. Если вы хардкор, вы можете создать идеальный хеш из ваших ключевых слов.
2. Используйте DFA, чтобы разбить ввод на "слова". Это можно сделать с помощью библиотеки регулярных выражений или простого конечного автомата.
3. Посмотрите на каждое "слово", чтобы увидеть, является ли оно одним из ваших ключевых слов.