Рубрики

Построение суффикс-дерева Укконена — часть 1

Поиск по шаблону, Продвинутые Структуры данных

Дерево суффиксов очень полезно в многочисленных задачах обработки строк и вычислительной биологии. Многие книги и электронные ресурсы говорят об этом теоретически, и в некоторых местах обсуждается реализация кода. Но все же я чувствовал, что чего-то не хватает, и нелегко реализовать код для построения дерева суффиксов, и это используется во многих приложениях. Это попытка преодолеть разрыв между теорией и полной реализацией рабочего кода. Здесь мы обсудим алгоритм построения суффиксного дерева Укконена. Мы обсудим это шаг за шагом, детально и во многих частях от теории до реализации. Мы начнем с метода грубой силы и попытаемся понять различные концепции, приемы, включенные в алгоритм Укконена, и в последней части будет обсуждаться реализация кода.
Примечание : Вы можете найти некоторую часть алгоритма трудной для понимания при первом или втором чтении, и это совершенно нормально. С помощью нескольких попыток и размышлений вы сможете понять такие части.

Книжные алгоритмы на строках, деревьях и последовательностях: информатика и вычислительная биология Дэна Гасфилда очень хорошо объясняют эти концепции.

Дерево суффиксов T для m-символьной строки S является корневым ориентированным деревом с ровно m листьями, пронумерованными от 1 до m. (Учитывая, что последний символ строки уникален в строке)

  • Корень может иметь ноль, одного или нескольких детей.
  • Каждый внутренний узел, кроме корневого, имеет как минимум двух дочерних узлов.
  • Каждое ребро помечено непустой подстрокой S.
  • Никакие два ребра, выходящие из одного узла, не могут иметь метки ребер, начинающиеся с одного и того же символа.

Объединение меток ребер на пути от корня до листа i дает суффикс S, который начинается в позиции i, то есть S [i… m].

Примечание. Позиция начинается с 1 (индексируется не с нуля, а позже, при реализации кода мы будем использовать нулевую позицию)

Для строки S = xabxac с m = 6 дерево суффиксов будет выглядеть следующим образом:

Он имеет один корневой узел, два внутренних узла и 6 конечных узлов.

Строка Глубина красного пути равна 1 и представляет суффикс c, начиная с позиции 6
Строка Глубина синего пути равна 4 и представляет суффикс bxca, начиная с позиции 3
Строка Глубина зеленого пути равна 2 и представляет суффикс ac, начиная с позиции 5
Строка Глубина оранжевого пути равна 6 и представляет суффикс xabxac, начиная с позиции 1

Края с метками a ( зеленый ) и xa ( оранжевый ) являются неконцевыми краями (оканчивающимися на внутреннем узле). Все остальные края — край листа (заканчивается на листе)

Если один суффикс S совпадает с префиксом другого суффикса S (когда последний символ не является уникальным в строке), то путь для первого суффикса не заканчивается на листе.

Для строки S = xabxa с m = 5 следующее дерево суффиксов:

Здесь у нас будет 5 суффиксов: xabxa, abxa, bxa, xa и a.
Путь для суффиксов 'xa' и 'a' не заканчивается на листе. Дерево, подобное приведенному выше (рисунок 2), называется неявным деревом суффиксов, поскольку некоторые суффиксы ('xa' и 'a') не видны явно в дереве.

Чтобы избежать этой проблемы, мы добавляем символ, которого уже нет в строке. Обычно мы используем $, # и т. Д. В качестве символов завершения.
Далее следует дерево суффиксов для строки S = xabxa $ с m = 6, и теперь все 6 суффиксов заканчиваются на листе.

Наивный алгоритм построения дерева суффиксов
Для заданной строки S длиной m введите одно ребро для суффикса S [l ..m] $ (всю строку) в дерево, затем последовательно введите суффикс S [i..m] $ в растущее дерево для i увеличивается от 2 до м. Пусть N i обозначает промежуточное дерево, которое кодирует все суффиксы от 1 до i.
Таким образом, N i +1 строится из N i следующим образом:

  • Начнем с корня N i
  • Найдите самый длинный путь от корня, который соответствует префиксу S [i + 1..m] $
  • Совпадение заканчивается либо в узле (скажем, w), либо в середине ребра [скажем, (u, v)].
  • Если он находится в середине ребра (u, v), разбейте ребро (u, v) на два ребра, вставив новый узел w сразу после последнего символа на ребре, который соответствует символу в S [i + l ..m] и как раз перед первым символом на краю, который не соответствует. Новое ребро (u, w) помечено той частью метки (u, v), которая соответствует S [i + 1..m], а новое ребро (w, v) помечено оставшейся частью (U, V) метка.
  • Создайте новое ребро (w, i + 1) из w в новый лист, помеченный i + 1, и оно пометит новое ребро непревзойденной частью суффикса S [i + 1..m]

