эффективный алгоритм поиска одной из нескольких строк в тексте?

Question

Мне нужно искать входящие не очень длинные фрагменты текста на предмет наличия заданных строк. Строки являются постоянными для всего сеанса и не много (~ 10). Дополнительным упрощением является то, что ни одна из строк не содержится ни в одной другой.

В настоящее время я использую сравнение с регулярным выражением с str1 | str2 | .... Выполнение этой задачи важно, поэтому мне интересно, смогу ли я ее улучшить. Не то чтобы я мог программировать лучше, чем ребята из Boost, но, возможно, выделенная реализация более эффективна, чем обычная.

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

например, если строки abcx, bcy и cz, и я уже прочитал abc, я должен быть в комбинированном состоянии, что означает you're either 3 chars into string 1, 2 chars into string 2 or 1 char into string 1. Затем чтение x next переведет меня в состояние string 1 matched и т. Д., И любой символ, кроме xyz, перейдет в исходное состояние, и мне не нужно будет возвращаться к b.

Любые идеи или ссылки приветствуются.

Answer 1

Ознакомьтесь с алгоритмом сопоставления строк Ахо-Корасика !

Answer 2

Взгляните на Суффикс-дерево .

Answer 3

Посмотрите на это: http://www.boost.org/doc/libs/1_44_0/libs/regex/doc/html/boost_regex/configuration/algorithm.html

Существование рекурсивного / нерекурсивного различия - довольно убедительное предположение, что BOOST не обязательно является машиной с конечным состоянием в линейном времени. Поэтому есть большая вероятность, что вы сможете добиться большего успеха в своей конкретной проблеме.

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

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

Рабин-Карп создает DFSM из строки (или строк), для которой вы ищете, чтобы тест и движение курсора были объединены в одну операцию. Тем не менее, Rabin-Karp изначально был разработан для одной иглы, поэтому вам нужно будет поддерживать возврат назад, если одно совпадение когда-либо будет правильным префиксом другого. (Помните, что когда вы хотите повторно использовать свой код.)

Другая тактика - сдвинуть курсор более чем на один символ вправо, если это вообще возможно. Бойер-Мур делает это. Обычно он построен для одной иглы. Составьте таблицу всех символов и крайнюю правую позицию, в которой они появляются в игле (если вообще). Теперь установите курсор на len (иглу) -1. Запись в таблице скажет вам (а), какое смещение влево от курсора, что может быть найдена игла, или (б) что вы можете переместить курсор len (игла) дальше вправо.

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

Еще одна тактика - проверять более 8 бит одновременно. Существует инструмент для борьбы со спамом, который просматривает 32-битные машинные слова одновременно. Затем он выполняет некоторый простой хэш-код для подгонки результата к 12 битам, а затем просматривает таблицу, чтобы увидеть, есть ли совпадение. У вас есть четыре записи для каждого шаблона (смещения 0, 1, 2 и 3 от начала шаблона), и затем, несмотря на тысячи шаблонов в таблице, они проверяют только один или два на 32-битное слово в теме линия.

В общем, да, вы можете работать быстрее, чем регулярные выражения, КОГДА ИГЛЫ ПОСТОЯННЫ.

Answer 4

Я смотрю на ответы, но ни один из них не кажется достаточно явным ... и в основном сводится к паре ссылок.

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

Я бы наверняка взглянул на KMP / Boyer Moore, но я бы не стал применять их вслепую (по крайней мере, если у вас есть какое-то время на руке), потому что они предназначены для одной иглы, и я довольно убедившись, что мы можем извлечь выгоду из того факта, что у нас есть несколько строк, и проверить их все одновременно с помощью пользовательского автомата (или пользовательских таблиц для BM).

Конечно, вряд ли улучшится большой О (Бойер Мур работает по 3n для каждой строки, так что в любом случае он будет линейным), но вы, вероятно, могли бы выиграть от постоянного фактора.

Answer 5

Вы можете сделать это с помощью очень популярных инструментов Lex & Yacc, с поддержкой инструментов Flex и Bison. Вы можете использовать Lex для получения токенов строки. Сравните ваши предопределенные строки с токенами, возвращенными из Lexer. Когда совпадение найдено, выполните желаемое действие. Есть много сайтов, которые рассказывают о Lex и Yacc. Один из таких сайтов http://epaperpress.com/lexandyacc/

Answer 6

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

Answer 7

Всегда есть Бойер Мур

Answer 8

Ожидается, что инициализация движка Regex будет иметь некоторые накладные расходы, так что если нет регулярных выражений real , C - memcmp () должен делать хорошо.

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

Интересно: исследования memcmp и различия во времени

Привет

БВУ