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

Ответ 1

Не изобретайте колесо

Эта проблема интенсивно изучается. Любопытно, что лучшие алгоритмы поиска ONE pattern/string не экстраполируют легко на многострочное сопоставление.

Семейство "grep" реализует многострочный поиск очень эффективным способом. Если вы можете использовать их в качестве внешних программ, сделайте это.

Если вам действительно нужно реализовать алгоритм, я думаю, что самый быстрый способ - воспроизвести то, что делает agrep (agrep превосходит в многострочном сопоставлении!). Здесь являются исходными и исполняемыми файлами.

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

Заметка: многопоточное сопоставление было в значительной степени исследовано такими людьми, как Кнут, Бойер, Мур, Баэза-Йейтс и другие. Если вам нужен очень быстрый алгоритм, не стесняйтесь стоять на широких плечах. Не изобретайте велосипед.

Ответ 2

Как и в случае с одиночными шаблонами, существует несколько алгоритмов для сопоставления нескольких шаблонов, и вам нужно будет найти тот, который лучше всего подходит для вашей цели. В документе Быстрый алгоритм для многократного поиска (архивная копия) содержит обзор большинства из них, включая Aho-Corasick (который является своего рода мульти-шаблонная версия алгоритма Кнута-Морриса-Пратта с линейной сложностью) и Commentz-Walter (комбинация Бойер-Мура и Ахо-Корасика) и представляет новую, которая использует идеи Бойер-Мура для задача сопоставления нескольких шаблонов.

Альтернативным алгоритмом, основанным на хеше, не упомянутым в этой статье, является алгоритм Rabin-Karp, который имеет худшую сложность чем другие алгоритмы, но компенсирует это, уменьшая линейный коэффициент посредством хеширования. Какой из них лучше зависит, в конечном счете, от вашего прецедента. Возможно, вам придется реализовать несколько из них и сравнить их в своем приложении, если вы хотите выбрать самый быстрый.

Ответ 3

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

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

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

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

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

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

That is that and so it is.

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

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

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

Пройдите три с первым словом в поисковом выражении. Получите список совпадений и вставьте в hashTable H1.

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

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

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

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

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

Ответ 4

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

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

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

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

См. также

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

Ответ 5

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

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

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

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

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

В зависимости от того, какая оптимизация вам нужна...

Ответ 6

Являются ли слова поисковых терминов, которые вы ищете, или могут ли они быть полными датами?

Если это только слова, я бы предложил создать Red-Black Tree из всех слов, а затем искать каждое слово в дерево.

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