Вы когда-нибудь использовали алгоритмы KMP или BM?

Question

Я знаю, что алгоритмы KMP (Кнут-Моррис-Пратт) и BM (Бойерс-Мур) являются хорошими алгоритмами поиска строк. Я также знаю, что BM в 3-5 раз быстрее, чем KMP.

В своем опыте программирования для промышленного программного обеспечения вы когда-нибудь использовали алгоритмы BM или KMP? Здесь действительно имеет значение алгоритм?

Answer 1

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

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

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

На мой взгляд, эти алгоритмы довольно академичны и полезны только при особых обстоятельствах.

Answer 2

Функция

glibc strstr является линейной. Он использует Двусторонний алгоритм , который я считаю вариантом Бойера-Мура. Итак, я полагаю, что любой, кто использует strstr в gcc, на самом деле использует быстрый алгоритм поиска строк в реальном мире.

Что касается вопроса о том, имеет ли значение быстрый алгоритм, ИМХО это имеет значение, только если размер данных достаточно велик. Многие явные строковые операции, которые мы выполняем, выполняются на очень маленьких строках (скажем, менее 500 символов). Это не означает, что мы не выполняем тяжелые строковые операции (например, полнотекстовый поиск в базе данных), но в этом случае мы обычно позволяем базе данных или библиотеке выполнять тяжелую работу за нас. База данных или библиотека использует быстрые алгоритмы поиска строк - поэтому я бы не сказал, что они не имеют значения, только то, что их использование не видно нам напрямую.

Answer 3

Я однажды внедрил KMP на аппаратном уровне. Если аппаратное обеспечение представляет собой ПЛИС, вы можете использовать реконфигурируемость, чтобы иметь и самоизменяющуюся схему. Эта схема получает строку поиска. Чем сделать необходимое предварительное преобразование в аппаратных средствах и перенастроить себя на логику, которая делает KMP. Но и здесь необходимо, чтобы вам приходилось сканировать большое количество данных, чтобы ускорить процесс, но в некоторых случаях это было так (например, сопоставление ДНК).