Алгоритм для нахождения нескольких строковых соответствий

Предполагая, что большая часть текста представляет собой статический английский текст, и вам нужно сопоставить целые слова, вы можете попробовать следующее (вам действительно следует уточнить, что именно является «совпадением», какой текст вы просматриваете и т. Д. В вашем вопрос).

Сначала предварительно обработайте весь документ в Trie или DAWG .

Trie / Dawg имеет следующее свойство:

Учитывая trie / dawg и условие поиска длиной K, вы можете за время O (K) искать данные, связанные со словом (или определить, нет ли совпадения ).

Использование DAWG может сэкономить больше места по сравнению с деревом. Попытки используют тот факт, что многие слова имеют общий префикс, а DAWG используют общий префикс, а также свойство общего суффикса.

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

That is that and so it is.

, узел для последнего t в , что будет иметь список {1,3}, а узел для s в будет иметь список { 2,7} связанный.

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

Если вы получили запрос, состоящий из нескольких слов, вы можете сделать следующее.

Найдите первое слово в поисковом запросе. Получите список совпадений и вставьте в хэш-таблицу H1.

Теперь пройдитесь по дереву со вторым словом в поисковом запросе. Получите список совпадений. Для каждой позиции совпадения x проверьте, существует ли x-1 в HashTable H1. Если это так, добавьте x в новую хеш-таблицу H2.

Пройдите по дереву с третьим словом, получите список совпадений.Для каждой позиции совпадения y проверьте, существует ли y-1 в H3, если да, добавьте в новую хеш-таблицу H3.

Продолжайте так далее.

В конце вы получаете список совпадений для поисковой фразы, в котором указываются позиции последнего слова фразы.

Вы можете потенциально оптимизировать этап сопоставления фраз, поддерживая отсортированный список позиций в списке и выполняя бинарный поиск: например, например. для каждого ключа k в H2 вы выполняете двоичный поиск k + 1 в отсортированном списке для поискового запроса 3 и добавляете k + 1 к H3, если найдете его и т. д.

Значит, у вас много поисковых запросов и вы хотите посмотреть, есть ли какие-либо из них в документе?

Чисто алгоритмически вы можете отсортировать все свои возможности в алфавитном порядке, присоединяйтесь их с конвейерами, и использовать их как регулярное выражение, если механизм регулярных выражений посмотрит на / ant | ape / и правильно закоротит a в "ape", если он не нашел его в " муравей". Если нет, вы можете выполнить «предварительную компиляцию» регулярного выражения и «сжать» результаты до минимального перекрытия. Т.е.в приведенном выше случае / a (nt | pe) / и так далее, рекурсивно для каждой буквы.

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

Вы можете сделать это с вашими поисковыми запросами, чтобы сделать сверхбыструю формулировку "соответствует ли это слово чему-либо в моем списке поисковых запросов", если количество ваших поисковых запросов велико.

Теоретически вы можете сделать и обратное - упаковать документ в дерево, а затем использовать в нем условия поиска - если ваш документ статичен и условия поиска сильно меняются.

Зависит от того, сколько вам нужно оптимизации ...

Это слова из поисковых запросов, которые вы ищете, или это тоже могут быть полные сообщения?

Если это только слова, то я бы предложил построить Красно-Черное дерево из всех слов, а затем поиск каждого слова в дереве.

Если бы это могло быть послание, тогда это могло бы быть намного сложнее ... (?)

Оптимальным решением этой проблемы является использование дерева суффиксов (или массива суффиксов ). По сути, это дерево всех суффиксов строки. Для текста длиной O (N) это может быть построено в O (N) .

Тогда на все k вхождений строки длиной m можно оптимально ответить в O (m + k) .

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

Это типичная структура данных, которая используется при анализе строк ДНК, длина которых может составлять миллионы / миллиарды оснований.

См. Также

• Википедия / Суффиксное дерево
• Алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология (Дэн Гасфилд).