8

我想就能够存储和查询词频计数的良好设计获得社区共识。我正在构建一个应用程序，我必须在其中解析文本输入并存储一个单词出现的次数（随着时间的推移）。所以给定以下输入：

  • 《杀死一只知更鸟》
  • “嘲笑钢琴演奏者”

将存储以下值：

Word    Count
-------------
To      1
Kill    1
A       2
Mocking 2
Bird    1
Piano   1
Player  1

并且以后能够快速查询给定任意词的计数值。

我目前的计划是简单地将单词和计数存储在数据库中，并依赖缓存单词计数值......但我怀疑我不会获得足够的缓存命中来使其成为长期可行的解决方案。

任何人都可以提出算法、数据结构或任何其他可能使其成为性能良好的解决方案的想法吗？

4

5 回答 5

6

字数统计是MapReduce程序的典型示例（来自 Wikipedia 的伪代码）：

void map(String name, String document):
  for each word w in document:
     EmitIntermediate(w, "1");

void reduce(String word, Iterator partialCounts):
  int result = 0;
  for each pc in partialCounts:
    result += ParseInt(pc);
  Emit(AsString(result));

我并不是说这是实现它的方法，但如果您需要在不同单词的数量超过单台机器上可用内存的情况下可以很好地扩展的东西，这绝对是一种选择。只要您能够保持在内存限制以下，更新哈希表的简单循环就可以解决问题。

于 2010-05-17T20:54:40.033 回答
3

我不明白你为什么觉得数据库不是一个合适的解决方案。您可能只有大约 100000 行，并且表的小尺寸意味着它可以完全存储在内存中。将单词设为主键，查找速度会非常快。

于 2010-05-17T20:54:49.240 回答
2

如果性能是您的主要目标，您可以仅在 RAM 中使用基于哈希或基于树的结构。假设您无论如何都做了一些有用的过滤（不计算非单词字符的术语），表中的最大单词数将在 10⁶ 到 10⁷ 的范围内（即使涉及多种语言），所以这很容易适合当前 PC 的内存（并完全避免所有数据库处理）。

另一方面，如果您必须自己实现哈希表的详细信息，那么您可能会做错更多的代码（而数据库人员希望将他们的代码调整到最大）。因此，即使您自己实现中的小细节也可能再次导致性能损失。

所以这个困境清楚地向我们展示了优化的第一条和第二条规则： 1. 不要过早优化。2. 在优化之前测量。

:)

于 2010-05-17T21:30:51.437 回答
1

使用哈希表。

于 2010-05-17T20:56:10.717 回答
1

你的解决方案听起来不错。如果缓存基于最近的使用计数，那么它将保存最常用单词的字数。（单词分布类似于前 100 个单词覆盖 90% 的单词实例），因此您不需要非常大的缓存。

如果要提高性能并删除数据库，可以将单词编码为 trie，并将使用计数存储在叶节点中。从本质上讲，如果您对单词文本进行索引，这就是数据库正在做的事情，因此您实际上只是在避免数据库延迟。如果这是目标，那么还有其他方法可以避免数据库延迟，例如使用并行查找。

于 2010-05-17T20:57:51.073 回答