如何统计每个单词的出现次数？

Question

如果我有英文文章或英文小说文章，并且想要计算每个单词出现的次数，用Java编写的最快算法是什么？

有人说你可以用Map < String，Integer>（）来完成这个，但我想知道怎么知道关键词是什么？每篇文章都有不同的单词，你如何知道“关键”单词，然后在其数量上添加一个单词？

Answer 1

Map<String, Integer> countByWords = new HashMap<String, Integer>(); 
    Scanner s = new Scanner(new File("your_file_path")); 
    while (s.hasNext()) { 
     String next = s.next(); 
     Integer count = countByWords.get(next); 
     if (count != null) { 
      countByWords.put(next, count + 1); 
     } else { 
      countByWords.put(next, 1); 
     } 
    } 
    s.close(); 

这个数“我”因为只有一个字

Answer 2

的步骤总体概述：

创建HashMap<String, Integer> 阅读文件一个字的时间。如果它不存在于您的HashMap中，请添加它并将计数值更改为1.如果存在，请将该值增加1.读取直至文件结束。

这将导致一组所有单词和每个单词的计数。

Answer 3

如果我是你，我会使用map<String, int>的一个实现，如散列图。然后，如果已经存在每个单词，则循环遍历整个单词，否则将其添加到地图中。最后，您可以提取所有单词，或者根据特定单词查询该单词以获得计数。

如果订单对您很重要，您可以尝试SortedMap<String, int>以便按字母顺序排列。

希望有帮助！

Answer 4

这里是另一种方式与出现在Java中8要做的事情是：

private void countWords(final Path file) throws IOException { 
    Arrays.stream(new String(Files.readAllBytes(file), StandardCharsets.UTF_8).split("\\W+")) 
     .collect(Collectors.groupingBy(Function.<String>identity(), TreeMap::new, counting())).entrySet() 
     .forEach(System.out::println); 
} 

那么是什么做？

1. 它将文本文件完全读入内存，更精确地写入字节数组：Files.readAllBytes(file)。这种方法在Java 7中出现，并且允许非常快速地加载文件的方法，但是对于文件将完全存储在内存中的代价，会花费大量内存。对于速度而言，这是一个很好的评价。
2. 将字节[]转换为字符串：new String(Files.readAllBytes(file), StandardCharsets.UTF_8)，同时假定该文件是UTF8编码的。根据自己的需要进行更改。价格是内存中已有巨大数据的完整内存拷贝。它可能改为使用内存映射文件。
3. 该字符串被拆分为非Word字符串：...split("\\W+")，它会创建一个包含所有单词的字符串数组。
4. 我们从该阵列创建一个流：Arrays.stream(...)。这本身并不是很多，但我们可以用流
5. 做很多有趣的事情我们将所有单词组合在一起：Collectors.groupingBy(Function.<String>identity(), TreeMap::new, counting())。这意味着：
   • 我们希望通过单词本身对单词进行分组（identity()）。我们也可以例如如果您希望分组不区分大小写，请首先在此处输入字符串。这将最终成为地图中的关键。
   • 作为存储分组值的结果，我们需要一个TreeMap（TreeMap::new）。TreeMaps按键排序，因此我们可以按字母顺序轻松输出。如果你不需要排序，你也可以在这里使用HashMap。
   • 作为每个组的价值，我们希望每个词的出现次数（counting()）。在背景中，这意味着对于我们添加到组中的每个单词，我们增加一个计数器。
6. 从第5步开始，我们剩下一个地图，将单词映射到他们的计数。现在我们只想打印它们。因此，我们访问此地图中所有键/值对的集合（.entrySet()）。
7. 最后实际打印。我们说每个元素都应该传递给println方法：.forEach(System.out::println)。现在你留下了一个不错的名单。

那么这个答案有多好？好处是非常短暂，因此具有很强的表现力。它也只与一个隐藏在Files.readAllBytes之后的系统调用相关（或者至少是一个固定的数字，我不确定这是否真的可以在单个系统调用中工作），系统调用可能是一个瓶颈。例如。如果您正在从流中读取文件，则每个要读取的呼叫都可能触发系统调用。这通过使用名称为缓冲区的BufferedReader显着减少。但stilly readAllBytes应该是最快的。这样做的代价是它消耗了大量的内存。然而，维基百科宣称，一本典型的英文书籍有500 pages with 2,000 characters per page which mean roughly 1 Megabyte，即使您使用的是智能手机，树莓派或真正旧的计算机，在内存消耗方面也不应该存在问题。

这个解决方案确实涉及到一些在Java 8之前不可能的优化。例如，成语map.put(word, map.get(word) + 1)要求在地图中查找“单词”，这是一种不必要的浪费。

但是，一个简单的循环可能更容易优化编译器，并可能节省大量的方法调用。所以我想知道，并把这个测试。我生成使用文件：

[ -f /tmp/random.txt ] && rm /tmp/random.txt; for i in {1..15}; do head -n 10000 /usr/share/dict/american-english >> /tmp/random.txt; done; perl -MList::Util -e 'print List::Util::shuffle <>' /tmp/random.txt > /tmp/random.tmp; mv /tmp/random.tmp /tmp/random.txt 

