dosyas 15 мар 2011 в 01:03

Суффиксный массив — удобная замена суффиксного дерева

14 мин

33K

Алгоритмы*

+45

Комментарии 12

Colwin 15 мар 2011 в 09:13

Отличная статья.
Особенно радует наличие ссылок на источники предварительных знаний, чтобы быть в курсе, читая основную статью.

nalp 15 мар 2011 в 09:28

Спасибо за статью!

Только все-таки суффиксный массив — не замена дереву. Дерево умеет гораздо больше в силу своей структуры и благодаря всяким поддерживаемым ссылкам. Интересно, а практическое применение есть у массива?

dosyas 15 мар 2011 в 10:56

Основное практическое применение — это как раз индексация текстов для быстрого поиска в них. Т.е. например проиндексировать по-простому (без морфологии) справку для полнотекстового поиска, или же проиндексировать геном. Думаю не совру, если скажу что практически все поисковики пользуются суффиксными массивами тоже. Слишком уж много сложностей с деревьями.

НЛО прилетело и опубликовало эту надпись здесь

nalp 16 мар 2011 в 23:40

В теории да, посколько суффиксный автомат, суффиксный массив и суффиксное дерево — равномощные алгоритмы. Но только использовать массив для стандартных задач — глупо. Даже найти все вхождения шаблона в текст уже не так просто

Skiminok 15 мар 2011 в 11:32

Превосходная статья, спасибо. (Давно хотел рассказать про суффиксный массив, но всё как-то руки не доходили.) А тут всё даже лучше расписано, чем можно было бы представить :)

Вообще, алгоритм Сандерса, насколько мне известно, применяется редко: у него и константа нехорошая в оценке сложности, и кодировать его не так-то просто на самом деле. Алгоритма за O(N log N) в большинстве случаев вполне хватает. (Собственно, точно как же, как и RMQ алгоритмом Фараха-Колтона-Бендера… хотя его ещё можно кое-где встретить.)

На самом-то деле есть еще суффиксный автомат. По классу решаемых задач он аналогичен суффиксному дереву, а строится гораздо проще Укконненна, тоже за O(N). Опять же, если экономить память и хранить таблицу переходов мапами, то время построения увеличивается… аж до O(N log |Σ|), где Σ — размер алфавита. Серьёзно, даже для китайских иероглифов это капля в море.