City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Suffix trees: new ideas and open problems
Saint Petersburg / spring 2014, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

В 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.

Date and time Class|Name Venue|short Materials
23 February
11:15–12:50
Лекция, Lecture ПОМИ РАН slides,  video
23 February
13:00–14:35
Лекция, Lecture ПОМИ РАН video
23 February
15:35–17:10
Лекция, Lecture ПОМИ РАН video