algorithm - 在庞大的列表中查找热门关键字

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

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

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

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

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

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