Файл заголовка «boyer_moore.hpp» содержит реализацию алгоритма Бойера-Мура для поиска последовательностей значений.
Алгоритм поиска строк Boyer–Moore является особенно эффективным алгоритмом поиска строк, и он был стандартным эталоном для практической литературы поиска строк. Алгоритм Бойера-Мура был изобретен Бобом Бойером и Дж.Стротером Муром и опубликован в октябре 1977 года в выпуске Communications of the ACM, и копия этой статьи доступна по адресуhttp://www.cs.utexas.edu/~moore/publications/fstrpos.pdf.
Алгоритм Бойера-Мура использует две предварительно вычисленные таблицы, чтобы обеспечить лучшую производительность, чем наивный поиск. Эти таблицы зависят от искомого шаблона и дают алгоритму Бойера-Мура больший объем памяти и затраты на запуск, чем более простой алгоритм, но эти затраты быстро восстанавливаются во время процесса поиска, особенно если шаблон длиннее нескольких элементов.
Однако алгоритм Бойера-Мура нельзя использовать для сравнения с предикатами типа<std::search>.
Номенклатура: Я называю последовательность, которую ищут, «паттерном», а последовательность, которую ищут, — «корпусом».
Для гибкости алгоритм Бойера-Мура имеет два интерфейса: объектный и процедурный. Объектный интерфейс строит таблицы в конструкторе и использует оператор () для выполнения поиска. Процессуальный интерфейс создает таблицу и выполняет поиск всего за один шаг. Если вы собираетесь искать один и тот же шаблон в нескольких корпусах, то вы должны использовать интерфейс объекта и строить таблицы только один раз.
Вот интерфейс объекта:
template <typename patIter>
class boyer_moore {
public:
boyer_moore ( patIter first, patIter last );
~boyer_moore ();
template <typename corpusIter>
corpusIter operator () ( corpusIter corpus_first, corpusIter corpus_last );
};
Вот соответствующий процедурный интерфейс:
template <typename patIter, typename corpusIter>
corpusIter boyer_moore_search (
corpusIter corpus_first, corpusIter corpus_last,
patIter pat_first, patIter pat_last );
Каждая из функций передается двумя парами итераторов. Первые два определяют корпус, а вторые два определяют образец. Обратите внимание, что две пары не обязательно должны быть одного типа, но они должны «указать» на один и тот же тип.<patIter::value_type>и<curpusIter::value_type>должны быть одинаковыми.
Обратное значение функции — итератор, указывающий на начало рисунка в корпусе. Если образец не найден, он возвращает конец корпуса (<corpus_last>).
Время выполнения алгоритма Бойера-Мура, хотя и линейное по размеру строки поиска, может иметь значительно меньший постоянный фактор, чем многие другие алгоритмы поиска: для поиска не нужно проверять каждый символ строки, а скорее пропускать некоторые из них. Как правило, алгоритм становится быстрее, поскольку искомый шаблон становится длиннее. Его эффективность обусловлена тем, что при каждой неудачной попытке найти соответствие между поисковой строкой и текстом, который он ищет, он использует информацию, полученную из этой попытки, чтобы исключить как можно больше позиций текста, где строка не может соответствовать.
Алгоритм выделяет две внутренние таблицы. Первый пропорционален длине рисунка; второй имеет одну запись для каждого члена «алфавита» в рисунке. Для (8-битных) типов символов эта таблица содержит 256 записей.
Наихудшая производительность для поиска шаблона в корпусе —O(N)(линейное) время; то есть пропорционально длине исследуемого корпуса. В общем, поиск сублинейный; не каждую запись в корпусе нужно проверять.
Как объектно-ориентированные, так и процедурные версии алгоритма Бойера-Мура берут свои параметры по значению и не используют никакой информации, кроме той, что передается. Таким образом, оба интерфейса обеспечивают сильную гарантию исключения.
- При использовании интерфейса, основанного на объекте, шаблон должен оставаться неизменным во время поиска; то есть с момента создания объекта до окончательного вызова оператора () возвращается.
- Алгоритм Бойера-Мура требует итераторов случайного доступа как для шаблона, так и для корпуса.
Объект Бойера-Мура принимает параметр шаблона черт, который позволяет абоненту настроить, как хранится одна из предварительно вычисленных таблиц. Эта таблица, называемая таблицей пропусков, содержит (логически) одну запись для каждого возможного значения, которое может содержать шаблон. При поиске 8-битных данных символов эта таблица содержит 256 элементов. Класс признаков определяет используемую таблицу.
Класс признаков по умолчанию использует<boost::array>для небольших «альфабетов» и<tr1::unordered_map>для более крупных. Таблица пропуска на основе массива дает отличную производительность, но может быть непомерно большой, когда растет «алфавит» элементов, подлежащих поиску. Неупорядоченная версия на основе карты только растет как количество уникальных элементов в шаблоне, но делает гораздо больше выделений кучи и дает более медленную производительность поиска.
Чтобы использовать другую таблицу пропусков, вы должны определить свой собственный объект таблицы пропусков и свой собственный класс признаков и использовать их для создания объекта Бойера-Мура. Интерфейс этих объектов описывается TBD.
