Сдвиг плохого символа, используемый в алгоритме Боуера - Мура, не очень эффективен для маленького алфавита, но, когда размер алфавита большой по сравнению с длиной образца, как это часто имеет место с

таблицей ASCII и при обычном поиске в текстовом редакторе, он становится чрезвычайно полезен. Использование в алгоритме только его одного может быть весьма эффективным.

После попытки совмещения x и y [i, i+m-1], длина сдвига - не менее 1. Таким образом, символ y [ i + m ] обязательно будет вовлечен в следующую попытку, а значит, может быть использован в текущей попытке для сдвига плохого символа. Модифицируем функцию плохого символа, чтобы принять в расчет последний символ х:

bc[ a ] = min j , если a встречается в x,

bc[ a ] = m в противоположном случае.

Сравнения текста и образца могут производиться в любом порядке.

Турбо БМ (Классификация Thierry Lecroq [2]).

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

Это даст нам два преимущества:

1. Возможность перескочить через этот сегмент

2. Возможность применения «турбо - сдвига»

«Турбо - сдвиг» может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.

Пусть u - запомненный сегмент, а v - cуффикс, совпавший во время текущей попытки, такой что uzv - суффикс x. Тогда av - суффикс x, два символа а и b встречаются на расстоянии p в тексте, и суффикс x длины |uzv| имеет период длины p, а значит не может перекрыть оба появления символов а и b в тексте. Наименьший возможный сдвиг имеет длину |u| - |v| ( его мы и называем «турбо - сдвигом» ).

1.5. Поиск подстрок с помощью конечного автомата.

1.5.1. Структура автомата.

По определению, конечный автомат представляет собой пятерку М = (Q, q0, A, , ), где:

Q -- конечное множество состояний;

q0Q -- начальное состояние;

АQ -- конечное множество допускающих состояний;

-- конечный входной алфавит;

-- функция Q х Q, называемая функцией переходов автомата.

Первоначально конечный автомат находится в состоянии q0. Затем он по очереди читает символы из входной строки. Находясь в состоянии q и читая символ а, автомат переходит в состояние (q,a). Если автомат находится в состоянии q A говорят, что он допускает прочитанную часть входной строки. Если q А, то прочитанная часть строки отвергнута.

С конечным состоянием М связана функция , называемая функцией конечного состояния, определяемая следующим образом: есть состояние, в которое придет автомат (из начального состояния), прочитав строку w. Автомат допускает строку w тогда и только тогда, когда А

Для каждого образца Р можно построить конечный автомат, ищущий этот образец в тексте. Первым шагом в построении автомата, соответствующего строке-образцу Р[1..m], является построение по Р вспомогательной суффикс-функциии (как в алгоритме КМП). Теперь определим конечный автомат, соответствующий образцу Р[1..m], следующим образом:

· Его множество состояний Q = {0,1,..., m}. Начальное состояние q0 = 0. Единственное допускающее состояние m;

· Функция переходов определена соотношением (q -- состояние, -- символ): (q,a) = (Pqa). (1)

Поясним это соотношение. Требуется сконструировать автомат таким образом, чтобы при его действии на строку Т соотношение

(Тi) = (Тi)

являлось инвариантом (тогда равенство (Тi) = m будет равносильно тому, что Р входит в Т со сдвигом i -- m, и автомат тем самым найдет все допустимые сдвиги). Однако в этом случае вычисление перехода по формуле (1) необходимо для поддержания истинности инварианта, что следует из теорем, приведенных ниже.[3]

Теорема. Пусть q = (х), где х -- строка. Тогда для любого символа а имеет место (ха) = (Pqa).

Теорема. Пусть -- функция конечного состояния автомата для поиска подстроки Р[1.. m]. Если Т[1.. n] -- произвольный текст, то (Тi) = (Тi) для i=0,1,..., n. [14]

Из изложенного следует, что задача поиска подстроки состоит из двух частей:

