代码之家 › 专栏 › 技术社区 › Joel Martinez

跟踪/计数字频率

word-frequency indexing algorithm

Joel Martinez · 技术社区 · 15 年前

我想就一个好的设计获得一些社区共识,以便能够存储和查询单词频率计数。我正在构建一个应用程序,在这个应用程序中,我必须解析文本输入并存储一个单词出现的次数(随着时间的推移)。因此,考虑到以下输入:

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

将存储以下值:

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

以后可以快速查询给定任意字的计数值。

我目前的计划是简单地将单词和计数存储在数据库中,并依赖于缓存单词计数值…但我怀疑,我无法获得足够的缓存命中率来使这成为一个长期可行的解决方案。

有人能提出算法、数据结构或其他任何可能使这成为一个性能良好的解决方案的想法吗?

5 回复 | 直到 11 年前

Mark Byers 15 年前

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

Jørn Schou-Rode dscher 15 年前

字数统计是 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));

我是不说这是这个这样做的方法,但如果您需要一些扩展性很好的东西,当不同的单词的数量超过了一台机器上可用的内存时,它绝对是一个选项。只要您能够保持在内存限制以下,更新哈希表的简单循环就可以做到这一点。

Bananeweizen 15 年前

如果性能是您的主要目标,那么您只能在RAM中使用基于哈希或基于trie的结构。假设您仍然进行一些有用的筛选(不计算非字词字符的字词),则表中的最大字数将在10到10的范围内(即使涉及多种语言),因此这很容易放入当前PC的内存中(并完全避免所有数据库处理)。

另一方面,如果您必须自己实现哈希表的详细信息,那么就有更多的代码可以出错(尽管数据库人员希望将代码调整到最大)。因此,即使在您自己的实现中有一些小细节,也可能再次导致性能损失。

因此,这一困境清楚地向我们展示了优化的第一条和第二条规则: 1。不要过早优化。 2。在优化之前测量。

BlueRaja - Danny Pflughoeft 15 年前

使用A hash table .

mdma 15 年前

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

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