如何在内存不足的环境下找到书中的高频词？

Question

最近在一次技术面试中，我被要求编写一个程序来查找教科书中的高频词（出现次数最多的词）。 该程序的设计方式应使其能够用最少的内存处理整本教科书。 性能不是问题。 我能够通过编程来查找单词的频率，但它消耗了大量的内存。

如何减少此操作的内存消耗？ 有什么策略/解决方案吗？

-斯内哈尔

Answer 1

与许多好的面试问题一样，该问题的措辞有点含糊/不准确，以迫使受访者提出澄清问题并陈述假设。 我认为这里的许多其他答案都很好，因为它们探讨了这些假设并展示了对大局的理解。

我假设文本“离线”存储在某个地方，但是有一种方法可以迭代文本中的每个单词，而无需将整个文本加载到内存中。

然后下面的 F# 代码找到前 N 个单词。 它唯一的数据结构是键值对（单词、频率）的映射，并且只保留其中的前 N ​​个，因此内存使用量为 O(N)，很小。 运行时间为 O(numWordsInText^2)，虽然很差，但考虑到问题的限制是可以接受的。 该算法的要点很简单，对于文本中的每个单词，计算它出现的次数，如果它在运行的 best-N 中，则将其添加到列表中并删除之前的最小条目。

请注意，下面的实际程序将整个文本加载到内存中，只是为了方便说明。

#light
// some boilerplate to grab a big piece of text off the web for testing
open System.IO 
open System.Net 
let HttpGet (url: string) = 
    let req = System.Net.WebRequest.Create(url) 
    let resp = req.GetResponse() 
    let stream = resp.GetResponseStream() 
    let reader = new StreamReader(stream) 
    let data = reader.ReadToEnd() 
    resp.Close() 
    data 
let text = HttpGet "http://www-static.cc.gatech.edu/classes/cs2360_98_summer/hw1"
let words = text.Split([|' ';'\r';'\n'|], System.StringSplitOptions.RemoveEmptyEntries)
// perhaps 'words' isn't actually stored in memory, but so long as we can 
// 'foreach' over all the words in the text we're good
let N = 5  // how many 'top frequency' words we want to find
let FindMin map =
    // key-value pair with mininum value in a map
    let (Some(seed)) = Map.first (fun k v -> Some(k,v)) map
    map |> Map.fold_left 
        (fun (mk,mv) k v -> if v > mv then (mk,mv) else (k,v)) 
        seed
let Main() =
    let mutable freqCounts = Map.of_list [ ("",0) ]
    for word in words do
        let mutable count = 0
        for x in words do
            if x = word then
                count <- count + 1
        let minStr,minCount = FindMin freqCounts
        if count >= minCount then
            freqCounts <- Map.add word count freqCounts
        if Seq.length freqCounts > N then
            freqCounts <- Map.remove minStr freqCounts
    freqCounts 
    |> Seq.sort_by (fun (KeyValue(k,v)) -> -v) 
    |> Seq.iter (printfn "%A")
Main()

输出：

[the, 75]
[to, 41]
[in, 34]
[a, 32]
[of, 29]

Answer 2

您可以结合使用外部合并排序和优先级队列。 合并排序将确保您的内存限制得到遵守，优先级队列将维护您的前 K 个搜索。 显然，优先级队列必须足够小以适合内存。

• 首先，将输入字符串分成块，对每个块进行排序并存储到辅助存储中（外部排序） - O(n log n)
• 读取每个块并在块内计算单词的频率，因此在这一步结束时，每个块是减少到块内的（唯一词频计数）。 O(n)
• 开始跨块读取元素并聚合每个单词。 由于块是排序的，因此您可以在 O(n) 内完成。
• 现在，维护 K 个元素的最小优先级堆（堆顶部是堆中的最小元素）。 通过前 K 个元素填充优先级堆，然后进行下一个（唯一单词 - 最终计数），如果其计数大于堆中的顶部元素，则弹出顶部并推送当前单词。 O(n log k)

所以你的最终时间复杂度是 O(n(log k + log n))
-

Answer 3

好吧，如果你想要绝对糟糕的表现......

取出书中的第一个单词，并计算它出现的次数。 取出书中的第二个单词，数数它出现了多少次。 如果超过最后一个单词，则丢弃最后一个单词。 依此类推...您最终会多次计算相同的单词，除非您将它们的列表保存在某个地方，但如果您真的想要最小化内存，那么这应该只需要几个整数。 应该在 O(n^2) 时间内运行，其中 n 是书中的单词数。

