Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 228
Текст из файла (страница 228)
Покажите, что магпеиапгическое ожидание количества сравнений одного символа с другим, выполняемых в неявном цикле в строке 4 простейшего алгоритма, во всех итерациях этого цикла равно сл-оа (и — т+ 1) ( 2(п — т+ 1) 1 — д г (Предполагается, что в простейшем алгоритме сравнение символов для данного сдвига прекращается, как только будет обнаружено несовпадение или совпадет весь образец.) Таким образом, для случайных строк простейший алгоритм достаточно эффективен. 32.1.4 Предположим, что в образце Р может содержаться специальный символ пробева (дар сЬагасгег) О, который может соответствовать произвольной строке (даже нулевой длины).
Например, образец аЬ<~Ьафс встречается в тексте саЬссЬасЬасаЬ как с аЬ сс Ьа сЬа с аЬ аЬ О Ьа О с и как с аЬ ссЬас Ьа с аЬ . аь О ьа О с Заметим, что в образце символ пробела может встречаться произвольное количество раэ, но предполагается, что в тексте он не встречается вообще. Разработайте !Озб Часть )гл. Избранные темы алгоритм с полиномиальным временем работы, определяющий, встречается ли заданный образец Р в тексте Т, и проанализируйте время его работы. 32.2.
Алгоритм Рабина — Карпа Рабин (КаЪ(п) и Карп (Каур) предложили алгоритм поиска подстрок, показывающий на практике хорошую производительность, а также допускающий обобщения на другие родственные задачи, такие как задача о сопоставлении двумерного образца.
В алгоритме Рабина-Карпа время 0(т) затрачивается на предварительную обработку, а время его работы в наихудшем случае оказывается равным Е)((тз — т+ 1)тл). Однако с учетом определенных предположений удается показать, что среднее время работы этого алгоритма существенно лучше. В этом алгоритме используются обозначения из элементарной теории чисел, такие как эквивалентность двух чисел по модулю третьего числа. Соответствующие определения можно найти в разделе 31.1.
Для простоты предположим, что Е = (О, 1, 2,..., 9), т.е. что каждый символ представляет собой десятичную цифру. (В общем случае можно предположить, что каждый символ — зто цифра в системе счисления с основанием г(, где г1 = [Е].) Теперь строку из lс последовательных символов можно рассматривать как десятичное число из и цифр.
Таким образом, символьная строка 31415 соответствует числу 31415. При такой двойной интерпретации входных символов и как графических знаков, и как десятичных цифр в этом разделе удобнее обозначать их цифрами, входящими в стандартный текстовый шрифт. Для заданного образца Р[1 .. тп] обозначим через р соответствующее ему десятичное значение. Аналогично для заданного текста Т[1 .. и] обозначим через (, десятичное значение подстрок Т[п + 1 ..
з+ т] длиной т при а = О, 1,..., п — тп. Очевидно, что 8, = р тогда и только тогда, когда Т[з + 1 .. з + т] = Р[1 .. т]; таким образом, и — допустимый сдвиг тогда и только тогда, когда т, = р. Если бы значение р можно было вычислить за время (В(т), а все значения бл — за суммарное время тВ(п — т + 1) ', то значения всех допустимых сдвигов можно было бы определить за время ~Э(т) + Е)(п — т + 1) = Е)(п) путем сравнения значения р с каждым из значений бл. (Пока что мы не станем беспокоиться по поводу того, что величины р и (, могут оказаться очень большими числами.) С помощью правила Горнера (см.
раздел 30.1) величину р можно вычислить за время (Э(тл): р = Р[т] + 10 (Р[т — 1] + 10(Р~тп — 2] + + 10(Р[2] + 10Р[1]) .. )) . Аналогично го можно вычислить из Т[1 .. т] за то же время Е)(т). Мы используем запись сг(п — гп + 'з) вместо гз(п пз), поскольку всего имеется и гп -~- 'г различнык значений, которые может принимать величина а. Слагаемое *'-Ь Г' вмкно в асимптотичсском смысзгс, поскольку при пг = и для вычисления единственного значения е, требуется время Щ1), а не сг(О).
!037 Глава 32. Поиск иодсмрок Чтобы вычислить остальные значения 8ы1з,..., 8„за время Й(п — т), заметим, что величину 1,.и1 можно вычислить из величины 1, за константное время, так как 1,.с1 = 10(1, — 10~ 1Т[я+ Ц) + Т[я+ т+ Ц . (32.1) Вычитание 10 'Т[я+ Ц удаляет старшую цифру из 1„умножение полученного результата на 10 сдвигает число влево на один десятичный разряд, а добавление Т[я + т+ Ц вносит в него соответствующую младшую цифру. Например, если т = 5 и 1, = 31415, то необходимо удалить старшую цифру Т[я + Ц = 3 и добавить новую младшую цифру (предположим, зто Т[я + 5 + Ц = 2), чтобы получить 1,~.1 = 10(31415 — 10000 3) + 2 = 14152 . Если предварительно вычислить константу 10~ ' (с помощью методов, описанных в разделе 31.6, это можно сделать в течение времени 0(1к т), хотя для данного приложения вполне подойдет обычный метод, требующий времени 0(т)), то для каждого вычисления результатов выражения (32.1) потребуется фиксированное количество арифметических операций.
Таким образом, число р можно вычислить за время 6(т), величины 1о, 1ы..., 1„— за время 9(п — т + 1), а все вхождения образца Р[1 .. т] в текст Т[1 ., и] можно найти, затратив на фазу предварительной обработки время 9(т), а на фазу сравнения — время В(п — т + 1). Единственная сложность, возникающая в зтой процедуре, может быть связана с тем, что значения р и 1, могут оказаться слишком большими и с ними будет неудобно работать.
Если образец Р содержит т символов, то предположение о том, что каждая арифметическая операция с числом р (в которое входит т цифр) занимает "фиксированное время", не отвечает действительности. К счастью, эта проблема имеет простое решение (рис. 32.5): вычислять значения р и 1„ по модулю некоторого числа д.
Значение р по модулю д можно вычислить за время 9(т), а все значения 1, по модулю д — за время Е1(п — т + 1). Если выбрать в качестве значения л такое простое число, что 104 помещается в компьютерное слово, то все необходимые вычисления можно выполнить с использованием арифметики одинарной точности. В общем случае, если имеется с(-символьный алфавит (0,1,...,4 — 1), значение с7 выбирается таким образом, чтобы величина Й1 помещалась в компьютерное слово, и рекуррентное соотношение (32.1) исправляется так, чтобы оно работало по модулю д, т.е. записываем его в виде 1,~.1 = (с((1, — Т[я+ Ц7с) + Т[я+ т+ Ц) шос) д, (32.2) где 6: — 4 ' (шос) 4) — значение цифры "1" в старшем разряде окна размером гп цифр.
Однако решение работать по модулю д не лишено недостатков, поскольку из 1,: — р (|нос) 4) не следует, что 1, = р. С другой стороны, если 1, ф р (шос) д), то, определенно, выполняется соотношение 1, ф р, так что сдвиг я недопустимый. Таким образом, проверку 1,: — р (шос) ц) можно использовать в качестве )038 Часть 775 Иэбраллме теми ~ 2 ~ 3 , ,'5: 9! 0 2 ~ 3"; 1 ' 4 ( 1;) 5 ~ 2 ~ 5 ~ 7 ~ 3' ,9: 9 , '2: 1,, п 113 Е.' '~ (а) г э э 4 э б 7 а 9 10 ы 1э гэ 14 1э 16 17 га 19 2, 3, 5! 9 , '0 ' 2 1:3 'г".Г~.:4",71'с 5., 2 (бэ(7(г 3';:)'9'(79) 2! 1; пюб 13 (8! 9, :3! 11~ О! 1 '',.7) 8! 4 ~ 5; 10'11(7-'„'' 9,11! Истинное )йвкное (б) Старый Новый ста(илий младший рюр л Сдвиг рмр л 14152 и (3141 5 — 3 10000) 10 + 2 (пкгд 13) и (7-3.3) 10+2 (шо413) и 8 (пкх) 13) (в) Рис.
31.5. Алгоритм Рабина-Карпа. Кюкдый символ представляет собой десятичную цифру, а вычисления проводятся по модулю 13. (а) Текстовая строка. Окно длиной 5 вылелено серым цвеюм. Выполняется поиск численного значения выделенной подстроки по мшйспо 13, в результате чего получается значение 7. (6) Та ~ке текстовая строка, в которой для всех возможных 5-символьных подстрок вычислены соответствующие им значения по модушо 13. Если предположить, что образец имеет внд Р = 31415, то нужно найти подстроки, которым соответствуют значения 7 по модулю 13, посмшьку 31415 и 7 (пюг( 13).
Алгоритм находит два тюшх окна, выделеииьгх серой штриховкой. Первое, начинающееся в текстовой позиции 7, действительно представляет собой обратен. в то время кек второе, начинающееся с позиции 13, является лгекным совпадением. (в) Кех в течение фиксированного времени вычислить значение, соответствующее заданному окну, по эна. чению предыдущего окна. Значение, соответствующее первому окну, равно 31415. Если отбросить цифру 3 в старшем разряде, выполнить сдвиг числа влево (умножить его на 10), а затем добавить к результату цифру 2 в младшем разряде. получится новое зиаиение — 14152.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
