Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
прога_билеты.docx
Скачиваний:
4
Добавлен:
01.03.2025
Размер:
3 Мб
Скачать
☆

Время работы

Время работы алгоритма составит  . Для доказательства этого нужно заметить, что итоговое количество итераций цикла   определяет асимптотику алгоритма. Теперь стоит отметить, что   увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение  . Поскольку внутри цикла   значение   лишь уменьшается, получается, что   не может суммарно уменьшиться больше, чем   раз. Значит цикл   в итоге выполнится не более   раз, что дает итоговую оценку времени алгоритма  .

Алгоритм Ахо-Корасика.

В задаче точного сопоставления множеств (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-ую терминальную вершину, в которую можно перейти по обычным ссылкам (находятся аналогично обычным ссылкам).