|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[260] (иными словами, Р[г] = Р[т + 1 - i] и 7r[t] - максимальное и < t, для которого Ри □ Р(). Пусть участок X строки Р заканчивается в позиции к (то есть является суффиксов строки Рк) и равен P[j + 1..то]. Длины обоих равных участков равны то - j, и легко понять, что эти участки (в перевёрнутом виде) будут суффиксом и префиксом строки Р{, где / = (то - к) + (то - j) (здесь (то - к) - расстояние от конца участка X до конца образца, (то - j) - длина участка). Поэтому 7г[/] то - j. Докажем, что на самом деле имеет место равенство В самом деле, если бы более длинный участок X, начинающийся в той же позиции, что и X, был бы суффиксом образца, то некоторый его суффикс совпадал бы с P\j-\-l..m] и потому X не был бы самым правым участком строки Р, совпадающим с P[j + 1..то], Равенство (34.8) можно переписать как j = то - 7г[/]; кроме того, из него следует, что к = то - / + тт[1]. поэтому можно окончательно переписать нашу формулу для так: = то -тах({7г[то]}и{ то -/+7г[/] : 1 < I т и j = т - тг[1]}) = min({ то - тг[то] } U { / - тг[1] :1/tohj = to - тг[/] }) (34.9) (опять-таки, второе множество может оказаться пустым). Теперь можно выписать псевдокод для функции, вычисляющей 7- Comput e-Good-Suffix-Funct ion(P,m) 1\pi \gets Compute-Prefix-Function(P,m) 2P \gets обращение строки P 3\pi \gets Compute-Prefix-Function(P,m) 4for j \gets 0 to m 5do \gamma[j] \gets m-\pi[m] 6for 1 \gets 1 to m 7do j \gets m - \pi[l] 8if \gamma[j] > 1 - \pi[l] 9then \gamma[j] \gets 1 - \pi[l] 10return \gamma Процедура Compute-Good-Suffix-Function проводит вычисления в точности по формуле (34.9). Её время работы есть О (то). Время работы алгоритма Бойера - Мура в худшем случае есть 0((п - то + 1)то + £), поскольку на исполнение Compute-Last-Occurrence-Function уходит время 0(то + £), на Compute-Good-Suffix-Function уходит О(то), и в худшем случае алгоритм Бойера - Мура (как и алгоритм Рабина - Карпа) потратит время О (то) на проверку каждого априори возможного сдвига. На практике, однако, именно алгоритм Бойера-Мура часто оказывается наиболее эффективным. 7г[/] = ТО - j. 34.5.3. Упражнения 34.5-1 Вычислите функции А и 7 для строки Р = 0101101201. 34.5-2 Покажите на примерах, что эвристики стоп-символа и эвристика безопасного суффикса, действуя вместе, могут дать большой выигрыш по сравнению с использованием только эвристики безопасного суффикса. 34-5.3* На практике вместо функции 7 часто используют усовершенствованную функцию у, определенную так: y[j] = то - max{ к : 0 к < то, P[j + l..m] ~ Р n(k-m + j>0=> P[j] ф Р[к - то + j]) } (иными словами, мы дополнительно требуем, чтобы при новом сдвиге напротив стоп-символа в тексте стоял не тот же заведомо негодный символ образца, что при предыдущем). Как эффективно вычислять функцию у1 Задачи 34-1 Алгоритм поиска, учитывающий повторения в образце Через у1 будем далее обозначать г-кратную конкатенацию строки у с собой (например, (ab)3 = ababab). Будем говорить, что строка х £ У* имеет коэффициент повторения (has repetition factor) г, если х = уг, где г > 0 и у £ У*. Через р(х) обозначим наибольший из коэффициентов повторения строки х. (а)Разработайте эффективный алгоритм, находящий р(Р{) для данной строки Р и для всех г = 1, 2,..., то. Оцените время работы вашего алгоритма. (б)Для строки Р[1..то] положим р*(Р) = maxi8m р(Р{). Пусть У = 2 и строка Р выбирается случайным образом. Покажите, что математическое ожидание р*(Р) ограничено сверху константой, не зависящей от то. (в)Покажите, что приведенная ниже программа находит все вхождения образца Р в текст Г за время 0(р*(Р)п + то). Repetition-Matcher(Р,Т) 1m \gets length[Р] 2п \gets length[Т] 3к \gets l+\rho~*(P) 4q \gets 0 5s \gets 0 6 while s \leqslant n-m 7do if T[s+q+l]=P[q+l] 8then q \gets q+1 9if q=m 10then print Образец входит со сдвигом s 11if q=m или T[s+q+l]\ne P[q+1] 12then s \gets s+\max(l, \lceil q/k \rceil) 13q \gets 0 Этот алгоритм предложили Галил и Сейферас. Развивая эти идеи, они получили алгоритм для поиска подстрок, работающий за линейное время и использующий всего 0(1) памяти помимо требуемой для хранения Р и Т. 34-2 Параллельный алгоритм поиска Обсудим, как можно использовать параллельный компьютер для поиска подстрок. Пусть для данного образца Р у нас есть конечный автомат М, предназначенный для поиска Р в тексте. Пусть Q - множество его состояний, а (р - функция, которая ставит в соответствие каждому слову состояние автомата М после чтения этого слова. Пусть Т[1..га] - текст, в котором мы ищем образец Р, тогда нам необходимо найти <~р(Т{) для всех г. Мы будем действовать как в разделе 30.1.2. Для всякой строки х обозначим через 8x(q) состояние автомата М, в которое он придёт, если поместить его в состояние q и подать на вход строку х. (Таким образом, 8Х есть функция из Q в Q.) (а)Покажите, что 8у о 8Х = 8ху (в левой части стоит композиция отображений). (б)Покажите, что операция о ассоциативна. (в)Покажите, что таблица значений функции 8ху может быть вычислена на CREW PRAM за время 0(1) исходя из таблиц значений 8Х и 8у. Оцените необходимое для этого число процессоров в зависимости от \Q\. (г)Покажите, что <~р(Т{) = 8тг(уо), где до - исходное состояние. (д)Покажите, что на CREW PRAM все вхождения образца Р в текст Г длины га можно найти за время О (lgra) (считайте, что образец Р задан в виде соответствующего конечного автомата). 34.6. Замечания Связь задачи о поиске подстрок с конечными автоматами обсуждается у Ахо, Хопкрофта и Ульмана [4]. Алгоритм Кнута - Морриса - Пратта был независимо изобретен Кнутом и Моррисом, с одной стороны, и Праттом - с другой; в результате они опубли- |
Среды: 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 | ||