跟踪/计数字频率

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 行，并且表的小尺寸意味着它可以完全存储在内存中。将单词作为主键，查找速度会非常快。