Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 209
Текст из файла (страница 209)
Говорят, что сдвиг а = 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.
Часть Ч11. Избранные тены 1022 32.1-2. Предположим, что в образце Р все символы различны. Покажите, кяя ускорить процедуру Ымче Бтн1нп МАтснен, чтобы время ее выполнения при обработке и-символьного текста Т было равно О (и). 32.1-3. Предположим, что образец Р и текст Т вЂ” строки длиной т и п соответственно, случайно выбранные из с(-символьного алфавита Ев = = 10, 1,..., с( — 1), где д > 2. Покажите, что математическое ожидание количества сравнений одного символа с другим, производимых в неявном цикле в строке 4 простейшего алгоритма, во всех итерациях этогь цикла равно 1 — 1а (и — т+1) < 2(и — т+1). (Предполагается, что в простейшем алгоритме сравнение символов дяя данного сдвига прекращается, как только будет обнаружено несовпадение или совпадет весь образец.) Таким образом, для случайных строя простейший алгоритм вполне эффективен.
32.1-4. Предположим, в образце Р может содержаться символ пробела (яар сЬагасгег) О, который может соответствовать произвольной строке (даже нулевой длины). Например, образец аЬОЬафс встречается в тексте саЬссЬасЬасаЬ как с а6 сс Ьа сЬа с а6 аь О ьа О с и как с а6 ссЬас Ьа с аЬ. аь О ь О с Заметим, что в образце символ пробела может встречаться произвольное количество раз, но предполагается, что в тексте он не встречается вообще. Сформулируйте алгоритм с полиномиальным временем работы, определяющий, встречается ли заданный образец Р в тексте Т, и проведите анализ времени его работы. 32.2 Алгоритм Рабина-Карпа Рабин (ВаЬ(п) и Карп (Кагр) предложили алгоритм поиска подстрок, показывающий на практике хорошую производительность, а также допускающий обобщения на другие родственные задачи, такие как задача о сопоставлении двумерного образца.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
