Насколько линейна временная сложность построения суффиксного дерева в наихудшем случае?

Мне трудно понять, почему временная сложность построения суффиксного дерева в наихудшем случае является линейной, особенно когда нам нужно построить суффиксное дерево для строки, которая может состоять из повторяющихся одиночных символов, таких как "aaaaa" .

Даже если бы я построил сжатое дерево суффиксов для «aaaaa», я не смог бы сжать какие-либо узлы, поскольку никакие два ребра, начинающиеся с узла, не могут иметь строковые метки, начинающиеся с одного и того же символа.

Это привело бы к дереву суффиксов высотой 5, и при каждой вставке суффикса мне нужно было бы продолжать переход от корня к листу.

Вот как я подошел: суффиксы: а, аа, ааа, аааа, ааааа

Создайте корневой узел, создайте ребро, несущее «а», и соедините его с новым узлом, где слева от него стоит «$», и повторяйте этот процесс, пока мы не сможем ааааа.

Это приведет к O (n ^ 2) вместо O (n). Что мне здесь не хватает?


algorithm data-structures time-complexity big-o suffix-tree
person sia831    schedule 23.07.2015    source источник
comment
Вы упускаете из виду тот факт, что алгоритм построения намного сложнее, чем то, что вы описываете. Взгляните на это великолепное объяснение алгоритма Укконена   -  person Niklas B.    schedule 24.07.2015
comment
Кстати, сжатие связано с тем, что вы помечаете свои ребра строковыми индексами, а не реальными подстроками. У вас есть n листовых узлов и, следовательно, не более n-1 внутренних узлов, что дает в общей сложности не более 2n-1 ребер, каждое из которых помечено O (1) словами. Вот почему в первую очередь можно хранить суффиксное дерево в пространстве O (n) (хотя не уверен, что это было частью вашей путаницы)   -  person Niklas B.    schedule 24.07.2015

Ответы (1)


arrow_upward
3
arrow_downward

Я согласен с комментариями, но вот еще некоторые подробности:

Процедура, которую вы описываете для формирования дерева aaaaa, - это O (n), а не O (n ^ 2). Создание узлов и листьев — это операции с постоянным временем, и вы выполняете их n == 5 раз. Ваше предположение об O (n ^ 2), похоже, основано на идее, что вы будете переходить от корня к листу на каждом шаге, но в этом нет необходимости; например в алгоритме Укконена:

  • Вы сохраняете указатель на узел, на котором остановились, прежде чем вставить следующий
  • А в случае повторений вы не выполняете никакой работы до тех пор, пока не закончатся повторения, а затем производите вставки конечного знака $ один за другим, следуя за символами на созданном вами ребре, а также цепочкой суффиксных звеньев в случае более сложных повторений

Ключ к тому, почему алгоритм Укконена (подробности здесь) O(n) состоит в том, что он поддерживает «память» о том, где делать вставки, в форме (а) указателя на то место, где была сделана предыдущая вставка, и (б) сети суффиксных ссылок. Эта сеть может быть обширной, но на каждый внутренний узел приходится только одна суффиксная ссылка, поэтому ее размер по-прежнему равен O(n).

person jogojapan    schedule 04.08.2015