Алгоритм Укконена
Алгоритм Укконена — алгоритм построения суффиксного дерева для заданной строки за линейное время.
Содержание
Первая версия алгоритма
Рассмотрим сначала метод, который строит дерево за время , где — длина исходной строки . В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы.
Описание
Алгоритм делится на фаз. В фазе с номером в дерево добавляются все суффиксы подстроки . При добавлении суффикса алгоритм сначала находит конец пути из корня, помеченного подстрокой , затем добавляет к найденной вершине новое ребро с листом , если этот символ не был добавлен ранее.
Возможные исходы операции insert
Ниже приведены три возможных случая, которые могут возникнуть при добавлении подстроки в дерево.
| Случай | Правило | Пример |
|---|---|---|
| 1. Продление листа | Пусть подстрока кончается в листе. Добавим элемент в конец последнего ребра. | 
|
| 2. Создание листа | Пусть подстрока кончается в вершине, не являющейся листом, из которой нет пути по символу . Создадим новую дугу с началом в элементе и листом . | 
|
| 3. Ничего не делать | Пусть подстрока кончается в вершине, из которой есть путь по . Тогда ничего делать не надо. | 
|
Оптимизация алгоритма Укконена
Рассмотрим две леммы, позволяющие ускорить алгоритм Укконена до .
Лемма 1. Стал листом — листом и останешься
| Лемма: |
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой (для суффикса, начинающегося в позиции строки ), он останется листом во всех последовательных деревьях, созданных алгоритмом.
|
| Доказательство: |
| Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом , правило продолжения 1 будет применяться для продолжения на всех последующих фазах. |
Лемма 2. Правило 3 заканчивает дело
| Лемма: |
В любой фазе, если правило продолжения 3 применяется в продолжении , оно будет реализовываться во всех дальнейших продолжениях(от по ) до конца фазы.
|
| Доказательство: |
| При использовании правила продолжения 3 путь, помеченный в текущем дереве, должен продолжаться символом , и точно так же продолжается путь, помеченный , поэтому правило 3 применяется в продолжениях |
Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу после первого же использования правила прохождения 3. Если это случится в продолжении i, то уже не требуется явно находить концы строк с .
Алгоритм Укконена за квадратичное время
Рассмотрим правила продолжения суффиксов.
При использовании правила 1 по лемме 1 в последующих фазах будет выполняться правило 1. Поэтому скажем, что мы создаём лист не только для рассмотренной части строки, а для всей всей строки до конца.
При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу 1.
При использовании правила 3 по лемме 2 никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксы.
Таким образом, операция insert позволяет суффиксы не только для подстрок , но и сразу для всего суффикса .
Суффиксные ссылки
| Определение: |
| Пусть обозначает произвольную строку, где — ее первый символ, а — оставшаяся подстрока(возможно пустая). Если для внутренней вершины с путевой меткой существует другая вершина с путевой меткой , то ссылка из в называется суффиксной ссылкой. |
Лемма 3. Существование суффиксных ссылок
| Лемма: |
Для любой внутренней вершины суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину . |
| Доказательство: |
| Рассмотрим внутренную вершину с путевой меткой . Так как эта вершина внутренняя, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина . По определению суффиксная ссылка вершины ведет в |
Построение суффиксных ссылок
Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина с путевой меткой . Перейдем к следущему шагу текущей фазы, на котором в дерево будет добавлен суффикс соответствующий вершине (возможно до продления суффикс оканчивался на ребре, но в этом случае по рассуждениям аналогичным Лемме 1 будет создана новая внутрення вершина). По определению суффиксная ссылка из вершины ведет в .
Использование суффиксных ссылок
Опишем как искать концы суффиксов в дереве, которые нужно продлить. Пусть мы только что продлили суффикс . Найдем с помощью построенных ссылок конец суффикса . Пройдем вверх по дереву от конца суффикса до ближайшей внутренней вершины . Ей соответствует некоторая подстрока . У вершины есть суффиксная ссылка, так как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину , которой соответствует подстрока . Теперь пройдем от вершины пройдем вниз по дереву, читая текст , и придем к концу суффикса .
Оценка числа переходов
| Определение: |
| Глубиной вершины назовем число ребер на пути от корня до вершины |
Лемма 4.
| Лемма: |
При переходе по суффиксной ссылке глубина уменьшается не более чем на 1. |
| Доказательство: |
| Пусть мы переходим из вершины с путевой меткой по суффиксной ссылке в вершину с путевой меткой Определим множество как множество вершин на пути от корня до , исключая корень. Множество определим как множество вершин на пути от корня до , исключая корень. Если длина первого ребра на пути от корня до равна единице, то выкинем из множества вершину, в которую ведет это ребро. Итого по построению получаем: , . Теперь заметим, что суффиксная ссылка из любой вершины множества ведет в некоторую вершину множества , и очевидно суффиксные ссылки из разных вершин ведут в разные вершины, поэтому , а значит |
Лемма 5.
| Лемма: |
Число переходов по ребрам внутри фазы номер не превышает |
| Доказательство: |
| Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на 1. Переход по суффиксной ссылке уменьшает высоту не более чем на 1 (по Лемме 4). Значит в течение одной фазы вверх мы переходим не более раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до 1), поэтому вниз мы могли пройти не более ребер. Итого получаем оценку |
Псевдокод
string s;
int n;
struct node {
int l, r, par, link;
map<char,int> next;
node (int l=0, int r=0, int par=-1)
: l(l), r(r), par(par), link(-1) {}
int len() { return r - l; }
int &get (char c) {
if (!next.count(c)) next[c] = -1;
return next[c];
}
};
node t[MAXN];
int sz;
struct state {
int v, pos;
state (int v, int pos) : v(v), pos(pos) {}
};
state ptr (0, 0);
state go (state st, int l, int r) {
while (l < r)
if (st.pos == t[st.v].len()) {
st = state (t[st.v].get( s[l] ), 0);
if (st.v == -1) return st;
}
else {
if (s[ t[st.v].l + st.pos ] != s[l])
return state (-1, -1);
if (r-l < t[st.v].len() - st.pos)
return state (st.v, st.pos + r-l);
l += t[st.v].len() - st.pos;
st.pos = t[st.v].len();
}
return st;
}
int split (state st) {
if (st.pos == t[st.v].len())
return st.v;
if (st.pos == 0)
return t[st.v].par;
node v = t[st.v];
int id = sz++;
t[id] = node (v.l, v.l+st.pos, v.par);
t[v.par].get( s[v.l] ) = id;
t[id].get( s[v.l+st.pos] ) = st.v;
t[st.v].par = id;
t[st.v].l += st.pos;
return id;
}
int get_link (int v) {
if (t[v].link != -1) return t[v].link;
if (t[v].par == -1) return 0;
int to = get_link (t[v].par);
return t[v].link = split (go (state(to,t[to].len()), t[v].l + (t[v].par==0), t[v].r));
}
void tree_extend (int pos) {
for(;;) {
state nptr = go (ptr, pos, pos+1);
if (nptr.v != -1) {
ptr = nptr;
return;
}
int mid = split (ptr);
int leaf = sz++;
t[leaf] = node (pos, n, mid);
t[mid].get( s[pos] ) = leaf;
ptr.v = get_link (mid);
ptr.pos = t[ptr.v].len();
if (!mid) break;
}
}
void build_tree() {
sz = 1;
for (int i=0; i<n; ++i)
tree_extend (i);
}
Итоговая линейная оценка
Оценим время работы алгоритма при использовании всех вышеперечисленных эвристик.
Все неявные продления листов суммарно можно выполнить за (по Лемме 1) По Лемме 2 алгоритм делает не более явных продлений. При использовании суффиксных ссылок, как показано в Лемме 5 время на продление равно константе плюс время пропорциональное числу ребер, пройденных при спуске по дереву. Оценим суммарное число таких переходов по ребрам. Первое явное продолжение в любой фазе (кроме первой) начинается с продолжения, которое было последним явным в предыдущей фазе. Поэтому текущаю вершинная глубина не изменяется при переходе к следущей фазе. Как было показано в Лемме 5, каждое продление представляет собой переход не более чем на 2 единицы глубины вверх, а затем несколько переходов вниз, каждый из которых увеличивает глубину на 1. Так как максимальная глубина не превосходит , а количество явных продлений не превышает , то по рассуждениям аналогичным Лемме 5 суммарное число таких переходов имеет порядок
Источники
- Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
- Реализация алгоритма Укконена
- Построение суффиксного дерева: алгоритм Укконена
