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

Question

假设我们想要一个系统来保持前k个频繁的单词在过去一个小时内出现在tweet中。如何设计？

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

实际上这是面试中的一个问题
首先，我使用hashmap计算每个单词的频率。我还保存了日志，以便随着时间的推移，我可以倒数最古老的单词的频率
然后我保留了一个长度为K（顶K数组）和数字N的条目数组，N是数组中最小的计数
每次出现一个新词，我都会更新计数哈希映射，并获取这个新词的计数编号。如果它大于N，我将发现这个单词是否在数组中。如果是，则更新数组中的该条目。如果没有，我将删除数组中最小的条目，并将这个新词插入其中。（相应地更新N）

问题是，我的方法无法处理删除。我可能需要迭代整个计数hashmap，以找到新的前K。
此外，正如面试官所说，系统应该很快得到结果。我想到几台机器一起工作，每台机器都会记下一些单词。然而，如何组合结果也成为一个问题。

Answer 1

以下是一个对您的目的相当有效的算法：-

1. 首先使用字典而不是hashmap来存储字符串，因为它提供了更好的空间效率

时间复杂性：-

更新顶k：-O（logk）为heapify，插入，删除

更新或搜索单词：O（|W|）其中|W|是单词的长度

堆的空间复杂性：O（k）

字典，HashMap，堆指针的空间：-O（N）N是总词

Answer 2

这组问题被称为数据流算法。在你的特殊情况下，有两个合适的——“损失计数”和“粘性采样”这是解释它们或这个的论文，带有图片。这是一个更简化的介绍。

编辑：（太长，无法放入注释）

尽管这些流式算法本身并不打折过期的数据，但可以运行60个滑动窗口，每小时每分钟一个，然后每分钟删除并创建一个新窗口。顶部的滑动窗口用于查询，其他仅用于更新。这将为您提供1百万分辨率。

批评说，流式算法是概率的，不会给你确切的计数，虽然这是真的，请比较例如与Rici的算法在这里，一个确实控制错误频率，并可以使它非常低，如果需要的话。随着流的增长，您希望将其设置为流大小的%，而不是绝对值。

流式算法非常节省内存，这是实时处理大型流时最重要的事情。与Rici的精确算法相比，它需要一台主机将当前滑动窗口的所有数据保存在内存中。它可能无法很好地扩展-增加速率为100/s-

作为Rici算法重要组成部分的hastable需要一个连续的内存块，随着内存块的增长，这个内存块的问题越来越大。

Answer 3

如果单词没有加权（除了权重0和1），那么可以使用O（N）辅助存储来导出一个简单的数据结构，该数据结构保持单词计数的顺序，其中N是在滑动窗口（示例中为一小时）。所有操作（添加一个单词，过期一个单词，查找最频繁的单词）都可以在O（1）时间内执行。由于任何精确的解决方案都需要保留滑动窗口中所有唯一的单词，因此尽管每个单词的常数因子并不小，但这种解决方案不会渐近地变差。

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

最后，为了在单词寿命结束时衰减，我们需要保留滑动窗口中的整个数据流，滑动窗口的大小为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中的计数指针更改为指向新计数节点。

然后，假设绘图的使用到期，那么它的新计数将是11。我们可以从12的前身是11这一事实中看出，不需要创建新的计数节点；我们只需将绘图从其字列表中删除，并将其附加到与11，修复它的计数指针，因为我们这样做。现在我们注意到与12相关联的word list是空的，因此我们可以将12Count-list中的节点删除。

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

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

---编辑

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

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

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