在大名单中查找热门关键词

Question

我有一个很大的清单，大概有10万行这样的文字：

• 依地新闻
• 副枕
• cddeeffipad
• 地狱世界
• 这个世界..。诸若此类

想要找到流行的子串，在这种情况下，"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是单词总数。