跟踪/计数字频率

我想获得一些社区对良好设计的一致意见，以便能够存储和查询单词频率计数。我正在构建一个应用程序，在该应用程序中，我必须解析文本输入并存储单词出现的次数（随着时间的推移）。因此，考虑以下输入：跟踪/计数字频率

“杀死一只小八哥”
“惩戒钢琴玩家”

将存储以下值：

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

和更高版本能够快速查询给定任意单词的计数值。

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

任何人都可以提出算法，或数据结构，或任何其他想法，可能会使这一表现良好的解决方案？

来源

2010-05-17 Joel Martinez

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

来源

2010-05-17 20:54:49

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

我不说这是的方式做到这一点，但它肯定的是选项，如果你需要的东西可以很好地扩展单个机器上可用内存的数量。只要你能够保持低于内存限制，更新散列表的简单循环应该能够做到。

来源

2010-05-17 20:54:40

使用hash table。

来源

2010-05-17 20:56:10

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

如果要提高性能并删除数据库，可以将这些单词编码为树状结构，并将使用计数存储在叶节点中。在本质上，如果你在单词文本上编制索引，数据库就是这么做的，所以你只能避免数据库延迟。如果这是目标，那么还有其他避免数据库延迟的方法，例如使用并行查找。

来源

2010-05-17 20:57:51 mdma

如果性能是您的主要目标，那么您只能在RAM中使用基于散列或基于树结构的结构。假设你做了一些有用的过滤（不要用非单词字符来统计术语），表中最大字数将在10⁶到10⁷的范围内（即使涉及多种语言），所以这很容易适合当前PC的内存（并完全避免所有的数据库处理）。另一方面，如果你必须自己实现散列表细节，那么你可以做的更多的代码是错误的（尽管数据库人员希望尽可能地调整他们的代码）。所以即使你自己实现的细节也可能导致性能再次下降。

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

来源

2010-05-17 21:30:51 Bananeweizen

跟踪/计数字频率

回答

相关问题