这给了我大约1,3MB文件，所以不就是非典型的一本书大部分的话被重复15次，但在随机为了规避这个目的达到成为分支预测测试。然后，我跑到了以下测试：

public class WordCountTest { 

    @Test(dataProvider = "provide_description_testMethod") 
    public void test(String description, TestMethod testMethod) throws Exception { 
     long start = System.currentTimeMillis(); 
     for (int i = 0; i < 100_000; i++) { 
      testMethod.run(); 
     } 
     System.out.println(description + " took " + (System.currentTimeMillis() - start)/1000d + "s"); 
    } 

    @DataProvider 
    public Object[][] provide_description_testMethod() { 
     Path path = Paths.get("/tmp/random.txt"); 
     return new Object[][]{ 
      {"classic", (TestMethod)() -> countWordsClassic(path)}, 
      {"mixed", (TestMethod)() -> countWordsMixed(path)}, 
      {"mixed2", (TestMethod)() -> countWordsMixed2(path)}, 
      {"stream", (TestMethod)() -> countWordsStream(path)}, 
      {"stream2", (TestMethod)() -> countWordsStream2(path)}, 
     }; 
    } 

    private void countWordsClassic(final Path path) throws IOException { 
     final Map<String, Integer> wordCounts = new HashMap<>(); 
     for (String word : new String(readAllBytes(path), StandardCharsets.UTF_8).split("\\W+")) { 
      Integer oldCount = wordCounts.get(word); 
      if (oldCount == null) { 
       wordCounts.put(word, 1); 
      } else { 
       wordCounts.put(word, oldCount + 1); 
      } 
     } 
    } 

    private void countWordsMixed(final Path path) throws IOException { 
     final Map<String, Integer> wordCounts = new HashMap<>(); 
     for (String word : new String(readAllBytes(path), StandardCharsets.UTF_8).split("\\W+")) { 
      wordCounts.merge(word, 1, (key, oldCount) -> oldCount + 1); 
     } 
    } 

    private void countWordsMixed2(final Path path) throws IOException { 
     final Map<String, Integer> wordCounts = new HashMap<>(); 
     Pattern.compile("\\W+") 
      .splitAsStream(new String(readAllBytes(path), StandardCharsets.UTF_8)) 
      .forEach(word -> wordCounts.merge(word, 1, (key, oldCount) -> oldCount + 1)); 
    } 

    private void countWordsStream2(final Path tmpFile) throws IOException { 
     Pattern.compile("\\W+").splitAsStream(new String(readAllBytes(tmpFile), StandardCharsets.UTF_8)) 
      .collect(Collectors.groupingBy(Function.<String>identity(), HashMap::new, counting())); 
    } 

    private void countWordsStream(final Path tmpFile) throws IOException { 
     Arrays.stream(new String(readAllBytes(tmpFile), StandardCharsets.UTF_8).split("\\W+")) 
      .collect(Collectors.groupingBy(Function.<String>identity(), HashMap::new, counting())); 
    } 

    interface TestMethod { 
     void run() throws Exception; 
    } 
} 

结果是：

type length diff 
classic 4665s +9% 
mixed 4273s +0% 
mixed2 4833s +13% 
stream 4868s +14% 
stream2 5070s +19% 

注意，我以前也有树状图进行测试，却发现包含HashMap是要快得多，即使我排序的输出之后。在Tagir Valeev在下面关于Pattern.splitAsStream()方法的评论中告诉我时，我还更改了上述测试。由于我得到的结果差异很大，因此我将测试运行了很长一段时间，正如您可以看到上面的秒数，以获得有意义的结果。

我怎么判断的结果：

1. “混合”的做法，完全不使用流，但使用在Java 8中引入并改进性能回调“合并”的方法。这是我期望的，因为经典的get/put appraoch需要在HashMap中查找两次密钥，并且这对于“合并”方法不再需要。

2. 令我惊讶的是Pattern.splitAsStream() appraoch实际上比Arrays.asStream(....split())慢。我看过两种实现的源代码，我注意到调用split()将结果保存在一个ArrayList中，该ArrayList的大小为零，并根据需要进行放大。这需要许多复制操作，最后需要另一个复制操作来将ArrayList复制到数组中。但是“splitAsStream”实际上创建了一个我认为可以根据需要查询的迭代器，完全避免了这些复制操作。我没有仔细查看将迭代器转换为流对象的所有源代码，但它看起来很慢，我不知道为什么。最后，它理论上可能与CPU内存缓存有关：如果完全相同的代码一遍又一遍地执行，代码将更可能在缓存中，然后实际上在大型函数链上运行，但这是一个非常疯狂的猜测我这边。它也可能是完全不同的东西。然而splitAsStream可能有更好的内存占用，也许它没有，我没有分析。

3. 一般流的方法是相当缓慢的。这并不完全出乎意料，因为相当多的方法调用发生，包括例如像Function.identity那样毫无意义的事情。不过，我并没有预料到在这么大的差别。

作为一个有趣的方面说明，我发现最快的混合方法阅读和理解。对“合并”的调用对我来说并不是最具影响力的，但如果你知道这个方法正在做什么，它似乎对我来说是最易读的，同时groupingBy命令对我来说更难以理解。我想有人可能会说，这个groupingBy是如此特别和高度优化，它是有道理的使用它的性能，但如这里演示，情况并非如此。