|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[253] раций за время 0(1) едва ли допустимо. К счастью, эту трудность можно обойти следующим образом: надо проводить вычисления чисел р и to, а также вычисления по формуле (34.1), по модулю фиксированного числа q (рис. 34.4; по поводу арифметики по модулю q см. разд. 33.1). Тогда все числа не превосходят q и можно считать, что число р и все tj будут действительно вычислены за время О (га + то). Обычно в качестве q выбирают простое число, для которого 10q помещается в машинное слово - это упрощает программирование вычислений. В общем случае (для алфавита { О, 1, 2,..., d }) выбирают такое простое число q, что dq помещается в машинное слово (благодаря этому все арифметические операции происходят в пределах одного слова); рекуррентное соотношение (34.1) приобретает вид ts+1 = (d(ts - T[s + l]h) + T[s + то + 1]) mod q,(34.2) где h = dm~l (mod q). Вычисления по модулю q хороши всем, кроме одного: из равенства ts = р (mod q) ещё не следует, что ts = р. Поэтому, если ts ф р (mod q), то сдвиг s заведомо недопустим и о нем можно забыть, а если ts = р (mod q), то надо еще проверить, совпадают ли строки Р[1..то] и T[s+1..s+to] на самом деле. Если совпадают, то мы нашли вхождение образца в строку, а если не совпадают, то произошло холостое срабатывание (spurious hit). Если простое число q достаточно велико, то можно надеяться, что дополнительные затраты на анализ холостых срабатываний будут невелики. Запишем текст соответствующей процедуры Rabin-Karp-Matcher. Она получает на вход текст Г, образец Р, «основание системы счисления» d (обычно берут d = Е) и простое число q. Rab in-Karp-Mat cher(Т,P,d,q) 1n \gets length[T] 2m \gets length[P] 3h \gets d~{m-l} \bmod q 4p \gets 0 5t \gets 0 6for i \gets l to m 7do p \gets (dp+P[i]) \bmod q 8t \gets (dt+T[i]) \bmod q 9for s \gets 0 to n-m 10do if p=t 11then if P[l..m]=T[s+l..s+m] 12then print Образец входит со сдвигом s 13if s<n-m 14then t \gets (d(t-T[s+l]h) + T[s+m+l]) \bmod q Опишем работу процедуры. Все символы рассматриваются как d-ичные цифры. В строках 1-5 переменным присваиваются началь- Рис.34.4, занимающий целую страницу. Переводы надписей, входящих в рисунок: valid match - вхождение образца, spurious hit - холостое срабатывание, old high-order digit - цифра старшего разряда, new low-order digit - цифра младшего разряда, shift не переводить и не воспроизводить (ни слово, ни стрелку). Подпись: Рис.34.4. Алгоритм Рабина-Карпа. У = { 0, 1, 2,..., 9 }, q = 13. (а) Строка Г (текст). Серым выделено окошко ширины 5. Численное значение выделенной подстроки равно 7 по модулю 13. (б) Для того же текста указаны численные значения (по модулю 13) всех подстрок длины 5. Если образец есть Р = 31415, то нас интересуют подстроки со значением 7, поскольку 31415 = 7 (mod 13). Таких подстрок всего две; одна из них соответствует вхождению образца в текст, а другая - холостому срабатыванию, (в) Изменение числового значения при сдвиге окошка. В предыдущем окошке стояло 31415. Удалив цифру старшего разряда и приписав новую цифру младшего разряда, получаем 14152. Те же вычисления по модулю 13 из старого значения 7 получают новое значение 8. ные значения (h - это «единица старшего разряда» в й-ичной системе). В цикле в строках 6-8 с помощью схемы Горнера вычисляются значения р и to (последнее присваивается переменной t). Цикл в строках 9-14 перебирает все возможные значения s; в момент исполнения строки 10 имеем t = ts (mod q). Если оказывается, что ts = р, то строки T[s+ l..s + гаг] и Р[1..га] сравниваются и, в случае совпадения, об этом печатается сообщение (строки 11-12). Если ts ф р, то программа проверяет, будет ли цикл выполняться далее (строка 13), и если будет, то обновляет значение t по формуле (34.2) - строка 14. В худшем случае эта процедура требует времени в ((га - га+1)га), как и простейший алгоритм - уже потому, что для всех допустимых сдвигов происходит посимвольная проверка. Например, если Р = ат и Т = а™, то сравнение в строке 11 будет выполняться для всех значений s (и алгоритм отличается от тривиального лишь в худшую сторону за счёт дополнительных затрат на вычисление h в строке 3, на цикл в строках 6-8 и на вычисления в строке 14). Во многих приложениях следует ожидать, что допустимых сдвигов будет немного; в этом случае время работы алгоритма Рабина - Карпа будет О (га + гаг) плюс небольшие дополнительные затраты на обработку холостых срабатываний. Можно сделать нестрогую прикидку, основываясь на следующих соображениях. Будем считать, что отображение редукции по модулю q - случайная функция из Е* в Zq. Это утверждение трудно поддается формализации и доказательству, но эмпирически подтверждается (ср. разд. 12.3.1, где мы обсуждали применение деления с остатком к хешированию). Тогда можно надеяться, что количество холостых срабатываний есть 0(ra/g), поскольку вероятность того, что случайное число ts сравнимо с р по модулю q, равна 1/q. Стало быть, ожидаемое время работы алгоритма Рабина - Карпа есть О(га) + 0(m(v + ra/g)), где v - количество вхождений образца в текст. Если q гаг (то есть длина образца не превосходит выбранного значения q) и v = 0(1), то получается, что алгоритм работает за время О (га + гаг). 34.2.1. Упражнения 34.2-1 Сколько холостых срабатываний даст алгоритм Рабина-Карпа, если q = 11, Г = 3141592653589793 и Р = 26? 34.2-2 Обобщите алгоритм Рабина - Карпа на случай, когда в тексте надо искать одну из к данных подстрок. 34-2.3 Обобщите алгоритм Рабина - Карпа на случай, когда надо искать квадрат размером гаг X гаг в матрице размером га X га с |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||