Файл заголовка «boyer_moore_horspool.hpp» содержит реализацию алгоритма поиска последовательностей значений Бойера-Мура-Хорспула.
Алгоритм поиска Boyer-Moore-Horspool был опубликован Найджелом Хорспулом в 1980 году. Это усовершенствованный алгоритм Бойера-Мура, который обменивает пространство на время. Он использует меньше места для внутренних таблиц, чем Бойер-Мур, и имеет худшую производительность.
Алгоритм Бойера-Мура-Хорспула нельзя использовать для сравнения с предикатами типа<std::search>.
Номенклатура: Я называю последовательность, которую ищут, «паттерном», а последовательность, которую ищут, — «корпусом».
Для гибкости алгоритм Бойера-Мура-Хорспула имеет два интерфейса: объектный и процедурный. Объектный интерфейс строит таблицы в конструкторе и использует оператор () для выполнения поиска. Процессуальный интерфейс создает таблицу и выполняет поиск всего за один шаг. Если вы собираетесь искать один и тот же шаблон в нескольких корпусах, то вы должны использовать интерфейс объекта и строить таблицы только один раз.
Вот интерфейс объекта:
template <typename patIter>
class boyer_moore_horspool {
public:
boyer_moore_horspool ( patIter first, patIter last );
~boyer_moore_horspool ();
template <typename corpusIter>
corpusIter operator () ( corpusIter corpus_first, corpusIter corpus_last );
};
Вот соответствующий процедурный интерфейс:
template <typename patIter, typename corpusIter>
corpusIter boyer_moore_horspool_search (
corpusIter corpus_first, corpusIter corpus_last,
patIter pat_first, patIter pat_last );
Каждая из функций передается двумя парами итераторов. Первые два определяют корпус, а вторые два определяют образец. Обратите внимание, что две пары не обязательно должны быть одного типа, но они должны «указать» на один и тот же тип.<patIter::value_type>и<curpusIter::value_type>должны быть одинаковыми.
Обратное значение функции — итератор, указывающий на начало рисунка в корпусе. Если образец не найден, он возвращает конец корпуса (<corpus_last>).
Время выполнения алгоритма Бойера-Мура-Хорспула является линейным по размеру искомой строки; оно может иметь значительно меньший постоянный фактор, чем многие другие алгоритмы поиска: для поиска не нужно проверять каждый символ строки, а скорее пропускать некоторые из них. Как правило, алгоритм становится быстрее, поскольку искомый шаблон становится длиннее. Его эффективность обусловлена тем, что при каждой неудачной попытке найти соответствие между строкой поиска и текстом, который он ищет, он использует информацию, полученную из этой попытки, чтобы исключить как можно больше позиций текста, где строка не может соответствовать.
Алгоритм представляет собой внутреннюю таблицу, которая имеет одну запись для каждого члена «алфавита» в шаблоне. Для (8-битных) типов символов эта таблица содержит 256 записей.
Наихудшая производительность -O(m x n), гдеm- длина рисунка иn- длина корпуса. Среднее времяO(n). Наилучшая производительность является сублинейной и, по сути, идентична Бойеру-Муру, но инициализация происходит быстрее, а внутренняя петля проще, чем у Бойера-Мура.
Как объектно-ориентированные, так и процедурные версии алгоритма Бойера-Мура-Хорспула берут свои параметры по значению и не используют никакой информации, кроме той, которая передается. Таким образом, оба интерфейса обеспечивают сильную гарантию исключения.
- При использовании интерфейса, основанного на объекте, шаблон должен оставаться неизменным во время поиска; то есть с момента создания объекта до окончательного вызова оператора () возвращается.
- Алгоритм Бойера-Мура-Хорспула требует итераторов случайного доступа как для шаблона, так и для корпуса.
Объект Boyer-Moore-Horspool принимает параметр шаблона черт, который позволяет абоненту настроить способ хранения предвычисленной таблицы. Эта таблица, называемая таблицей пропусков, содержит (логически) одну запись для каждого возможного значения, которое может содержать шаблон. При поиске 8-битных данных символов эта таблица содержит 256 элементов. Класс признаков определяет используемую таблицу.
Класс признаков по умолчанию использует<boost::array>для небольших «альфабетов» и<tr1::unordered_map>для более крупных. Таблица пропуска на основе массива дает отличную производительность, но может быть непомерно большой, когда растет «алфавит» элементов, подлежащих поиску. Неупорядоченная версия на основе карты только растет как количество уникальных элементов в шаблоне, но делает гораздо больше выделений кучи и дает более медленную производительность поиска.
Чтобы использовать другую таблицу пропусков, вы должны определить свой собственный объект таблицы пропусков и свой собственный класс признаков и использовать их для создания объекта Бойер-Мур-Хорспул. Интерфейс этих объектов описывается TBD.
