Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 229
Текст из файла (страница 229)
Однако все вычисления выполняются по модулю 13, поэтому для первого окна получаетса значение 7, а для второго— значение 8. тяаеа 32. Поиск кодсосрок быстрого эвристического теста, позволяющего исключить недопустимые сдвиги в. Любой сдвиг в, для которого справедливо соотношение 1, = р (шос( д), необходимо подвергнуть дополнительному тестированию, чтобы проверить, действительно ли этот сдвиг является допустимым или это просто лажное совпадение (врипоия Ь11).
Такое тестирование можно осуществить путем явной проверки условия Р[1 .. т) = Т[в+1 .. в+т). Если значение д достаточно большое, то можно надеяться, что ложные совпадения встречаются довольно редко и стоимость дополнительной проверки окажется низкой. Приведенная ниже процедура использует описанные выше идеи. В роли входных данных для нее выступают текст Т, образец Р, основание системы счисления с( (в качестве значения которого обычно выбирается )Е[) и простое число д. йявсм-Клкг-Млтсиеи(Т, Р, д,9) 1 п = Т.1епдй 2 т = Р.1епдй 3 Ь со д с шос( с7 4 р=О 5 1о=О б Тогс=1гот 7 р = (с(р+ Р[с]) пюс1 д 8 1а = (с(1о+Т[т)) шос(9 9 1огв = 01оп — т // Сравнение 1О 11р == 1, 11 Ы Р[1 ., тп] == Т[в + 1 ..
в + ти] 12 рппс "Образец найден со сдвигом" в 13 Ыв(п — т 14 1отт = (с((1, — Т[я + ЦЬ) + Т[я + т + 1]) пюс1 д // Предварительная обработка При выполнении строки 10 справедливо соотношение 1, = Т[я + 1 .. в + т) пюс1 9 . Если в строке 10 выполняется условие р = 1, ("совпадение"), то в строке 11 проверяется справедливость равенства Р[1..т) = Т[я + 1..в + т], чтобы исключить ложные совпадения. Все обнаруженные допустимые сдвиги выводятся в строке 12. Если в < п — т (это неравенство проверяется в строке 13), то цикл Гог нужно будет выполнить хотя бы еще один раз, поэтому сначала выполняется Процедура Каиса-Клкг-Млтснци работает следующим образом.
Все символы рассматриваются как цифры в системе счисления по основанию с(. Индексы переменной 1 приведены для ясности; программа будет правильно работать и без них. В строке 3 переменная 6 инициализируется цифрой, расположенной в старшем разряде т-цифрового окна. В строках 4-8 вычисляются значение р, равное Р[1 .. т] шос( с7, и значение 1о, равное Т[1 .. тп) пюс1 9. В цикле Тог в строках 9-14 выполняются итерации по всем возможным сдвигам в. При этом сохраняется сформулированный ниже инвариант.
!040 Часть е11. Избранные темь строка 14, чтобы гарантировать соблюдение инварианта цикла, когда мы снова перейдем к строке 10. В строке 14 на основании значения 1, шос1 д с использованием уравнения (32.2) за константное время вычисляется величина бе.е! шос) 0. В процедуре КАв!м-Клкр-Мятсннк на предварительную обработку затрачивается время Е!(т), а время сравнения в нем в наихудшем случае равно Е!((п — т+ 1)т), поскольку в алгоритме Рабина — Карпа (как и в простейшем алгоритме поиска подстрок) явно проверяется допустимость каждого сдвига. Если Р = а, а Т = а", проверка займет время !Э((п — т+ 1)т), поскольку все п — т + 1 возможных сдвигов являются допустимыми. Во многих приложениях ожидается небольшое количество допустимых сдвигов (возможно, выражаемое некоторой константой с); в таких приложениях математическое ожидание времени работы алгоритма равно сумме величины 0((п — гп + 1) + ст) = О(п + т) и времени, необходимого для обработки ложных совпадений.
В основу эвристического анализа можно положить предположение, что приведение значений по модулю д действует как случайное отображение множества Е* на множество .'Ее. (См. в разделе 1!.3.1 обсуждение вопроса об использовании операции деления для хеширования. Сделанное предположение трудно формализовать и доказать, хотя один из многообещающих подходов заключается в предположении о случайном выборе числа д среди целых чисел подходящего размера.
В этой книге такая формализация не применяется.) В таком случае можно ожидать, что число ложных совпадений равно 0(п/д), потому что вероятность того, что произвольное число 1, будет эквивалентно р по модулю 0, можно оценить как 1/д. Поскольку имеется всего 0(п) позиций, в которых проверка в строке !О дает отрицательный результат, а на обработку каждого совпадения затрачивается время 0(т), математическое ожидание времени сравнения в алгоритме Рабина-Карпа равно О(п) + 0(т(зз+ п/д)), где зз — количество допустимых сдвигов.
Если и = 0(1), а д выбрано так, что 0 > т, то приведенное выше время выполнения равно 0(п). Другими словами, если математическое ожидание количества допустимых сдвигов малб (0(1)), а выбранное простое число д превышает длину образца, то можно ожидать, что для выполнения фазы сравнения процедуре Рабина-Карпа потребуется время О(п+ т). Поскольку т < п, ожидаемое время сравнении равно О(п). Упражнения 32.2.1 Сколько ложных совпадений произойдет в процедуре Рабина — Карпа при поиске Р = 26 в тексте Т = 3141592653589793, если в качестве модуля 0 выбрано значение 11? 32.2.2 Как можно обобщить метод Рабина-Карпа для задачи поиска в текстовой строке одного из lс заданных образцов? Начните с предположения о том, что все й об- 104/ Гаааа 92.
Поиск оодстрок разцов имеют одинаковую длину. Затем обобщите решение таким образом, чтобы в нем учитывалась возможность того, что образцы могут быть разной длины. 32.2.3 Покажите, как обобщить метод Рабина — Карпа, чтобы он позволял решать задачу поиска заданного образца размером пз х т в символьном массиве размером и х и. (Образец можно сдвигать по вертикали и по горизонтали, но нельзя вращать.) 32.2с4 Алиса располагает копией длинного и-битового файла А = (а„1, а„з,..., ас), а Борис — копией и-битового файла В = (Ь„1, Ь„з,..., Ьо). Алиса и Борис захотели узнать, идентичны ли их файлы.
Чтобы не передавать весь файл А или файл В, они используют описанную ниже быструю вероятностную проверку. Совместными усилиями они выбирают простое число д > 1000п, а затем случайным образом выбирают целое число х из множества (О, 1,..., »1 — 1). После этого Алиса вычисляет значение и — 1 А(х) = ~~» а»х» шо»1 4 »=О а Борис — соответствующее значение В(х). Докажите, что если А ~ В, то имеется не более одного шанса из 1000, что А(х) = В(х), а если файлы одинаковы, то величины А(х) и В(х) также обязательно совпадут.
(Указание» см. упр. 31.4.4.) 32.3. Поиск подстрок с помощью конечных автоматов Многие апгоритмы поиска подстрок начинают выполнение работы с того, что строят конечный автомат — простую машину для обработки информации, — который сканирует строку текста Т, выполняя поиск всех вхождений в нее образца Р. В этом разделе представлен метод построения такого автомата. Подобные автоматы для поиска подстрок очень эффективны: они проверяют каждый символ текста ровно ло одному раз»», затрачивая на каждый символ фиксированное количество времени. Поэтому после предварительной обработки образца для построения автомата время, необходимое для поиска, равно О(п).
Однако время построения автомата может оказаться значительным, если алфавит Е большой. В разделе 32.4 описан остроумный способ решения этой задачи. В начале этого раздела дадим определение конечного автомата. Затем мы познакомимся со специальными автоматами, предназначенными для поиска подстрок, и покажем, как с их помощью можно найти все вхождения образца в текст.
Наконец будет показано, как сконструировать автомат поиска подстрок для заданного входного образца. Чесме РП. Избранные темы Конечные автоматы Конечный автаиат М, проиллюстрированный на рис. 32.6, представляет собой кортеж из пяти значений (Я, оо, А, Е, 6), где Я вЂ” конечное множеспю состояний; ое ŠΠ— начальное состояние; А С (г — множество различных доиускаюи(их состояний; Š— конечный входной алфавит; 6 — функция, отображающая Я х Е в Я и называемая функцией иервзздов автомата М. Вначале конечный автомат находится в состоянии оо и считывает символы входной строки по одному. Если автомат находится в состоянии о и считывает входной символ а, он совершает переход из состояния о в состсанне 6(о, а). Если текущее состояние о является членом А, то машина М принимает, или допускает (ассергег(), строку, считанную к зтому моменту.
Не принятые входные данные являются отвергнутыми (ге)ес(ег(). С конечным автоматом М связана функция ф, которая называется функцией конечного состояния (Йпа( з(а(е йтпсноп) и отображает множество Е' на множество (,), так, что значение ф(ш) представляет собой состояние, в котором оказывается автомат М после сканирования строки ш. Таким образом, М принимает строку ш тогда и только тогда, когда ф(ш) Е А. Функция ф определяется следуюшим рекурреитным соотношением с использованием функции переходов: Ф(е) = Чо, ф(ша) =6(ф(ш),а) для ш 6 Е*,об Е. Вход Состояние а Ь 'Н (а) (б) Рнс. 32.6.
Простой конечный автомат с двумя состояниями Я = [О, 1), начальным состоянием ао = 0 и входным алфавитам е = (а,ь). (в) табличное представление функции перехацов 6. (б) Эквивалентная диаграмма состояний. Состояние 1, показанное черным цветом, — единственное допускающее аостаяние. Переищы прелспюлены ориентированными ребрами. Например, ребро, ведущее из состояния 1 в состояние О и обозначенное меной Ь, указывает, что Б(1, Ь) = О. Рассматриваемый автомат принимает те строки, мпорые оканчиваются нечетным количеством символов а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
