Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Суффиксные деревья: новые идеи и открытые проблемы
Санкт-Петербург / весна 2014, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

Дата и время Занятие Место Материалы
23 февраля
11:15–12:50
Лекция, Лекция ПОМИ РАН слайды,  видео
23 февраля
13:00–14:35
Лекция, Лекция ПОМИ РАН видео
23 февраля
15:35–17:10
Лекция, Лекция ПОМИ РАН видео