Суффиксные деревья: новые идеи и открытые проблемы

Общая информация
ЛекторТ. А. Стариковская
Семестрвесна 2014
Дата начала23.02.2014
Количество пар3
Язык курсарусский
Анонсы
Встреча на сайте T&Phttp://theoryandpractice.ru/seminars/59510-suffiksnye-derevya-novye-idei-i-otkry...
Анонс habrahabr.ruhttp://habrahabr.ru/events/4218/
Аннотация

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

Первая задача, которую мы рассмотрим, состоит в поиске документов, содержащих вхождения некоторого образца. Мы поймем, как решать эту задачу с использованием оптимального времени и памяти [1].

Вторая и очень важная задача — задача построения суффиксных деревьев. Конечно, еще Вайнер показал, что суффиксные деревья можно строить за линейное время. Впоследствии, было предложено еще несколько алгоритмов построения суффиксных деревьев, в том числе, знаменитый алгоритм Укконена. Все эти алгоритмы читают слово буква за буквой и на каждом шаге достраивают текущее дерево так, чтобы получить суффиксное дерево прочитанной части слова. Недостаток этих алгоритмов состоит в том, что на один шаг в худшем случае можно потратить линейное время. Существует ли алгоритм, который на каждый шаг тратит лишь константу времени — открытая проблема. Мы обсудим лучший из существующих алгоритмов [2].

В свете большого количества приложений суффиксных деревьев очень важно хорошо понимать их свойства. В частности, хотелось бы научиться определять, является ли заданное дерево суффиксным деревом. Эта задача, последняя из тех, что мы рассмотрим, еще открыта. Тем не менее, существуют подходы, позволяющие решить эту задачу при условия наличия некоторой дополнительной информации. О них мы и поговорим [3].

  1. S. Muthukrishnan: Efficient algorithms for document retrieval problems. SODA 2002: 657-666.
  2. Dany Breslauer, Giuseppe F. Italiano: Near Real-Time Suffix Tree Construction via the Fringe Marked Ancestor Problem. SPIRE 2011: 156-167.
  3. Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda: Inferring Strings from Suffix Trees and Links on a Binary Alphabet.Stringology 2011: 121-130.
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

Ваша оценка: Пусто Средняя: 4 (9 votes)
Share |
Татьяна Стариковская
Татьяна Стариковская и студенты