Какой самый быстрый алгоритм поиска подстроки?

Question

ОК, поэтому я не звучу как идиот, я собираюсь изложить проблему / требования более четко:

• Игла (шаблон) и стог сена (текст для поиска) - оба Cв стиле строки с нулевым символом в конце.Информация о длине не предоставляется;если необходимо, он должен быть вычислен.
• Функция должна возвращать указатель на первое совпадение, или NULL, если совпадение не найдено.
• Случаи сбоев не допускаются.Это означает, что любой алгоритм с непостоянными (или большими постоянными) требованиями к хранилищу должен иметь запасной вариант для сбоя выделения (и, следовательно, производительность в резервном режиме повышает производительность в худшем случае).Реализация должна быть на C, хотя хорошее описание алгоритма (или ссылки на него) без кода тоже подойдет.

... а также то, что я подразумеваю под "быстрым":

• Детерминистический O(n), где n = длина стога сена.(Но возможно использовать идеи из алгоритмов, которые обычно O(nm) (например, скользящий хеш), если они объединены с более надежным алгоритмом для получения детерминированных O(n) результатов).
• Никогда не выполняет(измеримо; пара часов для if (!needle[1]) и т. д. в порядке) хуже, чем алгоритм наивной грубой силы, особенно на очень коротких иглах, которые, вероятно, являются наиболее распространенным случаем.(Безусловные тяжелые накладные расходы на предварительную обработку - это плохо, так как пытаются улучшить линейный коэффициент для патологических игл за счет вероятных игл.)
• При произвольной игле и стоге сена сопоставимые или более высокие показатели (не хуже 50%больше времени поиска) по сравнению с любым другим широко реализованным алгоритмом.
• Помимо этих условий, я оставляю определение «самого быстрого» открытого типа.Хороший ответ должен объяснить, почему вы считаете подход, который вы предлагаете, «самым быстрым».

Моя текущая реализация работает примерно на 10% медленнее и в 8 раз быстрее (в зависимости от ввода), чем реализация glibcof Two-Way.

Обновление: Мой текущий оптимальный алгоритм выглядит следующим образом:

• Для игл длины 1 используйте strchr.
• Для игл длиной 2-4 используйте машинные слова, чтобы сравнить 2-4 байта одновременно следующим образом: предварительно загрузить иглу в 16- или 32-битном целом числе со смещением в битах и ​​зациклить старый байт / новые байты из стога сенана каждой итерации.Каждый байт стога сена читается ровно один раз и проверяется на 0 (конец строки) и одно 16- или 32-битное сравнение.
• Для игл длиной> 4 используйте двусторонний алгоритм сневерная таблица смещения (например, Бойера-Мура), которая применяется только к последнему байту окна.Чтобы избежать затрат на инициализацию таблицы размером 1 Кб, что может привести к чистым потерям для многих игл средней длины, я сохраняю битовый массив (32 байта), отмечающий, какие записи в таблице сдвига инициализированы.Биты, которые не установлены, соответствуют значениям байтов, которые никогда не появляются в игле, для которых возможен полный сдвиг длины иглы.

Большие вопросы, которые остались в моем уме:

• Есть ли способ лучше использовать таблицу плохих смен?Бойер-Мур лучше всего использует его, сканируя в обратном направлении (справа налево), но для двухстороннего сканирования требуется сканирование слева направо.
• Единственные два приемлемых алгоритма-кандидата, которые я нашел для общегорегистр (без условий памяти или квадратичной производительности): Двусторонняя и Строковое соответствие для упорядоченных алфавитов .Но есть ли легко обнаруживаемые случаи, когда разные алгоритмы были бы оптимальными?Конечно, многие из O(m) (где m - длина иглы) в космических алгоритмах могут быть использованы для m<100 или около того.Также было бы возможно использовать алгоритмы, которые являются наихудшими квадратичными, если есть простой тест для игл, которые, как доказано, требуют только линейного времени.

Бонусные баллы за:

