Разъяснение относительно Суффикс-дерева Укконена

Question

Я перечитывал суффиксное дерево Укконена для своей работы и хотел подтвердить, верно ли следующее.

Правильно ли будет сказать, что в суффиксном дереве Укконен:

---

Только ребра, ведущие к узлам листа, могут иметь несколько последовательных символы сжаты как часть этого. И что края между интерьером узлы (как, скажем, от корня до внутреннего узла) могут представлять только один символ.

---

Answer 1

Я не думаю, что это утверждение верно.Я реализовал дерево суффиксов, используя эту статью .Вы можете видеть, что конечное дерево суффиксов, которое они строят для примера, имеет ребра, содержащие более буквы.

Answer 2

Неверное утверждение. Дерево суффиксов - это дерево Патриции, что означает, что все ребра имеют строковые метки (любой длины, в отличие от одиночных символов). Но обратите внимание, что метки реализованы как (от, до) ссылки на входной текст, поэтому объем памяти, занимаемый ребром, равен O (1) независимо от длины метки.