Редактирование: Алгоритм Укконена
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
'''Алгоритм Укконена''' (англ. ''Ukkonen's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время. | '''Алгоритм Укконена''' (англ. ''Ukkonen's algorithm'') — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> за линейное время. | ||
| − | == | + | == Первая версия алгоритма == |
| − | Рассмотрим сначала | + | Рассмотрим сначала метод, который строит дерево за время <tex>O(n^3)</tex>, где <tex>n</tex> — длина исходной строки <tex>s</tex>. В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы. |
{{Определение | {{Определение | ||
| − | |definition= '''Неявное суффиксное дерево''' | + | |definition= '''Неявное суффиксное дерево''' строки <tex>S</tex> {{---}} дерево, образованное от суффиксного дерева для <tex>S\$</tex>, .}} |
| − | |||
| − | |||
| − | Алгоритм | + | === Описание === |
| − | + | Алгоритм делится на <tex>n</tex> фаз. В фазе с номером <tex>j</tex> в дерево добавляются все суффиксы подстроки <tex>s[1..j]</tex>. При добавлении суффикса <tex>s[i..j]</tex> алгоритм сначала находит конец пути из корня, помеченного подстрокой <tex>s[i..j-1]</tex>, затем добавляет к найденной вершине новое ребро с листом <tex>s_{j}</tex>, если этот символ не был добавлен ранее. | |
| − | < | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | == | + | == Возможные исходы операции insert == |
| − | Ниже приведены | + | Ниже приведены три возможных случая, которые могут возникнуть при добавлении подстроки <tex>s[i..j]</tex> в дерево. |
| − | {| border="1" cellpadding=" | + | {| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=70% |
!style="background:#f2f2f2"|Случай | !style="background:#f2f2f2"|Случай | ||
!style="background:#f2f2f2"|Правило | !style="background:#f2f2f2"|Правило | ||
| Строка 25: | Строка 17: | ||
|- | |- | ||
|style="background:#ffffff"|''1. Продление листа'' | |style="background:#ffffff"|''1. Продление листа'' | ||
| − | |style="background:#ffffff"|Пусть | + | |style="background:#ffffff"|Пусть подстрока <tex>s[i..j-1]</tex> кончается в листе. Добавим элемент <tex>s_{j}</tex> в конец последнего ребра. |
| − | |style="background:#ffffff"|[[Файл: | + | |style="background:#ffffff"|[[Файл:Case2.png]] |
| − | |||
| − | |||
| − | |||
| − | |||
|- | |- | ||
| − | |style="background:#ffffff"| | + | |style="background:#ffffff"|''2. Создание листа'' |
| − | |style="background:#ffffff"|[[Файл: | + | |style="background:#ffffff"|Пусть подстрока <tex>s[i..j-1]</tex> кончается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_{j}</tex>. Создадим новую дугу с началом в элементе <tex>s[j-1]</tex> и листом <tex>s_{j}</tex>. |
| + | |style="background:#ffffff"|[[Файл:Case1.png]] | ||
|- | |- | ||
|style="background:#ffffff"|''3. Ничего не делать'' | |style="background:#ffffff"|''3. Ничего не делать'' | ||
| − | |style="background:#ffffff"|Пусть | + | |style="background:#ffffff"|Пусть подстрока <tex>s[i..j-1]</tex> кончается в вершине, из которой есть путь по <tex>s_{j}</tex>. Тогда ничего делать не надо. |
| − | |style="background:#ffffff"|[[Файл: | + | |style="background:#ffffff"|[[Файл:Case3.png]] |
|} | |} | ||
| + | |||
| + | ==Оптимизация алгоритма Укконена== | ||
| + | |||
| + | Рассмотрим две леммы, позволяющие ускорить алгоритм Укконена до <tex>O(n^2)</tex>. | ||
| + | <br /> | ||
| + | {{Лемма|id=l1 | ||
| + | |about= Стал листом — листом и останешься | ||
| + | |statement= | ||
| + | Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>i</tex> (для суффикса, начинающегося в позиции <tex>i</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом. | ||
| + | <br /> | ||
| + | |proof= | ||
| + | Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>i</tex>, правило продолжения 1 будет применяться для продолжения <tex>i</tex> на всех последующих фазах. | ||
| + | }} | ||
| + | |||
| + | {{Лемма|id=l2 | ||
| + | |about= Правило 3 заканчивает дело | ||
| + | |statement= | ||
| + | В любой фазе, если правило продолжения 3 применяется в продолжении <tex>i</tex>, оно будет реализовываться во всех дальнейших продолжениях (от <tex>i + 1</tex> по <tex>j + 1</tex>) до конца фазы. | ||
| + | <br /> | ||
| + | |proof= | ||
| + | При использовании правила продолжения 3 путь, помеченный <tex>S[i..j]</tex> в текущем дереве, должен продолжаться символом <tex>j+1</tex>, и точно так же продолжается путь, помеченный <tex>S[i + 1..j]</tex>, поэтому правило 3 применяется в продолжениях <tex>i + 1, i + 2, ..., j + 1</tex> | ||
| + | }} | ||
| + | <br /> | ||
| + | Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Поэтому можно заканчивать каждую фазу <tex>j + 1</tex> после первого же использования правила прохождения 3. Если это случится в продолжении i, то уже не требуется явно находить концы строк <tex>S[k..j]</tex> с <tex>k > i</tex>. | ||
| + | |||
| + | ==Алгоритм Укконена за квадратичное время== | ||
| + | |||
| + | Рассмотрим правила продолжения суффиксов. | ||
| + | |||
| + | При использовании правила 1 по [[#l1|лемме 1]] в последующих фазах будет выполняться правило 1. Поэтому скажем, что мы создаём лист не только для рассмотренной части строки, а для всей всей строки до конца. <br /> | ||
| + | При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу 1. <br /> | ||
| + | При использовании правила 3 по [[#l2|лемме 2]] никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксы. | ||
| + | |||
| + | Таким образом, операция insert позволяет суффиксы не только для подстрок <tex>S[i..j]</tex>, но и сразу для всего суффикса <tex>S[i..n]</tex>. | ||
==Суффиксные ссылки== | ==Суффиксные ссылки== | ||
{{Определение | {{Определение | ||
| − | |definition= Пусть <tex>x\alpha</tex> обозначает произвольную строку, где <tex>x</tex> {{---}} | + | |definition= Пусть <tex>x\alpha</tex> обозначает произвольную строку, где <tex>x</tex> {{---}} ее первый символ, а <tex>\alpha</tex> {{---}} оставшаяся подстрока(возможно пустая). Если для внутренней вершины <tex>v</tex> с путевой меткой <tex>x\alpha</tex> существует другая вершина <tex>s(v)</tex> с путевой меткой <tex>\alpha</tex>, то ссылка из <tex>v</tex> в <tex>s(v)</tex> называется '''суффиксной ссылкой'''.}} |
| − | }} | + | |
{{Лемма|id=l3 | {{Лемма|id=l3 | ||
|about= Существование суффиксных ссылок | |about= Существование суффиксных ссылок | ||
| Строка 50: | Строка 73: | ||
Для любой внутренней вершины <tex>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>. | Для любой внутренней вершины <tex>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>. | ||
|proof= | |proof= | ||
| − | Рассмотрим | + | Рассмотрим внутренную вершину <tex>v</tex> с путевой меткой <tex>t_i ... t_j</tex>. Так как эта вершина внутренняя, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>t_{i+1} ... t_j</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведет в <tex> u</tex> |
}} | }} | ||
| − | === | + | === Построение суффиксных ссылок === |
| − | |||
| − | + | Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина <tex>v </tex> с путевой меткой <tex>t_i ... t_j</tex>. Перейдем к следущему шагу текущей фазы, на котором в дерево будет добавлен суффикс <tex>t_{i + 1} ... t_j</tex> соответствующий вершине <tex>u</tex> (возможно до продления суффикс оканчивался на ребре, но в этом случае по рассуждениям аналогичным [[#l1|Лемме 1]] будет создана новая внутрення вершина). По определению суффиксная ссылка из вершины <tex>v</tex> ведет в <tex>u</tex>. | |
| − | + | === Использование суффиксных ссылок === | |
| − | |||
| − | === | ||
| − | + | Опишем как искать концы суффиксов в дереве, которые нужно продлить. Пусть мы только что продлили суффикс <tex>t_i ... t_j</tex>. Найдем с помощью построенных ссылок конец суффикса <tex>t_{i + 1} ... t_j</tex>. Пройдем вверх по дереву от конца суффикса <tex>t_i ... t_j</tex> до ближайшей внутренней вершины <tex>v</tex>. Ей соответствует некоторая подстрока <tex>t_i ... t_k </tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для новой внутренней вершины строится внутри фазы ее создания. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует подстрока <tex>t_{i + 1} ... t_k</tex>. Теперь пройдем от вершины <tex>u</tex> пройдем вниз по дереву, читая текст <tex>t_{k + 1} ... t_j</tex>, и придем к концу суффикса <tex>t_{i + 1} ... t_j</tex>. | |
| − | === Оценка числа переходов === | + | ==== Оценка числа переходов ==== |
{{Определение | {{Определение | ||
| − | |definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число | + | |definition= '''Глубиной вершины''' <tex>d(v)</tex> назовем число ребер на пути от корня до вершины <tex>v</tex>}} |
{{Лемма|id=l4 | {{Лемма|id=l4 | ||
| Строка 73: | Строка 93: | ||
При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>. | При переходе по суффиксной ссылке глубина уменьшается не более чем на <tex>1</tex>. | ||
|proof= | |proof= | ||
| − | + | Пусть мы переходим из вершины <tex> v </tex> с путевой меткой <tex>t_i ... t_j</tex> по суффиксной ссылке в вершину <tex> u </tex> с путевой меткой <tex>t_{i + 1} ... t_j</tex> Определим множество <tex> A </tex> как множество вершин на пути от корня до <tex> u </tex>, исключая корень. Множество <tex> B </tex> определим как множество вершин на пути от корня до <tex> v </tex>, исключая корень. Если длина первого ребра на пути от корня до <tex> v </tex> равна единице, то выкинем из множества <tex>B</tex> вершину, в которую ведет это ребро. Итого по построению получаем: <tex>|A| = d(u)</tex>, <tex>|B| \ge d(v) - 1</tex>. Теперь заметим, что суффиксная ссылка из любой вершины множества <tex>B</tex> ведет в некоторую вершину множества <tex> A</tex>, и очевидно суффиксные ссылки из разных вершин ведут в разные вершины, поэтому <tex>|A| \ge |B|</tex>, а значит <tex>d(u) \ge d(v) - 1</tex> | |
| − | |||
| − | |||
| − | |||
}} | }} | ||
{{Лемма|id=l5 | {{Лемма|id=l5 | ||
| − | |||
|statement= | |statement= | ||
| − | Число переходов по | + | Число переходов по ребрам внутри фазы номер <tex>i</tex> не превышает <tex>4i</tex> |
|proof= | |proof= | ||
| − | Оценим количество переходов по | + | Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на <tex>1</tex>. Переход по суффиксной ссылке уменьшает высоту не более чем на <tex>1</tex> (по [[#l4|Лемме 4]]). Значит в течение одной фазы вверх мы переходим не более <tex> 2i </tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до <tex>1</tex>), поэтому вниз мы могли пройти не более <tex> 2i </tex> ребер. Итого получаем оценку <tex> 4i </tex> |
}} | }} | ||
| − | === | + | == Псевдокод == |
| + | <code style = "display: inline-block;"> | ||
| + | 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) | ||
| + | </code> | ||
| − | + | == Итоговая линейная оценка == | |
| − | + | Оценим время работы алгоритма при использовании всех вышеперечисленных эвристик. | |
| − | + | Все неявные продления листов суммарно можно выполнить за <tex>O(n)</tex> ([[#l1|по Лемме 1]]) | |
| + | [[#l2|По Лемме 2]] алгоритм делает не более <tex>2n</tex> явных продлений. При использовании суффиксных ссылок, как показано в [[#l5|Лемме 5]] время на продление равно константе плюс время пропорциональное числу ребер, пройденных при спуске по дереву. | ||
| − | + | Оценим суммарное число таких переходов по ребрам. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | Первое явное продолжение в любой фазе (кроме первой) начинается с продолжения, которое было последним явным в предыдущей фазе. Поэтому текущаю вершинная глубина не изменяется при переходе к следущей фазе. Как было показано в [[#l5|Лемме 5]], каждое продление представляет собой переход не более чем на <tex>2</tex> единицы глубины вверх, а затем несколько переходов вниз, каждый из которых увеличивает глубину на <tex>1</tex>. Так как максимальная глубина не превосходит <tex>n</tex>, а количество явных продлений не превышает <tex>2n</tex>, то по рассуждениям аналогичным [[#l5|Лемме 5]] суммарное число таких переходов имеет порядок <tex>O(n)</tex> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== См. также== | == См. также== | ||
* [[Алгоритм МакКрейта]] | * [[Алгоритм МакКрейта]] | ||
| − | * [[Алгоритм Фарача | + | * [[Алгоритм Фарача]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | == Источники | + | == Источники == |
* Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил. | * Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил. | ||
| − | |||
* [http://e-maxx.ru/algo/ukkonen MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена] | * [http://e-maxx.ru/algo/ukkonen MAXimal :: algo :: Суффиксное дерево. Алгоритм Укконена] | ||
| − | * [http://habrahabr.ru/post/111675/ Habrahabr | + | * [http://habrahabr.ru/post/111675/ Habrahabr — Построение суффиксного дерева: алгоритм Укконена] |
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Словарные структуры данных]] | [[Категория: Словарные структуры данных]] | ||
[[Категория: Суффиксное дерево]] | [[Категория: Суффиксное дерево]] | ||
