Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 211
Текст из файла (страница 211)
В строке 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 зсаге йтпсбоп) и которая отображает множество Е' на множество ф Значение ф (хо) представляет собой состояние, в котором оказывается автомат М после прочтения строки то. Таким образом, М допускает строку то тогда и только тогда, когда ф(хе) е А. Функция ф определяется следующим рекурреитным соотношением: ф(е) =д ф(хна) = б (ф (и), а) для се Е Е', а Е Е.
Автоматы поиска подстрок Для каждого образца Р существует свой автомат поиска подстрок; его необходимо сконструировать по образцу на этапе предварительной обработки, чтобы впоследствии его можно было использовать для поиска текстовой строки. Процесс такого конструирования для образца Р = аЬабаса проиллюстрирован на рис. 32.6. С этого момента предполагается, что образец Р— это заданная фиксированная строка: для краткости мы будем опускать в обозначениях зависимость от Р. Чтобы создать автомат поиска подстрок, соответствующий заданному образцу Р [1..тл], сначала определим вспомогательную функцию о, которая называется суффиксной функцией (зпщх гппспол), отвечающей образцу Р.
Функция о является отображением множества Е' на множество (О, 1,..., т), таким что величина о (х) равна длине максимального префикса Р, который является суффиксом строки х: о (х) = шах(к: Рь 1х). Суффиксная функция о вполне определена, поскольку пустая строка Ро —— е является суффиксом любой строки. В качестве примера рассмотрим образец вида 1032 Часть Ч11. Избранные темы суффикса Т;, который одновременно является префиксом образца Р. Если следующим сканируемым символом является символ Т [1+ 1] = а, то машина должна осуществить переход в состояние сг (Т+~) = о (Тга).
Из доказательства этой теоремы видно, что и (Тга) = <т (Рта). Другими словами, чтобы вычислить количество символов в самом длинном суффиксе Т;а, юторый является префиксом образца Р, можно найти самый длинный суффикс Рца, юторый является префиксом Р. На каждом этапе машине нужна информация о длине самого длинного префикса Р, который является суффиксом считанной до сих пор строки. Таким образом, если положить 6 (д, а) = и (Рда), то будет поддерживаться нужный инвариант (32.4). Вскоре это неформальное пояснение будет изложено в более строгой форме. Например, в автомате поиска подстрок, представленном на рис. 32.6, 6 (5, Ь) = = 4.
Этот переход осуществляется потому, что если автомат считывает символ Ь, находясь в состоянии 11 = 5, то РяЬ = аЬаЬаЬ, и самый длинный префикс образца Р, совпадающий с суффиксом строки аЬаЬаЬ вЂ” Ря = аЬаЬ. Рассмотрим рис. 32.6 подробнее. В части а приведена диаграмма состояний для автомата поиска подстрок, который воспринимает все строки, оканчиваюшиеся строкой аЬаЬаса. Состояние Π— начальное, а состояние 7 (оно выделено черным цветом) — единственное допустимое состояние. Ориентированные ребра, направленные от состояния 1 в состояние 7' и обозначенные меткой а, представляют значение функции б (г, а) = т1 Ребра, направленные вправо, которые образуют "хребет" автомата и выделены на рисунке жирными линиями, соответствуют точным совпадениям образца и входных символов. Ребра, направленные влево, соответствуют несовпадениям.
Некоторые ребра, соответствующие несовпадениям, не показаны; в соответствии с соглашением, если для некоторого символа а Е Е у состояния 4 отсутствуют исходящие ребра с меткой а, то 6 (1, а) = О. В части б представлена соответствующая функция переходов б, а также строка образца Р = аЬаЬаса. Элементы, соответствующие совпадениям между образцом и входными символами, выделены серым цветом. В части в проиллюстрирована обработка автоматом текста Т = аЬаЬаЬасаЬа. Под каждым символом текста Т [г) указано состояние ф (Т;), в котором находится автомат после обработки префикса Т;. Образец встречается в тексте один раз, причем совпадающая подстрока оканчивается на девятой позиции.
Чтобы пояснить работу автомата, предназначенного для поиска подстрок, приведем простую, но эффективную программу для моделирования поведения такого автомата (представленного функцией переходов 6) при поиске образца Р длиной гп во входном тексте Т [1..п[. Как и в любом другом автомате поиска подстрок, предназначенном для образца длиной т, множество состояний Я имеет внд (О, 1,..., тл), начальное состояние имеет индекс О, а единственным допустимым является состояние т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
