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

Question

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

Answer 2

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

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

Интересно: memcmp explorations и timing differences

С уважением

БВУ

Answer 3

Посмотрите на Suffix Tree.

Answer 4

Существует всегда Boyer Moore

Answer 5

Кроме Рабин-Карп-алгоритм и Кнут-Моррис-Пратта-алгоритм, мой алгоритм книга предлагает Finite State Machine для струнного Matching. Для каждой строки поиска вам нужно построить такую ​​машину конечного состояния.

Answer 6

Проверьте Aho–Corasick string matching algorithm!

Answer 7

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

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

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

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

Answer 8

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