- •Граф. Ориентированный граф. Представления графа. Обход графа в глубину и в ширину.
- •Топологическая сортировка. Подсчет числа путей в орграфе.
- •Сильно связные компоненты.
- •Поиск кратчайших путей в графе. Алгоритм Флойда. Алгоритм Дейкстры. Алгоритм Форда-Беллмана.
- •Алгоритм a*. Эвристики.
- •Минимальное остовное дерево. Алгоритм Прима. Биномиальная куча.
- •Амортизационная стоимость. Фибоначчиева куча. Амортизационная стоимость (анализ)
- •Метод потенциалов
- •Структура
- •Фибоначчиева Куча
- •Время работы
- •Система непересекающихся множеств. Алгоритм Крускала.
- •Наивная реализация
- •Эвристика сжатия пути
- •Эвристика объединения по рангу
- •Потоки, Форда-Фалкерсона.
- •Декартово дерево
- •Дерево Фенвика. Дерево отрезков и динамическое программирование для rmq.
- •Сведение rmq к lca и наоборот.
- •Препроцессинг
- •Ответы на запросы
- •Алгоритм
- •Доказательство
- •Сложность
- •Алгоритм
- •Минимум внутри блока
- •Результат
- •Поиск нескольких минимумов на отрезке. Задача поиска подстрок. Алгоритм Рабина-Карпа. Конечный автомат. Алгоритм Бойера-Мура.
- •Метод хеширования
- •Алгоритм
- •Время работы
- •Алгоритм Бойера-Мура
- •Поиск со звездочками. Алгоритм Кнута-Морриса-Пратта.
- •Время работы
- •Алгоритм Ахо-Корасика.
- •Дерево ключевых слов (бор)
- •Пример дерева ключевых слов (бора)
- •Построение бора
- •Поиск строки в бору
- •Автомат Ахо-Корасик
- •Суффиксное дерево, Алгоритм Укконена.
- •2. Квадратичный алгоритм
- •3. Линейный алгоритм
- •Суффиксный массив.
- •Наивный алгоритм поиска
- •Алгоритм, использующий префиксы циклических сдвигов
- •Исключения
- •Шаблоны
- •Stl: итераторы
- •Сортировка и поиск в stl. Алгоритмы stl
- •Куча в stl. Алгоритмы stl.
- •Ассоциативный массив. Интерфейс, варианты реализации.
Время работы
Время
работы алгоритма составит
.
Для доказательства этого нужно заметить,
что итоговое количество итераций
цикла
определяет
асимптотику алгоритма. Теперь стоит
отметить, что
увеличивается
на каждом шаге не более чем на единицу,
значит максимально возможное значение
.
Поскольку внутри цикла
значение
лишь
уменьшается, получается, что
не
может суммарно уменьшиться больше,
чем
раз.
Значит цикл
в
итоге выполнится не более
раз,
что дает итоговую оценку времени
алгоритма
.
Алгоритм Ахо-Корасика.
В задаче точного сопоставления множеств (exact set matching problem) требуется обнаружить все появления шаблонов из множества P = {P1,...,Pk} в тексте T[1..m]. Пусть n = Σi=1k |Pi|. Задача точного сопоставления множеств может быть решена за время O (|P1| + m + ... + |Pk| + m) = O (n + km), если применить k раз любой алгоритм, работающий за линейное время. Алгоритм Ахо-Корасик (АК) (Aho-Corasick algorithm) (AC) - классическое решение задачи точного сопоставления множеств. Он работает за время O (n + m + z) , где z - количество появлений шаблонов в T. АК основан на структуре данных "дерево ключевых слов" (keyword tree).
Дерево ключевых слов (бор)
Дерево ключевых слов (или "бор") (keyword tree, trie) для множества шаблонов P - это дерево с корнем K, такое что: 1. Каждое ребро e в K отмечено одним символом. 2. Всякие два ребра, исходящие из одной вершины, имеют разные метки. Определим метку вершины v как конкатенацию меток ребер, составляющих путь из корня в v, и обозначим ее L (v). 3. Для каждого шаблона Pi из множества P есть вершина v, такая что L (v) = Pi. 4. Метка каждой вершины-листа является шаблоном из множества P.
Пример дерева ключевых слов (бора)
Дерево
ключевых слов для P = {he, she, his, hers}:
Бор
- хороший способ хранения словаря строк.
Построение бора
Начинаем с дерева из одной вершины (корня); добавляем шаблоны Pi один за другим: Следуем из корня по ребрам, отмеченным буквами из Pi, пока возможно. Если Pi заканчивается в v, сохраняем идентификатор Pi (например, i) в v. Если ребра, отмеченного очередной буквой Pi нет, то создаем новые ребра и вершины для всех оставшихся символов Pi. Это занимает, очевидно, O (|P1| + ... + |Pk|) = O (n) времени.
Поиск строки в бору
Поиск строки S в бору: начинаем в корне, идем по ребрам, отмеченным символами S, пока возможно. Если с последним символом S мы приходим в вершину с сохраненным идентификатором, то S - слово из словаря. Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки S в словаре нет. Ясно, что это занимает O (|S|) времени. Таким образом, бор - это эффективный способ хранить словарь и искать в нем слова. Теперь перейдем от бора к автомату (automaton), чтобы добиться поиска шаблонов в тексте за линейное время.
Автомат Ахо-Корасик
Состояния: узлы бора. Начальное состояние: корень, обозначим его 0. Действия автомата определяются тремя функциями, определенными для всех состояний: 1. Функция goto g (s, a) указывает, в какое состояние переходить из данного состояния s при просмотре символа a. Если ребро (u, v) отмечено символом a, то g (u, a) = v; g (0, a) = 0 для всех символов a, которыми не отмечено ни одно ребро, выходящее из корня. ~>Автомат остается в корне, пока просматриваются побочные символы. При всех остальных аргументах g пусть выдает -1. 2. Функция неудачи f (s) указывает, в какое состояние переходить при просмотре неподходящего символа. Рассмотрим метку вершины s и найдем самый длинный суффикс этой метки, такой, что с него начинается некоторый шаблон из множества P. Тогда f (s) пусть указывает на вершину, метка которой - этот суффикс. 3. Выходная функция out (s) выдает множество шаблонов, которые обнаруживаются при переходе в состояние s.
Пример автомата АК
Пунктиром
обозначены переходы при неудаче (значения
функции f);
те, которые не показаны, ведут в корень.
Поиск шаблонов с помощью автомата АК
q := 0; // начальное состояние - корень. for i := 1 to m do while g (q, T [i]) = -1 do q := f (q); q := g (q, T [i]); if out (q) ≠ 0 then print i, out (q); endfor;
Построение автомата АК
Автомат АК строится в два этапа.
Этап I:
1. Строим бор для словаря P. При добавлении каждого слова Pi из P, вершине v с меткой Pi, сопоставим out (v) := {Pi} 2. Закончим построение функции goto, добавив несуществующие переходы из корня: g (0, a) = 0 для всех символов a, не отмечающих ни одного ребра, выходящего из корня. Это также можно сделать неявно. Если алфавит фиксирован, этап I занимает O (n) времени.
Результат этапа I:
Этап II:
Q := пустая очередь для каждого символа a, отмечающего хоть одно ребро из корня [g (0, a) ≠ 0] f (g (0, a)) := 0 добавить в очередь Q вершину g (0, a) пока очередь Q не пуста взять вершину r из очереди Q для каждого символа a, отмечающего хоть одно ребро из вершины r [g (r, a) ≠ -1] u := g (r, a) добавить в очередь Q вершину u v := f (r) пока g (v, a) = -1 v := f (v) f (u) := g (v, a) out (u) := out (u)∪out (f (u)) Функция неудачи и выходная функция вычисляются для всех вершин в порядке обхода в ширину. Когда мы работаем с вершиной, все вершины, находящиеся ближе, чем она, к корню (в т. ч. все те, метки которых короче, чем метка данной), уже обработаны. Рассмотрим узлы r и u = g (r, a), т. е. r - родитель u, и L (u) = L (r) a. Теперь нужно, чтобы f (u) указывало на ту вершину, метка которой является самым длинным суффиксом L (u), являющимся также началом некоторого шаблона из множества P. Эта вершина ищется путем просматривания вершин, метки которых являются все более и более короткими суффиксами L (r), пока не находится вершина v, для которой g (v, a) определено; тогда g (v, a) и присваивается f (u). Кстати, и v, и g (v, a) могут быть корнем. Теперь разберемся с out (u) := out (u)∪out (f (u)). Это делается потому, что все шаблоны, распознаваемые при переходе в состояние f (u) (и только они) являются надлежащими суффиксами L (u) и должны быть отслежены при переходе в состояние u. Функция неудачи – то же самое, что и ссылка (для тех кто писал).
Кроме того, нам слишком долго иногда ходить по ссылкам, ведь нам нужна та ссылка, в которой заканчивается какой-то шаблон, поэтому сделаем еще 1 вид ссылок (hard-ссылки). Они будут указывать на 1-ую терминальную вершину, в которую можно перейти по обычным ссылкам (находятся аналогично обычным ссылкам).
