Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 227
Текст из файла (страница 227)
Несмотря на то, что строгий анализ этого алгоритма провести сложно, при разумных ПрЕдПОЛОжЕНИяХ МОЖНО ОцЕНИтЬ ВрЕМя ЕГО рабстЫ КаК Ь[1/Зс Н)'ЭОЗЬ=11), ГдЕ Г[,„П) Е(!пп)" (1а1ааР Метод эллиптических кривых, предложенный Ленстрой (Ьепзпа) [232], может оказаться эффективнее для некоторых входных данных, чем теоретию-чнсловой метод решета, посюльку, как и р-метод Полларда, он достаточно быстро позволяет найти небольшой простой множитель р. Время его работы при поиске множителя р оценивается как Ь[1/2, р)' з+а11>. Глава 32. Поиск подстрок В программах, предназначенных для редактирования текста, часто необходимо найти все фрагменты текста, которые совпадают с заданным образцом.
Обычно текст — это редактируемый документ, а образец — это искомое слово, введенное пользователем. Эффективные алгоритмы решения этой задачи (часто именуемой сопоставлением строк (зпэпй ша1сЫпй)) могут сокрашать время реакции текстовых редакторов на действия пользователя. Среди множества приложений алгоритмы поиска подстрок используются, например, для поиска заданных образцов в молекулах ДНК. Поисковые системы в Интернете также используют их при поиске веб-страниц.
отвечаюших запросам. Формацнзуем постановку задачи поиска подстрок (яппй-пшгсЫпй ргоЪ|еш) следующим образом. Предполагается, что текст задан в виде массива Т[1 .. и] длиной и, а образец (шаблон) — в виде массива Р[1 .. т) длиной пз < и. Далее, предполагается, что элементы массивов Р и Т вЂ” символы иэ конечного алфавита Е. Например, алфавит может иметь вид Е = 10, Ц или Е = (а, Ь,..., х). Символьные массивы Р и Т часто называют строками (апэпйа) символов. Обратимся к рис.
32,1. Мы говорим, что образец Р встречается в гцексте со сдвигом е (или, что то же самое, что образец Р встречаетса начиная с позиции в + 1 в тексте Т), если О < л < и — т и Т[л + 1 .. л + тп) = Р[1 .. гп) (те. если Т[в + Я = Р[)] для 1 < 3 < пз). Если Р встречается в Т со сдвигом е, то л называется допусгпимым, или корректным, сдвигам; в противном случае л является недопустимым, или некорректным, сдвигам. Задача поиска подстроки представляет собой задачу поиска всех допустимых сдвигов, с которыми заданный образец Р встречается в тексте Т. Кроме описанного в разделе 32.1 простейшего алгоритма решения задачи "в лоб", все рассматриваемые в этой главе алгоритмы выполняют определенную образец Р - — — — -' -Аб Ьх*:1а ) и:, Ряс. 32Д.
Пример задачи поиска подстроки, в которой необходимо найти все вхождения образца Р = аЬаа в тексте Т = аЬсаЬааЬсаЬас. Образец встречается в тексте талыш один рвз, со сдвигом е = 3, который мы называем допустимым сдвигом. Вертикальные линии соединяют юскдый символ образца с соответствующим символом текста, и все совпадающие символы заштрихованы. 2032 Часть РУ. Избранные ыеиы Время предварительной об аботки Алгоритм "В лоб" Время веления О((п — тп + 1)тп) 0((п — т + 1)тп) тЭ(п) 9(п) 0 9(тп) О( ~КВ 0(тп) Рабина-Карпа Конечный автомат Кнута-Морриса — Пратта предварительную обработку представленного образца, после чего выполняют поиск всех допустимых сдвигов; последняя фаза алгоритма будет называться сравнением, или сопоставлением. На рис. 32.2 приведены времена предварительной обработки и сравнения для каждого из представленных в этой главе алгоритмов.
Полное время работы каждого алгоритма равно сумме времени предварительной обработки и времени сравнения. В разделе 32.2 описан интересный алгоритм поиска подстрок, предложенный Рабином (КаЬтп) и Карпом (Катр). Несмотря на то что время работы этого алгоритма в наихудшем случае (равное 9((п — тп+ 1)т) не лучше, чем время работы простейшего метода "в лоб", на практике в среднем он работает намного лучше. Он также легко обобщается на случаи других подобных задач поиска образцов. Затем в разделе 32.3 описывается алгоритм поиска подстрок, работа которого начинается с конструирования конечного автомата, специально предназначенного для поиска совпадений заданного образца Р с фрагментами текста. Время предварительной обработки в этом алгоритме равно 0(тп Д), зато время сравнения в нем равно всего лишь 6(п).
Аналогичный, но более совершенный алгоритм Кнута-Морриса-Пратта (Клцт)т-Мопзз-ргап, илн КМР) представлен в разделе 32.4; время сравнения в этом алгоритме остается тем же, т.е, оно равно 0(п), но время предварительной обработки в нем уменьшается до величины сь(тп). Обозначения и терминология Обозначим через Е' множество всех строк конечной длины, образованных с помощью символов алфавита Е. В этой главе рассматриваются только строки конечной длины. Пуситая строка (ешрту зпзпя), которая обозначается г и имеет нулевую длину, также принадлежит множеству Е'. Длина строки х обозначается )х~.
Конкатенация (сопсатепабоп) строк х и у, которая обозначается ху, имеет длину ~х! + (у! и состоит из символов строки х, после которых следуют символы строки у. Мы говорим, что строка ш является префиксам (ргебх) строки х (обозначается как и~ Г х), если х = юу для некоторой строки у е Е'. Заметим, что если тл С х„то )тп! < ~х~. Аналогично строку ю называют суффиксам (зн11)х) строки х (обозначается как тл ~ х), если существует такая строка у е Е*, что х = упт.
Как и в случае префикса, из то ~ х следует неравенство (ю~ < (х!. Например, аЬ ь аЬсса и сса Л аЬсса. Пустая строка е является одновременно и суффиксом, Рнс. 32.2. Алюрнтмы поиска подстрок, представленные в данной главе, и их времена предварительной обработки и сравнения. Глана 32. Поиск лодстрок 1033 хГ 7 х (',,:,:! г. у 1' х (*,",;т':.*!~ (в) (в) Рис.
323. Грвфическое доказательство леммы 32.1. Предполагаем, что х л в и у л х. Нв кюкдой из трех частей рисунка проиллюстрироввиы трк случая леммы. Вертикальными линиями соединены совпадающие области строк (выделенные серым фоном). (в) Если (х( < (у(, то к л у. (6) Если (л( > (у(, то у л к. (в) Если (х( = (у1 то х = у. и префиксом любой строки. Для произвольных строк х н у и для любого символа а соотношение х 1 у выполняется тогда и только тогда, когда ха Л уа. Кроме того, заметим, что отношения С и 1 являются транзитивными. Впоследствии окажется полезной сформулированная ниже лемма.
Локазаюельсллеа. На рис.32.3 представлено графическое доказательство этой леммы. Обозначим для краткости lс-символьный префикс Р(1 .. Ц образца Р[1 .. гп) как Рь. Таким образом, Ре = е и Р = Р = Р(1 .. пт). Аналогично )с-символьный префикс текста Т обозначим как Ть. С помощью этих обозначений задачу поиска подстрок можно сформулировать как задачу о выявлении всех сдвигов л в интервале О < л < и — т, таких„что Р:1 Т,+ В псевдокоде предполагается, что сравнение двух строк одинаковой длины является примитивной операцией.
Если строки сравниваются слева направо и процесс сравнения прерывается, когда обнаружено несовпадение, то считается, что время, которое требуется для подобного теста, выражается линейной функцией от количества совпавших символов. Точнее говоря, считается, что тест "'х == у" выполняется за время Е)((+ 1), где 1 — длина самой длинной строки г, такой, что л С х и в (: у. (Чтобы учесть случай, когда 1 = О, вместо Щ() мы пишем 9((+ 1). В этой ситуации не совпадает первый же сравниваемый символ, но для проверки этого требуется некоторое положительное время.) Лемма 32.1 (Лемма и иерекрвваающихея суффиксах) Предположим, что х, у н л являются строками, такими, что х л в и у 1 л. Если (х! < (у), то х Л у.
Если Ц > (у), то у 1 х. Если (х~ = (у(„то х = у. ИП4 Часть РИ. Избранные темы 32.1. Простейший алгоритм поиска подстрок В простейшем алгоритме поиск всех допустимых сдвигов выполняется с помощью цикла, в котором проверяетсн условие Р[1 .. т] = Т(л + 1 .. л + ги] для каждого из и — т + 1 возможных значений л. )((А)чн-антк)нс-МАтсннк(Т, Р) 1 и = Т.1еидй 2 ги = Р.1еирй 3 $огл=Оц)и — т 4 1ГР(1..т]==Т(л+1..л+т] 5 рпп( "Образец найден со сдвигом" и На рис. 32.4 простейшая процедура поиска подстрок проиллюстрирована как скольжение "шаблона" с образцом по тексту, в процессе которого отмечается, для каких сдвигов все символы шаблона равны соответствующим символам текста Цикл 1ог в строках 3-5 явно исследует каждый сдвиг.
Проверка в строке 4 определяет корректность данного сдвига; этот тест неявно включает цикл проверки соответствующих позиций символов до тех пор, пока не выяснится, что все символы совпадают, или пока не будет найдено несоответствие символов. В строке 5 выводится каждый корректный сдвиг а Время работы процедуры )((А)чй-зткпчс-млтсннк равно 0((и — т+ 1)т), и зто точная оценка в наихудшем случае. Например, рассмотрим текстовую строку а" (строку, состоящую из и символов а) и образец а™.
Для каждого из и — т+1 возможных значений сдвига л неявный цикл в строке 4 для проверки совпадения соответствующих символов должен выполнить т итераций, побы подтвердить допустимость сдвига. Таким образом, время работы в наихудшем случае равно ез((и — т + 1)т), так что в случае т = ] и/2] оно становится равным 6(из). Время работы процедуры ХА(чи-Зтк)нн-МАтснйк равно времени сравнения, так как фаза предварительной обработки отсутствует. Вскоре вы увидите, по процедура ХА)чй-Бткпчс-МАтсник не является оптимальной для этой задачи.
В этой главе вы встретитесь с ашоритмом Кнута- Морриса — Пратта, который в наихудшем случае оказывается гораздо лучшим. Про- а с е а Ь с л1с)е )'~с з=п с:-г"~ —— з=! в е --:са((в.) а:,~'(з ~ (6) (г] (а) (в) Рнс. 32.4. Действия простейшего алгоритма поиска подсгрок для обрвзцв Р = авЬ и гсксгв Т = асеево. Мвкно представить образец Р квк смшъзлщий вдоль текста. (н)-(г) Четыре последовегельные размещения, проверенные ялгоризмом. В кыкдой части вертикальные лшши соедииеог совпвлвющие области (звшгрияоввны), в ломаные линии соединяют первые несовпвлеющие символы, если таювые имеются. Алгоритм обнвру1киввег в тексте одно совпадение с образцом со сдвигом в = 2, показанное в части (в).
Глава 52. Поиск аодоаоок !055 стейший алгоритм поиска подстрок оказывается неэффективным, поскольку информация о тексте, полученная для одного значения в„полностью игнорируется при рассмотрении других значений в. Однако эта информация может оказаться очень полезной. Например, если образец имеет вид Р = аааЬ и если найдено, что сдвиг в = О допустйм, то ни один из сдвигов 1, 2 и 3 не может быть допустимым, поскольку Т)4) = Ь. В последующих разделах исследуется несколько способов эффективного использования информации такого рода. Упражнении 32.1.1 Покажите, какие сравнения выполняются простейшим алгоритмом поиска подстрок, если образец имеет вид Р = 0001, а текст Т = 000010001010001.
32.1.2 Предположим, что в образце Р все символы различны. Покажите, как ускорить процедуру Хл!че-бткцчб-МАтснек, чтобы время ее выполнения при обработке и-символьного текста Т было равно О(п). 32.1.3 Предположим, что образец Р и текст Т представляют собой строки длиной т и и соответственно, случайно выбранные из д-символьного алфавита Ев = .[О, 1,..., й — 1), где д > 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
