您可以使用什么算法在字符串中查找重复的短语？

Question

给定一个任意字符串,找到重复短语的有效方法是什么？我们可以说短语必须长于一定长度才能包括在内.

理想情况下,您最终会得到每个短语的出现次数.

Answer 1

理论上

• 甲后缀数组是"最好"的答案,因为它可以被实现为使用线性空间和时间,以检测任何重复的子串.然而 - 天真的实现实际上需要花费时间O(n ^ 2 log n)来对后缀进行排序,并且如何将其减少到O(n log n)并不是完全明显的,更不用说O(n)了,尽管你可以阅读相关文件,如果你想.
• 一个后缀树可以采取稍微更多的内存(仍然是线性的,虽然)不是一个后缀数组,但更容易实现快速构建,因为你可以使用像一个基数排序主意,因为你添加的东西树(见从维基百科链接详细信息的名称).
• 该KMP算法也不错,要知道,这是专门为非常迅速寻找一个较长的字符串中的特定字符串.如果您只需要这种特殊情况,只需使用KMP即可,无需首先构建足够的索引.

在实践中

我猜你正在分析一个实际自然语言(例如英语)单词的文档,你实际上想要对你收集的数据做些什么.

在这种情况下,您可能只想对某些小n 进行快速n-gram分析,例如只有n = 2或3.例如,您可以通过去掉标点符号,大写字母,将文档标记为单词列表,和词干(运行,运行 - >'运行')以增加语义匹配.然后,只需构建每个相邻词对的哈希映射(例如C++中的hash_map,python中的字典等)到目前为止的出现次数.最后,您将获得一些非常有用的数据,这些数据代码非常快,并且运行速度不会太慢.

Answer 2

就像前面的人提到的那样，后缀树是完成这项工作的最佳工具。我最喜欢的后缀树网站是http://www.allisons.org/ll/AlgDS/Tree/Suffix/。它在一页上列举了后缀树的所有巧妙用法，并js嵌入了一个测试应用程序来测试字符串并完成示例。