В более ранних статьях дерева суффиксов мы создавали дерево суффиксов для одной строки, а затем запрашивали это дерево для проверки подстроки , поиска всех шаблонов , самой длинной повторяющейся подстроки и построенного массива суффиксов (все операции с линейным временем).
Существует множество других проблем, связанных с несколькими строками.
например, поиск по шаблону в текстовом файле или словаре, проверка орфографии, телефонная книга, автозаполнение , проблема самой длинной общей подстроки , самая длинная палиндромная подстрока и многое другое .
Для таких операций все задействованные строки должны быть проиндексированы для более быстрого поиска и извлечения. Один из способов сделать это — использовать суффикс trie или суффиксное дерево. Мы обсудим здесь дерево суффиксов.
Дерево суффиксов, созданное из набора строк, называется обобщенным деревом суффиксов .
Мы обсудим простой способ построения обобщенного суффиксного дерева здесь только для двух строк .
Позже мы обсудим другой подход к созданию обобщенного суффиксного дерева для двух или более строк .
Здесь мы будем использовать реализацию дерева суффиксов для одной обсуждаемой строки и немного ее изменить для построения обобщенного дерева суффиксов .
Давайте рассмотрим две строки X и Y, для которых мы хотим построить обобщенное суффиксное дерево. Для этого мы создадим новую строку X # Y $, где # и $ оба являются терминальными символами (должны быть уникальными). Затем мы создадим дерево суффиксов для X # Y $, которое будет обобщенным деревом суффиксов для X и Y. Та же логика будет применяться для более чем двух строк (т.е. объединить все строки с использованием уникальных терминальных символов, а затем построить дерево суффиксов для объединенной строки) ,
Допустим, X = xabxa, а Y = babxba, тогда
X # Y $ = xabxa # babxba $
Если мы запустим код, реализованный в Ukkonen's Suffix Tree Construction — часть 6 для строки xabxa # babxba $, мы получим следующий вывод:
Выход:

Графический вид:
Мы можем использовать это дерево для решения некоторых проблем, но мы можем немного его уточнить, удалив ненужные подстроки в метке пути. У метки пути должна быть подстрока только из одной входной строки, поэтому, если есть метки пути, имеющие подстроки из нескольких входных строк, мы можем оставить только начальную часть, соответствующую одной строке, и удалить всю последующую часть. Например, для пути этикетки # babxba $, A # babxba $ и BXA # babxba $, мы можем удалить babxba $ (принадлежит 2 — й строке ввода) , а затем новые этикетки пути будут #, A # и BXA # соответственно. С этим изменением приведенная выше диаграмма будет выглядеть следующим образом:
Ниже реализация построена поверх оригинальной реализации . Здесь мы удаляем нежелательные символы на метках пути. Если метка пути содержит символ «#», то мы обрезаем все символы после «#» в этой метке пути.
Примечание. Эта реализация создает обобщенное суффиксное дерево только для двух строк X и Y, которые объединяются в X # Y $.
|
Вывод: (Вы можете видеть, что нижеприведенный вывод соответствует 2- му рисунку, показанному выше)
# [5] $ [12] a [-1] # [4] $ [11] bx [-1] a# [1] ba$ [7] b [-1] a [-1] $ [10] bxba$ [6] x [-1] a# [2] ba$ [8] x [-1] a [-1] # [3] bxa# [0] ba$ [9]
Если две строки имеют размер M и N, эта реализация займет O (M + N) времени и пространства.
Если входные строки еще не конкатенированы, то всего потребуется 2 (M + N) пространства, пространство M + N для хранения обобщенного суффиксного дерева и другое пространство M + N для хранения сцепленной строки.
Следовать за:
Расширить вышеприведенную реализацию более чем на две строки (т.е. объединить все строки, используя уникальные символы терминала, а затем построить дерево суффиксов для объединенной строки)
Одной из проблем этого подхода является необходимость уникального символа терминала для каждой входной строки. Это будет работать для нескольких строк, но если будет слишком много входных строк, мы не сможем найти столько уникальных терминальных символов.
Вскоре мы обсудим другой подход к созданию обобщенного суффиксного дерева, в котором нам понадобится только один уникальный символ терминала, который решит вышеуказанную проблему и может быть использован для построения обобщенного суффиксного дерева для любого количества входных строк.
Мы опубликовали следующие дополнительные статьи о приложениях дерева суффиксов:
- Приложение суффиксного дерева 1 — Проверка подстроки
- Suffix Tree Application 2 — Поиск по всем паттернам
- Приложение суффиксного дерева 3 — самая длинная повторяющаяся подстрока
- Suffix Tree Application 4 — построение линейного суффиксного массива времени
- Приложение суффиксного дерева 5 — самая длинная общая подстрока
- Приложение Suffix Tree 6 — длинная палиндромная подстрока
Эта статья предоставлена Анураг Сингх . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме
Рекомендуемые посты:
- Suffix Tree Application 4 — построение линейного суффиксного массива времени
- Обзор структур данных | Набор 3 (График, Три, Сегментное дерево и Суффикс-дерево)
- Поиск по шаблону с использованием дерева суффиксов
- Построение Суффикса Укконена — Часть 2
- Построение суффикс-дерева Укконена — часть 1
- Построение Суффикса Укконена — Часть 6
- Приложение суффиксного дерева 1 — Проверка подстроки
- Suffix Tree Application 2 — Поиск по всем паттернам
- Построение Суффикса Укконена — Часть 5
- Построение Суффикса Укконена — Часть 3
- Построение суффикс-дерева Укконена — часть 4
- Приложение Suffix Tree 6 — длинная палиндромная подстрока
- Приложение суффиксного дерева 3 — самая длинная повторяющаяся подстрока
- Приложение суффиксного дерева 5 — самая длинная общая подстрока
- Самый длинный префикс, который также является суффиксом
0.00 (0%) 0 votes