5

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

您如何使此操作占用更少的内存？有什么策略/解决方案？

-斯内哈尔

4

12 回答 12

5

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

光谱的另一端是看第一个单词，然后通读整本书，看看这个单词出现了多少次。这需要最少的内存。然后你对下一个单词做同样的事情并通读整本书。如果该单词出现更多次，则将其添加为顶部单词（或顶部 N 个单词）。当然，这是非常低效的——如果第一个词和第三个词相同，即使你只是对第一个词做了同样的事情，你最终还是会再次阅读整本书。

于 2009-04-12T18:19:45.243 回答
4

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

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

因此，只需为出现的最高哈希值创建一个位图。然后在单词的第二遍中，如果一个单词在位图中的哈希值“命中”，则查找它或将其添加到哈希表并增加其计数。这通过创建仅包含最高出现单词的哈希表来最小化内存使用量。

于 2009-04-12T18:27:26.490 回答
4

我是物理学家，所以我最喜欢的方法是近似。您无需阅读整个文本即可获得最常用的单词。反而：

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

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

注意：这确实假设最常见的单词确实在整个文本中出现的频率最高，而不仅仅是在文本中的一个地方。对于英文文本，这个假设是正确的，因为“the”等词的频率贯穿始终。如果您担心此要求，请要求算法至少完成整个文本的一遍。

于 2009-04-12T18:45:02.330 回答
4

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

如果文本是英文并且您只想找到前 5 个最常用的单词，那么这是您的程序：

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

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

于 2009-04-12T19:06:06.723 回答
3

如果性能真的无关紧要，您可以依次检查每个单词，检查它是否在您的“前 N 个”中，如果不是，计算所有出现的次数。这样你只存储 N 个值。当然，您会多次计算相同的单词，但是，正如您所说，性能不是问题 - 代码将是微不足道的（这通常是可取的 - 所有其他条件都相同）。

于 2009-04-12T18:10:32.707 回答
2

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

我们可以在没有大量内存的情况下对单词进行就地排序（以缓慢的性能进行交易）。

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

于 2009-04-12T18:07:35.413 回答
2

你的意思是很多进程内存？如果是这样，一种方法是将磁盘用作虚拟内存（也就是编写文件系统包装器）。

于 2009-04-12T18:07:42.480 回答
2

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

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

于 2009-04-12T18:21:40.513 回答
2

像许多好的面试问题一样，这个问题的措辞有点模棱两可/不准确，以迫使受访者提出澄清问题和陈述假设。我认为这里的许多其他答案都很好，因为它们戳穿了这些假设并展示了对全局的理解。

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

然后下面的 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]
于 2009-04-12T19:06:17.723 回答
1

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

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

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

于 2013-09-26T20:10:34.567 回答
0

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

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

于 2009-04-12T19:16:17.043 回答
0

如何创建一个单词键的二叉树（当您继续从文件中读取单词时）。这有助于在 O(Log(n)) 中搜索已经重复的单词。所以最后你得到了 O(nLog(n)) 的热门词搜索。

基本算法将是

对于文件中的每个单词：

  1. 为给定单词创建唯一键（加权 ascii char 例如“bat”可以是 1*'b' + 2*'a' + 3*'c';
  2. 将这个词添加到树中。如果单词已经存在，则增加新计数。
  3. 将单词和当前计数输入到maintainTop5(word, count)。维护Top5() 维护top5 计数和相关单词的动态列表。

文件末尾有前 5 个单词。

于 2012-02-09T07:40:30.513 回答