從後綴樹生成後綴

我已經基於此處的網站構建了一個基於Java的後綴樹http://marknelson.us/1996/08/01/suffix-trees/但我遇到了問題。我可以建立一個後綴樹，但我可以嘗試從樹中構建一組所有後綴。我基本上找到所有的「端節點」和由「末端節點」返回的表示字符串從後綴樹生成後綴

該算法適用於一個字，如「會計」

├── (1) bookkeeper 
├── (9) e 
│ ├── (8) eper 
│ ├── (10) per 
│ └── (12) r 
├── (6) k 
│ ├── (7) eeper 
│ └── (5) keeper 
├── (3) o 
│ ├── (4) kkeeper 
│ └── (2) okkeeper 
├── (11) per 
└── (13) r

後綴：

[bookkeeper, ookkeeper, okkeeper, kkeeper, keeper, eeper, eper, er, per, r]

但是，當我使用類似「ATATATATATA」

├── (1) ATATATATATA 
└── (2) TATATATATA

後綴失敗：

[ATATATATATA, TATATATATA]

但適當的後綴應該是：

[A, ATA, ATATA, ATATATA, ATATATATA, ATATATATATA, TA, TATA, TATATA, TATATATA, TATATATATA]

我可以找到通過找出每個「端節點」字符串的所有後綴的答案，但似乎並不像正確的做法。還有其他建議嗎？編輯：謝謝izomorphius！將END_CHAR添加到原始字符串幫助了一大堆。

├── (21) # 
├── (19) A 
│ ├── (20) # 
│ └── (15) TA 
│  ├── (16) # 
│  └── (11) TA 
│   ├── (12) # 
│   └── (7) TA 
│    ├── (8) # 
│    └── (3) TA 
│     ├── (4) # 
│     └── (1) TA# 
└── (17) TA 
    ├── (18) # 
    └── (13) TA 
     ├── (14) # 
     └── (9) TA 
      ├── (10) # 
      └── (5) TA 
       ├── (6) # 
       └── (2) TA#

後綴：

[A, ATA, ATATA, ATATATA, ATATATATA, ATATATATATA, TA, TATA, TATATA, TATATATA, TATATATATA]

來源

2012-04-09 Justin

看起來你的樹沒有完成'ATATATATATA'。 – Howard 2012-04-09 13:53:27

關於如何建立一個後綴樹是多加一個人工字符，你知道是不是在字母表中的典型尖。我通常添加'＃'，然後爲ATATATATATA＃構建後綴樹，這樣您就不會再遇到這個問題了。

你得到你描述的問題，因爲缺失的後綴實際上是作爲另一個後綴的前綴被滿足的。在最後添加一個人造角色可確保這絕不會發生。

來源

2012-04-09 13:54:18

啊。感謝後綴 - >前綴連接。這現在非常合理。 – Justin 2012-04-09 14:04:56

從後綴樹生成後綴

回答

相關問題