Создание суффиксного дерева строки S[2..m] из суффиксного дерева строки S[1..m]

Существует ли быстрый (время сложности O(1)) способ создания суффиксного дерева строки S[2..m ] из суффиксного дерева строки S[1..m]?

Я знаком с Укконеном, поэтому знаю, как составить быстрое суффиксное дерево строки S[1..m+1] из суффиксного дерева строки S[1..m], но не смог применить алгоритм для обратной ситуации .


algorithm data-structures complexity-theory suffix-tree
person user2356167    schedule 06.05.2013    source источник
comment
Думаю, нет. По сути, нам нужно удалить строку [1..m] в дереве суффиксов S[1..m]. С чего вы взяли, что существует алгоритм с постоянной временной сложностью?   -  person Faraway    schedule 07.05.2013
comment
Если я не ошибаюсь, сложность состоит в том, чтобы определить, какой листовой узел соответствует S[1..m]. Когда у вас есть лист, я думаю (но не пытался на самом деле записать доказательство), что удаление этого листа и (при необходимости) внутреннего узла, который указывает на него, должно быть O (1). Поиск листа занимает O(m), но вы можете использовать дополнительное пространство O(1) для хранения указателя на самый глубокий лист в дереве, что сократит время поиска листа до O(1). После удаления листа вам придется обновить этот указатель, но это можно сделать за O(1) амортизированное время, если у вас есть суффиксные ссылки в дереве.   -  person jogojapan    schedule 07.05.2013
comment
Алгоритм Укконена достиг сложности O(n) за счет построения дерева суффиксов слева направо. Алгоритмы до этого строят его справа налево, и все не смогли достичь O (n). Так что я думаю, что нет.   -  person Chen Pang    schedule 23.09.2013

Ответы (1)


arrow_upward
1
arrow_downward

Ну, как говорит @jogojapan, чтобы получить дерево S[2..m] из дерева S[1..m], нам нужно:

  • Найдите лист позиции 0 L.
  • Если L имеет более одного родственного элемента, удалите указатель с родительского элемента L на L.
  • Если у L ровно один родственный элемент, измените указатель с прародителя L на родителя L, чтобы вместо этого он указывал на L брат и сестра.

@jogojapan также предлагает сохранить указатель на самый глубокий лист дерева. С этим есть две проблемы: L не обязательно является самым глубоким листом в дереве, так как Пример из Википедии показывает, и, во-вторых, если вы хотите иметь возможность выводить структуру данных того же типа, что и получили, после удаления L вам нужно найти новый< /em> position-0 leaf, что в любом случае займет O(m) времени.

(Вы могли бы создать массив указателей на каждый лист за время O(m) и отсортировать их по позиции за время O(m). Тогда вы сможете построить все деревья { S[t..n] : 1 ‹= t ‹= m в постоянном амортизированном времени каждый)

Предполагая, что вас не интересует амортизированное время, давайте докажем, что то, о чем вы просите, невозможно.

  • Мы знаем, что любой алгоритм изменения суффиксного дерева S[1..m] должен начинаться с корня: он не может начинаться где-либо еще, потому что мы ничего не знаем о лежащей в основе конкретной структуре данных, и мы не знаем, что дерево узлы имеют указатели parent, поэтому единственная позиция, из которой доступно все дерево, — это корень.
  • Мы также знаем, что он должен найти лист позиции 0, прежде чем он сможет надеяться изменить структуру данных в суффиксное дерево для S[2..m]. Для этого он, очевидно, должен пройти через каждый узел между корнем и листом позиции 0.
  • Дело в том, что рассмотрим суффиксное дерево a^m (символ a повторяется m раз): длина пути м-1. Таким образом, любой алгоритм должен посетить не менее m-1 узлов, и, следовательно, в худшем случае потребуется O(m) времени.
person Andy Jones    schedule 23.09.2013