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

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

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

理论上

甲后缀数组是"最好"的答案,因为它可以被实现为使用线性空间和时间,以检测任何重复的子串.然而 - 天真的实现实际上需要花费时间O(n ^ 2 log n)来对后缀进行排序,并且如何将其减少到O(n log n)并不是完全明显的,更不用说O(n)了,尽管你可以阅读相关文件,如果你想.

一个后缀树可以采取稍微更多的内存(仍然是线性的,虽然)不是一个后缀数组,但更容易实现快速构建,因为你可以使用像一个基数排序主意,因为你添加的东西树(见从维基百科链接详细信息的名称).

该KMP算法也不错,要知道,这是专门为非常迅速寻找一个较长的字符串中的特定字符串.如果您只需要这种特殊情况,只需使用KMP即可,无需首先构建足够的索引.

在实践中

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

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