Суффиксный автомат (15 сентября 2016)

  1. Определение, связь с суффиксным деревом, единственность, конечные вершины
    1. Бор, несжатое суфдерево, суфдерево − какой-то автомат.
    2. Суфавтомат = минимальный по числу вершин автомат.
    3. Как из дерева получить автомат? Начинаем сжимать одинаковые вершины. Примеры: ababc, ababb
    4. Заметим, что формально вершины одинаковы = равны их правые контексты. Rs(v) = {x | дополнить vx − суффикс s}
    5. Определим VA = {u | Rs(u) = A} − все строки с правым контекстом A. Заметим, что каждому классу VA должна соответствовать какая-то вершина автомата.
    6. Рёбра между классами проводятся однозначно: x ∈ A, xc ∈ B ⇒ между A и B есть ребро по символу "c"
    7. Устройство классов VA. Lm 1: Rs(v) = Rs(u) ⇒ v и u суффиксы друг друга, Lm 2: v ≤ w ≤ u ⇒ и w тоже.
    8. Какие вершины являются конечными? Определим last, len[V], min[V], suf[V]. Получили ответ: last, suf[last], suf[suf[last]], ...
  2. Онлайн алгроитм построения за O(n)
    1. Что будем поддерживать? start, last, suf[], len[], next[][] (рёбра)
    2. База: s = ε start = last = 1
    3. Переход s → sa ⇒ Rs(v) = {z1, ..., zk} → Rsa(v) = {z1a, ..., zka} +? ε
    4. В каких случаях добавляется ε? v − суффикс sa.
    5. Что произойдёт с вершинами? Добавится новая: sa ∈ V{ε}. Строки из разных классов не могли оказаться в одном. Строки из одного могли оказаться в разных!
    6. Что произойдёт с рёбрами? Если два класса VA, VB не поменялись, наличие ребра между ними осталось. Поменяются только рёбра смежные с изменившимися вершинами.
    7. Rs(x) = Rs(y), Rsa(x) ≠ Rsa(y), x ≤ y ⇒ x − суффикс sa, y − не суффикс sa
    8. Рассмотрим z − самый длинный суффикс sa: v[z] = VRs(z) разделится. Тогда suf[v[z]], suf[suf[v[z]]] и т.д. содержат только суффиксы sa, а суффиксы sa содержатся только в них.
    9. Т.е. доказали, что если что-то разделится, то только v[z]. Как её найти? Суффикс sa = суффикс s + символ a. Будем перебирать суффиксы s.
    10. last, suf[last], suf[suf[last]]... если нет ребра по символу "a", пропускаем. Первое ребро по символу "a" ведёт из p в q=v[z].
    11. Правда ли, что все строки в q являются суффиксами sa? Самый длинный суффикс sa в q имеет длину len[p]+1, самая длинная строка в q имеет длину len[q]. Сравним.
    12. Раздваивание вершины: newQ = суффиксы sa, q = не суффиксы sa. Рёбра по "a" из части цепочки выше p направим в newLast, рёбра по "a", шедшие в q, направим в newQ.
  3. Написание алгоритма
  4. Оценка размера автомата
    1. Не более 2n вершин
    2. Не более (2n-1) + (n-1) = 3n-2 рёбер
  5. Оценка времени работы
    1. Потенциал длина суффиксной цепочки last, suf[last], suf[suf[last]], ...
    2. Изменение: часть длины ti заменили на часть длины 1, общий префикс уменьшился по принципу Дирихле
  6. Применение: проверка, лежит ли строка в тексте.