0

我有一个巨大的列表,大约有 100 000 行,如下所示:

  • ipad新闻
  • 阿基帕德
  • cddeffipad
  • 地狱世界
  • iworldthis .. 等等

并且想找到流行的子字符串,在这种情况下,“ipad”将是最受欢迎的,“world”将排在第二位。最小长度应为三个或四个字符。

我无法预测子字符串,所以使用字典是不行的。

4

3 回答 3

4

这是一个相对复杂的问题……但使用前缀/后缀树很容易处理。它本质上是最长公共子序列最长公共子串问题的变体。- 这就是我要开始的地方。

实际上有很多关于这个表格问题的研究——你应该能够使用上面的术语来缩小你的搜索范围。

于 2010-11-12T20:04:50.653 回答
2

您可以使用可以及时构建的通用后缀树来解决此问题O(n)。这实际上是对LCS 问题的一种发挥。

于 2010-11-12T20:07:24.187 回答
0

我将使用以下逻辑流程来解决这个问题:

  1. 提取每个单词的后缀集。所以从“ipadnews”我们得到:“ipadnews”、“padnews”、“adnews”等等。这样,“新闻”将是后缀之一,而不是“ipad”。

  2. 为了弥补上述步骤中缺少的子字符串,还要提取前缀。我们得到“ipadnew”、“ipadne”等,包括“ipad”。

  3. 对于上面的每个子字符串,将它们散列到一个计数中,例如 $hash{$substr}++。

最后,我们将有一个长哈希表,其中单词的频率作为值。假设您只想要 10 个最流行的单词,而不是昂贵的排序。从一开始就保留一个集合,其标准是其中的任何单词的分数都必须高于当前的最低分数。您可以使用最低分数跟踪单词,当您添加分数高于最低分数的第 11 个项目时,将最低分数的单词剔除并更新最低分数指针。

哈希表中的最大键数为 2*k*n,其中 k 是单词的平均长度,n 是单词的总数。

于 2010-11-12T20:22:53.860 回答