java - 查找词频、最大词频和总词数的高效算法

Question

我正在尝试查找文件某个部分中出现的每个单词的频率以及该部分的总字数。 例如，如果有一个文件:file.txt:

This is a file section which is part of the file.
# This is another file section which is part of the same file separated by hash.

我希望以高效的方式找到每个词的频率，哪个词在每个部分中具有最大频率和总词数。这样:

In Section 1: This-1; is-2; a-1; file-2; section-1; which-1; part-1; of-1; the-1| Total Words: 11| Word having Maximum Frequency: is,file
In Section 2: This-1; is-2; another-1; file-2; section-1; which-1; part-1; of-1; the-1; same-1; by-1; hash-1;| Total Words:15| Words having Maximum Frequency: is,file

到目前为止，我想出了一个遍历每个单词的循环，增加总字数，然后将每个单词放入具有每个单词频率的键/值对中。我不知道最大频率。有没有我可以尝试使用的有效算法？

我希望在 Java 中这样做。因此，我正在考虑使用 HashMap，但欢迎任何更好的方法。

谢谢:)

Answer 1

您可以在更新每个单词时轻松跟踪当前的最大值。例如，每个部分的循环:

Initialize HashMap of Words
maxWord = null  // word with current max count
while not end of section
    get word
    if word in Words
        increment count of word in HashMap
    else
        add to Words with count of 1
    if maxWord == null || Words[word].Count > Words[maxWord].Count
        maxWord = word
end while

当您完成该部分的处理后，您将获得所有单词的频率，并且 maxWord 包含具有最大计数的单词。

整个算法是O(n)。您可以在一次文件传递中完成此操作。

不过，要简单得多，只需构建单词的 HashMap，然后在每个部分的末尾按顺序遍历它以选出具有最大计数的单词。这也被认为是 O(n)。