algorithm - 使用词频生成“顶级列表”的算法

Question

我收集了大量人工生成的内容。我想找到最常出现的单词或短语。什么是有效的方法来做到这一点？

Answer 1

不要重新发明轮子。使用全文搜索引擎，例如Lucene。

Answer 2

简单/天真的方法是使用哈希表。遍历单词并在进行时增加计数。

在该过程结束时，按计数对键/值对进行排序。

Answer 3

基本思想很简单——在可执行的伪代码中，

from collections import defaultdict

def process(words):
  d = defaultdict(int)
  for w in words: d[w] += 1
  return d

当然，魔鬼在细节中——如何将大集合变成产生单词的迭代器？它是否足够大以至于您不能在单台机器上处理它，而是需要一个 mapreduce 方法，例如通过 hadoop？等等，等等 。NLTK可以在语言方面提供帮助（在语言中隔离单词，它们不能完全分开）。

在单机执行（不包括 mapreduce）上，可能出现的一个问题是，这个简单的想法会给您提供太多的单例或类似情况（单词出现一次或仅出现几次），这会填满内存。对此的概率反驳是进行两次遍历：一次随机采样（仅获得十个单词中的一个，或一百个中的一个）以生成一组候选单词作为最高排名，然后第二次遍历跳过那些不在候选集中。根据您要采样的单词数量以及结果中需要的单词数量，可以通过这种方式计算您错过重要单词的概率的上限（对于合理的数字，以及任何自然语言） ，我向你保证，你会没事的）。

一旦您的字典将单词映射到出现次数，您只需要按出现次数选择前 N 个单词 - 如果字典太大而无法按全部出现次数排序（例如在我的最喜欢的可执行伪代码，例如 heapq.nlargest 会这样做）。

Answer 4

研究Apriori 算法。它可用于查找频繁项和/或频繁项集。

就像维基百科文章所述，有更有效的算法可以做同样的事情，但这可能是一个很好的开始，看看这是否适用于您的情况。

Answer 5

也许您可以尝试使用PATRICIA trie 或实用算法来检索以字母数字 trie 编码的信息？

Answer 6

为什么不使用键作为单词，计数器作为值的简单映射。通过采用高值计数器，它将给出最常用的单词。这只是一个 O(N) 操作。