Лекции по информатике (984119), страница 15
Текст из файла (страница 15)
~ ът1Се1п: жг1Се('> '); М; 0; лгЬ11е поС ео1п с1о Ьеи1п 1' Образеи, — строка, входного текстового файла з~ геас1(с): р[М[: с; М:- М- 1; епс1; геас11п; ът1Се1п; ппС11 М > 0; 1' ... до агах пор, пока, не бйдет введен образец ненулевой дллсны ~ о; — 1; с1 [0]:- — 1; / Не бьело совпадений / жЫ1е ) лс (М вЂ” 1) с1о Ьеи1п / Построение таблицы — пгот же поиск, / лл Ы1е$ > — 0) апс1 Я[ < > р[1с[) с1о / В первый раз 1: == — Х и цикл не вьиолпяетсл, д/0/ задано вручную ( — Х/ / с1[1[; ( ХХоии1ем — ка сначо,.ла в образце / 3: 3 1с; 1с -,-1; 1Х рЦ [ -- р[Ц СЬеп сЦ) [ ь..
сЦЦ е1ве с1[) [ ь- 1с; епс1; ( Таблица построена тем ясе методом Х(ЛХХХ 3 ( Начало поиска Х 1:- 0; ,1: —. О:, 1;ь 0; лл Ы1еЦ < М) апс1 (1 с Хч)с1о Ьеи1п н Ы1е(1с <' 1) с1о Ьеи1п лътйе(а [Ц); 1: епс1; Ми1е([ >- 0) апс1 (эЯ <> р[Я) с1о 1: дБ[; 1: 1 ~ 1; .[-' 1; епс1; Г 1 М 1Ьеп жг1Хе('! Найдено' ) егн1; епс1. 6.1.5.1 Анализ КМП-поиска Точный анализ КМП-поиска, как и сам алгоритм, весьма, сложен. Его авторами получена сложностная оценка числа сравнений 0(ЛХ + К), существенно лучшая, чем оценка прямого поиска 0(гч э ЛХ). Достоинством КМП-метода является его однопроходность, ведь указатель сканирования 1 никогда не возвращается назад, и электромеханическим устройствам не придется делать реверс, преодолевая инерцию.
Это также удобно для поиска на удаленных (сетевых) дисках. В начале третьего тысячелетия А. Л. Калининым [[ было предложено обобщение КМП-алгоритма па случай одновременного поиска нескольких образцов. Алгоритм Кнута-Мориса-Пратта-Калинина позволил выполнить эффективную реализацию антиспамового фильтра почтовых сообщений Каэрега1су Ап11враш и явился одним из результатов его кандидатской диссертации. 6.1.6 Алгоритм Бойера-Мура Остроумная схема КМП-поиска дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае образец сдвигается более чем па едипипу. К несчастью, это скорее исключение, чем правило: совпадения встречаются реже, чем несовпадения. Поэтому реальный выигрыш от использования КМП-стратегии в большинстве случаев поиска весьма незначителен.
В 1977 году Р. Бойер и Д. Мур предложили другой метод поиска, который не только улучшает обработку самого плохого случая (когда и в образце, и в последовательности многократно повторяется нсболыпое число букв), но и дает выигрыш в промежуточных ситуациях. БМ-поиск основан на необычном для большинства культур письменности соображении сравнение литер проводится нс с начала образца,, слева направо, а наоборот, с конца, образца справа, налево. Чтение в обратном направлении характерно для семитских языков и нотаций. Как и в случае КМП-поиска, сначала по образпу генерируется таблица, сдвигов, в которой задаются максимально допустимые в каждой ситуации прыжки вперед.
Пусть для каждого знака алфавита х И означает его расстояние от самого правого (семитское чтение!) вхождения в образец до ого конца. Если в процессе поиска обнаружено расхождение образца и строки, то образец сразу же можно сдвинуть вправо на. Иря, позипий, т. с.
на число позиций, скорее всего, болыпое единицы. Если Х-'у -„в образце вообще не встречается, .то сдвиг можно сделать сразу на вен> длину образца. Вот пример, иллюстрирующий этот процесс: Ноо1а-Ноо1а я1г1в 11ке Ноо11яапв. Ноо11яап Ноо11яап Ноо11яап Ноо11яап Ноо11яап Мы видим, что здесь количество гаагов заметно меньше, чем в КМП-алгоритме для этого же примера (пам даже не пришлось использовать многоточие!) Поскольку сравнение литер теперь идет справа налево, будет удобно модифицировать предикаты частичного совпадения Р и первого вхождения Я; заменив в первом из них 0 на 1, А на Л1 и г на г — 1, а во втором ЛХ на 0 и г на А в соответствии с вводимой БМ-алгоритмом инверсией порядка, сравнения Р'(г, 1) = Ы: 1г < А < ЛХ: в....ь = Рь С~'Я = ЧА:: 0 < А < ъ'; - Р'(,Ь, О) Предикат Р' указывает, что в последовательности, начиная с позиции г, не совпало 1 букв твпсп~а (суффикса) образца, т.
е. фактически А Р ЛХ вЂ” 1 — 1-ая ее литера сравнивается с Л1 — 1-ой литерой образца, г + Л1 — 1 — 2-ая — с ЛХ вЂ” 2-ой, и т. д. г-тая литера последовательности, ка,к нетрудно видеть, совпадает с 1г-той литерой образца,. Полное совпадение достигается тогда, когда не совпало 0 букв, гсоэтому предикат Р(ю', 1) становится истинным при 1 = 0: Р(г, 0) = 1гие. В отличие от Р' Я' действует все равно в соответствии с направлением просмотра последовательности слева направо и утверждает. что в любой ее позиции левее 1-той (О < Л: < 1) полных совпадений (Р'(к, 0)!) не было. Сформулируем с помощьк> этих предикатов инварианты поиска с реверсным сравнением в упрощенной версии алгоритма Бойера-Мура 1:-- М; М всЬ11е (1 > 0) апс1 (~ < ~М) с1о Ьее1п Я('г — ЛХ) 1 М: эс Ь11е (1 > 0) апс1 (в~1с — 1) =-- р~1 — 1~) с1о Ьеи1п Р(Х: — 1, 1) б1 Р; - Хс — — ЛХ)) 1с: 1с — 1: 1 епс1:, 1: — 1 —, ,с1[в(1 — Ц~ епс1; Индексы г, Х и /с удовлетворяют условиям 0 < 1 < ЛХ и 0 < г, Л'.
< Лс. Поэтому из окончания цикла при 1 = 0 вместе с Р(сс — ~, Я следует совпадение в 1с-й позиции Р(сс, 0). При окончании цикла с 1 > 0 необходимо, чтобы 1 достигло значения Лс, следовательно, истинность Я(г — ЛХ) влечет ис:тинность Я(Ж вЂ” ЛХ), что означает отсутствие совпадений. Убедимся, что Я(г — ЛХ) и Р(А", — 1, 1) действительно инварианты двух циклов. В начале повторений они, естественно, истинны как ®(0) так и Х~(0, ЛХ), и ни полного, ни частичного совпадения нет. Далее необходимо разобраться в эффекте двух операторов, синхронно уменьшающих ~с и 1.
На 0(г — ЛХ) они действуют, и так как было выяснено, что а|,. ~ — — р, и то справедливость предусловия Р(Й вЂ” 1, Х вЂ” 1) гарантирует истинность Р(Й вЂ” 1', 1) в качестве постусловия. Если внутренний цикл заканчивается при Х > О, то из ву„. ~ ф р ~ следует ложность Р(Хс — 1, 0), так как — Р(1. 0) = ЛЛ: 0 < Л < ЛХ: вн с Ус Рь Более того, из к — 1 = ЛХ вЂ” 1 следует сХ(~, — ЛХ) Й вЂ” Р(Л вЂ” Х, 0) = Я(г — ЛХ+ Ц, фиксирующее несовпадение в гюзиции 1 — ЛХ + 1. Теперь нам нужно показать, что оператор 1:= 1+с(,, никогда, не делает инвариант ложным и цикл делает то, что надо.
Гарантировано, .что перед этим оператором сХ(г+с1.с . — ЛХ) истинно. Так как мы знаеъс, что С?(1+1 — ЛХ) истинно, .то достаточно установить истинность отрицания — Р(1-р 6 — ЛХ, О),чля 6 = 2, 3,..., с1,,, Вспомним. что с1,. опрсделсно нами как расстояние от самого правого вхождения знака х в образец до сгго конца. Формально зто может быть записано так: И; ЛХ вЂ” с1 < lс < ЛХ-1; Рк Ф т т. е. далее в образце несовпадение. Подставляя гн вместо т, получаем Ч6: ЛХ вЂ” л1„,.
л < 6 < ЛХ вЂ” 1: з, л ул рн -- несовпадение Х6 1' 6 <с1ч — 1 зл — !Фрь — м М6: 1 < 6 < сХн 1 . — Р(1+ 6 — ЛХ,О) что и требовалось доказать. Ниже приводится программа упрощенного алгоритма Бойера-Мура, построение которой аналогично предыдущей программе. Упрощение заключается в том, что используется только правило плохой литеры без правила хорошего суффикса. Об этом правиле можно прочитать в [87). ргоигаш ВМ('прпС, опСрпг); сопеС Мшах -- 100; Хшах 1000; айаг 1, 1, 1с, 10, М, д: шСеиег: с: сЬаг; р: аггау10..лМплах — 11 оГ сЬаг; ( образец 3 а: аггау'10..%пах — Ц оГсЬаг; (строка лЛ с1: аггау~сЬаг) оГ шСеиег; Ьеи1п з': — О: ( Ввод текста, в котором будет осуществляться поиск 3 Мп1е поС ео1п с1о Ьеиш геас1(с); вЯь-с: лз ь- 1х —, 1; епс1; геас11п; гереаС илг1Се1п1 ъччСе('>„'); М: - 0; ( Счиплывание образца.
3 жЬ11е поС ео!п с1о Ьеиш геас1(с); р~М~: с; М: — М--' 1; епс1; геас11п; Г М <> 0 СЬеп Ьеиш ( Если образец пуст, поиск пе выполняется Х / Заглаллнение таблицъс сдвияов л1 Х Гог с: — сЬг(0) Со с1п1255) с1о сЦс~: - М; ( Пока все буквы в образце отсутсапвуют л Гог 1: -- 0 Со М вЂ” 2 с1о сЦрЦ Ц ь- М вЂ” 1 — 1; ( В масхеиве с~ остается. самое правое (послледллее1) всеождение буквы в образеи, (блслолсайилее к концу при чгпенллсл задом злопеХлед!),Л 1' Поиск подстроки Х :- М; о:-- о; гереаС ът1Се1п; 010 >ОСЬеп жг1Се(' ': 10); жЬ11е 10 < 1 с1о Ьен1п ът1Се(э [10 ) ); 10:- 10--1; епс1; М; 1с:=-.
1: гереаС 1с:-= 1с — 1:, 3: --,1 ппС11 (.1 < 0) ог (р[1[ <;- эЩ; :-= 1 '- с1[э[1 — 1Ц; ппС11Ц < 0) ог (1 > Х); 1С 1 <ОСЬеп т~т1Се('! Пайден'): епс1; ппС11 ео1: епс1. 6.1.6.1 Анализ алгоритма Бойера-Мура При публикации алгоритма авторы привели детальный анализ его производительности. Замечательные свойства этого алгоритма в том, что почти всегда. кроме специально построенных примеров (типа «убийцы КМП» задом наперед). он требует значительно меньше Х сравнений, проходя саженьнэ образца по рулетке последовательности. В самых благоприятных обстоятельствах, когда последняя литера, образца всегда нс совпадает с соответствующими литерами текста, проходимого аршином длины ЛХ, число сравнений равно ХСХлХ.
Худшая оценка алгоритма. ХЛХ маловероятна. Публикуя свою работу после статьи Кнута„Мориса и Пратта, Бойер и Мур приводят соображения по поводу дальнейших усовершенствований алгоритма. Одно из них --. объединить стратегию Бойера-Мура, обеспечивающую большие сдвиги в случаях несовпадения., со стратегией Кнута-Мориса-Пратта, дающей существенные сдвиги при частичном совпадении.
Комбинированная стратегия базируется на двух таблицах: КМП и БМ. В каждой ситуации поиска из двух сдвигов выбирается больший, поскольку оба алгоритма гарантируют, что никакой меньший сдвиг пе может привести к совпадению. Анализируя эту изощренную стратегию, проф. Н. Вирт пессимистически иронизирует, что такое усложнение генерации таблиц и самого поиска вряд ли приведет к существенному выигрышу[541. 6.1.7 Алгоритм Рабина-Карпа Рабин и Карп изобрели еще один алгоритм поиска подстрок, который эффективен на практике и к тому же обобщается на многомерный случай [например, поиск на двумерной решетке). Хотя в ху>пнем случае время работы алгоритма Рабина-Карпа 0(ЛХ(Л> — ЛХ+1)), в среднем он работает достаточно быстро.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
