8

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

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

4

5 回答 5

7

理论上

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

在实践中

我猜您正在分析实际自然语言（例如英语）单词的文档，并且您实际上想对您收集的数据做一些事情。

在这种情况下，您可能只想对一些小的 n 进行快速的n-gram分析，例如 n=2 或 3。例如，您可以通过去除标点符号、大写字母、和词干提取（运行，同时运行 -> 'run'）以增加语义匹配。然后只需为每个相邻的单词构建一个哈希映射（例如 C++ 中的 hash_map，python 中的字典等）到它的出现次数。最后，您会得到一些非常有用的数据，这些数据编码起来非常快，而且运行起来也不会很慢。

于 2008-09-18T15:38:29.467 回答
4

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

于 2008-09-17T23:49:14.413 回答
1

后缀树是实现这一点的好方法。那篇文章的底部有不同语言实现的链接。

于 2008-09-17T23:23:52.993 回答
0

就像 jmah 所说，您可以为此使用后缀树/后缀数组。

您可以在此处使用一种算法的描述（参见第 3.1 节）。

您可以在他们引用的书（Gusfield，1997 年）中找到更深入的描述，该书位于 google 图书上。

于 2008-09-17T23:33:24.467 回答
0

假设给定排序数组 A，其中包含 n 个条目 (i=1,2,3,...,n)

Algo(A(i))
{
  while i<>n
  {
    temp=A[i];
    if A[i]<>A[i+1] then
    {     
      temp=A[i+1];
      i=i+1;
      Algo(A[i])
    }
    else if A[i]==A[i+1] then
      mark A[i] and A[i+1] as duplicates
  }
}

该算法在 O(n) 时间运行。

于 2009-02-24T01:40:49.483 回答