Clarification regarding Ukkonen's Suffix Tree

I have been reading up on Ukkonen's Suffix tree for my work and wanted to confirm if the following is true.

Would it be correct to say that in a Ukkonen Suffix Tree:

---

Only edges that lead to leaf nodes can have multiple consecutive characters compressed as part of it. And that edges between interior nodes (like say, from the root to an interior node) can only represent a single character.

---

---

I do not think this statement is true. I have implemented a suffix tree using this article. You can see the final suffix tree they build for the example has edges with more then a letter.

---

The statement is incorrect. A suffix tree is a Patricia tree, which means all edges carry string labels (of any length, as opposed to single characters). But note that the labels are implemented as (from,to) references to the input text, hence the memory space taken by an edge is O(1) regardless of the length of the label.

链接地址: http://www.djcxy.com/p/40122.html

上一篇: 插入排序算法的Big Theta符号

下一篇: 澄清关于Ukkonen的后缀树