Answer 4

创建一个单词键的二叉树怎么样（当您不断从文件中读取单词时）。 这有助于在 O(Log(n)) 中搜索已经重复的单词。 所以最后你得到了 O(nLog(n)) 的顶级单词搜索。

基本算法适用

于文件中的每个单词：

1. 为给定单词创建唯一键（加权 ascii 字符，例如“bat”可以是 1*'b' + 2*'a' + 3*'c'；
2. 将此单词添加到如果该单词已存在，则增加
3. 单词和当前计数以维护Top5（单词，计数）维护Top5计数和相关单词的动态列表。

该 字。

Answer 5

您可能使用了内存密集型但具有恒定查找时间的哈希表，因此性能/内存的权衡是显而易见的。 当你读完本书时，你就会知道答案。 此外，为每个单词递增计数器的速度很快（因为可以快速查找哈希表）。

另一种方法是查看第一个单词，然后浏览整本书，看看该单词出现了多少次。 这需要最少的内存。 然后你对下一个单词做同样的事情并浏览整本书。 如果该单词出现次数较多，则将其添加为最上面的单词（或最前面的 N 个单词）。 当然，这是极其低效的——如果第一个和第三个单词相同，即使你只是对第一个单词做了同样的事情，你最终还是会再次浏览整本书。

Answer 6

好的，如果您只对出现次数最多的 n 个单词感兴趣，一种方法是分两遍，第一遍基于修改后的 布隆过滤器。 不要使用位图来跟踪哈希出现，而是使用整数数组 - 字节、16 位、32 位甚至 64 位，具体取决于输入大小。 如果布隆过滤器只是设置与单词的每个哈希值相对应的位，则您将增加数组中哈希索引处的计数。

这种方法的问题是两个单词可能会给出相同的哈希值。 因此，您需要执行第二遍，忽略单词，除非它们的哈希总数高于某个阈值，从而减少需要分配的内存量来进行精确计数。

因此，只需创建一个位图，其中为最高出现的哈希值设置位。 然后，在单词的第二遍中，如果某个单词在位图中的哈希值“命中”，则查找它或将其添加到哈希表中并增加其计数。 通过创建仅包含出现次数最多的单词的哈希表，可以最大限度地减少内存使用量。

Answer 7

我是一名物理学家，所以我最喜欢的方法是近似。 您无需浏览整个文本即可获得最常见的单词。 相反：

• 解析足够小的块以允许您的内存限制，
• 跳过随机数量的文本，
• 重复，组合累积的结果。
• 当列表令人满意地收敛时停止。

如果您对较小的块使用内存高效的算法（例如排序），那么您可以获得比读取每个单词的最有效算法快得多的性能。

注意：这确实假设最常见的单词确实在整个文本中出现最频繁，而不仅仅是在文本中的某个位置。 对于英文文本，这个假设是正确的，因为像“the”等单词在整个文本中出现的频率很高。 如果您担心这一要求，请要求算法至少完成整个文本的一次传递。

Answer 8

我可能会对此投反对票...

如果文本是英文，而您只想找到最常见的 5 个单词，那么您的程序如下：

print "1. the\n";
print "2. of\n";
print "3. and\n";
print "4. a\n";
print "5. to\n";

运行速度快并且消耗最少的内存！

Answer 9

如果性能确实不重要，您可以依次浏览每个单词，检查它是否在您的“前 N”中，如果不是，则计算它的所有出现次数。 这样你就只存储 N 个值。 当然，您会多次计算相同的单词，但是，正如您所说，性能不是问题 - 而且代码很简单（这通常是更可取的 - 所有其他条件都相同）。

Answer 10

一种可能的解决方案是使用 trie 数据结构来存储与其出现次数相关的所有单词。

其他解决方案可以在这个相关问题的答案中找到：Space-用于存储单词列表的高效数据结构？

Answer 11

一种方法是首先对列表进行排序。

我们可以就地对单词进行排序，而无需占用大量内存（以性能低下为代价）。

然后我们可以有一个简单的计数循环来查找频率最大的单词，而不必将所有内容保存在内存中，因为它们是排序形式的。

Answer 12

你的意思是大量的进程内存吗？ 如果是这样，一种方法是使用磁盘作为虚拟内存（也称为编写文件系统包装器）。