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

Question

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

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

Answer 1

理论上

• A suffix array 是“最佳”答案，因为它可以实现为使用线性空间和时间来检测任何重复的子字符串。然而 - 天真的实现实际上需要时间 O(n^2 log n) 来对后缀进行排序，并且如何将其减少到 O(n log n) 并不完全明显，更不用说 O(n)，尽管你可以阅读相关论文，如果你愿意的话。
• A suffix tree 可以比后缀数组占用更多的内存(虽然仍然是线性的)，但是更容易实现快速构建，因为你可以在向树中添加东西时使用类似基数排序的想法(参见维基百科链接从名称中获取详细信息)。
• KMP algorithm 也需要注意，它专门用于在较长的字符串中快速搜索特定的子字符串。如果您只需要这种特殊情况，只需使用 KMP 即可，无需费心先构建足够的索引。

在实践中

我猜您正在分析一份包含实际自然语言(例如英语)单词的文档，并且您实际上想对收集到的数据执行某些操作。

在这种情况下，您可能只想快速执行一次 n-gram分析一些小的 n，例如 n=2 或 3。例如，您可以通过去除标点符号、大写和词干词(running，runs both -> 'run')将您的文档标记为单词列表以增加语义匹配。然后只需构建一个 HashMap (例如 C++ 中的 hash_map，python 中的字典等)，将每个相邻的单词对构建到它到目前为止出现的次数。最后，您会得到一些非常有用的数据，这些数据的编码速度非常快，而且运行速度也不会太慢。