Найти слово с максимальным количеством вхождений

Question

Каков наиболее оптимальный способ (алгоритм) поиска слова с максимальным числом вхождений в документе?

Answer 1

Нахождение слова, которое встречается в документе чаще всего, может быть выполнено в O (n) с помощью простой гистограммы [на основе хэша]:

histogram <- new map<String,int>
for each word in document: 
   if word in histogram:
      histogram[word] <- histogram[word] + 1
   else:
      histogram[word] <- 1
max <- 0
maxWord<- ""
for each word in histogram:
  if histogram[word] > max:
     max <- histogram[word]
     maxWord <- word
return maxWord

Это O (n), и поскольку проблема явно является проблемой Omega (n), она является оптимальной с точки зрения big O нотации .

Answer 2

1. Сканируйте документ один раз, сохраняя счет того, сколько раз вы видели каждое уникальное слово (возможно, для этого использовали хеш-таблицу или дерево).
2. Выполняя шаг 1, следите за словом, которое имеет наибольшее количество всех слов, которые когда-либо видели.