2

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

在这一点上，我关心两件事：

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

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

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

我们可以使用 ukkonen 的算法来比较两个文档并识别它们之间的所有公共子字符串吗？如果是这样，请逐步解释。

Ukkonen's suffix tree algorithm in plain English对Ukkonen's suffix tree有很好的解释吗？

4

1 回答 1

1

如果您有两个文档，您可以使用 Ukkonen 算法为这两个文档构建一个通用后缀树，然后执行后处理步骤以清理不可能的配置。

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

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

于 2017-09-17T20:58:18.133 回答