• Можете ли вы улучшить производительность, если предположить, что игла и стог сена хорошо сформированы UTF-8? (С символами различной длины байтов правильная форма накладывает некоторые требования к выравниванию строк между иглой и стогом сена и допускает автоматические сдвиги в 2-4 байта, когда встречается несоответствующий главный байт. Но эти ограничения дают вам многое / что-либо помимо того вычисления максимального суффикса, хорошие сдвиги суффиксов и т. д. уже дают вам различные алгоритмы?)

Примечание: Я хорошо знаю большинство алгоритмов, только не то, насколько хорошо они работают на практике. Вот хороший справочник, чтобы люди не давали мне ссылки на алгоритмы в виде комментариев / ответов: http://www -igm.univ-mlv.fr / ~ lecroq / string / index.html

Answer 1

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

Бойер-Мур использует таблицу плохих символов с хорошей таблицей суффиксов.

Бойер-Мур-Хорспул использует таблицу неверных символов.

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

Рабин-Карп использует запущенные хэши.

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

Редактировать:

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

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

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

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

Если бы мне понадобился набор образцов, думаю, я бы очистил сайт, такой как Google или Википедия., а затем уберите HTML со всех страниц результатов.Для поискового сайта введите слово, а затем используйте одну из предложенных поисковых фраз.Выберите несколько разных языков, если это применимо.Используя веб-страницы, все тексты будут короткими и средними, поэтому объедините достаточно страниц, чтобы получить более длинные тексты.Вы также можете найти общедоступные книги, юридические записи и другие крупные текстовые материалы.Или просто генерировать случайный контент, выбирая слова из словаря.Но суть профилирования состоит в том, чтобы проверить тип контента, который вы будете искать, поэтому, если возможно, используйте примеры из реального мира.Что касается иглы, я думаю о коротком как до 8 символов, средний как до 64 символов, и длиной до 1 КБ.Для стога сена, я думаю, короткий как 2 ^ 10, средний как менее 2 ^ 20, и длиной до 2 ^ 30 символов.

Answer 2

Опубликованный в 2011 году, я полагаю, что это вполне может быть «Простое сопоставление строк в постоянном пространстве в реальном времени» , разработанный Дэни Бреслауэром, Роберто Гросси и Филиппо Миньоси.

Обновление:

В 2014 году авторы опубликовали это улучшение: На пути к оптимальному сопоставлению упакованных строк .

Answer 3

http://www -igm.univ-mlv.fr / ~ lecroq / string / index.html ссылка, на которую вы указываете, отличный источник и краткое изложение некоторых из самых известных и исследованных алгоритмы сопоставления строк.

Решения большинства проблем поиска включают Компромиссы в отношении затрат на предварительную обработку, времени и космические требования. Нет единого Алгоритм будет оптимальным или практичным во всех случаях.

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

Потратьте некоторое время на изучение конкретных сильных и слабых сторон алгоритмы, на которые вы уже ссылались. Провести обзор с целью найти набор алгоритмы, которые охватывают диапазон и область поиска строк вы интересует. Затем создайте внешний поисковый селектор на основе классификатора Функция для определения лучшего алгоритма для заданных входов. Таким образом, вы можете использовать самый эффективный алгоритм, чтобы сделать работу. Это особенно эффективен, когда алгоритм очень хорош для определенных поисков, но плохо ухудшается. За Например, грубая сила, вероятно, лучше всего подходит для игл длиной 1, но быстро уменьшается при увеличении длины иглы, после чего sustik-moore algoritim может стать более эффективным (для маленьких алфавитов), тогда для более длинных игл и больших алфавитов алгоритмы KMP или Бойера-Мура могут быть лучше. Это всего лишь примеры, иллюстрирующие возможную стратегию.

Многофункциональный подход не новая идея. Я считаю, что это было использовано несколькими коммерческие пакеты сортировки / поиска (например, SYNCSORT, обычно используемые на мэйнфреймах несколько алгоритмов сортировки и использует эвристику, чтобы выбрать «лучший» для заданных входных данных)

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

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

