java最常用词

Question

在Java中，从文本中获取50个频率最高的单词的最有效方法是什么

我想搜索约1000000条文字，每条文字约10000字，并希望它能在合理的时间范围内工作

Answer 1

你最好的选择是O（n）算法，我会选择一个文本阅读器，它会拆分单词，然后将其添加到一个有序的树中，你会按出现的数量排序，并将它们链接到一个单词。之后，只需进行50次迭代遍历即可获得最高值

Answer 2

O(n)

1. 数一数单词的数量
2. 将文本按单词顺序拆分为单词列表
3. 创建word=>；发生次数
4. 遍历地图并选择“最大50”
5. 将它们除以单词总数，得到频率

当然，这些步骤中的一些可能是同时完成的，也可能是不必要的，具体取决于您将使用的数据结构

Answer 3

最有效的可能是使用链接到max-heap的Patricia trie。每次你读一个单词时，把它放在trie上，转到heap和increase-key。如果它不在trie中，那么add选择它并在堆中适当地设置它的密钥

用一个Fibonacci heap，increase-key就是O(1)

---

一个不太合理的解决方案是使用Map<String, Integer>，每次遇到一个单词时都添加计数，然后根据计数对其entrySet()进行自定义排序，以获得前50名

如果O(N log N)排序不可接受，请使用selection algorithm在O(N)中查找前50名

---

哪种技巧更好实际上取决于你的要求（也就是说，评论这是否更像是一个[algorithm]问题，而不是一个[java]问题很能说明问题）

紧跟着选择算法的Map<String, Integer>是最实用的，但Patricia trie解决方案显然仅在空间效率方面就优于它（因为公共前缀不会被冗余存储）

Answer 4

以下伪代码应该可以做到这一点：

build a map<word, count>
build a tokenizer that gives you a word per iteration
for each word*,
   if word in map, increment its count
   otherwise add with count = 1
sort words by count
for each of the first 50 words,
   output word, frequency = count / total_words

这本质上是O（N），也是jpabluz所建议的。然而，如果你打算在任何类型的“野生”文本中使用它，你会注意到大量垃圾：大写/小写、标点符号、URL、停止词，例如“the”或“and”，计数非常高，同一个单词的多个变体。。。正确的方法是将所有单词小写，删除所有标点符号（以及URL等内容），并在上述伪代码中用星号标记的点添加停止词删除和词干生成