Курсовая работа: Алгоритмы поиска подстроки в строке. Результаты и анализ эксперимента. Алгоритм прямого поиска
Наиболее типичным приложением такой задачи является документальный поиск: задан фонд документов, состоящих из последовательности библиографических ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «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 и текста Т.
Быстрый поиск (Классификация Thierry Lecroq ).
Сдвиг плохого символа, используемый в алгоритме Боуера - Мура, не очень эффективен для маленького алфавита, но, когда размер алфавита большой по сравнению с длиной образца, как это часто имеет место с
таблицей 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| (его мы и называем «турбо – сдвигом»).
1.5. Поиск подстрок с помощью конечного автомата.
1.5.1. Структура автомата.
По определению, конечный автомат
представляет собой пятерку М = (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.
Из изложенного следует, что задача поиска подстроки состоит из двух частей:
построение автомата по образцу (определение функции переходов для заданного образца);
применение этого автомата для поиска вхождений образца в заданный текст.
1.5.2. Пример построения конечного автомата
Построим конечный автомат, допускающий строку 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).
Часть 2. Экспериментальный анализ алгоритмов.
2.1. Суть эксперимента.
Мы рассмотрели несколько алгоритмов, провели оценку их временной и емкостной сложности. Однако, как уже говорилось, данные критерии оценки не позволяют нам наверняка сказать, какой из алгоритмов будет быстрее работать. Поэтому, для дополнительной оценки проведем их экспериментальный анализ, т.е. измерим время, за которое алгоритм выполняет конкретно поставленную задачу.
Имеется несколько текстовых
файлов, содержащих 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 букв русского алфавита, и построенный автомат был бы слишком громоздок. Эффективность этого алгоритма возрастает при малом количестве букв в алфавите.
Заключение.
Мы рассмотрели различные алгоритмы поиска подстроки в строке, сделали их анализ. Результаты можно представить в таблице (Табл. 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.
Абстрактный автомат Мили
Абстрактный синтез 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...
Эквивалентность и минимизация конечных автоматов
Разные конечные автоматы могут функционировать одинаково, даже если у них разное число состояний. Важной задачей является нахождение минимального конечного автомата, который реализует заданное автоматное отображение ...