Ukkonen的算法广义后缀树

2018-05-31 09:25:00

我了解ukkonen的算法。我只是很好奇如何将它扩展为有多个字符串（以特殊字符“$”结尾）。

我在某处读到给定字符串s1（例如“abcddefx $”）和s2（例如“abddefgh $”），我应该通过ukkonen的算法正常插入s1。然后用s2遍历树。那就是我应该在树中搜索s2。一旦我到达搜索结束的节点（“ab”，在'b'之后），我应该从这里恢复ukkonen的算法。

我理解这背后的基本逻辑。但我很好奇的是，旧的后缀链接会发生什么。他们仍然有效吗？当我开始新的传递时，我也会对我的三元组（active_node，active_length，remaining）感到困惑，如果它是（节点代表“ab”，0,0）

为了处理特殊字符，您可以使用Unicode专用区。这些是为您自己使用保留的几个特殊字符范围，但范围只有大约4000个字符。取决于您使用的语言对unicode的支持，这可能非常简单或困难。

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

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