0

假设我需要计算一个非常大的文件中的单词（单词被 " " 分割）

我会做以下

  1. 不在内存中加载整个文件，逐行读取流。
  2. 对于每一行拆分单词并将不同的单词添加到“字典”（我的意思是，在 .NET 中使用 Dictionary 类）及其计数。

现在要检索最常用的单词，对字典进行排序并获取它。

但是大多数解决方案都是对此有利的 Trie 数据结构，请说明原因（另外，如果不说明字典上的哈希表的原因，那就太好了）。

谢谢。

4

2 回答 2

1

我不禁要提到，这不仅是 map-reduce 问题，还是map -reduce 问题。

除此之外，您使用 trie 实现的原因是为了提高查找每个单词以增加其计数的效率（或添加一个在 trie 中尚不存在的单词）。在基本的 trie 中，每个单词的查找时间是O(n)，其中n是单词中的字符数。在整个文档中，如果没有并行处理，您将只查看O(n)时间以进行查找，其中n是文档中的字符数。然后，将（可能）进行深度优先搜索以检索所有单词，以便您可以提取所需的信息。深度优先搜索的最坏情况性能是相同的O(n)，但由于公共前缀，预期情况会更好。

如果您使用涉及散列查找的不同结构（例如标准System.Collections.Generic.Dictionary<TKey, TValue>），则成本与散列查找和实现以及散列冲突的普遍性有关。然而，即使这可能不是成本的主要部分。假设arguendo哈希查找是恒定时间的且微不足道的。因为相等的哈希码不能保证相等的字符串，正如 MSDN 文档反复警告的那样，仍然需要比较字符串是否相等，这几乎可以肯定实现为O(n)，其中n是字符数（为简单起见）。因此，根据 trie 和一些基于哈希查找的字典的实现，基于哈希查找的字典可能并不比 trie 好，而且可能更糟。

对我的分析的一个有效批评可能是对 trie 中每个节点的查找可能不是恒定时间的。这将取决于用于确定后续节点边缘的集合。但是，如果我们不关心稍后对键进行排序，则基于哈希查找的字典可能会在这里工作得很好。当输入是一个字符时，哈希冲突不太可能发生，并且与完整字符串相比，相等比较涉及的内容要少得多。插入性能也可能是合理的，同样取决于实现。

但是，如果您知道要n通过字数来确定排名靠前的单词，那么除了在 trie 中跟踪它们之外，您可能还需要随时跟踪排名靠前的n字数。这样，您不需要在填充 trie 后重新计算顶部。n

于 2014-09-02T04:07:12.270 回答
0

您可以使用File.ReadLines它类似于流阅读器。

var mostFrequent = File.ReadLines("Path")
    .SelectMany(l => l.Split()) // splits also by tabs
    .GroupBy(word => word)
    .OrderByDescending(g => g.Count())
    .First(); // or Take(10) if you want the top 10

Console.Write("Word:{0} Count:{1}", mostFrequent.Key, mostFrequent.Count());
于 2014-09-01T22:15:00.163 回答