Для построения дерева суффиксов для строки S длины m требуется O (m 2 ).
Ниже приведены несколько шагов для построения дерева суффиксов на основе строки «xabxa $» на основе вышеуказанного алгоритма:

Неявное суффиксное дерево
При создании дерева суффиксов с использованием алгоритма Укконена мы увидим неявное дерево суффиксов в промежуточных шагах несколько раз в зависимости от символов в строке S. В деревьях неявных суффиксов не будет ребра с меткой $ (или # или любого другого символа завершения) и нет внутренний узел с одним выходящим из него ребром.
Чтобы получить неявное дерево суффиксов из дерева суффиксов S $,

  • Удалите все терминальные символы $ с краевых меток дерева,
  • Удалите любой край, на котором нет метки
  • Удалите любой узел, у которого только один край выходит из него, и объедините края.

Описание высокого уровня алгоритма Укконена
Алгоритм Укконена создает неявное суффиксное дерево T i для каждого префикса S [l ..i] в S (длиной m).
Сначала он строит T 1, используя 1- й символ, затем T 2, используя 2- й символ, затем T 3, используя 3- й символ,…, T m, используя m- й символ.
Неявное суффиксное дерево T i +1 строится поверх неявного суффиксного дерева T i .
Истинное дерево суффиксов для S строится из T m путем добавления $.
В любое время алгоритм Укконена строит дерево суффиксов для символов, которые были замечены до сих пор, и поэтому имеет свойство онлайн, которое может быть полезно в некоторых ситуациях.
Требуемое время O (м).

Алгоритм Укконена разделен на m фаз (одна фаза для каждого символа в строке длиной m)
На этапе i + 1 дерево T i +1 строится из дерева T i .

Каждая фаза i + 1 дополнительно делится на i + 1 расширения, по одному для каждого из i + 1 суффиксов S [1..i + 1]
В расширении j фазы i + 1 алгоритм сначала находит конец пути от корня, помеченного подстрокой S [j..i].
Затем он расширяет подстроку, добавляя символ S (i + 1) до конца (если его там еще нет).
В расширении 1 фазы i + 1 мы помещаем строку S [1..i + 1] в дерево. Здесь S [1..i] уже будет присутствовать в дереве из-за предыдущего этапа i. Нам просто нужно добавить S [i + 1] -й символ в дерево (если его там еще нет).
В расширении 2 фазы i + 1 мы помещаем строку S [2..i + 1] в дерево. Здесь S [2..i] уже будет присутствовать в дереве из-за предыдущего этапа i. Нам просто нужно добавить S [i + 1] -й символ в дерево (если его там еще нет)
В расширении 3 фазы i + 1 мы помещаем строку S [3..i + 1] в дерево. Здесь S [3..i] уже будет присутствовать в дереве из-за предыдущего этапа i. Нам просто нужно добавить S [i + 1] -й символ в дерево (если его там еще нет)
,
,
В расширении i + 1 фазы i + 1 мы помещаем строку S [i + 1..i + 1] в дерево. Это всего лишь один символ, которого может не быть в дереве (если персонаж виден впервые). Если это так, мы просто добавляем новый край листа с меткой S [i + 1].

Алгоритм высокого уровня Укконена
Построить дерево T 1
Для меня от 1 до м-1 сделать
начало {фаза i + 1}
Для j от 1 до i + 1
begin {extension j}
Найдите конец пути от корня с меткой S [j..i] в текущем дереве.
Расширьте этот путь, добавив символ S [i + l], если его там уже нет
конец;
конец;

Расширение суффикса — это добавление следующего символа в построенное до сих пор дерево суффиксов.
В расширении j фазы i + 1 алгоритм находит конец S [j..i] (который уже находится в дереве из-за предыдущей фазы i), а затем расширяет S [j..i], чтобы убедиться, что суффикс S [j..i + 1] находится в дереве.

Есть 3 правила расширения:
Правило 1 : Если путь от корня, помеченного как S [j..i], заканчивается на краю листа (т. Е. S [i] — последний символ на краю листа), то символ S [i + 1] просто добавляется в конец этикетка на краю этого листа.

Правило 2 : Если путь от корня, помеченного как S [j..i], заканчивается на неконцевом ребре (т. Е. После S [i] на пути больше символов) и следующий символ не равен s [i + 1], то новый край листа с меткой s {i + 1] и номером j создается начиная с символа S [i + 1].
Новый внутренний узел также будет создан, если s [1..i] заканчивается внутри (между ними) не-конечного ребра.

Правило 3 : если путь от корня, помеченного как S [j..i], заканчивается на неконцевом ребре (то есть после S [i] на пути больше символов), а следующий символ — это s [i + 1] (уже в дерево), ничего не делать.

Рекомендуемые посты:

Построение суффикс-дерева Укконена — часть 1

0.00 (0%) 0 votes