Алгоритмы - построение и анализ (1021735), страница 211
Текст из файла (страница 211)
Такое тестирование можно осуществить путем явной проверки условия Р [1..т] = Т [з + 1..з + т]. Если значение д достаточно большое, то можно надеяться, что ложные совпадения встречаются довольно редко и стоимость дополнительной проверки окажется низкой. Сформулированная ниже процедура поясняет описанные выше идеи. В роли входных значений для нее выступает текст Т, образец Р, разряд д (в качестве значения которого обычно выбирается ]Е[) и простое число д.
Клинч Клкг Млт~нпк(Т, Р, с(, д) 1 и — 1еидй[Т] 2 т — 1еидЯР] 3 й (Р' з шог(д 4 р+-О 5 го+- О 6 1ог 1 — 1 то т ~> Предварительная обработка 7 бор -(Ир+Р[г]) пюд д 8 Фо — (Жо+ Т[1]) шой д 9 1ог з — О 1о и — т 1> Проверка бо11'р=е, 11 тйеп 11' Р[1 .. т] = Т[в + 1 .. з + т] 12 Феп рпп1 "Образец обнаружен при сдвиге" з 13 Ыз(и — т 14 гйеп 1,+~ - (с((1, — Т[з+ 1]6) + Т[з+ т+ 1]) пюс1 д Опишем работу процедуры Клв1м Клкг Млтснлк. Все символы интерпретируются как цифры в системе счисления по основанию д.
Индексы переменной 1 приведены для ясности; программа будет правильно работать и без них. В строке 3 переменной 6 присваивается начальное значение, равное цифре, расположенной в старшем разряде т-цифрового текстового окна. В строках 4-8 вычисляется значение р, равное Р [1..т] шос1 д, и значение 1о, равное Т [1..т] пюб д. В цикле 1ог в строках 9-14 производятся итерации по всем возможным сдвигам з.
При этом сохраняется сформулированный ниже инвариант. 1027 Глава 32. Поиск подстрок При каждом выполнении строки 1О справедливо соотношение 1, = = Т[а + 1 .. з + т[.шой д. Если в строке 10 выполняется условие р = 8, ("совпадение"), то в строке 11 проверяется справедливость равенства Р [1..гп] = Т [а + 1..э + т[, чтобы исключить ложные совпадения.
Все обнаруженные допустимые сдвиги выводятся в строке 12. Если а < п — гп (это неравенство проверяется в строке 13), то цикл 1ог нужно будет выполнить хотя бы еще один раз, поэтому сначала выполняется строка 14, чтобы гарантировать соблюдение инварианта цикла, когда мы снова перейдем к строке 1О. В строке 14 на основании значения 1, той д с использованием уравнения (32.2) в течение фиксированного интервала времени вычисляется величина 1,+~ щой д. В процедуре КАшх КАкг МАтснлк на предварительную обработку затрачивается время 0(т), а время сравнения в нем в наихудшем случае равно 9((п — т+ 1) т), поскольку в алгоритме Рабина-Карпа (как и в простейшем алгоритме поиска подстрок) явно проверяется допустимость каждого сдвига. Если Р = а и Т = а", то проверка займет время 6 ((п — т+ 1) т), поскольку все п — гп + 1 возможных сдвигов являются допустимыми.
Во многих приложениях ожидается небольшое количество допустимых сдвигов (возможно, выражающееся некоторой константой с); в таких приложениях математическое ожидание времени работы алгоритма равно сумме величины О ((п — гп+ 1) + ст) = О (и+ т) и времени, необходимого для обработки ложных совпадений. В основу эвристического анализа можно положить предположение, что приведение значений по модулю о действует как случайное отображение множества Е' на множество Ея. (См. в разделе 11.3.1 обсуждение вопроса об использовании операции деления для хеширования. Сделанное предположение трудно формализовать и доказать, хотя один из многообещающих подходов заключается в предположении о случайном выборе числа д среди целых чисел подходящего размера. В этой книге такая формализация не применяется.) В таком случае можно ожидать, что число ложных совпадений равно 0 (п/д), потому что вероятность того, что произвольное число Ф, будет эквивалентно р по модулю о, можно оценить как 1/д.
Поскольку имеется всего 0 (п) позиций, в которых проверка в строке 10 дает отрицательный результат, а на обработку каждого совпадения затрачивается время 0 (т), математическое ожидание времени сравнения в алгоритме Рабина-Карпа равно О (п) + О (т (и + п/д)), где и — количество допустимых сдвигов. Если и = 0 (1), а о выбрано так, что д > т, то приведенное выше время выполнения равно 0(п). Другими словами, если математическое ожидание количества допустимых сдвигов мало (О (1)), а выбранное простое число д превышает длину образца, то можно ожидать, Часть ЧП.
Избранные темы 1028 что для выполнения фазы сравнения процедуре Рабина-Карпа потребуется время 0 (и +т). Поскольку т < и, то математическое ожидание времени сравнения равно 0 (и). Упражнения 322-1. Сколько ложных совпадений произойдет в процедуре Рабина-Карпа в случае текста Т = 3141592653589793, образца поиска Р = 26, а в качестве модуля д выбрано значение 11? 32.2-2. Как можно было бы обобщить метод Рабина-Карпа для задачи поиска в текстовой строке одного из Й заданных образцов? Начните с предположения, что все й образцов имеют одинаковую длину.
Затем обобщите решение таким образом, чтобы в нем учитывалась возможность того, что образцы могут быть разной длины. 32.2-3. Покажите, как обобщить метод Рабина-Крапа, чтобы он позволял решать задачу поиска заданного образца размерами т х т в символьном массиве размером и х и. (Образец можно сдвигать по вертикали и по горизонтали, но его нельзя вращать.) 32.2-4.
Алиса располагает копией длинного и-битового файла А = (а„1, а„ж ...,ао), а Борис — копией и-битового файла В = (5„1, Ьи з,...,5в). Алиса и Борис захотели узнать, идентичны ли их файлы. Чтобы не передавать весь файл А или файл В, они используют описанную ниже быструю вероятностную проверку Совместными усилиями они выбирают простое число д ) 1000и, а затем случайным образом выбирают целое число х из множества (О, 1,..., д — 1).
После этого Алиса вычисляет значение и — 1 А (х) = ,'1 а;х' шос1 9, 1=0 а Борис — соответствующее значение В(х). Докажите, что если А Р' ~ В, то имеется не более одного шанса из 1000, что А(х) = В(х), а если файлы одинаковы, то величины А (х) и В (х) также обязательно совпадут. (Указание: см. упражнение 31.4-4.) 32.3 Поиск подстрок с помощью конечных автоматов Многие алгоритмы поиска подстрок начинают с того, что строят конечный автомат, который сканирует строку текста Т, отыскивая все вхождения в нее образца Р. В этом разделе представлен метод построения такого автомата. Подобные Глава 32.
Поиск подстрок 1029 автоматы для поиска подстрок очень эффективны: они проверяют каждый символ текста ровно но одному разу, затрачивая на каждый символ фиксированное количество времени. Поэтому после предварительной обработки образца для построения автомата, время, необходимое для поиска, равно 6(п). Однако время построения автомата может оказаться значительным, если алфавит Е большой. В разделе 32А описан остроумный способ решения этой задачи.
В начале этого раздела дадим определение конечного автомата. Затем ознакомимся со специальными автоматами, предназначенными для поиска подстрок, и покажем, как с их помощью можно найти все вхождения образца в текст. Материал включает детальное описание имитации поведения автомата поиска подстрок при обработке текста. Наюнец, будет показано, как сконструировать автомат поиска подстрок для заданного входного образца. Конечные автоматы Конечный автомат (бш1е ап1оша1оп) М вЂ” это пятерка (Я, 9о, А, Е, б), где ° Я вЂ” юнечное множество состояний (з1айез), ° 9о ŠΠ— начальное состояние (зйазт МаГе), ° А С Я вЂ” конечное множество донустимых состояний (ассер11пя зсасез), ° Š— конечный входной алфавит (шрш а1рЬаЬе1), ° б — функция, которая отображает множество Я х Е на множество Я и называется функцией яереходов (1галябоп йпс11ол) автомата М.
Вначале конечный автомат находится в состоянии оо и считывает символы входной строки один за другим. Если автомат находится в состоянии д и считал входной символ а, то автомат переходит из состояния 9 в состояние б (д, а). Если текущее состояние д является членом множества А, то говорят, что машина М допускает (ассер1еб) считанную строку. Если же д (е А, то входные данные называют отвергнутыми (ге)есгед). Эти определения проиллюстрированы на рис. 32.5 на простом примере автомата с двумя состояниями.
В части и этого рисунка приведено табличное представление функции переходов Б. В части б изображена эквивалентная диаграмма состояний. Состояние 1 — единственное допустимое состояние (оно показано черным цветом). Переходы представлены ориентированными ребрами. Например, ребро, ведущее из состояния 1 в состояние О, которое обозначено меткой Ь, указывает, что б (1, Ь) = О. Рассматриваемый автомат допускает те строки, которые оканчиваются нечетным количеством символов а. Точнее говоря, строка х воспринимается тогда и только тогда, когда х = у-., где у = е или строка у оканчивается символом Ь, и г = а", где lс — нечетное.
Например, последовательность состояний, которые проходит этот автомат для входной строки аЬааа (включая начальное состояние), имеет вид (О, 1, О, 1, О, 1)„так что входная Часть Ч!1. Избранные темы 1030 Вход Состояние а ь Рис. 32.5. Простой автомат с двумя состояниями: Я = (О, 1), оо = О, Е = (а, Ь) строка воспринимается. Если входная строка имеет вид аЬЬаа, то автомат проходит последовательность состояний (О, 1, О, О, 1, О), поэтому такая входная строка отвергается.
С конечным автоматом М связана функция ф, которая называется функцией конечного состояния (бпа1 зсаге йтпсбоп) и которая отображает множество Е' на множество ф Значение ф (хо) представляет собой состояние, в котором оказывается автомат М после прочтения строки то. Таким образом, М допускает строку то тогда и только тогда, когда ф(хе) е А. Функция ф определяется следующим рекурреитным соотношением: ф(е) =д ф(хна) = б (ф (и), а) для се Е Е', а Е Е. Автоматы поиска подстрок Для каждого образца Р существует свой автомат поиска подстрок; его необходимо сконструировать по образцу на этапе предварительной обработки, чтобы впоследствии его можно было использовать для поиска текстовой строки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
