Алгоритмы - построение и анализ (1021735), страница 210
Текст из файла (страница 210)
Часть Ч11. Избранные тены 1022 32.1-2. Предположим, что в образце Р все символы различны. Покажите, кяя ускорить процедуру Ымче Бтн1нп МАтснен, чтобы время ее выполнения при обработке и-символьного текста Т было равно О (и). 32.1-3. Предположим, что образец Р и текст Т вЂ” строки длиной т и п соответственно, случайно выбранные из с(-символьного алфавита Ев = = 10, 1,..., с( — 1), где д > 2. Покажите, что математическое ожидание количества сравнений одного символа с другим, производимых в неявном цикле в строке 4 простейшего алгоритма, во всех итерациях этогь цикла равно 1 — 1а (и — т+1) < 2(и — т+1). (Предполагается, что в простейшем алгоритме сравнение символов дяя данного сдвига прекращается, как только будет обнаружено несовпадение или совпадет весь образец.) Таким образом, для случайных строя простейший алгоритм вполне эффективен.
32.1-4. Предположим, в образце Р может содержаться символ пробела (яар сЬагасгег) О, который может соответствовать произвольной строке (даже нулевой длины). Например, образец аЬОЬафс встречается в тексте саЬссЬасЬасаЬ как с а6 сс Ьа сЬа с а6 аь О ьа О с и как с а6 ссЬас Ьа с аЬ. аь О ь О с Заметим, что в образце символ пробела может встречаться произвольное количество раз, но предполагается, что в тексте он не встречается вообще.
Сформулируйте алгоритм с полиномиальным временем работы, определяющий, встречается ли заданный образец Р в тексте Т, и проведите анализ времени его работы. 32.2 Алгоритм Рабина-Карпа Рабин (ВаЬ(п) и Карп (Кагр) предложили алгоритм поиска подстрок, показывающий на практике хорошую производительность, а также допускающий обобщения на другие родственные задачи, такие как задача о сопоставлении двумерного образца. В алгоритме Рабина-Карпа время 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) можно производить по модулю 4, получается, что величина р по модулю су вычисляется за время О (т), а вычисление всех величин с, по модулю д — за время 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 аюа !.! "г У... У .. 7.. 14лнн ег Лемме СОИИОИ1ИИ СОВП04апаг 0! Рис. 32.4. Алгоритм Рабина-Карпа 81415 = — 7(шод13). Найдены две такие подстроки; они выделены серым цветом. Первая подстрока, которая начинается в тексте на позиции 7, действительно совпадает с образцом, в то время как вторая, которая начинается на позиции 13, представляет собой т.н. ложное совпадение. В части в показано, как в течение фиксированного времени вычислить значение, соответствующее данной подстроке, по значению предыдущей подстроки.
Значение, соответствующее первой подстроке, равно 31415. Если отбросить цифру 3 в старшем разряде, произвести сдвиг числа влево (умножение на 10), а затем добавить к полученному результату цифру 2 в младшем разряде, то получим новое значение 14152. Однако все вычисления производятся по модулю 13, поэтому для первой подстроки получится значение 7, а для второй — значение 8. С000иа !Ьваа сиропа ал:и мак МЯ'Яа пгоггз 1~!!! ' !! ! 1 ! ', Г;",', Гг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пг).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
