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的支持，这可能非常简单或困难。

如果不工作，而不是插入字符到你的树，它们包裹在一些其他类型的变量（结构，对象，字典），以“延长”其含义。这样你就可以提供所需的额外信息（这是字符串的结尾吗？哪一个字符串是它的结尾？）。然后你可以在这个新的包装上为自定义运算符提供相等性，而不是直接使用字符。