Поиск нескольких минимумов на отрезке. Задача поиска подстрок. Алгоритм Рабина-Карпа. Конечный автомат. Алгоритм Бойера-Мура. Примеры построенных суффиксных автоматов. Количество различных подстрок
- 1. Хакасский государственный университет им. Н.Ф. Катанова Структуры и алгоритмы обработки данных Лекция: Поиск подстрок. Николай Гребенщиков, www.grebenshikov.ru
- 2. Задачи на строках Основное приложение: вычислительная молекулярная био- логия (расшифровка ДНК). Поиск внутренних паттернов. Например, построение пре- фиксного дерева. Поиск частных паттернов. Например, поиск подстроки, растояния преобразования, наибольшей общей подпосле- довательности, совпадения с регулярным выражением. Поиск характеристических паттернов. Например, поиск кратных подстрок. 1
- 3. Поиск подстрок Дано: Текст в виде массива T и образец в виде массива P , где m ≤ n. Элементы массивов P и T - символы из конечного алфавита Σ. Говорят, что P встречается в T со сдвигом s, если 0 ≤ s ≤ n − m и T = P . Найти: Все допустимые сдвиги с которыми образец P встре- чается в тексте T . 2
- 4. Терминология Σ∗ - множество всех строк конечной длины, образованных с помощью символов алфавита Σ. - пустая строка. xy - конкатенация двух строк. w < x - w является префиксом строки x, то есть ∃y ∈ Σ∗, что x = wy. w = x - w является суффиксом строки x, то есть ∃y ∈ Σ∗, что x = yw. 3
- 5. Лемма о перекрывающихся суффиксах Пусть x, y, z - строки, для которых выполняются соотноше- ния x = z и y = z. Если |x| ≥ |y|, то x = y. Если |x| ≤ |y|, то y = x. Если |x| = |y|, то x = y. 4
- 6. Простейший алгоритм поиска подстрок NaiveStringMatcher(T, P) 1 n ← length 2 m ← length 3 for s ← 0 to n − m 4 do if P = T 5 then print(s) 5
- 7. Простейший алгоритм поиска подстрок 6
- 8. Анализ - простейшего алгоритма поиска подстрок Наихудший случай: T = an, P = am T (n) = Θ((n − m + 1)m) При m = n/2 T (n) = Θ(n2) 7
- 9. Алгоритм Рабина-Карпа Идея: использовать хэш-функцию опеределенную на множе- стве строк. h(S) = (S[k] + d(S + . . . + d(S + dS) . . .))mod q, где d - основание системы, q - модуль. 8
- 10. Алгоритм Рабина-Карпа h(P ) - хэш образца. {s: h(P ) = h(T ) ∧ 0 ≥ s ≥ n − m} - множество до- пустимых сдвигов. Обозначим ts = h(T ), тогда ts+1 = (d(ts − T g) + T ) mod q, где g ≡ dm−1(mod q) 9
- 11. Алгоритм Рабина-Карпа 10
- 12. Алгоритм Рабина-Карпа 11
- 13. Проблема алгоритма Рабина-Карпа Из равества h(P) = ts не следует, что P = T . Решение проверить сдвиг s посимвольным сравнением. 12
- 15. Анализ алгоритма Рабина-Карпа В наихудшем случае T (n, m) = Θ(m) + Θ((n − m + 1)m). Почему? В общем случае T (n, m) = O(n) + O(m(v + n/q)), где v - ко- личество допустимых сдвигов и q - модуль хэш-функции. Если v = O(1) ∧ q ≥ m ⇒ T (n, m) = O(m + n) = O(n), так как n≥m 14
- 16. Конечные автоматы M = (Q, q0, A, Σ, δ) Q - конечное множество состояний, q0 ∈ Q - начальное состояние, A ⊆ Q - конечное множество допустимых состояний, Σ - конечный входной алфавит, δ - функция переходов Q × Σ → Q. 15
- 17. Конечные автоматы φ - функция конечного состояния. φ() = q0 φ(wa) = δ(φ(w), a) для w ∈ Σ∗, a ∈ Σ 16
- 18. Конечный автомат для поиска подстрок σ(x) = max{k: Pk = x}, где Pk < P ∧ |Pk | = k - суффиксная функция Пример, P = ab, σ() = 0, σ(ccaca) = 1, σ(ccab) = 2. Правила построения автомата: 1. Q = {0, 1, . . . m}, q0 = 0, A = m 2. δ(q, a) = σ(Pq a) 17
- 19. Конечный автомат для образца P = ababaca 18
- 20. Алгоритм поиска подстроки с помощью конечного ав- томата 19
- 21. Алгоритм вычисления функции переходов 20
- 22. Анализ применения конечных автоматов для поиска под- строки Вычисление функции переходов - T (n, m) = O(m3|Σ|). Суще- ствуют алгоритмы - T (n, m) = O(m|Σ|) Поиск подстроки - T (n, m) = Θ(n) 21
- 23. На семинар и рефераты Поиск наибольшей общей последовательности. Алгоритмы поиска подстрок: Кнута-Морриса-Пратта, Бойера- Мура, Демелки-Бейза-Ятса-Гоннета, Бойера-Мура-Хоспула, Бойера-Мура-Санди, Бойера-Мура-Гелила. Алгоритмы вычисления растояния ммежду строками: Вагнера- Фишера, Хешберга, Ханта-Шиманского, Укконена-Майерса. 22
- 24. На семинар и рефераты Алгоритмы для поиска по регулярным выражениям. Алгоритмы вычисления периодичности: Крочемора, Мейна- Лоренца, Колпакова-Кучерова. Алгоритмы построения суффиксных деревьев: Укконена, Вайнера, Мак-Крейга. 23
- 25. Список литературы Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгорит- мы: построение и анализ, 2-е издание. - М. : Издатель- ский дом “Вильямс”, 2007. сс.1017-1046. Смит, Билл. Методы и алгоритмы вычислений на стро- ках. - М.: ООО “И.Д. Вильямс”, 2006. Гасфилд, Дэн. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. - СПб.: Невский Диалект; БХВ-Петербург, 2003. 24
Введение
Те, кому приходиться часто работать с текстовыми редакторами, знают цену функции нахождения нужных слов в тексте, существенно облегчающей редактирование документов и поиск нужной информации. Действительно, современные программы обработки текста приучили нас к такой удобной возможности, как поиск и замена фрагментов, и если вы разрабатываете подобную программу, пользователь вправе ожидать, что вы предоставите в его распоряжение соответствующие команды.
Конечно, сейчас функции поиска инкапсулированы во многие языки программирования высокого уровня – чтобы найти строчку в небольшом тексте вы, наверное, используете встроенную функцию. Но если такого рода поиск является ключевой задачей вашей программы, знать принципы организации функций поиска будет совсем нелишне. При этом. в готовых подпрограммах далеко не всегда все написано лучшим образом. Во-первых, в стандартных функциях не всегда используются самые эффективные алгоритмы, а во-вторых, вполне возможно, что вам понадобится изменить стандартное поведение этих функций (например, предусмотреть возможность поиска по шаблону). Наконец, область применения функции поиска не ограничивается одними лишь текстовыми редакторами. Следует отметить использование алгоритмов поиска при индексации страниц поисковым роботом, где актуальность информации напрямую зависит от скорости нахождения ключевых слов в тексте html – страницы . Работа простейшего спам – фильтра, заключается в нахождении в тексте письма фраз таких, как «Миллион за час» или «Раскрутка сайта». Все вышесказанное говорит об актуальности проблемы, затрагиваемой работой.
Поставим задачу поиска подстроки в строке. Пусть у нас есть строка, состоящая из некоторого количества символов. Нам нужно проверить, входит ли другая заданная строка в данный текст, и если входит, то начиная с какого символа текста.
В данной работе мы ставим цель, выявить наиболее оптимальный алгоритм, решающий поставленную задачу поиска.
Задачи данной работы:
рассмотреть основные алгоритмы, решающих задачу поиска;
систематизировать алгоритмы согласно используемым в них приемам;
выявить эффективные, с точки зрения времени выполнения, алгоритмы.
Работа содержит две основных части. В первой будут рассмотрены алгоритмы, их теоретическое обоснование, алгоритмическая модель, будет проведена попытка их классификации. Во второй части работы будут приведены данные о практическом применении алгоритмов. В заключении будет сделан вывод о наиболее эффективном (с временной точки зрения) алгоритме.
Часть 1. Теоретические сведения об алгоритмах поиска подстроки в строке.
1.1. Основные понятия.
1.1.1 Строка, её длина, подстрока.
Здесь мы приводим ряд определений, которые будем использовать в изложении материала .
Определение 1 . Строка (слово) - это последовательность знаков (называемых буквами) из некоторого конечного множества, называемого алфавитом.
Определение 2 . Длина строки – количество знаков в строке.
Слова будем обозначать буквами латинского алфавита, напр. X=xx…x[n] – слово длинной n, где x[i] (i-ая буква слова) принадлежит алфавиту. Lentgh(X)= =n – обозначение длины строки.
Определение 3 . Слово не содержащее ни одной буквы называется пустым.
Пустое слово обычно обозначают буквой L. Length(L)=0.
Определение 4 . Слово X называется префиксом слова Y, если есть такое слово Z, что Y=XZ. Причем само слово является префиксом для самого себя (т.к. найдется нулевое слово L, что X=LX.
Пример : слово ab является префиксом слова abcfa.
Определение 5 . Слово X называется суффиксом слова Y, если есть такое слово Z, что Y=ZX. Аналогично, слово является суффиксом самого себя.
Пример : слово bfg является суффиксом слова vsenfbfg.
Определение 6 .Слово X называется подстрокой строки Y, если найдутся такие строки Z 1 и Z 2 , что Y=Z 1 XZ 2 . При этом Z 1 называют левым, а Z 2 - правым крылом подстроки. Подстрокой может быть и само слово. Иногда при этом слово X называют вхождением в слово Y. Среди всех вхождений слова X в слово Y, вхождение с наименьшей длиной своего левого крыла называют первым или главным вхождением. Для обозначения вхождения используют обозначение X Y.
Пример : слова hrf и fhr является подстроками слова abhrfhr, gf sfdgfro.
1.1.2. Понятие о сложности алгоритма.
Целью нашей работы является найти эффективный алгоритм, однако ничего пока не было сказано о методе оценки алгоритмов.
Традиционно в программировании понятие сложности алгоритма связано с использованием ресурсов компьютера: насколько много процессорного времени требует программа для своего выполнения, насколько много при этом расходуется память машины? Учет памяти обычно ведется по объему данных и не принимается во внимание память, расходуемая для записи команд программы. Время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой для машин с разной тактовой частотой.
В данной работе будут рассмотрены две характеристики сложности алгоритмов - временная и емкостная. Мы не будем обсуждать логическую сложность разработки алгоритма - сколько «человеко-дней» нужно потратить на создание программы, поскольку не представляется возможным дать объективные количественные характеристики.
Временную сложность будем подсчитывать в исполняемых командах: количество арифметических операций, количество сравнений, пересылок (в зависимости от алгоритма). Емкостная сложность будет определяться количеством переменных, элементов массивов, элементов записей или просто количеством байт .
Эффективность алгоритма также будет оцениваться с помощью подсчета времени выполнения алгоритмом конкретно поставленной задачи, т.е. с помощью эксперимента, подробнее об этом в части 2 данной работы.
1.2. Алгоритмы основанные на методе последовательного поиска.
1.2.1. Алгоритм последовательного (прямого) поиска (The Brute Force Algorithm).
Самый очевидный алгоритм. Обозначим S - слово, в котором ищется образец X. Пусть m и n - длины слов S и X соответственно. Можно сравнить со словом X все подслова S, которые начинаются с позиций 1,2,...,m-n+1 в слове S; в случае равенства выводится соответствующая позиция (Листинг 1).
Очень просто, но очень неразумно. Ведь максимальное, количество сравнений будет равно O((m-n+1)*n+1), хотя большинство из них на самом деле лишние. Например, найдя строку aabc и обнаружив несоответствие в четвертом символе (совпало только aab), алгоритм будет продолжать сравнивать строку, начиная со следующего символа, хотя это однозначно не приведет к результату.
Следующий метод работает намного быстрее простейшего, но, к сожалению, накладывает некоторые ограничения на текст и искомую строку.
1.2.2. Алгоритм Рабина.
Алгоритм Рабина представляет собой модификацию линейного алгоритма; он основан на весьма простой идее, которую изложим, следуя книге .
«Представим себе, что в слове A, длина которого равна m, мы ищем образец X длины n. Вырежем "окошечко" размером n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в "окошечке" с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую числовую функцию на словах длины n, тогда задача сведется к сравнению чисел, что, несомненно, быстрее. Если значения этой функции на слове в "окошечке" и на образце различны, то совпадения нет. Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам.» (Листинг 2)
Error: Reference source not found
Этот алгоритм выполняет линейный проход по строке (n шагов) и линейный проход по всему тексту (m шагов), стало быть, общее время работы есть O(n+m). При этом мы не учитываем временную сложность вычисления хеш-функции, так как, суть алгоритма в том и заключается, чтобы данная функция была настолько легко вычисляемой, что ее работа не влияла на общую работу алгоритма. Тогда, время работы алгоритма линейно зависит от размера строки и текста, стало быть программа работает быстро. Ведь вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, мы можем проверять только те, которые «напоминают» образец. Итак, для того, чтобы легко устанавливать явное несоответствие, будем использовать функцию, которая должна:
1. Легко вычисляться.
2. Как можно лучше различать несовпадающие строки.
3. hash(y[ i+1 , i+m ]) должна легко вычисляться по hash(y[ i , i+m-1 ].
Во время поиска х будем сравнивать hash(x) с hash(y[ i, i+m-1 ]) для i от 0 до n-m включительно. Если обнаруживаем совпадение, то проверяем посимвольно.
Пример (удобной для вычисления функции) . Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге "окошечка" нужно добавить новое число и вычесть "пропавшее".)
Однако, проблема в том, что искомая строка может быть длинной, строк в тексте тоже хватает. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть, числа будут большими (порядка D*n, где D - количество различных символов), и работать с ними будет так же неудобно. Но какой интерес работать только с короткими строками и цифрами? Разработчики алгоритма придумали, как улучшить этот алгоритм без особых потерь в скорости работы.
Пример (семейства удобных функций) . Выберем некоторое число p (желательно простое) и некоторый вычет x по модулю p. Каждое слово длины n будем рассматривать как последовательность целых чисел (заменив буквы их кодами). Эти числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и x получается своя функция). Сдвиг "окошечка" на 1 соответствует вычитанию старшего члена, умножению на x и добавлению свободного члена. Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано и к тому же оно является простым, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены (мы предполагаем, что коды всех букв различны - это возможно при p, большем числа букв алфавита). Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, т.е. их разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если n много меньше p, то случайному значению x мало шансов попасть в "неудачную" точку.
Строго говоря, время работы всего алгоритма в целом, есть O(m+n+mn/P), mn/P достаточно невелико, так что сложность работы почти линейная. Понятно, что простое число следует выбирать большим, чем больше это число, тем быстрее будет работать программа.
Алгоритм Рабина и алгоритм последовательного поиска являются алгоритмами с наименьшими трудозатратами, поэтому они годятся для использования при решении некоторого класса задач. Однако эти алгоритмы не являются наиболее оптимальными (хотя бы потому, что иногда выполняют явно бесполезную работу, о чем было сказано выше), поэтому мы перейдём к следующему классу алгоритмов. Эти алгоритмы появились в результате тщательного исследования алгоритма последовательного поиска. Исследователи хотели найти способы более полно использовать информацию, полученную во время сканирования (алгоритм прямого поиска ее просто выбрасывает). Рассмотрим алгоритм Кнута – Морриса – Пратта.
1.3. Алгоритм Кнута - Морриса - Пратта (КМП).
Вначале рассмотрим некоторые вспомогательные утверждения. Для произвольного слова X рассмотрим все его начала, одновременно являющиеся его концами, и выберем из них самое длинное (не считая, конечно, самого слова X). Обозначим его n(X). Такая функция носит название префикс – функции .
Примеры .
n(aba)=a, n(n(aba))=n(a)=L;
n(abab)=ab, n(n(abab))=n(ab)=L;
n(ababa)=aba, n(n(ababa))=n(aba)=a, n(n(n(ababa)))=n(a)=L; n(abc)=L.
Докажем несколько используемых впоследствии фактов, а именно предложение (по [Шень,1995,с.165-166]):
(1) Последовательность слов n(X),n(n(X)),n(n(n(X))),... "обрывается" (на пустом слове L).
(2) Все слова n(X),n(n(X)),n(n(n(X))),...,L являются началами слова X.
(3) Любое слово, одновременно являющееся началом и концом слова X (кроме самого X), входит в последовательность n(X),n(n(X)),....,L.
Доказательство .
(1) Тривиально, т.к. каждое слово короче предыдущего.
(2) Каждое из них (по определению) является началом предыдущего. По той же причине все они являются концами слова X.
(3) Пусть слово Y является одновременно началом и концом X. Слово n(X) - самое длинное из таких слов, так что Y не длиннее n(X). Оба эти слова являются началами X, поэтому более короткое из них является началом более длинного: Y есть начало n(X). Аналогично, Y есть конец n(X). Рассуждая по индукции, можно предполагать, что утверждение задачи верно для всех слов короче X, в частности, для слова n(X). Так что слово Y, являющееся концом и началом n(X), либо равно n(X), либо входит в последовательность n(n(X)),n(n(n(X))),...,L.
Предложение доказано.
Метод КМП
использует
предобработку
искомой строки,
а именно: на ее
основе создается
префикс-функция.
При этом используется
следующая идея:
если префикс
(он же суффикс)
строки длинной
i длиннее одного
символа, то он
одновременно
и префикс подстроки
длинной i-1 (Листинг
3). Таким образом,
мы проверяем
префикс предыдущей
подстроки, если
же тот не подходит,
то префикс ее
префикса, и
т.д. Действуя
так, находим
наибольший
искомый префикс.
Следующий
вопрос, на который
стоит Error: Reference source not foundответить:
почему время
работы процедуры
линейно, ведь
в ней присутствует
вложенный цикл?
Ну, во-первых,
присвоение
префикс-функции
происходит
четко m раз,
остальное время
меняется переменная
k. Так как в цикле
while она уменьшается
(P[k] Доказать
что эта программа
работает за
линейное время,
можно точно
так же, как и
для префикс
- функции. Стало
быть, общее
время работы
программы есть
O(n+m), т. е. линейное
время. Напоследок
заметим, что
алгоритм
последовательного
поиска и алгоритм
КМП помимо
нахождения
самих строк
считают, сколько
символов совпало
в процессе
работы. 1.4. Алгоритм
Бойера
– Мура и
некоторые его
модификации.
1.4.1.
Алгоритм Боейера
– Мура.
Алгоритм
Бойера-Мура,
разработанный
двумя учеными
– Бойером (Robert
S. Boyer) и
Муром (Strother
Moore), считается
наиболее быстрым
среди алгоритмов
общего назначения,
предназначенных
для поиска
подстроки в
строке. Простейший
вариант алгоритма
Бойера-Мура
состоит из
следующих
шагов. На первом
шаге мы строим
таблицу смещений
для искомого
образца. Процесс
построения
таблицы будет
описан ниже.
Далее мы совмещаем
начало строки
и образца и
начинаем проверку
с последнего
символа образца.
Если последний
символ образца
и соответствующий
ему при наложении
символ строки
не совпадают,
образец сдвигается
относительно
строки на величину,
полученную
из таблицы
смещений, и
снова проводится
сравнение,
начиная с последнего
символа образца.
Если же символы
совпадают,
производится
сравнение
предпоследнего
символа образца
и т. д. Если все
символы образца
совпали с наложенными
символами
строки, значит
мы нашли подстроку
и поиск окончен.
Если же какой-то
(не последний)
символ образца
не совпадает
с соответствующим
символом строки,
мы сдвигаем
образец на один
символ вправо
и снова начинаем
проверку с
последнего
символа. Весь
алгоритм выполняется
до тех пор, пока
либо не будет
найдено вхождение
искомого образца,
либо не будет
достигнут конец
строки. Величина
сдвига в случае
несовпадения
последнего
символа вычисляется
исходя из следующих
соображений:
сдвиг образца
должен быть
минимальным,
таким, чтобы
не пропустить
вхождение
образца в строке.
Если данный
символ строки
встречается
в образце, мы
смещаем образец
таким образом,
чтобы символ
строки совпал
с самым правым
вхождением
этого символа
в образце. Если
же образец
вообще не содержит
этого символа,
мы сдвигаем
образец на
величину, равную
его длине, так
что первый
символ образца
накладывается
на следующий
за проверявшимся
символ строки. Величина
смещения для
каждого символа
образца зависит
только от порядка
символов в
образце, поэтому
смещения удобно
вычислить
заранее и хранить
в виде одномерного
массива, где
каждому символу
алфавита
соответствует
смещение относительно
последнего
символа образца.
Поясним все
вышесказанное
на простом
примере. Пусть
у нас есть алфавит
из пяти символов:
a, b, c, d, e и мы хотим
найти вхождение
образца “abbad”
в строке
“abeccacbadbabbad”. Следующие
схемы иллюстрируют
все этапы выполнения
алгоритма.
Таблица смещений
будет выглядеть
так. Начало поиска. Последний
символ образца
не совпадает
с наложенным
символом строки.
Сдвигаем образец
вправо на 5 позиций: Три символа
образца совпали,
а четвертый
– нет. Сдвигаем
образец вправо
на одну позицию: Последний
символ снова
не совпадает
с символом
строки. В соответствии
с таблицей
смещений сдвигаем
образец на 2
позиции: Еще раз сдвигаем
образец на 2
позиции: Теперь, в
соответствии
с таблицей,
сдвигаем образец
на одну позицию,
и получаем
искомое вхождение
образца: Реализуем
указанный
алгоритм на
языке Pascal. Прежде всего
следует определить
тип данных
«таблица смещений».
Для кодовой
таблицы, состоящей
из 256 символов,
определение
этого типа
будет выглядеть
так: TBMTable = Array of Integer; Теперь напишем
функцию, осуществляющую
поиск (Листинг
6). Параметр
StartPos позволяет
указать позицию
в строке s, с которой
следует начинать
поиск. Это может
быть полезно
в том случае,
если вы захотите
найти все вхождения
p в s. Для поиска
с самого начала
строки следует
задать StartPos равным
1. Если результат
поиска не равен
нулю, то для
того, чтобы
найти следующее
вхождение p в
s, нужно задать
StartPos равным значению
«предыдущий
результат плюс
длина образца». 1.4.2.
Модификации
БМ.
Сдвиг плохого
символа, используемый
в алгоритме
Боуера
- Мура, не очень
эффективен
для маленького
алфавита, но,
когда размер
алфавита большой
по сравнению
с длиной образца,
как это часто
имеет место
с Error: Reference source not found таблицей
ASCII и при обычном
поиске в текстовом
редакторе, он
становится
чрезвычайно
полезен. Использование
в алгоритме
только его
одного может
быть весьма
эффективным. После попытки
совмещения
x и y , длина сдвига
- не менее 1. Таким
образом, символ
y [ i + m ] обязательно
будет вовлечен
в следующую
попытку, а значит,
может быть
использован
в текущей попытке
для сдвига
плохого символа.
Модифицируем
функцию плохого
символа, чтобы
принять в расчет
последний
символ х: bc[ a ] = min { j | 0
j
m и x[ m - 1 - j ] = a }, если a
встречается
в x, bc[ a ] = m в противоположном
случае. Сравнения
текста и образца
могут производиться
в любом порядке. Турбо - БМ
является также
является улучшением
алгоритма
Боуера
- Мура. Мы будем
запоминать
сегмент текста,
который сошелся
с суффиксом
образца во
время прошлой
попытки (и только,
если произошел
сдвиг хорошего
суффикса). Это даст нам
два преимущества: 1. Возможность
перескочить
через этот
сегмент 2. Возможность
применения
«турбо – сдвига» «Турбо –
сдвиг» может
произойти, если
мы обнаружим,
что суффикс
образца, который
сходится с
текстом, короче,
чем тот, который
был запомнен
ранее. Пусть u - запомненный
сегмент, а v -
cуффикс, совпавший
во время текущей
попытки, такой
что uzv - суффикс
x. Тогда av - суффикс
x, два символа
а и b встречаются
на расстоянии
p в тексте, и суффикс
x длины |uzv| имеет
период длины
p, а значит не
может перекрыть
оба появления
символов а и
b в тексте. Наименьший
возможный сдвиг
имеет длину
|u| - |v| (его мы и называем
«турбо – сдвигом»). 1.5. Поиск
подстрок с
помощью конечного
автомата.
1.5.1.
Структура
автомата.
По определению,
конечный автомат
представляет
собой пятерку
М = (Q, q 0 , A,
,
),
где: Q - конечное
множество
состояний; q 0 Q
- начальное
состояние; А Q
- конечное
множество
допускающих
состояний; Конечный
входной алфавит; Функция
Q х
Q, называемая
функцией переходов
автомата. Первоначально
конечный автомат
находится в
состоянии q 0 .
Затем он по
очереди читает
символы из
входной строки.
Находясь в
состоянии q и
читая символ
а, автомат переходит
в состояние
(q,a).
Если автомат
находится в
состоянии q
A
говорят, что
он допускает
прочитанную
часть входной
строки. Если
q
А, то прочитанная
часть строки
отвергнута. С конечным
состоянием
М связана функция
,
называемая
функцией конечного
состояния,
определяемая
следующим
образом:
есть
состояние, в
которое придет
автомат (из
начального
состояния),
прочитав строку
w. Автомат
допускает
строку w
тогда и только
тогда, когда
А Для каждого
образца Р можно
построить
конечный автомат,
ищущий этот
образец в тексте.
Первым шагом
в построении
автомата,
соответствующего
строке-образцу
Р, является
построение
по Р вспомогательной
суффикс-функциии
(как в алгоритме
КМП). Теперь
определим
конечный автомат,
соответствующий
образцу Р,
следующим
образом: Поясним это
соотношение.
Требуется
сконструировать
автомат таким
образом, чтобы
при его действии
на строку Т
соотношение (Т i)
=
(Т i) являлось
инвариантом
(тогда равенство
(Т i)
= m будет
равносильно
тому, что Р входит
в Т со сдвигом
i - m, и
автомат тем
самым найдет
все допустимые
сдвиги). Однако
в этом случае
вычисление
перехода по
формуле (1) необходимо
для поддержания
истинности
инварианта,
что следует
из теорем,
приведенных
ниже. Теорема. Пусть
q =
(х),
где х - строка.
Тогда для любого
символа а имеет
место
(ха) =
(P q a). Теорема. Пусть
- функция конечного
состояния
автомата для
поиска подстроки
Р. Если
Т - произвольный
текст, то
(Т i)
=
(Т i)
для i=0,1,..., n.
Из изложенного
следует, что
задача поиска
подстроки
состоит из двух
частей: построение
автомата по
образцу (определение
функции переходов
для заданного
образца); применение
этого автомата
для поиска
вхождений
образца в заданный
текст. 1.5.2.
Пример построения
конечного
автомата
Построим
конечный автомат,
допускающий
строку ababaca. Поскольку
длина образца
m = 7 символов,
то в автомате
будет m + 1 =
8 состояний. Найдем функцию
переходов
.
В соответствии
с определением
(1),
(q,
a) = (Р q а),
где
- префикс-функция,
а - произвольный
символ из алфавита
,
q - номер состояния.
Таким образом,
необходимо
для каждого
префикса P q
= P, q = 0 .. m образца
Р и для всех
символов а
входного алфавита
найти длину
максимального
префикса Р,
который будет
являться суффиксом
строки Р q а.
Длина этого
префикса и
будет значением
функции переходов
(q,a).
Если а = P (очередной
символ текста
совпал со следующим
символом образца),
то Р q а =
Р q +1 и
(q,
a) = q+1. Такой случай
соответствует
успешным этапам
поиска. Иначе,
(q,a) q.
Например, для
префикса Р
= ababa и символа b
максимальным
суффиксом
строки Рb=ababab,
который одновременно
является префиксом
Р, будет abab. Его
длина равна
4, поэтому значение
функции переходов
(5,
b) = 4. Запишем
построенную
таким образом
функцию переходов
в виде таблицы
(Табл. 1): Строки соответствуют
входным символам,
столбцы - состояниям
автомата. Ячейки,
соответствующие
успешным этапам
поиска (входной
символ совпадает
со следующим
символом образца),
выделены серым
цветом. Построим
по таблице граф
переходов
автомата (Рис.
1), распознающего
образец ababaca. Находясь
в состоянии
q и прочитав
очередной
символ а, автомат
переходит в
состояние
(q,a).
Обратим внимание,
что его остов
помечен символами
образца (эти
переходы выделены
жирными стрелками). Здесь 0 - исходное
состояние, 7 -
единственное
допускающее
состояние
(зачернено).
Если из вершины
i в
вершину j ведет
стрелка, помеченная
буквой а, то
это означает,
что
(i,a)
= j. Отметим, что
переходы, для
которых
(i,a)
= 0, на графе переходов
для его упрощения
не обозначены.
Жирные стрелки,
идущие слева
направо, соответствуют
успешным этапам
поиска подстроки
Р - следующий
входной символ
совпадает с
очередным
символом образца.
Стрелки, идущие
справа налево,
соответствуют
неудачам -
следующий
входной символ
отличается
от очередного
символа образца. Ниже приведен
результат
применения
автомата к
тексту Т = abababacaba. Под
каждым символом
Т[г] записано
состояние
автомата после
прочтения этого
символа (иными
словами, значение
(Т i))
(Табл. 2). Найдено
одно вхождение
образца (начиная
с позиции 3).
Найденный
образец в тексте
помечен серым
цветом. Черным
цветом помечено
допускающее
состояние
автомата (состояние
с номером 7). Часть
2. Экспериментальный
анализ алгоритмов.
2.1. Суть
эксперимента.
Мы рассмотрели
несколько
алгоритмов,
провели оценку
их временной
и емкостной
сложности.
Однако, как уже
говорилось,
данные критерии
оценки не позволяют
нам наверняка
сказать, какой
из алгоритмов
будет быстрее
работать. Поэтому,
для дополнительной
оценки проведем
их экспериментальный
анализ, т.е. измерим
время, за которое
алгоритм выполняет
конкретно
поставленную
задачу. Имеется
несколько
текстовых
файлов, содержащих
10000 записей
вида: с разными
максимальными
длинами строк
и подстрок. Алфавитом
является 66 русских
заглавных и
строчных букв. Пусть это
будут строки
длиной не более
10, 100, 250 символов. Проведем
поиск подстрок
в строках для
каждого из
алгоритмов
и измерим время
работы программы.
При этом будем
учитывать
следующее: Строки
предварительно
загружаем в
оперативную
память (в виде
массива), причем
время считывания
в массив не
учитывается.
Предобработка
(создание таблиц
перехода) входит
в общее время. Каждый алгоритм
запускается
5 раз, время
выбирается
наименьшее. Стенд для
эксперимента.
Процессор
Intel Pentium IV 2,66Ггц 1024 Мб
ОЗУ Компилятор
Borland Delphi Enterprise, version 6.0 (Build 6.163) Фрагмент
кода тестируемой
программы
приведем в
листинге 7. Error: Reference source not found Понятно, что
такой замер
времени даст
нам весьма
расплывчатые
результаты,
так как напрямую
зависит от
характеристик
и загрузки
процессора.
Поэтому во
время проведения
эксперимента,
отключались
все сторонние
и фоновые приложения,
которые не
влияют на работу
программы. При
запуске одной
и той же задачи
мы можем получить
разное время,
поэтому совершается
несколько
запусков, из
которых выбирается
наилучший
результат. 2.2.
Результаты
и анализ эксперимента.
Эксперимент
проводился
для четырех
алгоритмов
– представителей
классов алгоритмов.
Так как все
алгоритмы
ставились в
одинаковые
условия, то
можно провести
их сравнительный
анализ. Заметим,
что данный
анализ применим
только для
данных параметров
поиска, и при
иных условиях
может отличаться. Результаты
эксперимента
занесем в таблицу
(Табл. 3). Как и предполагалось,
алгоритм Бойера
– Мура справился
с экспериментальной
задачей быстрее
остальных.
Следует, однако,
заметить, что
его эффективность
растет лишь
с увеличением
длины строки
и, соответственно,
длины образца.
Так при длине
строки меньшей
или равной 10
символов, он
показал себя
хуже, чем последовательный
поиск. Аналогичные
результаты
показывает
и алгоритм КМП,
как для коротких,
так и для длинных
слов. Его можно
использовать
как универсальный,
когда неизвестны
длины строки
и образца. Алгоритм
Рабина, при его
схожести с
последовательным
работает быстрее,
а его простота
и малые трудозатраты
на реализацию,
делают его
привлекательным
для использования
в неспециальных
программах. Наихудший
результат
показал алгоритм
последовательного
поиска. Как
предполагалось
лишь при небольшом
увеличении
длины строки,
он работает
в разы медленнее
остальных
алгоритмов. В данный
эксперимент
не включен
алгоритм поиска
с помощью конечного
автомата, т.к.
мы используем
алфавит, состоящий
из 66 букв русского
алфавита, и
построенный
автомат был
бы слишком
громоздок.
Эффективность
этого алгоритма
возрастает
при малом количестве
букв в алфавите. Заключение.
Мы рассмотрели
различные
алгоритмы
поиска подстроки
в строке, сделали
их анализ. Результаты
можно представить
в таблице (Табл.
4). Исходя из
полученных
результатов,
видно, что алгоритм
Бойера – Мура
является ведущим
по всем параметрам,
казалось бы,
найден самый
эффективный
алгоритм. Но,
как показывает
эксперимент,
алгоритм Кнута
– Мориса - Пратта,
превосходит
алгоритм БМ
на небольших
длинах образца.
Поэтому я не
могу сделать
вывод, что какой-то
из алгоритмов
является самым
оптимальным.
Каждый алгоритм
позволяет
эффективно
действовать
лишь для своего
класса задач,
об этом еще
говорят различные
узконаправленные
улучшения.
Алгоритм поиска
подстроки в
строке следует
выбирать только
после точной
постановки
задачи, которые
должна выполнять
программа. Сделав такой
вывод, мы выполнили
цель данной
работы, т.к. для
различных
классов задач
был выделен
свой эффективный
алгоритм. Библиографический
список.
1).
Kurtz, St. Fundamental Algorithms For A Declarative Pattern Matching
System [Текст].
– Bielefeld:. Universitдt Bielefeld, 1995. – 238 с. 2).
Lecro, T. Exact string matching algorithms [Электронный
ресурс].
Режим доступа
http://algolist.manual.ru/ 3).
Ахметов И. Поиск
подстрок с
помощью конечных
автоматов
[Текст]: Курсовая
работа.- С-П
государственный
университет
информационных
технологий,
механики и
оптики. 4).
Ахо, Альфред
Структура
данных и алгоритмы
[Текст]. – М.: Издательский
дом «Вильямс»,
2000. - 384 с. 5).
Белоусов А.
Дискретная
математика
[Текст]. – М.: Издательство
МГТУ им. Н.Э.
Баумана, 2001. – 744
с. 6).
Брайан, К. Практика
программирования
[Текст].- СПб:.
Невский диалект,
2001. - 381 с. 7).
Вирт, Н. Алгоритмы
и структуры
данных [Текст].–
М:. Мир, 1989. – 360 с. 8).
Гилл, Арт. Введение
в теорию конечных
автоматов
[Текст]. – М., 1966. -
272 с. 9).
Глушаков С.
Программирование
Web – страниц
[Текст]. – М.: ООО
«Издательство
АСТ», 2003. – 387 с. 10).
Кнут, Д. Искусство
программирования
на ЭВМ [Текст]:
Том 3. – М:. Мир,
1978. – 356 с. 11).
Матрос Д. Элементы
абстрактной
и компьютерной
алгебры: Учеб.
пособие для
студ. педвузов
[Текст]. – М.: Издательский
центр «Академия»,
2004. – 240 с. 12).
Успенский В.
Теория алгоритмов:
основные открытия
и приложения
[Текст]. – М.: Наука,
1987. – 288 с. 13).
Шень, А. Программирование:
теоремы и задачи
[Текст]. – М.: Московский
центр непрерывного
математического
образования,
1995. 14).
Кормен, Т. Алгоритмы:
построение
и анализ [Текст]/
Т. Кормен, Ч. Лейзерсон,
Р. Ривест - М.:
МЦНМО, 2002. М.: МЦНМО,
2002. Суффиксный автомат
(или ориентированный ациклический граф слов
) — это мощная структура данных, которая позволяет решать множество строковых задач. Например, с помощью суффиксного автомата можно искать все вхождения одной строки в другую, или подсчитывать количество различных подстрок данной строки — обе задачи он позволяет решать за линейное время. На интуитивном уровне, суффиксный автомат можно понимать как сжатую информацию обо всех подстроках
данной строки. Впечатляющим фактом является то, что суффиксный автомат содержит всю информацию в настолько сжатом виде, что для строки длины он требует лишь памяти. Более того, он может быть построен также за время (если мы считаем размер алфавита константой; в противном случае — за время ). Исторически
, впервые линейность размера суффиксного автомата была открыта в 1983 г. Blumer и др., а в 1985 — 1986 гг. были представлены первые алгоритмы его построения за линейное время (Crochemore, Blumer и др.). Более подробно — см. список литературы в конце статьи. На английском языке суффиксный автомат называется "suffix automaton" (во множественном числе — "suffix automata"), а ориентированный ациклический граф слов — "directed acyclic word graph" (или просто "DAWG"). Определение. Суффиксным автоматом
для данной строки называется такой минимальный детерминированный конечный автомат, который принимает все суффиксы строки . Расшифруем это определение. Простейшим, и вместе с тем важнейшим свойством суффиксного автомата является то, что он содержит в себе информацию обо всех подстроках строки . А именно, любой путь
из начального состояния , если мы выпишем метки дуг вдоль этого пути, образует обязательно подстроку
строки . И наоборот, любой подстроке строки соответствует некоторый путь, начинающийся в начальном состоянии . В целях упрощения объяснений, мы будем говорить, что подстроке соответствует
тот путь из начального состояния, метки вдоль которого образуют эту подстроку. И наоборот, мы будем говорить, что любому пути соответствует
та строка, которую образуют метки его дуг. В каждое состояние суффиксного автомата ведёт один или несколько путей из начального состояния. Будем говорить, что состоянию соответствует
набор строк, соответствующих всем этим путям. Приведём примеры суффиксных автоматов, построенных для нескольких простых строк. Начальное состояние мы будем обозначать здесь через , а терминальные состояния — отмечать звёздочкой. Для строки : Для строки : Для строки : Для строки : Для строки : Для строки : Для строки : Перед тем, как перейти непосредственно к описанию алгоритма построения, надо ввести несколько новых понятий и доказать простые, но очень важные для понимания суффиксного автомата леммы. Рассмотрим любую непустую подстроку строки . Тогда назовём множеством окончаний
множество всех позиций в строке , в которых оканчиваются вхождения строки . Мы будем называть две подстроки и -эквивалентными, если их множества окончаний совпадают: . Таким образом, все непустые подстроки строки можно разбить на несколько классов эквивалентности
соответственно их множествам . Оказывается, что в суффиксном автомате -эквивалентным подстрокам соответствует одно и то же состояние
. Иными словами, число состояний в суффиксном автомате равно количеству классов -эквивалентности среди всех подстрок, плюс одно начальное состояние. Каждому состоянию суффиксного автомата соответствуют одна или несколько подстрок, имеющих одно и то же значение . Это утверждение мы примем как аксиому
, и опишем алгоритм построения суффиксного автомата, исходя из этого предположения — как мы затем увидим, все требуемые свойства суффиксного автомата, кроме минимальности, будут выполнены. (А минимальность следует из теоремы Nerode — см. список литературы.) Приведём также несколько простых, но важных утверждений касательно значений . Лемма 1
. Две непустые подстроки и () являются -эквивалентными тогда и только тогда, когда строка встречается в строке только в виде суффикса строки . Доказательство практически очевидно. В одну сторону: если и имеют одинаковые позиции окончаний вхождения, то является суффиксом , и она присутствует в только в виде суффикса . В обратную сторону: если является суффиксом и входит только как этот суффикс, то их значения равны по определению. Лемма 2
. Рассмотрим две непустые подстроки и (). Тогда их множества либо не пересекаются, либо целиком содержится в , причём это зависит от того, является суффиксом или нет: Доказательство. Предположим, что множества и имеют хотя бы один общий элемент. Тогда это означает, что строки и оканчиваются в одном и том же месте, т.е. — суффикс . Но тогда каждое вхождение строки содержит на своём конце вхождение строки , что и означает, что его множество целиком вкладывается в множество . Лемма 3
. Рассмотрим некоторый класс -эквивалентности. Отсортируем все подстроки, входящие в этот класс, по невозрастанию длины. Тогда в получившейся последовательности каждая подстрока будет на единицу короче предыдущей, и при этом являться суффиксом предыдущей. Иными словами, подстроки, входящие в один класс эквивалентности, на самом деле являются суффиксами друг друга, и принимают всевозможные различные длины в некотором отрезке
. Доказательство. Зафиксируем некоторый класс -эквивалентности. Если он содержит только одну строку, то корректность леммы очевидна. Пусть теперь количество строк больше одной. Согласно лемме 1, две различные -эквивалентные строки всегда таковы, что одна является собственным суффиксом другой. Следовательно, в одном классе -эквивалентности не может быть строк одинаковой длины. Обозначим через длиннейшую, а через — кратчайшую строку в данном классе эквивалентности. Согласно лемме 1, строка является собственным суффиксом строки . Рассмотрим теперь любой суффикс строки с длиной в отрезке , и покажем, что он содержится в этом же классе эквивалентности. В самом деле, этот суффикс может входить в только в виде суффикса строки (поскольку более короткий суффикс входит только в виде суффикса строки ). Следовательно, согласно лемме 1, этот суффикс -эквивалентен строке , что и требовалось доказать. Рассмотрим некоторое состояние автомата . Как мы теперь знаем, состоянию соответствует некоторый класс строк с одинаковыми значениями , причём если мы обозначим через длиннейшую из этих строк, то все остальные будут суффиксами . Также мы знаем, что первые несколько суффиксов строки (если мы рассматриваем суффиксы в порядке убывания их длины) содержатся в том же самом классе эквивалентности, а все остальные суффиксы (как минимум, пустой суффикс) — в каких-то других классах. Обозначим через первый такой суффикс — в него мы и проведём суффиксную ссылку. Здесь мы считаем, что начальному состоянию соответствует отдельный класс эквивалентности (содержащий только пустую строку), и полагаем . Доказательство. Рассмотрим произвольное состояние . Суффиксная ссылка ведёт из него в состояние, которому соответствуют строки строго меньшей длины (это следует из определения суффиксной ссылки и из леммы 3). Следовательно, двигаясь по суффиксным ссылкам, мы рано или поздно придём из состояния в начальное состояние , которому соответствует пустая строка. Лемма 5
. Если мы построим из всех имеющихся множеств дерево
(по принципу "множество-родитель содержит как подмножества всех своих детей"), то оно будет совпадать по структуре с деревом суффиксных ссылок. Доказательство. То, что из множеств можно построить дерево, следует из леммы 2 (о том, что любые два множества либо не пересекаются, либо одно содержится в другом). Рассмотрим теперь произвольное состояние и его суффиксную ссылку . Из определения суффиксной ссылки и из леммы 2 следует: что вкупе с предыдущей леммой и доказывает наше утверждение: дерево суффиксных ссылок по сути своей есть дерево вкладывающихся множеств . Приведём пример
дерева суффиксных ссылок в суффиксном автомате, построенном для строки : Перед тем, как приступить к самому алгоритму, систематизируем накопленные выше знания, и введём пару вспомогательных обозначений. Приступим к описанию самого алгоритма. Алгоритм будет онлайновым
, т.е. будет добавлять по одному символу строки , перестраивая соответствующим образом текущий автомат. Чтобы достичь линейного потребления памяти, в каждом состоянии мы будем хранить только значение , и список переходов из этого состояния. Метки терминальных состояний мы поддерживать не будем (мы покажем, как расставить эти метки после построения суффиксного автомата, если имеется необходимость в них). Изначально
автомат состоит из единственного состояния , которое мы условимся считать нулевым состоянием (остальные состояния будут получать номера ). Присвоим этому состоянию , а значению присвоим для удобства (означающее ссылку на фиктивное, несуществующее состояние). Соответственно, вся задача теперь сводится к тому, чтобы реализовать обработку добавления одного символа
в конец текущей строки. Опишем этот процесс: После клонирования мы проводим суффиксную ссылку из в это состояние , также перенаправляем суффиксную ссылку из в . Наконец, последнее, что мы должны сделать — это пройтись от состояния по суффиксным ссылкам, и для каждого очередного состояния проверять: если имелся переход по букве в состояние , то перенаправлять его в состояние (а если нет, то останавливаться). Если нам также нужно знать, какие вершины являются терминальными
, а какие — нет, то мы можем найти все терминальные вершины после построения суффиксного автомата для всей строки. Для этого рассмотрим состояние, соответствующее всей строке (оно, очевидно, у нас сохранено в переменной ), и будем идти по его суффиксным ссылкам, пока не дойдём до начального состояния, и помечать каждое пройденное состояние как терминальное. Легко понять, что тем самым мы пометим состояния, соответствующие всем суффиксам строки , что нам и требовалось. В следующем разделе мы подробно рассмотрим каждый шаг алгоритма и покажем его корректность
. Здесь же лишь отметим, что из алгоритма видно, что добавление одного символа приводит к добавлению одного или двух состояний в автомат. Таким образом, линейность числа состояний
очевидна. Линейность числа переходов, да и вообще линейное время работы алгоритма менее понятны, и они будут доказаны ниже, после доказательства корректности алгоритма. Как можно увидеть из описания алгоритма, сплошные и несплошные переходы приводят к разным ветвям алгоритма. Сплошные переходы называются так потому, что, появившись впервые, они больше никогда не будут меняться. В противоположность им, несплошные переходы могут измениться при добавлении новых букв к строке (измениться может конец дуги-перехода). Однако возникает сложность с тем, куда вести суффиксную ссылку из состояния . Нам требуется провести суффиксную ссылку в такое состояние, в котором длиннейшей строкой будет являться как раз эта самая , т.е. для этого состояния должен быть равен . Однако такого состояния могло и не существовать: в таком случае нам надо произвести "расщепление"
состояния. Как производить это расщепление? Мы "клонируем"
состояние , делая его копию с параметром . Мы копируем в из все переходы, поскольку мы не хотим никоим образом менять пути, проходившие через . Суффиксную ссылку из мы ведём туда, куда вела старая суффиксная ссылка из , а ссылку из направляем в . После клонирования мы проводим суффиксную ссылку из в — то, ради чего мы и производили клонирование. Остался последний шаг — перенаправить некоторые входящие в переходы, перенаправив их на . Какие именно входящие переходы надо перенаправить? Достаточно перенаправить только переходы, соответствующие всем суффиксам строки , т.е. нам надо продолжить двигаться по суффиксным ссылкам, начиная с вершины , и до тех пор, пока мы не дойдём до фиктивного состояния или не дойдём до состояния, переход из которого ведёт в состояние, отличное от . Во-первых, сразу оговоримся, что мы считаем размер алфавита константой
. Если это не так, то говорить о линейном времени работы не получится: список переходов из одной вершины надо хранить в виде сбалансированного дерева, позволяющего быстро производить операции поиска по ключу и добавления ключа. Следовательно, если мы обозначим через размер алфавита, то асимптотика алгоритма составит при памяти. Впрочем, если алфавит достаточно мал, то можно, пожертвовав памятью, избежать сбалансированных списков, а хранить переходы в каждой вершине в виде массива длины (для быстрого поиска по ключу) и динамического списка (для быстрого обхода всех имеющихся ключей). Тем самым мы достигнем во времени работы алгоритма, но ценой потребления памяти. Если мы рассмотрим все части алгоритма, то он содержит три места, линейная асимптотика которых не очевидна: Воспользуемся известным фактом, что размер суффиксного автомата (как по числу состояний, так и по числу переходов) линеен
. (Доказательством линейности по числу состояний является сам алгоритм, а доказательство линейности по числу переходов мы приведём ниже, после реализации алгоритма.). Тогда очевидна линейная суммарная асимптотика первого и второго места
: ведь каждая операция здесь добавляет в автомат один новый переход. Осталось оценить суммарную асимптотику в третьем месте
— в том, где мы перенаправляем переходы, ведущие в , на . Обозначим . Это суффикс строки , и с каждой итерацией его длина убывает — а, значит, и позиция как суффикса строки монотонно возрастает с каждой итерацией. При этом, если перед первой итерацией цикла соответствующая строка была на глубине () от (если считать глубиной число суффиксных ссылок, которые надо пройти), то после последней итерации строка станет -ой суффиксной ссылкой на пути от (которое станет новым значением ). Таким образом, каждая итерация этого цикла приводит к тому, что позиция строки как суффикса всей текущей строки будет монотонно увеличиваться. Следовательно, всего этот цикл не мог отработать более итераций, что и требовалось доказать
. (Стоит заметить, что аналогичные аргументы можно использовать и для доказательства линейности работы первого места, вместо ссылки на доказательство линейности числа состояний.) Вначале опишем структуру данных, которая будет хранить всю информацию о конкретном переходе (, , список переходов). При необходимости сюда можно добавить флаг терминальности, а также другую требуемую информацию. Список переходов мы храним в виде стандартного контейнера , что позволяет достичь суммарно памяти и времени на обработку всей строки. Сам суффиксный автомат будем хранить в виде массива этих структур . Как доказывается в следующем разделе, если — это максимально возможная в программе длина строки, то достаточно завести память под состояний. Также мы храним переменную — состояние, соответствующее всей строке на данный момент. Приведём функцию, инициализирующую суффиксный автомат (создающую автомат с единственным начальным состоянием): Наконец, приведём реализацию основной функции — которая добавляет очередной символ в конец текущей строки, перестраивая соответствующим образом автомат: Как уже упоминалось выше, если пожертвовать памятью (до , где — размер алфавита), то можно достичь времени построения автомата даже для любых — но для этого придётся в каждом состоянии хранить массив размера (для быстрого поиска перехода по нужной букве) и список всех переходов (для быстрого обхода или копирования всех переходов). Число состояний в суффиксном автомате, построенном для строки длины , не превышает
(для ). Доказательством этого является описанный выше алгоритм (поскольку изначально автомат состоит из одного начального состояния, на первом и втором шагах добавляется ровно по одному состоянию, а на каждом из остальных шагах могло добавляться по две вершины из-за расщепления состояния). Однако эту оценку легко показать и без знания алгоритма
. Вспомним о том, что число состояний равно количеству различных значений множеств . Кроме того, эти множества образуют дерево по принципу "вершина-родитель содержит в себе как подмножества всех детей". Рассмотрим это дерево, и немного преобразуем его: пока в нём есть внутренняя вершина с одним сыном, то это означает, что этого сына не содержит как минимум одно число из родителя; тогда создадим виртуальную вершину с , равным этому числу, и привесим этого сына к родителю. В итоге мы получим дерево, в котором каждая внутренняя вершина имеет степень больше единицы, а число листьев не превосходит . Следовательно, всего в таком дереве не более вершины. Итак, мы показали эту оценку независимо, без знания алгоритма. Интересно заметить, что эта оценка неулучшаема, т.е. существует тест, на котором она достигается
. Этот тест выглядит таким образом: При обработке этой строки на каждой итерации, начиная с третьей, будет происходить расщепление состояния, и, тем самым, будет достигаться оценка . Число переходов в суффиксном автомате, построенном для строки длины , не превышает
(для ). Докажем
это. Оценим число сплошных переходов. Рассмотрим остовное дерево из длиннейших путей в автомате, начинающихся в состоянии . Этот остов будет состоять только из сплошных рёбер, а, значит, их количество на единицу меньше числа состояний, т.е. не превосходит . Оценим теперь число несплошных переходов. Рассмотрим каждый несплошной переход; пусть текущий переход — это переход по символу . Поставим ему в соответствие строку , где строка соответствует длиннейшему пути из начального состояния в , а — длиннейшему пути из в какое-либо терминальное состояние. С одной стороны, все такие строки для всех несплошных переходов будут различными (поскольку строки и образованы только сплошными переходами). С другой стороны, каждая из таких строк , по определению терминального состояния, будет суффиксом всей строки . Поскольку непустых суффиксов у строки всего штук, и к тому же вся строка среди этих строк не могла содержаться (т.к. всей строке соответствует путь из сплошных рёбер), то общее число несплошных переходов не превосходит . Складывая эти две оценки, мы получаем оценку . Однако, вспоминая, что максимальное число состояний достигается только на тесте вида , и на нём оценка явно не достигается, получаем окончательную оценку , что и требовалось доказать. Интересно отметить, что также существует тест, на котором эта оценка достигается
: Докажем две теоремы, устанавливающие взаимную связь между суффиксным автоматом и суффиксным деревом . Сразу оговоримся, что мы считаем, что входная строка такова, что каждый суффикс имеет собственную вершину в суффиксном дереве (поскольку для произвольных строк это, вообще говоря, неверно: например, для строки ). Обычно этого добиваются путём приписывания в конец строки какого-нибудь особого символа (обычно обозначаемого через знак доллара). Для удобства введём обозначения: — это строка , записанная в обратном порядке, — это суффиксный автомат, построенный для строки , — это суффиксное дерево строки . Введём понятие расширяющей ссылки
: зафиксируем вершину суффиксного дерева и символ ; тогда расширяющая ссылка ведёт в вершину дерева, соответствующую строке (если этот путь оканчивается посередине ребра, то проведём ссылку в нижний конец этого ребра); если такого пути вообще нет в дереве, то расширяющая ссылка не определена. В некотором смысле, расширяющие ссылки противоположны суффиксным ссылкам. Теорема 1
. Дерево, образованное суффиксными ссылками в , является суффиксным деревом . Теорема 2
. — это граф расширяющих ссылок суффиксного дерева . Кроме того, сплошные рёбра в — это инвертированные суффиксные ссылки в . Эти две теоремы позволяют по одной из структур (суффиксному дереву или суффиксному автомату) построить другую за время — эти два простых алгоритма будут рассмотрены нами ниже в теоремах 3 и 4. В целях наглядности, приведём суффиксный автомат с его деревом суффиксных ссылок и соответствующее суффиксное дерево для инвертированной строки. Для примера возьмём строку . И его дерево суффиксных ссылок (для наглядности мы подписываем каждое состояние его -строкой): Лемма
. Следующие три утверждения эквивалентны для любых двух подстрок и : Доказательство её довольно очевидно: если начала вхождений двух строк совпадают, то одна строка является префиксом другой, а, значит, одна строка лежит в суффиксном дереве на пути другой строки. Доказательство теоремы 1
. В терминах инвертированной строки это означает, что суффиксная ссылка ведёт в такой длиннейший префикс строки, соответствующей состоянию , чтобы этому префиксу соответствовало отдельное состояние . Иными словами, суффиксная ссылка ведёт в предка вершины в суффиксном дереве, что и требовалось доказать. Доказательство теоремы 2
. Состояния суффиксного автомата соответствуют вершинам суффиксного дерева. Рассмотрим произвольный переход в суффиксном автомате . Наличие этого перехода означает, что — это такое состояние, класс эквивалентности которого содержит подстроку Это как раз и означает, что: Первая часть теоремы доказана, осталось доказать вторую часть: что все сплошные переходы в автомате соответствуют суффиксным ссылкам в дереве. Сплошной переход отличается от несплошного тем, что , т.е. после приписывания символа мы попали в состояние со строкой, максимальной из класса эквивалентности этого состояния. Это означает, что при вычислении соответствующей расширяющей ссылки мы сразу попали в вершину дерева, а не спускались вниз до ближайшей вершины дерева. Таким образом, приписав один символ в начало, мы попали в другую вершину дерева — значит, если это и есть инвертированная суффиксная ссылка в дереве. Теорема полностью доказана. Теорема 3
. Имея суффиксный автомат , можно за время построить суффиксное дерево . Теорема 4
. Имея суффиксное дерево , можно за время построить суффиксный автомат . Доказательство теоремы 3
. Суффиксное дерево будет содержать столько же вершин, сколько состояний в , причём вершине дерева, получившейся из состояния автомата, соответствует строка длины . Согласно теореме 1, рёбра в дереве образуются как инвертированные суффиксные ссылки, и дуговые метки можно найти, исходя из разности состояний, и дополнительно зная для каждого состояния автомата один любой элемент его множества (этот один элемент множества можно поддерживать при построении автомата). Таким образом, за время мы можем построить суффиксное дерево вместе с суффиксными ссылками в нём. (Если мы считаем размер алфавита не константой, то на всё перестроение потребуется время .) Доказательство теоремы 4
. Суффиксный автомат будет содержать столько же состояний, сколько вершин в . У каждого состояния его длиннейшая строка будет соответствовать инвертированному пути из корня дерева до вершины . Согласно теореме 2, чтобы построить все переходы в суффиксном автомате, нам надо найти все расширяющие ссылки . Во-первых, заметим, что часть этих расширяющих ссылок получаются непосредственно из суффиксных ссылок в дереве. В самом деле, если для любой вершины мы рассмотрим её суффиксную ссылку , то это означает, что надо провести расширяющую ссылку из в по первому символу строки, соответствующей вершине . Однако так мы найдём не все расширяющие ссылки. Дополнительно надо пройтись по суффиксному дереву от листьев до корня, и для каждой вершины просмотреть всех её сыновей, для каждого сына просмотреть все расширяющие ссылки , и скопировать эту ссылку в вершину , если по этому символу ссылка из вершины ещё не была найдена: Этот процесс отработает за время , если мы считаем размер алфавита константным. Таким образом, описанный алгоритм за время строит суффиксный автомат по суффиксному дереву для инвертированной строки. (Если же мы считаем, что размер алфавита — также переменная величина, то асимптотика увеличится до .) Ниже мы рассмотрим, какие задачи можно решать с помощью суффиксного автомата. Условие
. Дан текст , и поступают запросы в виде: дана строка , требуется проверить, входит или нет строка в текст как подстрока. Асимптотика
. Препроцессинг Решение
. Построим суффиксный автомат по тексту за время Как теперь отвечать на один запрос. Пусть текущее состояние — это переменная , изначально она равна начальному состоянию . Будем идти по символам строки , соответствующим образом делая переход из текущего состояния в новое состояние. Если в какой-то момент случилось, что перехода из текущего состояния по нужному символу не оказалось — то ответ на запрос "нет". Если же мы смогли обработать всю строку , то ответ на запрос "да". Понятно, что это будет работать за время Условие
. Дана строка . Требуется узнать количество различных её подстрок. Асимптотика
. Решение
. Построим суффиксный автомат по строке . В суффиксном автомате любой подстроке строки соответствует какой-то путь в автомате. Поскольку повторяющихся строк в автомате быть не может, то ответ на задачу — это количество различных путей
в автомате, начинающихся в начальной вершине . Учитывая, что суффиксный автомат представляет собой ациклический граф, количество различных путей можно считать в нём с помощью динамического программирования. А именно, пусть — это количество различных путей, начинающихся с состояния (включая путь длины ноль). Тогда верно: т.е. можно выразить как сумму ответов по всевозможным переходам из состояния . Ответом на задачу будет значение (единица отнимается, чтобы не учитывать пустую подстроку). Условие
. Дана строка . Требуется узнать суммарную длину всех различных её подстрок. Асимптотика
. Решение
. Решение задачи аналогично предыдущей, только теперь надо считать в динамике две величины: количество различных подстрок и их суммарную длину . т.е. мы берём ответ для каждой вершины , и прибавляем к нему , тем самым как бы приписывая в начало каждой из строк по одному символу. Условие
. Дана строка . Поступают запросы — числа , и требуется находить -ую в порядке сортировки подстроку строки . Асимптотика
. на один запрос (где — это ответ на этот запрос, — размер алфавита). Решение
. Решение данной задачи базируется на той же идее, что и предыдущие две задачи. Лексикографически -ая подстрока — это лексикографический -ый путь в суффиксном автомате. Поэтому посчитав для каждого состояния количество путей из него, мы сможем легко искать -ый путь, двигаясь от корня автомата. Условие
. Дана строка . Требуется найти лексикографически наименьший её циклический сдвиг. Асимптотика
. Решение
. Построим суффиксный автомат для строки . Тогда этот автомат будет содержать в себе как пути все циклические сдвиги строки . Следовательно, задача сведётся к тому, чтобы найти в автомате лексикографически минимальный путь длины , что делается тривиальным образом: мы стартуем в начальном состоянии и каждый раз действуем жадно, переходя по переходу с минимальным символом. Условие
. Дан текст , и поступают запросы в виде: дана строка , требуется узнать, сколько раз строка входит в текст как подстрока (вхождения могут перекрываться). Асимптотика
. Препроцессинг Решение
. Построим суффиксный автомат по тексту . Дальше нам надо сделать такой препроцессинг: для каждого состояния автомата посчитать число , равное размеру множества . В самом деле, все строки, соответствующие одному и тому же состоянию, входят в одинаковое число раз, равное количеству позиций в множестве . Однако явно поддерживать множества для всех состояний мы не можем, поэтому научимся считать только их размеры . Для этого поступим следующим образом. Для каждого состояния, если оно не было получено путём клонирования (и начальное состояние мы также не учитываем), изначально присвоим . Затем будем идти по всем состояниям в порядке убывания их длины и пробрасывать текущее значение по суффиксной ссылке: Утверждается, что в конце концов мы так посчитаем для каждого состояния правильные значения . Почему это верно? Всего состояний, полученных не путём клонирования, ровно , и -ое из них появилось, когда мы добавили первые символов. Следовательно, каждому из этих состояний мы ставим в соответствие эту позицию, при обработке которой оно появилось. Поэтому изначально у каждого такого состояния , а у всех остальных состояний . Государственное образовательное учреждение высшего профессионального образования «Вятский государственный гуманитарный университет» Факультет информатики Кафедра информатики и методики обучения информатике Курсовая работа Алгоритмы поиска подстроки в строке Выполнил студент III курса математического факультета Проверил преподаватель кафедры информатики и методики обучения информатике Киров, 2006 г. Введение. 3 Часть 1. Теоретические сведения об алгоритмах поиска подстроки в строке. 5 1.1. Основные понятия. 5 1.1.1 Строка, её длина, подстрока. 5 1.1.2. Понятие о сложности алгоритма. 6 1.2. Алгоритмы основанные на методе последовательного поиска. 7 1.2.1. Алгоритм последовательного (прямого) поиска (The Brute Force Algorithm). 7 1.2.2. Алгоритм Рабина. 7 1.3. Алгоритм Кнута - Морриса - Пратта (КМП). 10 1.4. Алгоритм Бойера – Мура и некоторые его модификации. 13 1.4.1. Алгоритм Боейера – Мура. 13 1.4.2. Модификации БМ. 15 1.5. Поиск подстрок с помощью конечного автомата. 17 1.5.1. Структура автомата. 17 1.5.2. Пример построения конечного автомата. 19 Часть 2. Экспериментальный анализ алгоритмов. 21 2.1. Суть эксперимента. 21 2.2. Результаты и анализ эксперимента. 22 Заключение. 24 Библиографический список. 25 Те, кому приходиться часто работать с текстовыми редакторами, знают цену функции нахождения нужных слов в тексте, существенно облегчающей редактирование документов и поиск нужной информации. Действительно, современные программы обработки текста приучили нас к такой удобной возможности, как поиск и замена фрагментов, и если вы разрабатываете подобную программу, пользователь вправе ожидать, что вы предоставите в его распоряжение соответствующие команды. Конечно, сейчас функции поиска инкапсулированы во многие языки программирования высокого уровня – чтобы найти строчку в небольшом тексте вы, наверное, используете встроенную функцию. Но если такого рода поиск является ключевой задачей вашей программы, знать принципы организации функций поиска будет совсем нелишне. При этом. в готовых подпрограммах далеко не всегда все написано лучшим образом. Во-первых, в стандартных функциях не всегда используются самые эффективные алгоритмы, а во-вторых, вполне возможно, что вам понадобится изменить стандартное поведение этих функций (например, предусмотреть возможность поиска по шаблону). Наконец, область применения функции поиска не ограничивается одними лишь текстовыми редакторами. Следует отметить использование алгоритмов поиска при индексации страниц поисковым роботом, где актуальность информации напрямую зависит от скорости нахождения ключевых слов в тексте html – страницы . Работа простейшего спам – фильтра, заключается в нахождении в тексте письма фраз таких, как «Миллион за час» или «Раскрутка сайта». Все вышесказанное говорит об актуальности проблемы, затрагиваемой работой. Поставим задачу поиска подстроки в строке. Пусть у нас есть строка, состоящая из некоторого количества символов. Нам нужно проверить, входит ли другая заданная строка в данный текст, и если входит, то начиная с какого символа текста. В данной работе мы ставим цель, выявить наиболее оптимальный алгоритм, решающий поставленную задачу поиска. Задачи данной работы: · рассмотреть основные алгоритмы, решающих задачу поиска; · систематизировать алгоритмы согласно используемым в них приемам; · выявить эффективные, с точки зрения времени выполнения, алгоритмы. Работа содержит две основных части. В первой будут рассмотрены алгоритмы, их теоретическое обоснование, алгоритмическая модель, будет проведена попытка их классификации. Во второй части работы будут приведены данные о практическом применении алгоритмов. В заключении будет сделан вывод о наиболее эффективном (с временной точки зрения) алгоритме. Здесь мы приводим ряд определений, которые будем использовать в изложении материала . Определение 1
.
Строка (слово) - это последовательность знаков (называемых буквами) из некоторого конечного множества, называемого алфавитом. Определение 2
. Длина строки – количество знаков в строке. Слова будем обозначать буквами латинского алфавита, напр. X=xx…x[n] – слово длинной n, где x[i] (i-ая буква слова) принадлежит алфавиту. Lentgh(X)= Определение 3
. Слово не содержащее ни одной буквы называется пустым. Пустое слово обычно обозначают буквой L. Length(L)=0. Определение 4
. Слово X называется префиксом слова Y, если есть такое слово Z, что Y=XZ. Причем само слово является префиксом для самого себя (т.к. найдется нулевое слово L, что X=LX. Пример
: слово ab является префиксом слова abcfa. Определение 5
. Слово X называется суффиксом слова Y, если есть такое слово Z, что Y=ZX. Аналогично, слово является суффиксом самого себя. Пример
: слово bfg является суффиксом слова vsenfbfg. Определение 6
.Слово X называется подстрокой строки Y, если найдутся такие строки Z 1
и Z 2
, что Y=Z 1
XZ 2
. При этом Z 1
называют левым, а Z 2
- правым крылом подстроки. Подстрокой может быть и само слово. Иногда при этом слово X называют вхождением в слово Y. Среди всех вхождений слова X в слово Y, вхождение с наименьшей длиной своего левого крыла называют первым или главным вхождением. Для обозначения вхождения используют обозначение X Пример
: слова hrf и fhr является подстроками слова abhrfhr, gf Целью нашей работы является найти эффективный алгоритм, однако ничего пока не было сказано о методе оценки алгоритмов. Традиционно в программировании понятие сложности алгоритма связано с использованием ресурсов компьютера: насколько много процессорного времени требует программа для своего выполнения, насколько много при этом расходуется память машины? Учет памяти обычно ведется по объему данных и не принимается во внимание память, расходуемая для записи команд программы. Время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой для машин с разной тактовой частотой. В данной работе будут рассмотрены две характеристики сложности алгоритмов - временная и емкостная. Мы не будем обсуждать логическую сложность разработки алгоритма - сколько «человеко-дней» нужно потратить на создание программы, поскольку не представляется возможным дать объективные количественные характеристики. Временную сложность будем подсчитывать в исполняемых командах: количество арифметических операций, количество сравнений, пересылок (в зависимости от алгоритма). Емкостная сложность будет определяться количеством переменных, элементов массивов, элементов записей или просто количеством байт . Эффективность алгоритма также будет оцениваться с помощью подсчета времени выполнения алгоритмом конкретно поставленной задачи, т.е. с помощью эксперимента, подробнее об этом в части 2 данной работы. Самый очевидный алгоритм. Обозначим S - слово, в котором ищется образец X. Пусть m и n - длины слов S и X соответственно. Можно сравнить со словом X все подслова S, которые начинаются с позиций 1,2,...,m-n+1 в слове S; в случае равенства выводится соответствующая позиция (Листинг 1). Очень просто, но очень неразумно. Ведь максимальное, количество сравнений будет равно O((m-n+1)*n+1), хотя большинство из них на самом деле лишние. Например, найдя строку aabc и обнаружив несоответствие в четвертом символе (совпало только aab), алгоритм будет продолжать сравнивать строку, начиная со следующего символа, хотя это однозначно не приведет к результату. Поиск нескольких минимумов на отрезке.
0.
Если требуется получать сразу несколько минимумов по отрезку (всегда nминимумов на отрезке) – делаем дерево отрезков с функцией нахождения этих нескольких минимумов (но придется делать kсравнений èв kраз усложняет время) 1.
Альтернатива Надо найти kминимумов. Находим по RMQ – индекс первого. Потом запускаем RMQна подмассивах, на которые делится наш массив найденным индексом. Так найдем уже 3 минимума. И т.д. (на 4 подмассивах и т.д.) Поиск подстроки в строке.
Имеются строки и такие, что и элементы этих строк символы из конечного алфавита . Говорят, что строка встречается в строке со сдвигом , если и В задачах поиска традиционно принято обозначать шаблон поиска как needle
а строку, в которой ведётся поиск - как haystack
. Также обозначим через Σ алфавит, на котором проводится поиск. For i=0...|haystack|-|needle|for j=1...|needle|if haystack<>needle[j] then goto 1output("Найдено: ", i+1)1: Простейший алгоритм поиска даже в лучшем
случае проводит |haystack
|−|needle
|+1 сравнение; если же есть много частичных совпадений, скорость снижается до O
(|haystack
|·|needle
|). Показано, что примитивный алгоритм отрабатывает в среднем 2h
сравнений Метод хеширования
Для решения задачи удобно использовать полиномиальный хеш, так его легко пересчитывать: , где - это некоторое простое число, а - некоторое большое число, для уменьшения числа коллизий (обычно берётся или , чтобы модуль брался автоматически при переполнении типов). Стоит обратить внимание, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны. При удалении первого символа строки и добавлении символа в конец считать хеш новой строки при помощи хеша изначальной строки возможно за : Получается: . Следует учесть, что при получении отрицательного значения необходимо прибавить . Алгоритм
Алгоритм начинается с подсчета и . Для вычисляется и сравнивается с . Если они оказались равны, то образец содержится содержится в строке , начиная с позиции , но в этом случае возможны ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вообще, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в наивном алгоритме поиска подстроки в строке. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания останется хоть и небольшая, во втором случае проверка займет время равное длине образца, но исключит возможность ложного срабатывания. Для ускорения работы алгоритма оптимально предпосчитать . Если шаблон большой, нет большого увеличения по времени. Каждый шаг цикла не зависит от остальных (распараллеливание) Время работы
Изначальный подсчёт хешей выполняется за . В цикле всего итераций, каждая выполняется за . Итоговое время работы алгоритма . RabinKarp
(s, p) hp = hash(p) h = hash(s) for
i = 1 to
n - m + 1 if
h == hp h = (p * h - p * hash(s[i]) + hash(s)) mod r if
h < 0 if
answer.size() == 0 return
not found return
answer Конечный автомат
- абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию. Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: , где: · Q - множество состояний
автомата; · q 0 - начальное (стартовое) состояние
автомата (); · F - множество заключительных
(или допускающих
) состояний, таких что ; · Σ - допустимый входной алфавит
(конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом; · δ - заданное отображение множества во множество подмножеств Q: (иногда δ называют функцией переходов автомата
). Автомат начинает работу в состоянии q 0 , считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается». Через конечный автомат работают Ахо-Корасик, Бойер-Мур и Укконенн Алгоритм Бойера-Мура
1. Сканирование слева направо, сравнение справа налево.
Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен. Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько
символов вправо, и проверка снова начинается с последнего символа. Эти «несколько», упомянутые в предыдущем абзаце, вычисляются по двум эвристикам. 2. Эвристика стоп-символа.
Предположим, что мы производим поиск слова «колокол». Первая же буква не совпала - «к» (назовём эту букву стоп-символом
). Тогда можно сдвинуть шаблон вправо до последней
буквы «к». Строка: * * * * * * к * * * * * *Шаблон: к о л о к о лСледующий шаг: к о л о к о л Если стоп-символа в шаблоне вообще нет, шаблон смещается за этот стоп-символ. Строка: * * * * * а л * * * * * * * *Шаблон: к о л о к о лСледующий шаг: к о л о к о л В данном случае стоп-символ - «а», и шаблон сдвигается так, чтобы он оказался прямо за этой буквой. В алгоритме Бойера-Мура эвристика стоп-символа вообще не смотрит на совпавший суффикс (см. ниже), так что первая буква шаблона («к») окажется под «л», и будет проведена одна заведомо холостая проверка. Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает. Строка: * * * * к к о л * * * * *Шаблон: к о л о к о лСледующий шаг: к о л о к о л????? В таких ситуациях выручает третья идея АБМ - эвристика совпавшего суффикса. 3. Эвристика совпавшего суффикса.
Если при сравнении строки и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал. Строка: * * т о к о л * * * * *Шаблон: к о л о к о лСледующий шаг: к о л о к о л В данном случае совпал суффикс «окол», и шаблон сдвигается вправо до ближайшего «окол». Если подстроки «окол» в шаблоне больше нет, но он начинается на «кол», сдвигается до «кол», и т. д. Обе эвристики требуют предварительных вычислений - в зависимости от шаблона поиска заполняются две таблицы. Таблица стоп-символов по размеру соответствует алфавиту (например, если алфавит состоит из 256 символов, то её длина 256); таблица суффиксов - искомому шаблону. Именно из-за этого алгоритм Бойера-Мура не учитывает совпавший суффикс и несовпавший символ одновременно
- это потребовало бы слишком много предварительных вычислений. Опишем подробнее обе таблицы. Таблица стоп-символов
В таблице стоп-символов указывается последняя позиция в needle
(исключая последнюю букву
) каждого из символов алфавита. Для всех символов, не вошедших в needle, пишем 0 (для нумерации с 0 - соответственно, −1). Например, если needle=«abcdadcd», таблица стоп-символов будет выглядеть так. Символ a b c d [все остальные]Последняя позиция 5 2 7 6 0 Обратите внимание, для стоп-символа «d» последняя позиция будет 6, а не 8 - последняя буква не учитывается. Это известная ошибка, приводящая к неоптимальности. Для АБМ она не фатальна («вытягивает» эвристика суффикса), но фатальна для упрощённой версии АБМ - алгоритма Хорспула. Если несовпадение произошло на позиции i, а стоп-символ c, то сдвиг будет i-StopTable[c]. Таблица суффиксов
Для каждого возможного суффикса S
шаблона needle
указываем наименьшую величину, на которую нужно сдвинуть вправо шаблон, чтобы он снова совпал с S
. Если такой сдвиг невозможен, ставится |needle
| (в обеих системах нумерации). Например, для того же needle=«abcdadcd» будет: Суффикс [пустой] d cd dcd ... abcdadcdСдвиг 1 2 4 8 ... 8Иллюстрация было? ?d ?cd ?dcd ... abcdadcd стало abcdadcd abcdadcd abcdadcd abcdadcd ... abcdadcd Если шаблон начинается и заканчивается одной и той же комбинацией букв, |needle
| вообще не появится в таблице. Например, для needle=«колокол» для всех суффиксов (кроме, естественно, пустого) сдвиг будет равен 4. Суффикс [пустой] л ол... олокол колоколСдвиг 1 4 4 ... 4 4Иллюстрация было? ?л?ол... ?олокол колокол стало колокол колокол колокол... колокол колокол Существует быстрый алгоритм вычисления таблицы суффиксов. Этот алгоритм использует префикс-функцию строки. M = length(needle)pi = префикс-функция(needle)pi1 = префикс-функция(обращение(needle))for j=0..msuffshift[j] = m - pi[m]for i=1..m j = m - pi1[i]suffshift[j] = min(suffshift[j], i - pi1[i]) Здесь suffshift соответствует всей совпавшей строке; suffshift[m] - пустому суффиксу. Поскольку префикс-функция вычисляется за O
(|needle
|) операций, вычислительная сложность этого шага также равняется O
(|needle
|). Поиск со звездочками. Алгоритм Кнута-Морриса-Пратта.
Поиск со зведочками
Дан шаблон со звездочками (* - любой символ, но только 1), например ab*av**a (слово abqavqqa - подходит) Как осуществлять поиск? Надо разбить шаблон на шаблоны без звезд (назовем массив таких шаблонов - runs). То есть в вышеописанном примере runs = {ab,av,a}. Кроме того будем хранить позицию начала этих шаблонов (без *) во всем шаблоне. Создадим массив counts длины нашего текста. Изначально элементы равны в нем 0. Затем запустим поиск в тексте всех шаблонов без * (из массива runs). Это будет происходить по очереди, если используем КМП, или сразу, если Ахо-Корасик. Затем будем делать counts.position]++, если j-ый шаблон из массива runs встретился в нашей строке на позиции entry Потом мы пройдемся по массиву counts и все позиции в нем, где значение равно количеству шаблонов без * - это вхождения нашего шаблона (всего)
А
сейчас мы переходим
к самому алгоритму,
ищущему подстроку
в строке (Листинг
4).
Error: Reference source not found
Error: Reference source not foundБыстрый
поиск (Классификация
Thierry Lecroq
).
Турбо
БМ (Классификация
Thierry Lecroq
).
0
1
2
3
4
5
6
7
a
1
1
3
1
5
1
7
1
b
0
2
0
4
0
4
0
2
c
0
0
0
0
0
6
0
0
строка
подстрока
(имеющаяся в
данной строке)
место
вхождения
длина
подстроки
Алгоритм
Время
на пред. обработку
Среднее
время поиска
Худшее
время поиска
Затраты
памяти
Время
работы (мс) при
длине строки
≤250
Примечания
Алгоритмы
основанные
на алгоритме
последовательного
поиска
Алгоритм
прямого поиска
Нет
O((m-n+1)*n+1)/2
O((m-n+1)*n+1)
Нет
234
Mалые
трудозатраты
на программу,
малая эффективность.
Алгоритм
Рабина
Нет
O(m+n)
O((m-n+1)*n+1)
Нет
93
Алгоритм
Кнута-Морриса-Пратта
КМП
O(m)
O(n+m)
O(n+m)
O(m)
31
Универсальный
алгоритм, если
неизвестна
длина образца
Алгоритм
Бойера-Мура
БМ
O(m+s)
O(n+m)
O(n*m)
O(m+s)
32
Алгоритмы
этой группы
наиболее
эффективны
в обычных
ситуациях.
Быстродействие
повышается
при увеличении
образца или
алфавита.
Определение суффиксного автомата
Простейшие свойства суффиксного автомата
Примеры построенных суффиксных автоматов
Позиции окончаний , их свойства и связь с суффиксным автоматом
Суффиксные ссылки
Промежуточный итог
Алгоритм построения суффиксного автомата за линейное время
и выйти.
и выйти.Доказательство корректности алгоритма
Доказательство линейного числа операций
Реализация алгоритма
Дополнительные свойства суффиксного автомата
Число состояний
Число переходов
Связь с суффиксным деревом. Построение суффиксного дерева по суффиксному автомату и наоборот
:
. В инвертированной строке это означает, что это такое состояние, которому соответствует подстрока, от которой (в тексте ) совпадает с от подстроки 
.Применения при решении задач
Проверка вхождения
и 
на один запрос... Более того, алгоритм фактически ищет длину наидлиннейшего префикса , встречающегося в тексте — и если входные образцы таковы, что эти длины маленькие, то и алгоритм будет работать значительно быстрее, не обрабатывая всю строку целиком.Количество различных подстрок
.
Суммарная длина различных подстрок
.
Лексикографически k-ая подстрока
Наименьший циклический сдвиг
.Количество вхождений
и на один запрос.
Белов Денис Владимирович
Иванов С. Ю.
Введение
Часть 1. Теоретические сведения об алгоритмах поиска подстроки в строке.
1.1. Основные понятия.
1.1.1 Строка, её длина, подстрока.
1.1.2. Понятие о сложности алгоритма.
1.2. Алгоритмы основанные на методе последовательного поиска.
1.2.1. Алгоритм последовательного (прямого) поиска (The Brute Force Algorithm).
= . Если строка встречается в строке , то является подстрокой . Требуется проверить, является ли строка подстрокой .