построение автомата по образцу (определение функции переходов для заданного образца);

применение этого автомата для поиска вхождений образца в заданный текст.

1.5.2. Пример построения конечного автомата

Построим конечный автомат, допускающий строку ababaca. Поскольку длина образца m = 7 символов, то в автомате будет m + 1 = 8 состояний.

Найдем функцию переходов . В соответствии с определением (1), (q, a) =(Рqа), где -- префикс-функция, а -- произвольный символ из алфавита , q -- номер состояния. Таким образом, необходимо для каждого префикса Pq = P[0..q], q = 0 .. m образца Р и для всех символов а входного алфавита найти длину максимального префикса Р, который будет являться суффиксом строки Рqа. Длина этого префикса и будет значением функции переходов (q,a). Если а = P[q + 1] (очередной символ текста совпал со следующим символом образца), то Рqа = Рq+1 и (q, a) = q+1.

Такой случай соответствует успешным этапам поиска. Иначе, (q,a)q. Например, для префикса Р[0..5] = ababa и символа b максимальным суффиксом строки Р[0..5]b=ababab, который одновременно является префиксом Р, будет abab. Его длина равна 4, поэтому значение функции переходов (5, b) = 4.

Запишем построенную таким образом функцию переходов в виде таблицы (Табл. 1):

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

Построим по таблице граф переходов автомата (Рис. 1), распознающего образец ababaca. Находясь в состоянии q и прочитав очередной символ а, автомат переходит в состояние (q,a). Обратим внимание, что его остов помечен символами образца (эти переходы выделены жирными стрелками).

Здесь 0 -- исходное состояние, 7 -- единственное допускающее состояние (зачернено). Если из вершины i в вершину j ведет стрелка, помеченная буквой а, то это означает, что (i,a) = j. Отметим, что переходы, для которых (i,a) = 0, на графе переходов для его упрощения не обозначены. Жирные стрелки, идущие слева направо, соответствуют успешным этапам поиска подстроки Р -- следующий входной символ совпадает с очередным символом образца. Стрелки, идущие справа налево, соответствуют неудачам -- следующий входной символ отличается от очередного символа образца.

Ниже приведен результат применения автомата к тексту Т = abababacaba. Под каждым символом Т[г] записано состояние автомата после прочтения этого символа (иными словами, значение (Тi)) (Табл. 2).

Найдено одно вхождение образца (начиная с позиции 3). Найденный образец в тексте помечен серым цветом. Черным цветом помечено допускающее состояние автомата (состояние с номером 7).

Часть 2. Экспериментальный анализ алгоритмов.

Имеется несколько текстовых файлов, содержащих 10000 записей вида:
строка
подстрока (имеющаяся в данной строке)
место вхождения
длина подстроки

с разными максимальными длинами строк и подстрок.

Алфавитом является 66 русских заглавных и строчных букв.

Пусть это будут строки длиной не более 10, 100, 250 символов.

Проведем поиск подстрок в строках для каждого из алгоритмов и измерим время работы программы. При этом будем учитывать следующее:

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

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

Стенд для эксперимента.

Процессор Intel Pentium IV 2,66Ггц

1024 Мб ОЗУ

Компилятор Borland Delphi Enterprise, version 6.0 (Build 6.163)

Фрагмент кода тестируемой программы приведем в листинге 7.

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

2.2. Результаты и анализ эксперимента.

Результаты эксперимента занесем в таблицу (Табл. 3).

Как и предполагалось, алгоритм Бойера - Мура справился с экспериментальной задачей быстрее остальных. Следует, однако, заметить, что его эффективность растет лишь с увеличением длины строки и, соответственно, длины образца. Так при длине строки меньшей или равной 10 символов, он показал себя хуже, чем последовательный поиск. Аналогичные результаты показывает и алгоритм КМП, как для коротких, так и для длинных слов. Его можно использовать как универсальный, когда неизвестны длины строки и образца.

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

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

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

Заключение.