algorithm - 我们如何使用 Ukkonen 的后缀树来识别文档中所有常见的子字符串。 VC++

Question

我正在尝试使用 ukkonen 的后缀树来比较文档。

此时我担心两件事:

1. 首先，我尝试为一个文档生成后缀树，然后使用该后缀树查找该文档中的所有公共(public)子字符串。

2. 接下来是识别两个文档之间的所有公共(public)子字符串。

我能够为基于 http://marknelson.us/1996/08/01/suffix-trees/ 的文档生成 ukkonen 后缀树.并搜索给定的子字符串。但我仍然找不到一种方法来识别给定文档中的所有公共(public)子字符串。你能告诉我一个方法吗？我正在使用 Visual C++。

我们能否使用 ukkonen 的算法来比较两个文档并识别它们之间的所有公共(public)子字符串？如果是，请逐步说明。

在Ukkonen's suffix tree algorithm in plain English? 中对Ukkonen 的后缀树有很好的解释。

Answer 1

如果你有两个文件，你可以构造一个generalized suffix tree使用 Ukkonen 算法对两个文档进行处理，然后进行后处理步骤以清除不可能的配置。

一旦有了广义后缀树，就可以在树上运行 DFS 以识别树中的每个内部节点，这些节点的叶子对应于每个文档的后缀。这些节点中的每一个都对应于两个文档共有的子字符串，因为每个节点都对应于两个字符串的后缀的前缀。

从那里，您可以对这些子字符串做任何最合理的事情。如果你想要最长的公共(public)子串，只要搜索你在第一步中标记的字符串深度最高的节点。如果你想找到所有这样的子串，你可以遍历所有这些节点并打印出你一路积累的每个子串。