Построение суффиксного дерева: алгоритм Укконена

[@Krass]

Только сдал экзамен по информатике, но все равно спасибо за интересную статью :) кстати, я тоже с физтеха)

[@flashnik]

Может, вы оба даже с одного курса? :)

[@Krass]

А вы, почти наверное, один из наших экзаменаторов и ассистент на факультете :)

[@flashnik]

Эх, спалился :((

[@Zorkus]

Отличный пост! Спасибо.

Аха-Корасика да, можно)

[@DeMoN_MIPT]

Раз появились желающие… Но вообще-то я считаю, что алгоритм Ахо-Корасика более простой, чем Укконен, да и найти его описание тоже можно в больших местах. Но вот алгоритм Укконена я долго не мог найти, за исключением возможно всего пары мест: Ден Гасфилд «Строки, деревья и последовательности в алгоритмах» (причём там не очень понятно написано, и для тех, кто решил ознакомится с этим алгоримом впервые, будет сложно разобраться в нём), и как ниже указано, есть конспект Лифшица, но который я раньше не встечал. Поэтому и решил, что ещё одно описание алгоритму Укконена будет не лишним, что не могу сказать об алгоритме Ахо-Корасика.

PS. Возможно, через недельку-две смогу написать и про Ахо-Корасика.

[@flashnik]

Мне кажется, имеет смысл добавить ссылку на оригинал алгоритма и на конспект Юрия Лифшица.

Также надо учитывать, что решение зависит линейно от размера a алфавита (O(na) ). В отличие от, например, суффиксного массива.

[@Zorkus]

А может кто-то выложит полные лекции годного универа (типа МФТИ) по Computer Science? Было бы здорово. Уверен, многие бы скачали и почитали.

[@DeMoN_MIPT]

Я не в праве выкладывать такую информацию. Считаю, что это работа преподавателей, и им решать, где и что они хотят выложить в общественное пользование. Ведь у каждого ВУЗа есть свои секреты

[@Zorkus]

А контакты кого-нибудь из ваших преподавателей можно в личку? Я б пообщался с ними, возможно они бы поделились своими наработками.

[@Rustam]

Сайт итмо по вики-конспектам
По крайней мере, думаю, вас заинтересуют алгоритмы 1-2, а также 3-4 семестров

[@khorost]

Неплохо бы привести графические схемы и примеры. Так будет нагляднее и понятнее.

[@saterenko]

Когда писал библиотеку для поиска фраз в тексте, остановился на суффиксном массиве, так как он эффективно решал мою задачу и при этом оказался гораздо проще суффиксного дерева в понимании. Интересно, на сколько суффиксное дерево лучше/хуже суффиксного массива в плане скорости поиска строки в тексте по готовому дереву/массиву?

[@flashnik]

Если Вы строите массив за линейное время (например, алгоритм Фарача), то он лучше — время и память не зависят от размера алфавита. Особенно важно последнее обстоятельство. Но это нетривиальный алгоритм. Тот алгоритм построения массива, который чаще встречается и проще в реализации, строит за O(NlogN), что медленнее, чем построение дерева.

Вообще, массив вроде как и появился для оптимизации потребления памяти.

[@egorinsk]

О! Интересные темы пошли.

Может быть, кто-нибудь предложит тогда хороший алгоритм поиска похожего слова: например, у нас есть 1 млн. слов, на вход подается слово, похожее на одно (или несколько) из них, задача найти на какие. Естественно, тупо перебирать и считать для каждой пары editing distance или похожую функцию неэффективно.

Или, если упростить эту задачу: имеем цепочки чисел от 1 до N, где N в пределах 1000, выстроенных по возрастанию:

1 4 56 67
1 3 35 56 145
1 2 3

И на вход алгоритма подаем цепочку, к примеру 1 4 23 56 67

Задча: найти наиболее близкие к образцу цепочки.

[@flashnik]

Такая задача?

[@Joshik]

Хорошая статья!
Просто ради интереса — а тебе ведь в ЛКШ рассказали этот алгоритм?

Теперь можно еще и про суффиксный автомат рассказать — он сложнее для понимания, зато пишется очень просто и работает весьма быстро!:)

[@DeMoN_MIPT]

Этот алгоритм где мне только не рассказывали, но в ЛКШ тоже было дело. Но идея возникла только сейчас, при подготовке к сессии. А что, про него рассказывали этой зимой?

[@burdakovd]

> Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки.

Может кубу? Количество суффиксов — N^2, длина — N.

[@DeMoN_MIPT]

Вы ошиблись. Видимо, вы имели ввиду количество всех «подстрок» N^2. А мы рассматриваем только суффиксы. Суффикс — подстрока, конец которой совпадает с концом нашей строки. Таким образом, суффикс определяется своим началом, которых N

[@burdakovd]

Да, меня сбило с толку то, что в русском языке суффикс не обязательно находится в конце.
А со строковыми алгоритмами почти не работал, так что не привык к этой терминологии.

[@Achilles]

Если бы был указан список задач где можно решить етим алгоритмом — было бы замечательно!

[@dkosolobov]

Если кому-то интересно, сейчас появился алгоритм построения суффиксного дерева по-проще — это модификация старого алгоритма Вейнера. Можно посмотреть тут: habrahabr.ru/post/258121 (с исходником) или тут www.youtube.com/watch?v=q9bPAVSmzfA

Короткую реализацию алгоритма Укконена можно найти тут: codeforces.com/blog/entry/16780?locale=ru