Answer 4

Я был удивлен, увидев наш технический отчет, цитируемый в этой дискуссии;Я один из авторов алгоритма, который был назван Сустик-Мур выше.(Мы не использовали этот термин в нашей статье.)

Я хотел бы здесь подчеркнуть, что для меня наиболее интересной особенностью алгоритма является то, что довольно просто доказать, что каждая буква проверяется не более одного раза.Для более ранних версий Бойера-Мура они доказали, что каждая буква рассматривается не более 3, а затем не более 2 раз, и эти доказательства были более сложными (см. Ссылки в статье).Поэтому я также вижу дидактическую ценность в представлении / изучении этого варианта.

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

Наша главная цель состояла в том, чтобы донести эту версию до сведения тех, кто может улучшить ее.Поиск по строкам имеет так много вариаций, и мы сами не можем придумать, где эта идея может принести пользу.(Фиксированный текст и изменение шаблона, фиксированный шаблон другого текста, предварительная обработка возможна / невозможна, параллельное выполнение, поиск подходящих подмножеств в больших текстах, допустимые ошибки, близкие совпадения и т. Д. И т. Д. И т. Д.)

Answer 5

Самый быстрый алгоритм поиска подстроки будет зависеть от контекста:

1. размер алфавита (например, ДНК против английского)
2. длина иглы

В статье 2010 года "Проблема точного сопоставления строк: комплексная экспериментальная оценка" приведены таблицы с временем выполнения для 51 алгоритма (с различными размерами алфавита и длиной иглы), поэтому вы можете выбрать лучший алгоритм для вашего контекст.

Все эти алгоритмы имеют реализации на C, а также набор тестов, здесь:

http://www.dmi.unict.it/~faro/smart/algorithms.php

Answer 6

Действительно хороший вопрос.Просто добавьте крошечные кусочки ...

1. Кто-то говорил о сопоставлении последовательности ДНК.Но для последовательности ДНК мы обычно строим структуру данных (например, массив суффиксов, дерево суффиксов или индекс FM) для стога сена и сопоставляем множество игл с ним.Это другой вопрос.

2. Было бы здорово, если бы кто-то захотел сравнить различные алгоритмы.Есть очень хорошие тесты для сжатия и построения массивов суффиксов, но я не видел тестов для сравнения строк.Потенциальные кандидаты в стог сена могут быть из теста SACA .

3. Несколько дней назад я тестировал реализацию Бойера-Мура со страницы, которую вы рекомендовали (РЕДАКТИРОВАТЬ: мне нужен вызов функции, такой как memmem (), но это не стандартная функция, поэтому я решил ее реализовать).Моя программа бенчмаркинга использует случайный стог сена.Похоже, что реализация Boyer-Moore на этой странице в разы быстрее, чем у glibc memmem () и Mac strnstr ().В случае, если вас это интересует, реализация будет здесь , а код тестирования - здесь .Это определенно не реалистичный тест, но это начало.

Answer 7

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

Answer 8

Недавно я обнаружил хороший инструмент для измерения производительности различных доступных алгоритмов: http://www.dmi.unict.it/~faro/smart/index.php

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

Answer 9

Вы можете реализовать, скажем, 4 разных алгоритма.Каждые М минут (которые будут определены опытным путем) запускают все 4 на текущих реальных данных.Накапливать статистику по N прогонов (также TBD).Затем используйте только победителя в течение следующих M минут.

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

Answer 10

Двусторонний алгоритм, который вы упоминаете в своем вопросе (который, кстати, невероятен!), Недавно был улучшен для эффективной работы с многобайтовыми словами за раз: Оптимальное сопоставление упакованных строк .

Я не читал всю статью, но кажется, что они полагаются на пару новых специальных инструкций ЦП (включенных, например, в SSE 4.2), обозначающих O (1), для их заявления о сложности времени, хотя, если они не если они доступны, они могут смоделировать их за O (log log w) для w-битных слов, что звучит не так уж плохо.