關於Ukkonen的後綴樹的澄清

Question

我一直在閱讀Ukkonen後綴樹上的工作，並想確認以下內容是否屬實。

難道是正確地說，在Ukkonen後綴樹：

---

，導致葉節點可以有多個連續 字符壓縮爲它的一部分，只有邊緣。而內部節點之間的邊緣（比如說，從根節點到內部節點）只能代表 單個字符。

---

Answer 1

我不認爲這種說法是正確的。我已使用此article實施了後綴樹。您可以看到他們爲示例構建的最終後綴樹具有多於一個字母的邊緣。

Answer 2

該聲明不正確。後綴樹是帕特里夏樹，意思是所有的邊都帶有字符串標籤（任意長度，而不是單個字符）。但請注意，標籤實現爲（從，到）對輸入文本的引用，因此無論標籤的長度如何，邊緣佔用的內存空間都是O（1）。