Главная » Просмотр файлов » Алгоритмы - построение и анализ

Алгоритмы - построение и анализ (1021735), страница 213

Файл №1021735 Алгоритмы - построение и анализ (Алгоритмы - построение и анализ) 213 страницаАлгоритмы - построение и анализ (1021735) страница 2132017-07-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 213)

Вычисление функции переходов Приведенная ниже процедура вычисляет функцию переходов б по заданному образцу Р [1..т]. СомР11те Тило!т!ох рохст!ох(Р, Е) 1 т — 1епдсй[Р] 2 (ог д — О то т 3 до Тог (для) каждого символа а Е Е 4 бо й — пцп(т+ 1,о+ 2) 5 гереа1 1с — Й вЂ” 1 б ппгИ Рь 1 Ряа 7 б(д, а) - )с 8 гетнгн б В зтой процедуре функция б (д, а) вычисляется непосредственно, исходя из ее определения. Во вложенных циклах, которые начинаются в строках 2 и 3, рассматриваются все состояния о и символы а, а в строках 4-7 функции б(д,а) присваиваются максимальные значения й, при которых справедливо соотношение Рь 1Ряа. Время работы процедуры р1х1те Аотомлтох Млтснек равно О (т [Е[), поскольку внешние циклы дают вклад, соответствующий умножению на т [Е[, внутренний цикл гереа1 может повториться не более т + 1 раз, а для выполнения проверки в строке 6 может понадобиться сравнить вплоть до т символов.

Существуют процедуры, работающие намного быстрее; время, необходимое для вычисления функции б по заданному образцу Р, путем применения некоторых величин, ф (Т1+1) = ф(Т,а) = = б(ф(Т,),а) = б(д,а) = = а(Рча) = = о (Т1а) = = о (Т+1) (по определению величин Т1+1 и а) (по определению ф) (по определению д) (по определению б (32.3)) (согласно лемме 32.3 и гипотезе индукции) (по определению Т1+1). И Часть ЧП. Избранные темы 1036 остроумно вычисленных для этого образца (см. упражнение 32.4-6), можно улучшить до величины 0 (т Д). С помощью такой усовершенствованной процедуры вычисления функции 6 можно найти все вхождения образца длиной т в текст длиной гг для алфавита Е, затратив на предварительную обработку время 0 (т Д), а на сравнение — время 6 (гг). Упражнения 32.3-1. Сконструируйте автомат поиска подстрок для образца Р = ааЬаЬ и проиллюстрируйте его работу при обработке текста Т = аааЬаЬааЬааЬаЬааЬ.

32.3-2. Изобразите диаграмму состояний для автомата поиска подстрок, если образец имеет вид аЬаЬЬаЬЬаЬаЬЬаЬаЬЬа66, а алфавит — Е = 1а, Ь). 32.3-3. Образец Р называют строкой с уникальными префиксами (попочег1арРа61е), если из соотношениЯ Рь Л Рч следУет, что К = О или /с = г1. Как выглядит диаграмма переходов автомата для поиска подстроки с уникальными префиксами7 * 32.3-4. Заданы два образца Р и Р'. Опишите процесс построения конечного автомата, позволяющего найти все вхождения любого из образцов.

Попытайтесь свести к минимуму количество состояний такого автомата. 32.3-5. Задан образец Р, содержащий пробельные символы (см. упражнение 32.1-4). Опишите процесс построения конечного автомата, позволяющего найти все вхождения образца Р в текст Т, затратив при этом на сравнение время 0 (п), где и = ~Т~. * 32.4 Алгоритм Кнута-Морриса-Пратта Теперь представим алгоритм сравнения строк, который был предложен Кнутом (Кпшй), Моррисом (Могпз) и Пратгом (Ргап), и время работы которого линейно зависит от объема входных данных. В этом алгоритме удается избежать вычисления функции переходов 6, а благодаря использованию вспомогательной функции я 11..гл), которая вычисляется по заданному образцу за время О(пг), время сравнения в этом алгоритме равно Э (гг). Массив я позволяет эффективно (в амортизированном смысле) вычислять функцию Б "на лету", т.е. по мере необходимости. Грубо говоря, для любого состояния д = О, 1,..., гл и любого символа а е Е величина к [у) содержит информацию, которая не зависит от символа а и необходима для вычисления величины б (д, а) (пояснения по поводу этого замечания будут даны ниже).

Поскольку массив я содержит только т элементов (в то время как в массиве 6 их 6 (т1Е~)), вычисляя на этапе предварительной обработки функцию я вместо функции б, удается уменьшить время предварительной обработки образца в )Е! раз. Глава 32. Поиск подстрок 1037 Префикеная функция для образца Пусть символы Р [1..д] образца совпадают с символами текста Т[в + + 1..в + д]. Чему равен наименьший сдвиг в' > в, такой что Р[1..й] = Т [в'+1..в'+ )с], (32.5) где в'+/с = в+ 97 Такой сдвиг в' — первый после сдвига в, недопустимость которого не обязательно следует из наших знаний о подстроке Т [в + 1..в + д].

В лучшем случае в' = в+ д, и все сдвиги в+ 1, в+ 2,..., в+ у-1 немедленно отбрасываются. В любом случае для нового сдвига в' нет необходимости сравнивать первые lс символов образца Р и соответствующие символы текста Т, поскольку их совпадение гарантированно благодаря уравнению (32.5). Префиксная функция я, предназначенная для какого-нибудь образца, инкапсулирует сведения о том, в какой мере образец совпадает сам с собой после сдвигов. Эта информация позволяет избежать ненужных проверок в простейшем алгоритме поиска подстрок или предвычисления функции б при использовании конечных автоматов.

Рассмотрим работу обычного алгоритма сопоставления. На рис. 32.9а показан некоторый сдвиг в шаблона с образцом Р = аЬаЬаса вдоль текста Т. В этом примере д = 5 символов успешно совпали (они выделены серым цветом и соединены вертикальными линиями), а б-й символ образца отличается от соответствующего символа текста.

Сведения о количестве совпавших символов д позволяют сделать вывод о том, какие символы содержатся в соответствующих местах текста. Эти знания позволяют сразу же определить, что некоторые сдвиги будут недопустимыми. В представленном на рисунке примере сдвиг в + 1 точно недопустим, поскольку первый символ образца (а) находился бы напротив символа текста, для которого известно, что он совпадает со вторым символом образца (Ь). Однако из части б рисунка, на которой показан сдвиг в' = в+ 2, видно, что первые три символа образца совпадают с тремя последними просмотренными символами текста, так что такой сдвиг априори нельзя отбросить как недопустимый.

Полезную информацию, позволяющую сделать такой вывод, можно получить путем сравнения образца с самим собой. В части в рисунка изображен самый длинный префикс образца Р, который также является собственным суффиксом строк Рв и Рз. Эти данные предварительно вычисляются и заносятся в массив я, так что я [5] = 3. Если первые 9 символов совпали при сдвиге в, то следующий сдвиг, который может оказаться допустимым, равен в' = в + (д — сг [9]). Словом, в общем случае полезно знать ответ на сформулированный ниже вопрос. Часть Ч1!. Избранные темы 1038 у — — — 1 — — ~(а. ь в~ь.в~.,:а~ Р [ь ~а ~с ге'а [ь ~а[ь~к!к ~ь [с ге!а[а! г ю'=я, ~ — ь — э [ ю [ ь 1т а' ] ъ~'ь ) гт Гк ~ЬЯ Рз Рис.

32.9. Префнксная функция к Необходимую информацию об образце можно получить, сдвигая его вдоль самого себя (см. рис.32.9с). Поскольку Т [а' + 1..а' + й] — известная часть текста, она является суффиксом строки Рч. Поэтому уравнение (32.5) можно рассматривать как запрос о максимальном значении й < 9, таком что Рь л Ря.

Тогда следующий потенциально допустимый сдвиг равен з' = а+ (д — 1с). Оказывается, что удобнее хранить количество й совпадающих при новом сдвиге а' символов, чем, например, величину з' — з. С помощью этой информации можно ускорить и простейший алгоритм поиска подстроки, и работу конечного автомата.

Теперь дадим формальное определение. Префиксной функцией (ргебх Йпсбоп) заданного образца Р [1..тп] называется функция к: (1, 2,..., т) -+ (О, 1,..., тл — 1), такая что к [9] = шах (lс: к < д и Рь ) Рч) . Другими словами, и [у] равно длине наибольшего префикса образца Р, который является истинным суффиксом строки Рч. В качестве другого примера на рис. 32.10а приведена полная префиксная функция к для образца абабабаЬса. Алгоритм поиска подстрок Кнута-Морриса-Пратта приведен ниже в виде псевдокода процедуры КМР МАтсннв.

В процедуре КМР МАтсннк вызывается вспомогательная процедура Сомгитн Ркнщх Римспон, в которой вычисляется функция и. Глава 32. Поиск подстрок 1039 а) )б [Ь!а ~Ь[а [Ь,а[Ьт[с а ~а'[Ьса[Ьза[Ь*'а Ь с а [а]Ь[а Ь а Ь а Ь с а )в я[8[ 6 )б я[6] = 4 я[4[ 2 в ,'а Ь а Ь а Ь а Ь с а я[2[ О Рв б) Рис. 32.10.

Иллюстрация к лемме 32.5 лля образца Р = аЬаЬаЬаЬса ид= 8 Г~Мр МАтОнек(Т, Р) 1 тв - [епд8[в[Т] 2 т — [епд8[в[Р] 3 К б- СОМРОТЕ РКЕР)Х я'[)Ь[СТ1ОЫ(Р) 4 д — О с Число совпавших символов 5 Гоге -18отв с Сканирование текста слева направо б б[о вап[[е д ) О и Р[д + 1] ф Т[в] 7 до д б — к[д] с Следующий символ не совпадает 8 [Г Р[д + 1) = Т[в) 9 8[вен д — д+ 1 с Следующий символ совпадает 1О [Г д = т [> Совпали ли все символы образца Рд 11 8[вен рпп1 "Образец обнаружен при сдвиге" в — т 12 д - вг[д) 8 Поиск следующего совпадения Часть ЧП.

Избранные темы 1040 СОмгцте Ркее|х Рглчстюн(Р) 1 т — 1егг911г [Р] 2 я[Ц» — О 3 )с» — О 4 аког»7 — 21от 5 бо иИ!е 1с ) О и Р[1с+ Ц ф Р[г1] 6 бо )с я[/с] 7 !Г Р[гс+ Ц = р[»7] 8 1'пеп й — 1с+ 1 9 7г[9] — »с 1О гегпгп к Сначала проанализируем время работы этой процедуры. Доказательство ее кор- ректности окажется более сложным. Анализ времени работы С помощью метода потенциалов амортизационного анализа (см.

раздел 17.3) можно показать, что время работы процедуры Сомгите Ркее1Х Рглчст1он равно О (т). Потенциал величины й связывается с текущим ее значением в алгоритме. Как видно из строки 3, начальное значение этого потенциала равно О. В строке 6 значение величины 1с уменьшается при каждом его вычислении, поскольку я [»с] < )с. Однако в силу неравенства я [гс] > О, которое справедливо при всех 1с, значение этой переменной никогда не бывает отрицательным. Единственная другая строка, юторая тоже оказывает влияние на значение переменной Й,— строка 8.

Характеристики

Тип файла
DJVU-файл
Размер
18,3 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6527
Авторов
на СтудИзбе
301
Средний доход
с одного платного файла
Обучение Подробнее