Абстрактный автомат Мили
Абстрактный синтез 1. Выбор количества триггеров. Так как автомат имеет 5 состояний, то требуется q=]log25[=3 триггера. 2. Кодирование внутренних состояний входных...
Алгоритмы поиска подстроки в строке
Построим конечный автомат, допускающий строку ababaca. Поскольку длина образца m = 7 символов, то в автомате будет m + 1 = 8 состояний. Найдем функцию переходов. В соответствии с определением (1), (q, a) =(Рqа), где -- префикс-функция...
Лексический и синтаксический анализатор языка высокого уровня
Управляющая таблица лексического анализатора для заданной выше грамматики показана в таблице 2. Листинг программы, реализующей данную управляющую таблицу, приведен в приложении А...
Лисп-реализация конечных автоматов
Конечный автомат - в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии...
Поиск информации в Интернет
Конечный автомат - абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию. Существуют различные варианты задания конечного автомата. Например...
Применение автоматного программирования в жизненной практике
Автоматы удобно описывать с помощью таблиц, а для наглядности использовать графы. При табличном описании задают две таблицы...
Синтез конечного автомата для устройства управления ЭВМ
Обобщенная структурная схема конечного автомата КА (рис.1) содержит запоминающее устройство ЗУ (память на триггерах Т1-Тn) и два комбинационных устройства КУ для формирования сигналов q1, q2,......
Недетерминированный конечный автомат это пятерка A=(Q,V,М,S,Z), где Q - множество (алфавит) внутренних состояний; V - входной алфавит; М - функция переходов...
Синтез конечного распознающего автомата
Детерминированный конечный автомат это пятерка А=(Q,V,М,S,Z), где Q - алфавит состояний; V - входной алфавит; М - функция переходов (Q*VР(Q)); S - начальное состояние; Z - множество заключительных состояний; SZ. В этом автомате...
Синтез конечного распознающего автомата
Программа, моделирующая работу конечного автомата, обеспечивает различение допускаемых и не допускаемых цепочек. Цепочки символов вводятся с клавиатуры компьютера, программа различения цепочек имеет как автоматический...
Процедуру построения недетерминированного автомата по автоматной грамматике: 1. Входным множеством автомата будет терминальное множество грамматики; 2. Множеством состояний автомата будет нетерминальное множество грамматики...
Синтез распознающего автомата
Процедура перехода от недетерминированного автомата к детерминированному: Обозначения: АД - детерминированный автомат АН - недетерминированный автомат 1...
Табличный метод структурного синтеза конечных автоматов
Для задания конечного автомата S необходимо задавать совокупность из пяти объектов: S (A, X, Y, d, d), где A = {a0,a1,a2,.,an} - множество внутренних состояний автомата, X = {x1, x2,…, xm} - множество входных сигналов (входной алфавит), Xi буква входного алфавита, Y = {y1, y2...
Эквивалентность и минимизация конечных автоматов
Разные конечные автоматы могут функционировать одинаково, даже если у них разное число состояний. Важной задачей является нахождение минимального конечного автомата, который реализует заданное автоматное отображение ...
Поиск нескольких минимумов на отрезке.
0. Если требуется получать сразу несколько минимумов по отрезку (всегда nминимумов на отрезке) – делаем дерево отрезков с функцией нахождения этих нескольких минимумов (но придется делать kсравнений èв kраз усложняет время)
1. Альтернатива
Надо найти kминимумов. Находим по RMQ – индекс первого. Потом запускаем RMQна подмассивах, на которые делится наш массив найденным индексом. Так найдем уже 3 минимума. И т.д. (на 4 подмассивах и т.д.)
Поиск подстроки в строке.
Имеются строки и такие, что и элементы этих строк символы из конечного алфавита . Говорят, что строка встречается в строке со сдвигом , если и 
= . Если строка встречается в строке , то является подстрокой . Требуется проверить, является ли строка подстрокой .
В задачах поиска традиционно принято обозначать шаблон поиска как needle а строку, в которой ведётся поиск - как haystack . Также обозначим через Σ алфавит, на котором проводится поиск.
For i=0...|haystack|-|needle|for j=1...|needle|if haystack<>needle[j] then goto 1output("Найдено: ", i+1)1:
Простейший алгоритм поиска даже в лучшем случае проводит |haystack |−|needle |+1 сравнение; если же есть много частичных совпадений, скорость снижается до O (|haystack |·|needle |).
Показано, что примитивный алгоритм отрабатывает в среднем 2h сравнений
Метод хеширования
Для решения задачи удобно использовать полиномиальный хеш, так его легко пересчитывать: , где - это некоторое простое число, а - некоторое большое число, для уменьшения числа коллизий (обычно берётся или , чтобы модуль брался автоматически при переполнении типов). Стоит обратить внимание, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны.
При удалении первого символа строки и добавлении символа в конец считать хеш новой строки при помощи хеша изначальной строки возможно за :
Получается: .
Следует учесть, что при получении отрицательного значения необходимо прибавить .
Алгоритм
Алгоритм начинается с подсчета и .
Для вычисляется и сравнивается с . Если они оказались равны, то образец содержится содержится в строке , начиная с позиции , но в этом случае возможны ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вообще, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в наивном алгоритме поиска подстроки в строке. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания останется хоть и небольшая, во втором случае проверка займет время равное длине образца, но исключит возможность ложного срабатывания.
Для ускорения работы алгоритма оптимально предпосчитать .
Если шаблон большой, нет большого увеличения по времени. Каждый шаг цикла не зависит от остальных (распараллеливание)
Время работы
Изначальный подсчёт хешей выполняется за . В цикле всего итераций, каждая выполняется за . Итоговое время работы алгоритма .
RabinKarp (s, p)
hp = hash(p)
h = hash(s)
for i = 1 to n - m + 1
if h == hp
h = (p * h - p * hash(s[i]) + hash(s)) mod r
if h < 0
if answer.size() == 0
return not found
return answer
Конечный автомат - абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.
Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: , где:
· Q - множество состояний автомата;
· q 0 - начальное (стартовое) состояние автомата ();
· F - множество заключительных (или допускающих ) состояний, таких что ;
· Σ - допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;
· δ - заданное отображение множества во множество подмножеств Q:
(иногда δ называют функцией переходов автомата ).
Автомат начинает работу в состоянии q 0 , считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».
Через конечный автомат работают Ахо-Корасик, Бойер-Мур и Укконенн
Алгоритм Бойера-Мура
1. Сканирование слева направо, сравнение справа налево. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.
Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.
Эти «несколько», упомянутые в предыдущем абзаце, вычисляются по двум эвристикам.
2. Эвристика стоп-символа. Предположим, что мы производим поиск слова «колокол». Первая же буква не совпала - «к» (назовём эту букву стоп-символом ). Тогда можно сдвинуть шаблон вправо до последней буквы «к».
Строка: * * * * * * к * * * * * *Шаблон: к о л о к о лСледующий шаг: к о л о к о л
Если стоп-символа в шаблоне вообще нет, шаблон смещается за этот стоп-символ.
Строка: * * * * * а л * * * * * * * *Шаблон: к о л о к о лСледующий шаг: к о л о к о л
В данном случае стоп-символ - «а», и шаблон сдвигается так, чтобы он оказался прямо за этой буквой. В алгоритме Бойера-Мура эвристика стоп-символа вообще не смотрит на совпавший суффикс (см. ниже), так что первая буква шаблона («к») окажется под «л», и будет проведена одна заведомо холостая проверка.
Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает.
Строка: * * * * к к о л * * * * *Шаблон: к о л о к о лСледующий шаг: к о л о к о л?????
В таких ситуациях выручает третья идея АБМ - эвристика совпавшего суффикса.
3. Эвристика совпавшего суффикса. Если при сравнении строки и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал.
Строка: * * т о к о л * * * * *Шаблон: к о л о к о лСледующий шаг: к о л о к о л
В данном случае совпал суффикс «окол», и шаблон сдвигается вправо до ближайшего «окол». Если подстроки «окол» в шаблоне больше нет, но он начинается на «кол», сдвигается до «кол», и т. д.
Обе эвристики требуют предварительных вычислений - в зависимости от шаблона поиска заполняются две таблицы. Таблица стоп-символов по размеру соответствует алфавиту (например, если алфавит состоит из 256 символов, то её длина 256); таблица суффиксов - искомому шаблону. Именно из-за этого алгоритм Бойера-Мура не учитывает совпавший суффикс и несовпавший символ одновременно - это потребовало бы слишком много предварительных вычислений.
Опишем подробнее обе таблицы.
Таблица стоп-символов
В таблице стоп-символов указывается последняя позиция в needle (исключая последнюю букву ) каждого из символов алфавита. Для всех символов, не вошедших в needle, пишем 0 (для нумерации с 0 - соответственно, −1). Например, если needle=«abcdadcd», таблица стоп-символов будет выглядеть так.
Символ a b c d [все остальные]Последняя позиция 5 2 7 6 0
Обратите внимание, для стоп-символа «d» последняя позиция будет 6, а не 8 - последняя буква не учитывается. Это известная ошибка, приводящая к неоптимальности. Для АБМ она не фатальна («вытягивает» эвристика суффикса), но фатальна для упрощённой версии АБМ - алгоритма Хорспула.
Если несовпадение произошло на позиции i, а стоп-символ c, то сдвиг будет i-StopTable[c].
Таблица суффиксов
Для каждого возможного суффикса S шаблона needle указываем наименьшую величину, на которую нужно сдвинуть вправо шаблон, чтобы он снова совпал с S . Если такой сдвиг невозможен, ставится |needle | (в обеих системах нумерации). Например, для того же needle=«abcdadcd» будет:
Суффикс [пустой] d cd dcd ... abcdadcdСдвиг 1 2 4 8 ... 8Иллюстрация было? ?d ?cd ?dcd ... abcdadcd стало abcdadcd abcdadcd abcdadcd abcdadcd ... abcdadcd
Если шаблон начинается и заканчивается одной и той же комбинацией букв, |needle | вообще не появится в таблице. Например, для needle=«колокол» для всех суффиксов (кроме, естественно, пустого) сдвиг будет равен 4.
Суффикс [пустой] л ол... олокол колоколСдвиг 1 4 4 ... 4 4Иллюстрация было? ?л?ол... ?олокол колокол стало колокол колокол колокол... колокол колокол
Существует быстрый алгоритм вычисления таблицы суффиксов. Этот алгоритм использует префикс-функцию строки.
M = length(needle)pi = префикс-функция(needle)pi1 = префикс-функция(обращение(needle))for j=0..msuffshift[j] = m - pi[m]for i=1..m j = m - pi1[i]suffshift[j] = min(suffshift[j], i - pi1[i])
Здесь suffshift соответствует всей совпавшей строке; suffshift[m] - пустому суффиксу. Поскольку префикс-функция вычисляется за O (|needle |) операций, вычислительная сложность этого шага также равняется O (|needle |).
Поиск со звездочками. Алгоритм Кнута-Морриса-Пратта.
Поиск со зведочками
Дан шаблон со звездочками (* - любой символ, но только 1), например ab*av**a (слово abqavqqa - подходит)
Как осуществлять поиск? Надо разбить шаблон на шаблоны без звезд (назовем массив таких шаблонов - runs). То есть в вышеописанном примере runs = {ab,av,a}. Кроме того будем хранить позицию начала этих шаблонов (без *) во всем шаблоне.
Создадим массив counts длины нашего текста. Изначально элементы равны в нем 0.
Затем запустим поиск в тексте всех шаблонов без * (из массива runs). Это будет происходить по очереди, если используем КМП, или сразу, если Ахо-Корасик. Затем будем делать counts.position]++, если j-ый шаблон из массива runs встретился в нашей строке на позиции entry
Потом мы пройдемся по массиву counts и все позиции в нем, где значение равно количеству шаблонов без * - это вхождения нашего шаблона (всего)
Сдвиг плохого символа, используемый в алгоритме Боуера - Мура, не очень эффективен для маленького алфавита, но, когда размер алфавита большой по сравнению с длиной образца, как это часто имеет место с
таблицей ASCII и при обычном поиске в текстовом редакторе, он становится чрезвычайно полезен. Использование в алгоритме только его одного может быть весьма эффективным.
После попытки совмещения x и y , длина сдвига - не менее 1. Таким образом, символ y [ i + m ] обязательно будет вовлечен в следующую попытку, а значит, может быть использован в текущей попытке для сдвига плохого символа. Модифицируем функцию плохого символа, чтобы принять в расчет последний символ х:
bc[ a ] = min { j | 0 j m и x[ m - 1 - j ] = a }, если a встречается в x,
bc[ a ] = m в противоположном случае.
Сравнения текста и образца могут производиться в любом порядке.
Листинг 6
Урбо БМ (Классификация Thierry Lecroq ).
Турбо - БМ является также является улучшением алгоритма Боуера - Мура. Мы будем запоминать сегмент текста, который сошелся с суффиксом образца во время прошлой попытки (и только, если произошел сдвиг хорошего суффикса).
Это даст нам два преимущества:
1. Возможность перескочить через этот сегмент
2. Возможность применения «турбо – сдвига»
«Турбо – сдвиг» может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
Пусть u - запомненный сегмент, а v - cуффикс, совпавший во время текущей попытки, такой что uzv - суффикс x. Тогда av - суффикс x, два символа а и b встречаются на расстоянии p в тексте, и суффикс x длины |uzv| имеет период длины p, а значит не может перекрыть оба появления символов а и b в тексте. Наименьший возможный сдвиг имеет длину |u| - |v| (его мы и называем «турбо – сдвигом»).
По определению, конечный автомат
представляет собой пятерку М = (Q, q 0 ,
A,
,
),
где:
Q - конечное множество состояний;
q 0 
Q
- начальное состояние;
А 
Q
- конечное множество допускающих
состояний;
Конечный входной алфавит;
Функция Q х
Q, называемая функцией переходов автомата.
Первоначально конечный автомат
находится в состоянии q 0 .
Затем он по очереди читает символы из
входной строки. Находясь в состоянии q
и читая символ а, автомат переходит в
состояние
(q,a).
Если автомат находится в состоянии q
A
говорят, что он допускает прочитанную
часть входной строки. Если q
А, то прочитанная часть строки отвергнута.
С конечным состоянием М связана
функция
,
называемая функцией конечного состояния,
определяемая следующим образом:
есть
состояние, в которое придет автомат (из
начального состояния), прочитав строку
w.
Автомат допускает строку w
тогда и только тогда, когда
А
Для каждого образца Р можно построить конечный автомат, ищущий этот образец в тексте. Первым шагом в построении автомата, соответствующего строке-образцу Р, является построение по Р вспомогательной суффикс-функциии (как в алгоритме КМП). Теперь определим конечный автомат, соответствующий образцу Р, следующим образом:
Поясним это соотношение. Требуется сконструировать автомат таким образом, чтобы при его действии на строку Т соотношение
(Т i)
=
(Т i)
являлось инвариантом (тогда равенство (Т i) = m будет равносильно тому, что Р входит в Т со сдвигом i - m, и автомат тем самым найдет все допустимые сдвиги). Однако в этом случае вычисление перехода по формуле (1) необходимо для поддержания истинности инварианта, что следует из теорем, приведенных ниже.
Теорема. Пусть q = (х), где х - строка. Тогда для любого символа а имеет место (ха) = (P q a).
Теорема. Пусть - функция конечного состояния автомата для поиска подстроки Р. Если Т - произвольный текст, то (Т i) = (Т i) для i=0,1,..., n.
Из изложенного следует, что задача поиска подстроки состоит из двух частей:
построение автомата по образцу (определение функции переходов для заданного образца);
применение этого автомата для поиска вхождений образца в заданный текст.
Построим конечный автомат, допускающий строку ababaca. Поскольку длина образца m = 7 символов, то в автомате будет m + 1 = 8 состояний.
Найдем функцию переходов . В соответствии с определением (1), (q, a) =(Р q а), где - префикс-функция, а - произвольный символ из алфавита , q - номер состояния. Таким образом, необходимо для каждого префикса P q = P, q = 0 .. m образца Р и для всех символов а входного алфавита найти длину максимального префикса Р, который будет являться суффиксом строки Р q а. Длина этого префикса и будет значением функции переходов (q,a). Если а = P (очередной символ текста совпал со следующим символом образца), то Р q а = Р q +1 и (q, a) = q+1.
Такой случай соответствует успешным этапам поиска. Иначе, q. Например, для префикса Р = ababa и символа b максимальным суффиксом строки Р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).
Мы рассмотрели несколько алгоритмов, провели оценку их временной и емкостной сложности. Однако, как уже говорилось, данные критерии оценки не позволяют нам наверняка сказать, какой из алгоритмов будет быстрее работать. Поэтому, для дополнительной оценки проведем их экспериментальный анализ, т.е. измерим время, за которое алгоритм выполняет конкретно поставленную задачу.
Имеется несколько текстовых
файлов, содержащих 10000 записей
вида:
строка
подстрока (имеющаяся
в данной строке)
место вхождения
длина
подстроки
с разными максимальными длинами строк и подстрок.
Алфавитом является 66 русских заглавных и строчных букв.
Пусть это будут строки длиной не более 10, 100, 250 символов.
Проведем поиск подстрок в строках для каждого из алгоритмов и измерим время работы программы. При этом будем учитывать следующее:
Строки предварительно загружаем в оперативную память (в виде массива), причем время считывания в массив не учитывается. Предобработка (создание таблиц перехода) входит в общее время.
Каждый алгоритм запускается 5 раз, время выбирается наименьшее.
Стенд для эксперимента.
Процессор Intel Pentium IV 2,66Ггц
1024 Мб ОЗУ
Компилятор Borland Delphi Enterprise, version 6.0 (Build 6.163)
Фрагмент кода тестируемой программы приведем в листинге 7.
Понятно, что такой замер времени даст нам весьма расплывчатые результаты, так как напрямую зависит от характеристик и загрузки процессора. Поэтому во время проведения эксперимента, отключались все сторонние и фоновые приложения, которые не влияют на работу программы. При запуске одной и той же задачи мы можем получить разное время, поэтому совершается несколько запусков, из которых выбирается наилучший результат.
Эксперимент проводился для четырех алгоритмов – представителей классов алгоритмов. Так как все алгоритмы ставились в одинаковые условия, то можно провести их сравнительный анализ. Заметим, что данный анализ применим только для данных параметров поиска, и при иных условиях может отличаться.
Результаты эксперимента занесем в таблицу (Табл. 3).
Как и предполагалось, алгоритм Бойера – Мура справился с экспериментальной задачей быстрее остальных. Следует, однако, заметить, что его эффективность растет лишь с увеличением длины строки и, соответственно, длины образца. Так при длине строки меньшей или равной 10 символов, он показал себя хуже, чем последовательный поиск. Аналогичные результаты показывает и алгоритм КМП, как для коротких, так и для длинных слов. Его можно использовать как универсальный, когда неизвестны длины строки и образца.
Алгоритм Рабина, при его схожести с последовательным работает быстрее, а его простота и малые трудозатраты на реализацию, делают его привлекательным для использования в неспециальных программах.
Наихудший результат показал алгоритм последовательного поиска. Как предполагалось лишь при небольшом увеличении длины строки, он работает в разы медленнее остальных алгоритмов.
В данный эксперимент не включен алгоритм поиска с помощью конечного автомата, т.к. мы используем алфавит, состоящий из 66 букв русского алфавита, и построенный автомат был бы слишком громоздок. Эффективность этого алгоритма возрастает при малом количестве букв в алфавите.
Мы рассмотрели различные алгоритмы поиска подстроки в строке, сделали их анализ. Результаты можно представить в таблице (Табл. 4).
|
Алгоритм |
Время на пред. обработку |
Среднее время поиска |
Худшее время поиска |
Затраты памяти |
Время работы (мс) при длине строки ≤250 |
Примечания |
|
Алгоритмы основанные на алгоритме последовательного поиска |
||||||
|
Алгоритм прямого поиска |
O((m-n+1)*n+1)/2 |
Mалые трудозатраты на программу, малая эффективность. |
||||
|
Алгоритм Рабина |
||||||
|
Алгоритм Кнута-Морриса-Пратта |
||||||
|
Универсальный алгоритм, если неизвестна длина образца |
||||||
|
Алгоритм Бойера-Мура |
||||||
|
Алгоритмы этой группы наиболее эффективны в обычных ситуациях. Быстродействие повышается при увеличении образца или алфавита. |
||||||
Исходя из полученных результатов, видно, что алгоритм Бойера – Мура является ведущим по всем параметрам, казалось бы, найден самый эффективный алгоритм. Но, как показывает эксперимент, алгоритм Кнута – Мориса - Пратта, превосходит алгоритм БМ на небольших длинах образца. Поэтому я не могу сделать вывод, что какой-то из алгоритмов является самым оптимальным. Каждый алгоритм позволяет эффективно действовать лишь для своего класса задач, об этом еще говорят различные узконаправленные улучшения. Алгоритм поиска подстроки в строке следует выбирать только после точной постановки задачи, которые должна выполнять программа.
Сделав такой вывод, мы выполнили цель данной работы, т.к. для различных классов задач был выделен свой эффективный алгоритм.
1). Kurtz, St. Fundamental Algorithms For A Declarative Pattern Matching System [Текст]. – Bielefeld:. Universität Bielefeld, 1995. – 238 с.
2). Lecro, T. Exact string matching algorithms [Электронный ресурс]. Режим доступа http://algolist.manual.ru/
3). Ахметов И. Поиск подстрок с помощью конечных автоматов [Текст]: Курсовая работа.- С-П государственный университет информационных технологий, механики и оптики.
4). Ахо, Альфред Структура данных и алгоритмы [Текст]. – М.: Издательский дом «Вильямс», 2000. - 384 с.
5). Белоусов А. Дискретная математика [Текст]. – М.: Издательство МГТУ им. Н.Э. Баумана, 2001. – 744 с.
6). Брайан, К. Практика программирования [Текст].- СПб:. Невский диалект, 2001. - 381 с.
7). Вирт, Н. Алгоритмы и структуры данных [Текст].– М:. Мир, 1989. – 360 с.
8). Гилл, Арт. Введение в теорию конечных автоматов [Текст]. – М., 1966. - 272 с.
9). Глушаков С. Программирование Web – страниц [Текст]. – М.: ООО «Издательство АСТ», 2003. – 387 с.
10). Кнут, Д. Искусство программирования на ЭВМ [Текст]: Том 3. – М:. Мир, 1978. – 356 с.
11). Матрос Д. Элементы абстрактной и компьютерной алгебры: Учеб. пособие для студ. педвузов [Текст]. – М.: Издательский центр «Академия», 2004. – 240 с.
12). Успенский В. Теория алгоритмов: основные открытия и приложения [Текст]. – М.: Наука, 1987. – 288 с.
13). Шень, А. Программирование: теоремы и задачи [Текст]. – М.: Московский центр непрерывного математического образования, 1995.
14). Кормен, Т. Алгоритмы: построение и анализ [Текст]/ Т. Кормен, Ч. Лейзерсон, Р. Ривест - М.: МЦНМО, 2002. М.: МЦНМО, 2002.
Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)Наиболее типичным приложением такой задачи является документальный поиск: задан фонд документов, состоящих из последовательности библиографических ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «Java». Такой запрос можно трактовать следующим образом: существуют ли статьи, обладающие дескрипторами «Программирование» и «Java».
Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0
Идея алгоритма:
1. I=1,
2. сравнить I-й символ массива T с первым символом массива W,
3. совпадение → сравнить вторые символы и так далее,
4. несовпадение → I:=I+1 и переход на пункт 2,
Условие окончания алгоритма:
1. подряд М сравнений удачны,
2. I+M>N, то есть слово не найдено.
Сложность алгоритма:
Худший случай. Пусть массив T→{AAA….AAAB}, длина │T│=N, образец W→{A….AB}, длина │W│=M. Очевидно, что для обнаружения совпадения в конце строки потребуется произвести порядка N*M сравнений, то есть O(N*M).
Недостатки алгоритма:
1. высокая сложность - O(N*M), в худшем случае – Θ((N-M+1)*M);
2. после несовпадения просмотр всегда начинается с первого символа образца и поэтому может включать символы T, которые ранее уже просматривались (если строка читается из вторичной памяти, то такие возвраты занимают много времени);
3. информация о тексте T, получаемая при проверке данного сдвига S, никак не используется при проверке последующих сдвигов.
Алгоритм КМП-поиска фактически требует только порядка N сравнений даже в самом плохом случае.
Пример.
(Символы, подвергшиеся сравнению, подчеркнуты.)
После частичного совпадения начальной части образа W с соответствующими символами строки Т мы фактически знаем пройденную часть строки и может «вычислить» некоторые сведения (на основе самого образа W), с помощью которых потом быстро продвинемся по тексту.
Идея КМП-поиска – при каждом несовпадении двух символов текста и образа образ сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению.
Особенности КМП-поиска:
1. требуется порядка (N+M) сравнений символов для получения результата;
2. схема КМП-поиска дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае образ сдвигается более чем на единицу. К несчастью совпадения встречаются значительно реже чем несовпадения. Поэтому выигрыш от КМП-поиска в большинстве случаев текстов весьма незначителен.
На практике алгоритм БМ-поиска наиболее эффективен, если образец W длинный, а мощность алфавита достаточно велика.
Идея БМ-поиска – сравнение символов начинается с конца образца, а не с начала, то есть сравнение отдельных символов происходит справа налево. Затем с помощью некоторой эвристической процедуры вычисляется величина сдвига вправо s. И снова производится сравнение символов, начиная с конца образца.
Этот метод не только улучшает обработку самого плохого случая, но и даёт выигрыш в промежуточных ситуациях.
Почти всегда, кроме специально построенных примеров, БМ-поиск требует значительно меньше N сравнений. В самых же благоприятных обстоятельствах, когда последний символ образца всегда попадает на несовпадающий символ текста, число сравнений равно (N / M), в худшем же случае – О((N-M+1)*M+ p), где p – мощность алфавита.
Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│.
Пример. Пусть образец имеет вид W = 3 1 4 1 5
Вычисляем значения чисел из окна длины |W|=5 по mod q, q - простое число.
23590(mod 13)=8, 35902(mod 13)=9, 59023(mod 13)=9, …
k1=314157(mod 13) – вхождение образца,
k2=673997(mod 13) – холостое срабатывание.
Из равенства ki= kj (mod q) не следует, что ki= kj (например, 31415=67399(mod 13), но это не значит, что 31415=67399). Если ki= kj (mod q), то ещё надо проверить, совпадают ли строки W и T на самом деле.
Если простое число q достаточно велико, то дополнительные затраты на анализ холостых срабатываний будут невелики.
В худшем случае время работы алгоритма РК - Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).
Пример: Сколько холостых срабатываний k сделает алгоритм РК, если
q= 11, 13, 17. Пусть W={2 6}
26 mod 11=4 → k =3 холостых срабатывания,
26 mod 13=0 → k =1 холостое срабатывание,
26 mod 17=9 → k =0 холостых срабатываний.
Очевидно, что количество холостых срабатываний k является функцией от величины простого числа q (если функция обработки образца mod q) и, в общем случае, от вида функции для обработки образца W и текста Т.
