跟踪/计算词频

Question

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

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

将存储以下值：

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

稍后能够快速查询给定任意单词的计数值。

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

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

Answer 1

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

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));

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

Answer 2

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

Answer 3

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

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

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

:)

Answer 4

使用哈希表。

Answer 5

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

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