|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[259] Р[т] ф T[s + то]) и не встречается нигде в образце (представьте себе, что вы ищете подстроку ат в строке Ъп). В этом случае сдвиг s можно сразу увеличить на то: любой меньший сдвиг заведомо не подойдет, так как стоп-символ в тексте окажется напротив какого-то символа из образца. Если этот наиболее удачный случай повторяется постоянно, то при поиске подстроки мы просмотрим всего лишь 1/га часть текста (вот как полезно сравнивать справа налево!). В общем случае эвристика стоп-символа (bad-character heuristic) работает так. Предположим, что при сравнении справа налево мы наткнулись на первое несовпадение: P[j] ф T[s + j], где 1 j то. Пусть к - номер самого правого вхождения символа T[s + j] в образец Р (если этот символ вообще не появляется в образце, считаем к равным 0). Мы утверждаем, что можно увеличить s на j - к, не упустив ни одного допустимого сдвига. В самом деле, если к = 0, то стоп-символ T[s + j] вообще не встречается в образце Р, так что можно сразу сдвинуть образец на j - к = j позиций вправо (рис. 34.12 (а)); если 0 < к < j, то образец можно сдвинуть на j - к позиций вправо, так как при меньших сдвигах стоп-символ в тексте не совпадёт с соответствующим символом образца (рис. 34.12 (б)). Наконец, если к > j, то эвристика предлагает сдвигать образец не вправо, а влево; алгоритм Бойера-Мура эту рекомендацию игнорирует, поскольку эвристика безопасного суффикса всегда предлагает ненулевой сдвиг вправо. Чтобы применять эвристику стоп-символа, полезно для каждого возможного стоп-символа а £ £ вычислить значение к. Это делается простой процедурой Compute-Last-Occurrence-Function («найти последнее вхождение»), которая для каждого а £ £ вычисляет А[а] - номер крайнего правого вхождения а в Р, или нуль, если явРне входит. В этих обозначениях приращение сдвига, диктуемое эвристикой стоп-символа, есть j - \[T[s+j]], как и написано в строке 13 алгоритма Boyer-Moore-Matcher. Compute-Last-Occurrence-Function(P,m,\Sigma) 1for (для) каждого символа a \in \Sigma 2do \lambda[a] \gets О 3for j \gets 1 to m 4do \lambda[P[j] ] \gets j 5return \lambda Время работы процедуры Compute-Last-Occurrence-Function есть 0(£ + то). 34.5.2. Эвристика безопасного суффикса Если Q и R - строки, будем говорить, что они сравнимы (обозначение: Q ~ R), если одна из них является суффиксом другой. Рис. 34.12, занимающий целую страницу. Перевод надписи в рисунке: bad character - стоп-символ. Подпись: Рис. 34.12. Эвристика стоп-символа: три случая, (а) Стоп-символ в образце не встречается, так что образец можно сдвинуть на j = 11 позиций вправо, оставив стоп-символ позади, (б) Крайнее правое вхождение стоп-символа в образец - в позиции к < j. Образец можно сдвинуть вправо на j - к - так, чтобы стоп-символы в тексте и образце оказались друг под другом (в примере j = 10, к = 6, стоп-символ есть i, сдвиг на 10 - 6 = 4). (в) Стоп-символ встречается в образце в позиции к > j (в примере стоп-символ есть е, j = 10, к = 12). Эвристика предлагает сдвиг влево, но алгоритм это предложение игнорирует. Если выровнять две сравнимые строки по правому краю, то символы, расположенные один под другим, будут совпадать. Отношение ~ симметрично: если Q ~ R, то и R ~ Q. Из леммы 34.1 следует, что если Q □ R и S □ R, то Q ~ S.(34.7) Эвристика безопасного суффикса (good-suffix heuristic) состоит в следующем: если P[j] ф T[s + j], где j < то (и число j - наибольшее с таким свойством), то мы можем безбоязненно увеличить сдвиг на y[j] = т - max{ к : 0 к < то и P[j + l..m] ~ }. Иными словами, y[j] - наименьшее расстояние, на которое мы можем сдвинуть образец без того, чтобы какой-то из символов, входящих в «безопасный суффикс» T[s + j + l..s + то] оказался напротив не совпадающего с ним символа из образца. Поскольку строка P[j + 1..то] заведомо сравнима с пустой строкой Ро, число корректно определено для всех j. Стоит также заметить, что > О для всех j, так что на каждом шаге алгоритма Бойера - Мура образец будет сдвигаться вправо хотя бы на одну позицию. Мы будем называть у функцией безопасного суффикса (good-suffix function), ассоциированной со строкой Р. Посмотрим, как можно вычислить функцию безопасного суффикса у. Для начала заметим, что Рж[т] □ Р, откуда, в силу (34.7), имеем P[j + 1..то] ~ Рп[т] для любого j. Следовательно, максимум в правой части определения величины y[j] не меньше 7г[то], так что y[j] то - 7г[то] для всех j. Стало быть, можно переписать наше определение у так: y[j] = то - max{ k : ir[m] к < то и P[j + 1..то] ~ Р }. Условие P[j + 1..то] ~ Pk может выполняться в двух случаях: либо когда P[j + 1..то] □ Pk, либо когда Pk □ P[j + 1..то]. Во втором случае, однако, имеем Pk □ Рт, откуда к 7г[то] и потому к = тг[т]. Поэтому определение у можно переписать еще и так: y[j] = то - max ({тг[то]} U { к : тг[т] < к < то и P[j + 1..то] □ Pk }) Второе из этих множеств может оказаться пустым. В самом деле, мы ищем префикс Pk образца Р, в котором P[j + 1..то] является суффиксом; другими словами, мы ищем в образце участок равный его суффиксу P[j + 1..то] и расположенный левее (к < то) Нам нужно найти самый правый из таких участков (числа к, из которых берётся максимальное - это правые границы таких участков). Для этого полезно рассмотреть строку Р, являющуюся обращением строки Р и соответствующую ей префикс-функцию pi1 |
Среды: 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 | ||