algorithm - 设计一个实时保持前k个频繁词的系统

Question

假设我们想要一个系统保持最近一小时内出现在推文中的前 k 个频繁词。如何设计？

我可以想出 hashmap、heap、log 或 MapReduce，但我找不到一种非常有效的方法来做到这一点。

其实这是面试中的一个问题。
首先，我使用哈希图来计算每个单词的频率。我还记录了日志，随着时间的流逝，我可以倒数最旧的词频。
然后我保留了一个长度为 K(Top K 数组)和一个数字 N 的条目数组，它是数组中最小的计数数字。
每次有新词出现时，我更新计数hashmap并得到这个新词的计数数。如果它大于N，我会找到这个词是否在数组中。如果是，我会更新数组中的条目。如果没有，我删除数组中最小的条目并将这个新单词插入其中。 (相应地更新 N)

这是问题所在，我的方法无法处理删除。我可能需要迭代整个计数哈希图来找到新的前 K。
另外，正如面试官所说，系统应该很快就能得到结果。我想到了几台机器一起工作，每台机器都需要一些话。然而，如何组合结果也成为一个问题。

Answer 1

如果单词没有加权(权重 0 和 1 除外)，则可以使用 O(N) 辅助存储导出一个简单的数据结构，该数据结构按顺序维护单词计数，其中 N是在滑动窗口中遇到的唯一词的数量(在示例中为一小时)。所有操作(加词、过期词、查找最常用词)都可以在O(1)中进行。时间。由于任何准确的解决方案都需要保留滑动窗口中的所有唯一词，因此该解决方案虽然每个词的常数因子不小，但并不是渐进变差。

解决方案的关键是任何给定单词的计数只能增加或减少 1，并且所有计数都是整数。因此，可以维护一个双向链接的计数列表(按顺序)，其中列表中的每个节点都指向具有该计数的单词的双向链接列表。此外，单词列表中的每个节点都指向相应的计数节点。最后，我们维护一个哈希图，它允许我们找到与给定单词对应的节点。

最后，为了在生命结束时衰减单词，我们需要保留来自滑动窗口的整个数据流，其大小为 O(N')。哪里N'是滑动窗口期间遇到的单词总数。这可以存储为单链表，其中每个节点都有一个时间戳和一个指向单词列表中唯一单词的指针。

当一个词遇到或过期时，需要调整它的计数。由于计数只能递增或递减 1，因此调整始终包括将单词移动到相邻的计数节点(可能存在也可能不存在)；由于计数节点存储在一个已排序的链表中，因此可以及时找到或创建相邻节点O(1) .此外，通过从最大值向后遍历计数列表，始终可以在恒定时间内跟踪最流行的单词(和计数)。

如果这不明显，这里是给定时间点数据结构的粗略 ascii 艺术图:

Count list      word lists (each node points back to the count node)

  17            a <--> the <--> for
  ^
  |
  v
  12            Wilbur <--> drawing
  ^
  |
  v
  11            feature

现在，假设我们找到了 Wilbur .这将把它的数量增加到 13；我们可以从 12的成功中看出不是 13 13需要创建计数节点并将其插入计数列表。在我们这样做之后，我们删除 Wilbur从它当前的词表中，将其放入新创建的与新计数节点相关联的空词表中，并更改 Wilbur中的计数指针。指向新的计数节点。

然后，假设使用 drawing过期，所以它的新计数将是11。从 12的前身可以看出。是 11不需要创建新的计数节点；我们只需删除 drawing从它的单词列表中，并将其附加到与 11 相关联的单词列表中，在我们这样做时修复它的计数指针。现在我们注意到与 12 相关的词表是空的，所以我们可以删除 12从计数列表中计数节点并将其删除。

当单词的计数达到 0 时，而不是将其附加到 0计数节点，它不存在，我们只是删除单词节点。如果遇到新词，我们只需将该词添加到 1计数节点，如果它不存在，则创建该计数节点。

在最坏的情况下，每个单词都有唯一的计数，因此计数列表的大小不能大于唯一单词的数量。此外，单词列表的总大小正好是唯一单词的数量，因为每个单词都在一个单词列表中，完全过期的单词根本不会出现在单词列表中。

--- 编辑

这个算法有点耗内存，但它真的不应该有任何问题来保存一个小时的推文。甚至一天的值(value)。几天后，即使考虑缩写和拼写错误，独特单词的数量也不会发生太大变化。即便如此，还是值得考虑减少内存占用和/或使算法并行的方法。

为了减少内存占用，最简单的方法是删除几分钟后仍然唯一的单词。这将大大减少独特的字数，而不会改变流行词的数量。实际上，您可以在不改变最终结果的情况下进行更彻底的修剪。

为了并行运行该算法，可以通过使用散列函数生成机器号来将单个单词分配给不同的机器。 (与用于构造哈希表的哈希函数不同。)然后是顶部 k词可以通过合并顶部找到 k来自每台机器的单词；散列分配保证来自每台机器的词集是不同的。