Действительно сложно понять суффиксное дерево

Я долго искал учебники о дереве суффикса. В SO я нашел 2 сообщения о понимании дерева суффикса: 1, 2.

Но я не могу сказать, что я понимаю, как его построить, К сожалению. В учебном пособии по алгоритму алгоритма Skiena он говорит:

Поскольку линейные алгоритмы построения дерева суффикса времени нетривиальны, Я рекомендую использовать существующую реализацию.

Ну, так ли алгоритм построения он-лайн для дерева суффикса? Кто-нибудь может поставить меня в правильном направлении, чтобы понять это?

Во всяком случае, прервите погоню, помимо конструкции, есть еще одна вещь, которую я не понимаю о дереве суффиксов. Поскольку ребра в дереве суффикса - это всего лишь пара целых чисел (справа?), Определяющая начальную и конечную позицию подстроки, тогда, если я хочу найти строку x в этом дереве суффиксов, как мне это сделать? Отмените ссылки на эти целые числа в дереве суффиксов, затем сравните их один за другим с помощью x? Не может быть так.

Ответ 1

Во-первых, существует много способов построить дерево суффикса. Существует оригинальный метод O (n) Вайнера (1973), усовершенствованный McCreight (1976), наиболее известный Укконеном (1991/1992), и ряд дальнейших улучшений, в основном связанных с реализацией и хранением соображения эффективности. Наиболее примечательным среди них является Эффективная реализация ленивых суффиксных деревьев от Giegerich и Kurtz.

Кроме того, поскольку прямая конструкция массивов суффиксов стала возможной в O (n) времени в 2003 году (например, используя Skew алгоритм, но есть и другие), и поскольку существуют хорошо изученные методы для

эмуляция деревьев суффикса с использованием массивов суффикса (например, Abouelhoda/Kurtz 2004)
сжатие массивов суффиксов (см. Navarro/Mäkinen 2007 для опроса)

массивы суффиксов обычно предпочтительнее суффиксов. Поэтому, если вы намерены построить высоко оптимизированную реализацию для определенной цели, вам может понадобиться изучить алгоритмы построения суффикса-массива.

Однако, если ваш интерес заключается в построении дерева суффиксов и, в частности, алгоритме Укконена, я хотел бы предложить вам внимательно ознакомиться с описанием в это сообщение SO, о котором вы уже упоминали, и мы пытаемся улучшить это описание вместе. Это, безусловно, далеко от совершенно интуитивного объяснения.

Чтобы ответить на вопрос о том, как сопоставить входную строку с метками края: По соображениям эффективности во время построения и поиска, начальный символ каждой метки граней обычно хранится в node. Но остальное нужно искать в основной текстовой строке, как вы сказали, и действительно, это может вызвать проблемы, особенно когда строка настолько велика, что ее невозможно легко сохранить в памяти. Это (плюс тот факт, что, как и любая прямая реализация дерева, дерево суффикса представляет собой структуру данных, которая содержит много указателей, которые потребляют много памяти и затрудняют сохранение локальности ссылки и извлекают выгоду из кэширования памяти) одна из основных причин, по которой суффиксные деревья труднее обрабатывать, чем, например, инвертированные индексы.

Ответ 2

Если вы объедините массив суффикса с таблицей lcp и дочерней таблицей, что, конечно же, вы должны сделать, вы, по сути, получите дерево суффикса. Этот момент сделан в статье: Линеаризованные деревья суффикса Ким, Парк и Ким. Таблица lcp обеспечивает довольно неудобный обход снизу вверх, а дочерняя таблица обеспечивает легкий обход любого вида. Поэтому история о деревьях суффикса с использованием указателей, вызывающих локальность эталонных проблем, по-моему, является устаревшей информацией. Поэтому суффикс-дерево является "правильным и простым способом", если вы реализуете дерево с использованием базового массива суффиксов.

В статье Ким, Парка и Кима описывается вариант подхода в Abouelhoda et al., вводящий в заблуждение озаглавленный документ: Замена деревьев суффикса на расширенные массивы суффиксов. В статье Ким и др. Правильно сказано, что это суффикс-деревья , а не замена. Более того, детали конструкции Abouelhoda и др. Более просто и интуитивно описаны в Kim et al.

Ответ 3

существует реализация линейной конструкции деревьев Укконена деревьев суффикса (плюс массивы суффиксов, массив lcp) здесь: http://code.google.com/p/text-indexing/. визуализация, предоставляемая вместе с suffixtree.js, может помочь