Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 210
Текст из файла (страница 210)
В алгоритме Рабина-Карпа время 6 (т) затрачивается на предварительную обработку, а время его работы в наихудшем случае равно Э ((и — т + 1) т). Однако с учетом определенных предположений удается показать, что среднее время работы этого алгоритма оказывается существенно лучше. Глава 32. Поиск подстрок 1023 В этом алгоритме используются обозначения из элементарной теории чисел, такие как эквивалентность двух чисел по модулю третьего числа. Соответствующие определения можно найти в разделе 31.1.
Для простоты предположим, что Е = (О, 1,..., 9), т.е. каждый символ — это десятичная цифра. (В общем случае можно предположить, что каждый символ— это цифра в системе счисления с основанием г(, где с( = [Е[.) После этого строку из гс последовательных символов можно рассматривать как число длиной Й. Таким образом, символьная строка 31415 соответствует числу 31415. При такой двойной интерпретации входных символов и как графических знаков, и как десятичных чисел, в этом разделе удобнее подразумевать под ними цифры, входяшие в стандартный текстовый шрифт.
Для заданного образца Р [1..т] обозначим через р соответствующее ему десятичное значение. Аналогично, для заданного текста Т [1 ..и] обозначим через г, десятичное значение подстроки Т [в + 1..з+ т] длиной т при з = О, 1,..., и— — т. Очевидно, что 8, = р тогда и только тогда, когда Т [в + 1..з + т] = Р [1..т]; таким образом, в — допустимый сдвиг тогда и только тогда, когда (я = р. Если бы значение р можно было вычислить за время О (т), а все значения Ф, — за суммарное время 6 (и — т+ 1)', то значения всех допустимых сдвигов можно было бы определить за время 6 (ги) + О (и — т+ 1) = О (и) путем сравнения значения р с каждым из значений 8в.
(Пока что мы не станем беспокоиться по поводу того, что величины р и зв могут оказаться очень большими числами.) С помощью правила Горнера (см. раздел 30.1) величину р можно вычислить за время 6 (т): р= Р[т]+10(Р[т — Ц+10(Р[т — 2]+ .+10(Р[2]+10Р[Ц) )). Значение го можно вычислить из массива Т[1..т] за время О(т) аналогичным способом. Чтобы вычислить остальные значения 8д,гз,...,г„за время О (и — т), достаточно заметить, что величину 1в+1 можно вычислить из величины 1, за фиксированное время, так как ьвч з = 10(с, — 10~ Т[в+ Ц) +Т[з+т+ Ц.
(32.1) Например, если т = 5 и Фв = 31415, то нужно удалить цифру в старшем разряде Т [в + Ц = 3 и добавить новую цифру в младший разряд (предположим, это цифра Т [в + 5 + Ц = 2). В результате мы получаем 8+з = 10 (31415 — 10000 3) + 2 = = 14152. 'Мы используем запись 9 (и — т+ 1) вместо 9 (и — т), поскольку всего имеется и — т+ 1 различных значений, которые может принимать величина а. Слагаемое "+1" важно в асимптотическом смысле, поскольку при т = п для вычисления единственного значения г, требуется время 9 (1), а не В (О) .
1024 Часть Ч11. Избранные темы Чтобы удалить из числа 1, цифру старшего разряда, из него вычитается значение 10 'Т [в + 1]; путем умножения на 10 число сдвигается на одну позицию влево, а в результате добавления элемента Т [в + т + 1] в его младшем разряде появляется нужная цифра. Если предварительно вычислить константу 10"' ~ (с помощью методов, описанных в разделе 31.б, это можно сделать в течение времени О (1кт), хотя для данного приложения вполне подойдет обычный метод, требующий времени О (т)), то для каждого вычисления результатов выражения (32.1) потребуется фиксированное количество арифметических операций.
Таким образом, число р можно вычислить за время 6 (т), величины $о, уы..., 1„,„— за время О (и — т+ 1), а все вхождения образца Р [1..т] в текст Т [1..и] можно найти„затратив на фазу предварительной обработки время 6 (т), а на фазу сравнения — время 6 (и — т + 1). Единственная сложность, возникающая в этой процедуре, может быть связана с тем, что значения р и Ф, могут оказаться слишюм большими и с ними будет неудобно работать. Если образец Р содержит т символов, то предположение о том, что каждая арифметическая операция с числом р (в юторое входит т цифр) занимает "фиксированное время'*, не отвечает действительности.
К счастью, эта проблема имеет простое решение (рис. 32.4): вычислять значения р и 1, по модулю некоторого числа а. Поскольку вычисление величин р, со и рекуррентного соотношения (32.1) можно производить по модулю д, получается, что величина р по модулю су вычисляется за время О (т), а вычисление всех величин с, по модулю д — за время 6 (и — т + 1). В качестве модуля д обычно выбирается такое простое число, для которого длина величины 104 не превышает длины юмпьютерного слова. Это позволяет производить все необходимые вычисления с помощью арифметических операций с одинарной точностью. В общем случае, если имеется су-символьный алфавит (О, 1,..., сУ вЂ” 1), значение д выбирается таким образом, чтобы длина величины йу не превышала длины компьютерного слова, и чтобы с рекуррентным соотношением (32.!) было удобно работать по модулю д.
После этого рассматриваемое соотношение принимает вид с,+с = (сУ (~, — Т [в + 1] Ус) + Т [в + т + 1]) пюс1 <у, (32.2) где й = с1 ' (псосЬу) — значение, которое приобретает цифра "1", помещенная в старший разряд т-цифрового текстового окна. Работа алгоритма Рабина-Карпа проиллюстрирована на рис. 32.4. Каждый символ здесь представлен десятичной цифрой, а вычисления производятся по модулю 13. В части а приведена строка текста. Подстрока длиной 5 символов выделена серым цветом.
Находится численное значение выделенной подстроки по модулю 13, в результате чего получается значение 7. В части б изображена та же текстовая строка, в юторой для всех возможных 5-символьных подстрок вычислены соответствующие им значения по модулю 13. Если предположить, что образец имеет вид Р = 31415, то нужно найти подстроки, которым соответствуют значения 7 по модулю 13, поскольку Глава 32. Поиск подстрок 1025 ма!1', 1 0 0 4 '.
0 0 3 0 10 !1 !0 !0 14 !5 !6 !0 !5 !0 10 1! 15 0 (0 1~0 !3 !! !4 !1 )5 !2 б !" !3 0 .0 !1 аюа !.! ж. у . .. у . . у.. 14лнн ег Лаяаиг Сиамским СОВП04апаг 0! Рис. 32.4. Алгоритм Рабина-Карпа 81415 = — 7(шод13). Найдены две такие подстроки; они выделены серым цветом.
Первая подстрока, которая начинается в тексте на позиции 7, действительно совпадает с образцом, в то время как вторая, которая начинается на позиции 13, представляет собой т.н. ложное совпадение. В части в показано, как в течение фиксированного времени вычислить значение, соответствующее данной подстроке, по значению предыдущей подстроки. Значение, соответствующее первой подстроке, равно 31415. Если отбросить цифру 3 в старшем разряде, произвести сдвиг числа влево (умножение на 10), а затем добавить к полученному результату цифру 2 в младшем разряде, то получим новое значение 14152.
Однако все вычисления производятся по модулю 13, поэтому для первой подстроки получится значение 7, а для второй — значение 8. С000иа !Ьваа сиропа ал:и мак МЯ'Яа пгоггз ! ', Г;",', Ггl:, ! '.1.'.' С:г40:0! 1!Оил! 4 2наий ыллиаай разри! сиги400г гзпрга !41гг .—.,5!4!5 - 1.
!а0001. 10 0 п0 10 15! ь: !0 ! !! !0 ' ' Мм0 !!! 0 1иа0 !5! 1026 Часть 711. Избранные темы Итак, как видим, идея работы по модулю д не лишена недостатков, поскольку из 1,: — р (пюйд) не следует, что 1, = р. С другой стороны, если 1, фр (щось), то обязательно выполняется соотношение 1, ф р и можно сделать вывод, что сдвиг з недопустимый. Таким образом, соотношение 1,:— р (шос1д) можно использовать в качестве быстрого эвристического теста, позволяющего исключить недопустимые сдвиги з. Все сдвиги, для которых справедливо соотношение г, = р (шобд), необходимо подвергнуть дополнительному тестированию, чтобы проверить, что действительно ли сдвиг з является допустимым, или это просто ложное совладение (арапов 1пг).
Такое тестирование можно осуществить путем явной проверки условия Р [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О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
