logo标签列表

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

javacount
4

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

有些人说可以使用Map<String, Integer>()来完成这个任务，但我想知道如何确定关键词。每篇文章都有不同的单词，如何确定“关键”单词并将其计数加一？

你说的“key”关键字是什么意思？ - Vincent Beltman
你文本中的单词可以作为一个HashMap的键，包含键和计数。例如：HashMap<String, Integer>()。 - mreiterer
1
也许你可以使用专门的文本搜索引擎，比如 Lucene 来构建索引，并获取例如 High Frequency Terms。 - Xavi López
6个回答
7
这是另一种使用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. 将byte[]转换为字符串：new String(Files.readAllBytes(file), StandardCharsets.UTF_8)，假设文件是UTF8编码。根据需要进行更改。代价是对已经存在于内存中的巨大数据进行完全的内存复制。可能使用内存映射文件会更快。
  3. 字符串按非单词字符拆分：...split("\\W+")，这将创建一个包含所有单词的字符串数组。
  4. 我们从该数组中创建一个流：Arrays.stream(...)。这本身并没有做太多事情，但我们可以在流中进行许多有趣的操作。
  5. 我们将所有单词分组：Collectors.groupingBy(Function.<String>identity(), TreeMap::new, counting())。这意味着：
    • 我们要根据单词本身（identity()）将单词分组。如果您想使分组不区分大小写，也可以在此处先将字符串转换为小写。这将成为映射中的键。
    • 作为存储分组值的结果，我们想要一个TreeMap（TreeMap::new）。TreeMaps按其键进行排序，因此最终可以轻松地按字母顺序输出。如果您不需要排序，则也可以在此处使用HashMap。
    • 作为每个组的值，我们希望有每个单词出现的次数（counting()）。在背景中，这意味着对于我们添加到组中的每个单词，我们都将计数器增加1。
  6. 从第5步我们得到了一个将单词映射到它们计数的Map。现在我们只需要将它们打印出来。我们访问包含此映射中所有键/值对的集合（.entrySet()）。
  7. 最后是实际的打印。我们说应该将每个元素传递给println方法：.forEach(System.out::println)。现在您就有了一个漂亮的列表。
这个答案有多好呢？优点是非常简短，因此高度表达。它只需要一个系统调用，隐藏在Files.readAllBytes后面（或者至少我不确定这是否真的可以使用单个系统调用），而系统调用可能成为瓶颈。例如，如果您从流中读取文件，每次读取都可能触发系统调用。使用缓冲区读取器可以显著减少这种情况，但仍然readAllBytes应该最快。代价是它消耗大量内存。然而，维基百科声称一个典型的英文书籍有500页，每页2,000个字符，总共约1兆字节，即使您使用智能手机、树莓派或非常老旧的计算机，内存消耗也不应该成为问题。
这个解决方案涉及一些在Java 8之前无法实现的优化。例如，习语map.put(word, map.get(word) + 1)要求在地图中查找“word”两次，这是一种不必要的浪费。

但是一个简单的循环可能更容易被编译器优化，可以节省一些方法调用。因此，我想知道并进行测试。我使用以下方式生成了一个文件：

[ -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%

请注意，我之前也尝试过使用TreeMaps进行测试，但发现即使我之后对输出进行排序，HashMaps仍然要快得多。此外，在Tagir Valeev在下面的评论中告诉我Pattern.splitAsStream()方法后，我也更改了上面的测试。由于结果强烈变化，我让测试运行了相当长的时间，正如您可以从上面的秒数长度中看到的那样，以获得有意义的结果。
我的判断标准：

  1. “混合”方法完全不使用流，但使用Java 8中引入的带有回调的“merge”方法确实提高了性能。这是我预料到的，因为经典的get/put方法需要在HashMap中查找键两次，而使用“merge”方法则不再需要。

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

  3. 总体上，流方法相当慢。这并不完全出乎意料，因为会发生相当多的方法调用，包括像Function.identity这样毫无意义的东西。但是我没有预料到差异如此之大。

作为有趣的附注，我发现混合方法是最快速且易于阅读和理解的。对于我来说，“merge”方法的调用不是最明显的效果，但如果你知道这个方法正在做什么，它似乎对我来说是最可读的，同时groupingBy命令对我来说更难理解。我猜可能会有人倾向于说，这种groupingBy非常特殊且高度优化，因此在性能方面使用它是有意义的，但正如这里所演示的那样，情况并非如此。
使用 Pattern.compile("\\W+").splitAsStream(new String(...)) 可以节省数组分配，从而可能提高解决方案的性能和/或内存占用。 - Tagir Valeev
@TagirValeev：我之前不知道这一点，现在深入研究了这种可能性。我对答案进行了大量修改，以更深入地探讨等方面。 - yankee
6
    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();

这里的计算会将“I'm”视为一个单词

如果您使用entrySet()来更改已经放入集合中的单词的计数，速度会（稍微）更快吗？我预计地图将三次查找next，以防它已经包含在内（1：contains()，2：get()，3：put()）。 - tgmath
1

这实际上是一个经典的单词计数算法。 以下是解决方案：

public Map<String, Integer> wordCount(String[] strings) {

  Map<String, Integer> map = new HashMap<String, Integer>();
  int count = 0;

  for (String s:strings) {

    if (map.containsKey(s)) {
      count = map.get(s);
      map.put(s, count + 1);
    } else {
        map.put(s, 1);
    }

  }
  return map;
}
0

步骤概述：

创建一个 HashMap<String, Integer>。 逐个单词读取文件。如果在你的 HashMap 中不存在该单词，则添加它并将计数值更改为 1。如果存在，则将值增加 1。一直读取到文件结尾。

这将导致所有单词及其每个单词的计数集合。

0

如果我是你，我会使用一个map<String, int>的实现，比如hashmap。然后当你遍历每个单词时，如果它已经存在，只需将int增加一，否则将其添加到map中。最后，您可以提取所有单词，或根据特定单词查询它以获取计数。

如果顺序对您很重要，您可以尝试使用SortedMap<String, int>以能够按字母顺序打印它们。

希望这有所帮助！

0

这是我的解决方案：

Map<String, Integer> map= new HashMap();
 int count=0;
 for(int i =0;i<strings.length;i++){
   for(int j=0;j<strings.length;j++){
      if(strings[i]==strings[j])
      count++;
 }map.put(strings[i],count);
 count=0;
 }return map;
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接