Алгоритмы поиска подстроки в строке
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
т находится в состоянии 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):
01234567a11315171b02040402c00000600
Строки соответствуют входным символам, столбцы состояниям автомата. Ячейки, соответствующие успешным этапам поиска (входной символ совпадает со следующим символом образца), выделены серым цветом.
Построим по таблице граф переходов автомата (Рис. 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 символов.
Проведем поиск подстрок в строках для каждого из алгоритмов и измерим время работы программы. При этом будем учитывать следующее: