Комментарии 12
Отличная статья.
Особенно радует наличие ссылок на источники предварительных знаний, чтобы быть в курсе, читая основную статью.
Особенно радует наличие ссылок на источники предварительных знаний, чтобы быть в курсе, читая основную статью.
+2
Спасибо за статью!
Только все-таки суффиксный массив — не замена дереву. Дерево умеет гораздо больше в силу своей структуры и благодаря всяким поддерживаемым ссылкам. Интересно, а практическое применение есть у массива?
Только все-таки суффиксный массив — не замена дереву. Дерево умеет гораздо больше в силу своей структуры и благодаря всяким поддерживаемым ссылкам. Интересно, а практическое применение есть у массива?
0
Основное практическое применение — это как раз индексация текстов для быстрого поиска в них. Т.е. например проиндексировать по-простому (без морфологии) справку для полнотекстового поиска, или же проиндексировать геном. Думаю не совру, если скажу что практически все поисковики пользуются суффиксными массивами тоже. Слишком уж много сложностей с деревьями.
0
НЛО прилетело и опубликовало эту надпись здесь
Превосходная статья, спасибо. (Давно хотел рассказать про суффиксный массив, но всё как-то руки не доходили.) А тут всё даже лучше расписано, чем можно было бы представить :)
Вообще, алгоритм Сандерса, насколько мне известно, применяется редко: у него и константа нехорошая в оценке сложности, и кодировать его не так-то просто на самом деле. Алгоритма за O(N log N) в большинстве случаев вполне хватает. (Собственно, точно как же, как и RMQ алгоритмом Фараха-Колтона-Бендера… хотя его ещё можно кое-где встретить.)
На самом-то деле есть еще суффиксный автомат. По классу решаемых задач он аналогичен суффиксному дереву, а строится гораздо проще Укконненна, тоже за O(N). Опять же, если экономить память и хранить таблицу переходов мапами, то время построения увеличивается… аж до O(N log |Σ|), где Σ — размер алфавита. Серьёзно, даже для китайских иероглифов это капля в море.
Вообще, алгоритм Сандерса, насколько мне известно, применяется редко: у него и константа нехорошая в оценке сложности, и кодировать его не так-то просто на самом деле. Алгоритма за O(N log N) в большинстве случаев вполне хватает. (Собственно, точно как же, как и RMQ алгоритмом Фараха-Колтона-Бендера… хотя его ещё можно кое-где встретить.)
На самом-то деле есть еще суффиксный автомат. По классу решаемых задач он аналогичен суффиксному дереву, а строится гораздо проще Укконненна, тоже за O(N). Опять же, если экономить память и хранить таблицу переходов мапами, то время построения увеличивается… аж до O(N log |Σ|), где Σ — размер алфавита. Серьёзно, даже для китайских иероглифов это капля в море.
+1
Спасибо за статью. Узнал кое-что новое для себя. Если есть что ещё рассказать про алгоритмы на строках — буду с удовольствием читать.
0
Спасибо! Лучшее описание суффиксных массивов, которое я только видел.
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Суффиксный массив — удобная замена суффиксного дерева