Алгоритмы - построение и анализ (1021735), страница 209
Текст из файла (страница 209)
Предполагается, что текст задан в виде массива Т [1 ..и] длины и, а образец — в виде массива Р [1..гп] длины т < и. Далее, предполагается, что элементы массивов Р и Т вЂ” символы из конечного алфавита Е. Например, алфавит может иметь вид Е = 10, Ц или Е = (а, Ь,..., з). Символы массивов Р и Т часто называют сшроками (з1йпяз) или символами. Говорят, что образец Р встречается в тексте Т со сдвигом а (оссигз чл1Ь зЫй а), если О < э < и — гп и Т [з+ 1..а+ гп] = Р [1..т] (другими словами, если при 1 < 1' < т Т [а+ 1] = Р [2]).
(Можно также сказать, что образец Р встречается в тексте Т, начиная с позиции а + 1.) Если образец Р встречается в тексте Т со сдвигом а, то величину з называют допустимым сдвигам (ча!Ы зЫй); в противном случае ее называют педопустимьим сдвигам (1пча1Ы зЫй). Задача поиска подстрок — это задача поиска всех допустимых сдвигов, с которыми заданный образец Р встречается в тексте Т.
Эти определения проиллюстрированы на рис. 32.1. В представленном на этом рисунке примере предлагается найти все вхождения образца Р = аЬаа в текст Т = аЬсаЬааЬсаЬас. Образец встречается в тексте только один раз, со сдвигом а = 3. Говорят, что сдвиг а = 3 Часть Ч11.
Избранные темы 1018 оскс~ ! 1 с ! ь, с: 1а ь 1 а 1 а ~ О ~ с , '«.;:, в Г, Оо,"ока я — — — — — -з4 е 1ь 1а 1а 1 Рис. 32.1. Задача поиска подстрок Таблица 32.1. Алгоритмы поиска полстрок и время нх предварительной обработки и срав- нения Время предварительной обработки Время сравнения 0 ((о — т + 1) т) 0((п — т+ 1) т) 9 (и) 9 (и) Простейший Рабина-Карпа Конечный автомат О 9 (т) 9(тД) 9 (т) Кнута-Морриса-Пратта является допустимым.
Каждый символ образца соединен вертикальной линией с соответствующим символом в тексте, и все совпадающие символы выделены серым фоном. Все представленные в этой главе алгоритмы, кроме описанного в разделе 32.1 обычного алгоритма решения задачи "в лоб", производят определенную предварительную обработку представленного образца, а затем находят все допустимые сдвиги; последняя фаза будет называться поиском. В табл.
32.1 приведены времена предварительной обработки и сравнения для каждого из представленных в этой главе алгоритмов. Полное время работы каждого алгоритма равно сумме времени предварительной обработки и времени сравнения. В разделе 32.2 описан интересный алгоритм поиска подстрок, предложенный Рабином (ВаЫп) и Карпом (Кагр). Несмотря на то, что время работы этого алгоритма в наихудшем случае (равное 9((п — т+ 1) т)) не лучше, чем время работы простейшего метода "в лоб", на практике в среднем он работает намного лучше. Он также легко обобщается на случаи других подобных задач. Затем в разделе 32.3 описывается алгоритм поиска подстрок, работа которого начинается с конструирования конечного автомата, специально предназначенного для поиска совпадений заданного образца Р с фрагментами текста.
Время предварительной обработки в этом алгоритме равно 0(т1Е~), зато время сравнения в нем равно всего лишь 6(п). Аналогичный, но более совершенный алгоритм Кнута-Морриса-Прагга (Кпи1(з-Могпз-Ргап, или КМР) представлен в разделе 32.4; время сравнения в этом алгоритме остается тем же, т.е. оно равно 9 (и), но время предварительной обработки в нем уменьшается до величины 9 (т). Глава 32. Поиск подстрок 1019 Обозначения и терминология Обозначим через Е' множество всех строк конечной длины, образованных с помощью символов алфавита Е. В этой главе рассматриваются толью строки конечной длины.
пустая строки (ешргу з1ппя) конечной длины, которая обозначается е, также принадлежит множеству Е'. Длина строки х обозначается [х]. Конкатенация (сопса~епабоп) двух строк х и у, которая обозначается ху, имеет длину [х] + ]у[ и состоит из символов строки х, после которых следуют символы строки у. Говорят, что строка ю — нрефикс (ргебх) строки х (обозначается ю ~: х), если существует такая строка у Е Е', что х = юу. Заметим, что если ю С х, то [ю[ < ]х]. Аналогично, строку ю называют суффиксом (зпйх) строки х (обозначается как ю Л х), если существует такая строка у Е Е', что х = ую. Из соотношения ю 1 х также следует неравенство [ю[ < [х]. Пустая строка е является одновременно и суффиксом, и префиксом любой строки. В качестве примеров префикса и суффикса можно привести аЬ С абсса и сса ~ абсса.
Следует иметь в виду, что для произвольных строк х и у и для любого символа а соотношение х ~ у выполняется тогда и только тогда, когда ха 1 уа. Кроме того, заметим, что отношения с н л являются транзитивными. Впоследствии окажется полезной сформулированная ниже лемма. Лемма 32.1 (Лемма о перекрывающихся суффиксах). Предположим, что х, у и е — строки, для которых выполняются соотношения х 1 з и у 1 х. Если [х[ < [у[, то х 1 у.
Если [х[ > ]у[, то у 1 х. Если ]х[ = ]у[, то х = у. Доказательство. Графическое доказательство представлено на рис. 32.2. На каждой из трех частей рисунка проиллюстрированы три случая леммы. Вертикальными линиями соединены совпадающие области строк (выделенные серым фоном). В части а показан случай, когда [х[ < [у[; при этом х л у. В части б показан случай, когда [х[ > ]у[, и у ) х.
Из части в видно, что если [х[ = ]у[, то х = у. Обозначим для краткости й-символьный префикс Р [1..й] образца Р [1..т] через Рь. Таким образом, Ро — — е н Р = Р = Р [1..т]. Аналогично, lс-символьный префикс текста Т обозначим Ть. С помощью этих обозначений задачу поиска нодстрок можно сформулировать как задачу о выявлении всех сдвигов з в интервале О ( е ( и — гп, таких что Р:) Т,.ь В псевдокоде предполагается, что сравнение двух строк одинаковой длины является примитивной операцией. Если строки сравниваются слева направо, и процесс сравнения прерывается, когда обнаружено несовпадение, то считается, что время, которое требуется для подобного теста, выражается линейной функцией от количества совпавших символов. Точнее говоря, считается, что тест "х = у" выполняется за время 6 (1+ 1), где 1 — длина самой длинной строки е, такой Часть Ч!!. Избранные темы 1020 !' [ г ~ [ ~ Г и Рис. 32.2.
Графическое доказательство леммы 32.1 что л ! я и - !: у. (Чтобы учесть случай, когда г = О, вместо 6(8) мы пишем 9 (г + 1). В этой ситуации не совпадает первый же сравниваемый символ, но для проверки этого требуется некоторое положительное время.) 32.1 Простейший алгоритм поиска подстрок В простейшем алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие Р [1..т] = Т [в+ 1..в+ т] для каждого из и — т+ 1 возможных значений в.
!ЧАпе Бтк!нс МАтсннк(Т,Р) ! п — !епдй[Т] 2 т — !епуЯР] 3 (огз — О!оп — т 4 до !( Р[1..гп] = Т[в+ 1..в+т] 5 гиен рг(п! "Образец обнаружен при сдвиге" в !!ростейшую процедуру поиска подстрок можно интерпретировать графически как скольжение "шаблона*' с образцом по тексту, в процессе которого отмечается, для каких сдвигов все символы шаблона равны соответствующим символам текста. В частях а — г рис.
32.3, который иллюстрирует эту интерпретацию, показаны четыре последовательных положения, проверяемых в простейшем алгоритме поиска подстрок. В каждой части рисунка вертикальные линии соединяют соответствующие области, для которых обнаружено совпадение (эти области выделены серым цветом), а ломаные линии — первые не совпавшие символы (если такие имеются). В части в показано одно обнаруженное вхождение образца со сдвигом Глава 32. Поиск подстрок 1021 Рис.
32.3. Принцип работы простейшего алгоритма поиска подстрок для образца Р = ааЬ н текста Т = асааЬс з = 2. В цикле 1'ог, который начинается в строке 3, явным образом рассматриваются все возможные сдвиги. В строке 4 проверяется, действителен ли текущий сдвиг; в этот тест неявно включен цикл для проверки символов, которые находятся в соответствующих позициях, до тех пор, пока не совпадут все символы или не будет обнаружено несовпадение. В строке 5 выводится каждый допустимый сдвиг з.
Время работы процедуры Хл|чн Бтк1нс Млтсннк равно О ((и — го+ 1) т), и эта оценка достаточно точна в наихудшем случае. Например, рассмотрим текстовую строку а" (строку, состоящую из п символов а) и образец а'". Для каждого из п — т+ 1 возможных значений сдвига з неявный цикл в строке 4 для проверки совпадения соответствующих символов должен произвести т итераций, чтобы подтвердить допустимость сдвига. Таким образом, время работы в наихудшем случае равно О ((и — т + 1) тп), так что в случае т = '1п/21 оно становится равным 9 (пз). Время работы процедуры Имчн Бтк1мо Млтсннк равно времени сравнения, так как фаза предварительной обработки отсутствует.
Вскоре вы увидите, что процедура Хл!че Бтихс Млтснек не является оптимальной для этой задачи. В этой главе будет приведен алгоритм, время предварительной обработки в котором в наихудшем случае равно О (т), а время сравнения в наихудшем случае — 9 (и). Простейший алгоритм поиска подстрок оказывается неэффективным, поскольку информация о тексте, полученная для одного значения з, полностью игнорируется при рассмотрении других значений ж Однако эта информация может стать очень полезной.
Например, если образец имеет вид Р = = аааЬ, а значение одного из допустимых сдвигов равно нулю, то ни один из сдвигов, равных 1, 2 или 3, не могут быть допустимыми, поскольку Т [4] = 6. В последующих разделах исследуется несколько способов эффективного использования информации такого рода. Упражнения 32.1-1. Покажите, какие сравнения производятся простейшим алгоритмом поиска подстрок, если образец имеет вид Р = 0001, а текст — Т = 000010001010001.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
