Лекции по информатике (984119), страница 13
Текст из файла (страница 13)
То есть ищется неравенство двух букв с одинаковыми индексами. В случае неуспеха строки равны. Для дальнейших рассуждений необходимо сначала рассмотреть случай коротких строк., для которых приемлем линейный поиск расхождений или имеется аппаратная поддержка. В болыпинстве практических приложений удобно иметь дело со строками переменной длины.
Каждая такая строка содержит свой размер, обычно не превосходящий максимального .~И. Например, на ЭВМ ЧЛХ-11 была реализована аппаратная поддержка строк для .И = 255. Фактически это строки не переменной, а регулируемой длины. Это достаточно гибкая и эффективная схема, позволяющая реализовать основные практические потребности, не прибегая к динамическому распределению памяти. Наиболее распострансны следукпцие представления строк. 1. Как уже это делалось при отображении списков, размер строки явно нс указывается, Сама строка простирается от начала, заданного адресом или указателем, и до конца, определяемого теркплнирующим элементом. В качестве ограничителя строк обычно используют непечатный элемент кода с минимальным порядковым номером сбг(О), предшествующий обычным видимым буквам алфавита.
Именно так реализованы строки в Си и в Х1одуле-2, аналогично их можно запрограммировать в стандартном Паскале. 2. Размер строки агрегируется с ее телом и хранится в ее первом (нулевом) элементе как сверхкороткое целое. В этом случае легко извлечь длину строки из ее структуры и не тратить ресурсы на подсчет. Недостатками этого способа являк>тся: ограничение длины строки мощностью алфавита, усложнение интерпретации строки и возможные огпибки ввиду полной несовместимости с первым способом.
Далес мы будем отдавать предпочтение первому способу представления строк. Он позволяет организовать их сравнение и копирование более быстрым барьерным методом: 0; ( Цикл вьию>лнзется, тттгка тгоотттветстттвуютдие буквът строк совиадангт или >тока одна ттз строк нс законнитпся раньше. 11роверка для второй строки,— излтлтиняя„поскольку если вгаорая строка короче первой, возникнет несовпадение х(т/ <:. сбг(0) и ц(т] = сйг(0) ) ттЪ11е (х(т( у(т () апс1 (х(г( <> с1>т(0) ( ттнд (т>Я з > сйг(0)) ) с1о т: г-:1; В качестве барьера для прекращения цикла выступает терминирующий элемент строки с6г10).
Предусловие (инвариант) цикла Уу: О < ) < т': хг = у, ф с6г(0) отрицая которое ттолучим условие завершения тюиска (Сх, ф ут) У (х, = с6г(0))) м(ттрн': О < у < т: х = р ут сбг(0)) Т. е. при условии, что х, = рт;тля всех л строки х и у совпадают, а осли хотя бы для одного т х, -С у,, то строка, х лексикографически предшествует строке у: х -С Гь Вернемся к задаче поиска в таблицах.
Особенность поиска по составному ключу в том, что поит:к искомого ключа т;реди других ключсй таблицы в свою очсредь требует последовательных сравнений компонент клнгча. Рассмотрим турнирную таблицу Мтстозс>СС 1>>тая>по Спр 2005 С1Я. Здесь ключами являются названия вузов, а данными — — названия проектов и города,, гдс; назначен следуклций тур конкурса. Чтобы узнать, куда едет команда МГТУ, надо отыскать в таблице элемент с соответствуютттттм ключом, псгбуквенно проверяя компоненты ключа на М. Г, Т и У.
На скалярной ЭВМ это потребует цикла с параметром при фиксированной длине ключа или цикла с предусловием при использовании терминирующего элемента строки. М1сговой 1тпаи1пе Спр 2005 С18 Комбинированный тип данных для таблицы может быт>. таким Суре Т - аггау (О..М вЂ” 1] оГзсттпя; лаг х: зтттпв; Допустим. что Л достаточно велико а таблица Т лексиког1>афически гптгрядтг тент>,. Методом деления пополам. используя ранее составленные наброски программ двоичного поиска и сравнения, получим фрагмент программы поиска 1.: 0: В.: 1М; и>Ь11е 1, < В. с1о Ъеи1п тп: — (1. -: — 11) с1и 2; 0; тл>1п1е(Т(тп, т( х(т() апс1 ( х(т( <> с1>т(0)) с1о 01; 310 11(Т(гп, 1[ < х[1[) С1геп 1.:=- гп Ь 1 е1ве гс:-- п> епс1; 1' Проверка ключа правогра>личного элечентс> последнего интервала„не учи>с>ываелсогг> при,модифицировал*нам условии поиска а]Л] = ха ) 11 К < 1ч СЬеп Ьеиш 0; Мп1е(Т[К, 1[ -- х[1[) апс1 (х[1! <> с1>г(0)) с1о : — >+1 епс1; 1 условие совпадения> 1Л < Ю) апс> (>]гс, л]::= х]]) ] А теперь приведем гу >ке самую программу на языке Си.
Использование указателей позволяет за.писать фактически а,лгоритм ггоиска, поскольку зта функция применима к >побым массивам и подмассивам. Заметим, что и в библиотеке с1Т1. С ' ц присутствует подобный алгоритм 1'лпдО и предикат двоичного поиска, Ьлпагу зеагсЦ). ,,'л Функция ищсгп вхождение образпа и>1>с>1 в интервале [1 г), в случс>е неудачи возоращс>я .чаркер конг>а последовательное>ти г л,г Т* 1>1п зеагс1>(Тл 1, Т* г, Т лл1>а1),"'л Для типа Т должны бьгть определены орега1ог< и орега1ог=-== л ~ шФл ег>д - г; ~ Описание терминатора и установка его значения Ког (;;),~,' Бесконечныи цикл, завери>ается возвратом из функции р1г с1111 с1 =- г — 1;,'~ Примененный к указателям г и 1 орега1ог — О возвращаегп разность индексов, как если г и 1 были бы индексами в массиве 11'(с1 < О) >'Перехлест границ — неудача при поиске геСпгп епс1; Тл гп - 1 л- с1 ] 2;,~'' Указатель иглкре.ментируется на, реву.льтат целого де.ления л,й 1Г(лш — — лч1>а$) г к Покомпонентное сравнение выпоггняет автомагпически орега1ог==, если он определен.
Б С++ эгпо верно для зМ:з1гту л,>' ге$пгп пц 1Г(лгп < лг1>а1) 'л И здесь мьс опираемся, на всгароенньсй или переопределенный для типа, Т орега1ог< лl 1 — гп -- 1; е1ве г — >п — 1; В стандартной библиотеке Си имеется аналогичная функц>пг Ьзеагс1>1). 311 Если Т это ш$, то нримепсггие этой функ|~ии лля поиска в упорядоченном массиве выглядит так: ш$ аггауЦ -- 11, 2, 3, 4, 5); ш$* Гавг — ьтаггау[б[;,'т Этого элементпа в массиве нерп! Но он следуелп за последним и мозсно взятии его адрес для терминирования ту Гйп эеагсГг(йаггау[О[, Гавс, 4); т'' ' Вернетп указатпель со значением сэаттарГ',,т/ Гэ1п аеагсГг(Ыггау[1], Гав1, 1); т',т Вернетп указатпель со значением ГазГ 6.1.4 Поиск по образцу Другой часто встречающейся задачей поиска является поиск вхождения подстроки в некоторой последовательности знаков.
Поскольку длина этой последовательности может быть очень большой (поиск в глобальных сетях интернет, в текстовых и двоичных файлах, содержащих программы или дсишые), то весьма актуально получение сложпостпых оценок и ускорения такого поиска. Монография Дэна Гасфилда [87[ посвящена новому приложению алгоритмов поиска по образцу расшифровке молекулярных структур для задач биологии и генетики. 11усть в массиве з задана последовательность из гу элементов, а в массив р помещен более короткий образец для поиска длиной И': О < М < Х маг а: аггау [О..Х вЂ” Ц от 1гегп; р: агтау [О..М вЂ” Ц оГ йегп; 1!оиск подс:троки обнаруживает первое вхождение р в ж Рассмотрим прямолинейный метод поиска подстроки.
Результатом поиска будем считать индекс Г начала, первого вхождения образца, р в последовательность еь С целью точного формулирования условий поиска введем предикат часттгчного совтгадегигя Р(г,Я: Р(г', э') = Иг: О < lс < т': з; ь = рь который констатирует, что ггервые у букв образца совпадают с 1 буквами последовательности, начиная с 1-ой буквы. Результирующий индс*кс поиска должен удовлетворять этому предикату в точке (т, М), т.
е, Р(г, М) при успешном окончании поиска становится истинным. Кроме того, раз мы ищем первое вхождение образца, РЯ,, М) должно быть ложным и для всех й < т,'1 Обозначив соотзтеггстгвующий предикот первовлоэтсдения через Д(т), выразим это условие через ггредикат Р: ®т') = Ы: О < й < г: — РЯ, М) т. е. Р(Гг, М) для всех предыдущих /г ложно. Алгоритмически Я может быть определено для каждого Г как СГ: — Сгпе; 1с:-- О; и Гп1е СГ апсГ (Гс = Г) сГо ЬеиГп С1; — С2 апс1 пой Р(Гс, М); Гс; — Гс -,'- 1:, епсГ; 31'2 Ввиду зависимости этих прсдикатов поиск имеет смысл реализовать как повторяющееся срависние: 1:=- — 1; гер еаза — 1; (вычисление Я(ХХ~ Хопгк1: Р11, М) ппИ Гоппс1 ог (1 ~Х вЂ” М)):, Вычисление предиката Р вновь производится политерным сравнением фрагмента последовательности с образцом.
Применяя к формуле для Р закон де Моргана, получим: Р1ъ', Я = ~ЧЛ': О < Л. < Х: гч ь = рь) = 1Яlг: О < Л < Х: в;~ь ф рь) т. е. ищется несовпадение с образцом, причем закон де Моргана превращает истинность совттадепия для всех литер в ложность несовпадения хотя бы одной.
Поиск по образцу также, как и поиск по составному ключу, реализуется вложенными циклами, а предикаты Р и 0 инварианты этих циклов вк почаются в Паскаль-программу, увы, лишь как комментарии: 1: — 1; гер еаза — ь 1; ,: О, й()3 жЫ1е 1) < М) апс1 (а~1 -- Л -- р~) ~) с1о (еычиалевие Р(1, х' ~ ХД )+1 Яй ~Х Р(~,,д 6 ((Х вЂ”: ЛХ) 'Х ЖХ -',Х! Ф Ий)) ппй1 1) ...
М) ог Д - ~Х вЂ” М)); В условии окончания цикла множитель Х = ЛХ эквивалентен Хоиий, т. к. из пего следует Р11, ЛХ), а г = Х вЂ” ЛХ влечет Я(Х1Х вЂ” ЛХ) — отсутствие совпадений с образцом во всей последовательности 1совпадения не было и уже не будет -- слишком мало букв остается в последовательности).
Если поиск продолжается при 1 < ЛХ, то он не должен прекращаться при несовпадении в,, у'= р . По определению предиката, Р отсюда следует ложность Р11, Х), а по определению 0 истинность ®1 1 1), гго и подтверждает истинность фг) после очередного увеличения 1. Проанализируем алгоритм прямого поиска образца. Его недостатком является то„что всякий раз в случае неуспеха приходится возвращаться назад на всю совпавшую часть образца, чтобы продолжить сравнение с образцом со следующего за началом рассмотренного фрагмента элементом. Эти возвраты, ввиду конструктивных особенностей устройств внешней памяти, на которых нередко размещается сканируемая последовательность, еще больше замедляют прямой поиск. Этот алгоритм работает достаточно эффективно, если встреча префикса образца, в последовательности маловероятна и несовпадение наступает почти сразу после нескольких сравнений букв фрагмента и образца.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
