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

Question

Я ищу предложения для эффективного алгоритма поиска всех совпадений в большом тексте.Термины для поиска будут содержаться в списке и могут иметь более 1000 возможностей.Поисковые термины могут содержать 1 или более слов.

Очевидно, я мог бы сделать несколько проходов по тексту, сравнивая их с каждым поисковым термином.Не слишком эффективно.

Я думал об упорядочении поисковых терминов и объединении общих подсегментов.Таким образом, я мог быстро устранить большое количество терминов.Язык C ++, и я могу использовать boost.

Примером поисковых терминов может быть список названий компаний из списка Fortune 500.

Идеи?

Answer 1

Не изобретайте велосипед

Эта проблема интенсивно исследовалась.Любопытно, что лучшие алгоритмы поиска ОДНОГО шаблона / строки нелегко экстраполируются на сопоставление нескольких строк.

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

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

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

That is that and so it is.

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

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

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

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

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

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

Продолжите и т. Д.

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

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

Answer 4

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

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

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

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

См. также

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

Answer 5

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

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

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

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

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

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

Answer 6

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

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

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