В информатике , алгоритм Укконена является линейным временем, онлайн алгоритм для построения деревьев суффиксов , предложенные Эско Ukkonen в 1995 году [1] Алгоритм начинается с неявной дерева суффиксов , содержащий первый символ строки. Затем он проходит по строке, добавляя последовательные символы, пока дерево не будет завершено. Такой порядок сложения символов придает алгоритму Укконена свойство «оперативности». Первоначальный алгоритм, представленный Питером Вайнером, двигался в обратном направлении от последнего символа к первому, от самого короткого суффикса к самому длинному. [2] Более простой алгоритм был найден Эдвардом М. МакКрайтом., от самого длинного суффикса к самому короткому. [3]
Неявное суффиксное дерево
При генерации суффиксного дерева с использованием алгоритма Укконена мы увидим неявное суффиксное дерево на промежуточных этапах в зависимости от символов в строке S. В неявных суффиксных деревьях не будет ребра с меткой $ (или любого другого символа завершения) и не будет внутреннего узла только с один край выходит из него.
Описание алгоритма Укконена на высоком уровне
Алгоритм Укконена строит неявное суффиксное дерево T i для каждого префикса S [l ... i] os S (S - строка длины n). Сначала он строит T 1 с использованием 1- го символа, затем T 2 с использованием 2- го символа, затем T 3 с использованием 3- го символа, ..., T n с использованием n- го символа. Вы можете найти следующие характеристики в дереве суффиксов, в котором используется алгоритм Укконена:
- Неявное суффиксное дерево T i +1 строится поверх неявного суффиксного дерева T i .
- В любой момент времени алгоритм Укконена строит суффиксное дерево для символов, которые мы видели до сих пор, и поэтому он имеет свойство on-line , что позволяет алгоритму иметь время выполнения O (n).
- Алгоритм Укконена разделен на n фаз (одна фаза для каждого символа в строке длиной n).
- Каждая фаза i + 1 далее делится на i + 1 расширений, по одному для каждого из i + 1 суффиксов S [1 ... i + 1].
Расширение суффиксов - это добавление следующего символа в уже построенное суффиксное дерево. В расширении j фазы i + 1 алгоритм находит конец S [j ... i] (который уже находится в дереве из-за предыдущей фазы i), а затем расширяет S [j ... i], чтобы быть уверенным суффикс S [j ... i + 1] находится в дереве. Есть три правила расширения:
- Если путь от корня, помеченный S [j ... i], заканчивается на краю листа (т.е. S [i] - последний символ на краю листа), то символ S [i + 1] просто добавляется в конец метки. на краю листа.
- если путь от корня, помеченный S [j ... i], заканчивается нелистовым краем (т. е. после S [i] на пути есть еще символы) и следующий символ не является S [i + 1], то новый край листа с меткой S [i + 1] и номером j создается начиная с символа S [i + 1]. Новый внутренний узел также будет создан, если S [1 ... i] заканчивается внутри (между ними) нелистового ребра.
- Если путь от корня, помеченный S [j..i], заканчивается нелистовым краем (т.е. есть еще символы после S [i] на пути), а следующий символ - s [i + 1] (уже в дереве), ничего не делать.
Следует отметить один важный момент: от данного узла (корневого или внутреннего) будет одно и только одно ребро, начинающееся с одного символа. Из любого узла не должно выходить более одного ребра, начиная с одного и того же символа.
Время выполнения
Наивная реализация для генерации суффиксного дерева в будущем требует временной сложности O ( n 2 ) или даже O ( n 3 ) в большой нотации O , где n - длина строки. Используя ряд алгоритмических методов, Укконен сократил это время до O ( n ) (линейного) времени для алфавитов постоянного размера и O ( n log n ) в целом, что соответствует производительности двух предыдущих алгоритмов во время выполнения.
Пример алгоритма Укконена
Чтобы лучше проиллюстрировать, как строится суффиксное дерево с использованием алгоритма Укконена, мы можем использовать следующий пример:
S = xabxac
- Начните с пустого корневого узла.
- Постройте T 1 для S [1], добавив первый символ строки. Применяется правило 2, которое создает новый листовой узел.
- Постройте T 2 для S [1 ... 2], добавив суффиксы xa (xa и a). Применяется правило 1, которое расширяет метку пути в существующей кромке листа. Применяется правило 2, которое создает новый листовой узел.
- Постройте T 3 для S [1 ... 3], добавив суффиксы xab (xab, ab и b). Применяется правило 1, которое расширяет метку пути в существующей кромке листа. Применяется правило 2, которое создает новый листовой узел.
- Постройте T 4 для S [1 ... 4], добавив суффиксы xabx (xabx, abx, bx и x). Применяется правило 1, которое расширяет метку пути в существующей кромке листа. Применяется правило 3, ничего не делайте.
- Создает T 5 для S [1 ... 5], добавляя суффиксы xabxa (xabxa, abxa, bxa, xa и x). Применяется правило 1, которое расширяет метку пути в существующей кромке листа. Применяется правило 3, ничего не делайте.
- Создает T 6 для S [1 ... 6], добавляя суффиксы xabxac (xabxac, abxac, bxac, xac, ac и c). Применяется правило 1, которое расширяет метку пути в существующей кромке листа. Применяется правило 2, которое создает новый листовой узел (в этом случае создаются три новых передних ребра и два новых внутренних узла).
Рекомендации
- ^ Укконен, Е. (1995). «Он-лайн построение суффиксных деревьев» (PDF) . Алгоритмика . 14 (3): 249–260. CiteSeerX 10.1.1.10.751 . DOI : 10.1007 / BF01206331 . S2CID 6027556 .
- ^ Вайнер, Питер (1973). «Алгоритмы линейного сопоставления с образцом» (PDF) . 14-й ежегодный симпозиум по теории коммутации и автоматов (SWAT 1973) . С. 1–11. CiteSeerX 10.1.1.474.9582 . DOI : 10.1109 / SWAT.1973.13 .
- ^ МакКрайт, Эдвард Мейерс (1976). «Экономичный алгоритм построения суффиксного дерева». Журнал ACM . 23 (2): 262–272. CiteSeerX 10.1.1.130.8022 . DOI : 10.1145 / 321941.321946 . S2CID 9250303 .
Внешние ссылки
- Подробное объяснение на простом английском языке
- Быстрый поиск строк с помощью деревьев суффиксов Учебник Марка Нельсона. Имеет пример реализации, написанный на C ++.
- Реализация на C с подробным объяснением
- Слайды лекций Гая Блеллоха
- Домашняя страница Укконена
- Проект Text-Indexing (построение деревьев суффиксов Укконеном в линейное время)
- Реализация в C Часть 1 Часть 2 Часть 3 Часть 4 Часть 5 Часть 6