Алгоритм Укконенса - Ukkonens algorithm

В Информатика, Алгоритм Укконена это линейное время, онлайн алгоритм для строительства суффиксные деревья, предложено Эско Укконен в 1995 г.[1]

Алгоритм начинается с неявного дерева суффиксов, содержащего первый символ строки. Затем он проходит по строке, добавляя последовательные символы, пока дерево не будет завершено. Такое добавление символов в порядке придает алгоритму Укконена свойство «оперативности». Оригинальный алгоритм, представленный Питер Вайнер переходит назад от последнего символа к первому от самого короткого суффикса к самому длинному.[2] Более простой алгоритм был найден Эдвард М. МакКрайт, от самого длинного суффикса к самому короткому.[3]

Наивная реализация для генерации суффиксного дерева в будущем требует О(п2) или даже О(п3) временная сложность в нотация большой O, куда п - длина строки. Используя ряд алгоритмических методов, Укконен сократил это до О(п) (линейное) время для алфавитов постоянного размера и О(п бревно п) в целом, соответствует производительности двух предыдущих алгоритмов во время выполнения.

Рекомендации

  1. ^ Укконен, Э. (1995). «Он-лайн построение суффиксных деревьев» (PDF). Алгоритмика. 14 (3): 249–260. CiteSeerX  10.1.1.10.751. Дои:10.1007 / BF01206331. S2CID  6027556.
  2. ^ Вайнер, Питер (1973). «Алгоритмы линейного сопоставления с образцом» (PDF). 14-й ежегодный симпозиум по теории коммутации и автоматов (SWAT 1973). С. 1–11. CiteSeerX  10.1.1.474.9582. Дои:10.1109 / SWAT.1973.13.
  3. ^ МакКрайт, Эдвард Мейерс (1976). "Алгоритм построения экономичного суффиксного дерева". Журнал ACM. 23 (2): 262–272. CiteSeerX  10.1.1.130.8022. Дои:10.1145/321941.321946. S2CID  9250303.

внешняя ссылка