Эффективный алгоритм для поиска частоты слов, максимальной частоты слов и общего количества слов

Question

Я пытаюсь найти частоты каждого слова, встречающиеся в разделе файла, и общее количество слов этого раздела. Например, если есть файл: file.txt:

Это раздел файла, который является частью файла.
# Это еще один раздел файла, который является частью того же файла, разделенного хэшем.

Я хочу найти частоту каждого слова, слово которого имеет максимальную частоту и общее количество слов в каждом разделе эффективным образом. Такие, что:

В разделе 1: This-1; это-2; а-1; файл-2; секция 1; который 1; часть-1; из-1; -1 | Всего слов: 11 | Слово с максимальной частотой: есть, файл
В разделе 2: This-1; это-2; другое-1; файл-2; секция 1; который 1; часть-1; из-1; заместитель 1; же-1; по-1; Хэш-1; | Всего слов: 15 | Слова, имеющие максимальную частоту: есть, файл

До сих пор я придумал цикл, который проходит через каждое слово, увеличивает общее количество слов, а затем помещает каждое слово в пару с ключом/значением, имеющее частоту каждого слово. Я не знаю о максимальной частоте. Есть ли эффективный алгоритм, который я мог бы использовать?

Я хочу сделать это на Java. Итак, я думал об использовании HashMaps, но любой лучший подход приветствуется.

Спасибо :)

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). Вы можете сделать это за один проход файла.

Намного проще, однако, просто построить ваши слова и в конце каждого раздела последовательно пройти через него, чтобы выбрать тот, который имеет максимальное количество. Это тоже считается O (n).