Ukkonen的算法通用後綴樹

Question

我瞭解ukkonen's algorithm。我只是很好奇如何將它擴展爲有多個字符串（以特殊字符「$」結尾）。

我在某處讀到給定字符串s1（稱爲「abcddefx $」）和s2（稱爲「abddefgh $」），我應該通過ukkonen的算法正常插入s1。然後用s2遍歷樹。那就是我應該在樹中搜索s2。 一旦我到達搜索結束的節點（「ab」，在'b'之後），我應該從那裏恢復ukkonen的算法。

我明白這背後的基本邏輯。但我很好奇的是，舊的後綴鏈接會發生什麼。他們仍然有效嗎？ 另外我很困惑我的三重（active_node，active_length，餘數）應該是（節點代表「ab」，0,0），因爲我開始新的傳球？

Answer 1

對於特殊字符的處理，您可以使用Unicode Private Use Areas。這些是爲您自己使用保留的幾個特殊字符範圍，但範圍只有大約4000個字符。取決於您使用的語言對unicode的支持，這可能非常簡單或困難。

如果不工作，而不是插入字符到你的樹，它們包裹在一些其他類型的變量（結構，對象，字典），以「延長」其含義。這樣你就可以提供所需的額外信息（這是字符串的結尾嗎？哪一個字符串是它的結尾？）。然後你可以在這個新的包裝上爲自定義運算符提供相等性，而不是直接使用字符。