Rechercher un mot avec un nombre maximum d'occurrences - algorithme, trouver

Quel est le moyen le plus optimal (algorithme) de rechercher le mot ayant le nombre maximal d’occurrences dans un document?

Réponses:

Trouver le mot qui apparaît la plupart du temps dans un document peut être fait en O (n) par un simple histogramme [à base de hachage]:

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

C’est la solution O (n), et comme le problème est clairement oméga (n), elle est optimale en termes de grande notation O.

1. Numérisez le document une fois, en comptant le nombre de fois que vous avez vu chaque mot unique (peut-être en utilisant une table de hachage ou un arbre).
2. Tout en effectuant l’étape 1, gardez une trace du mot qui a le plus grand nombre de mots vus jusqu’à présent.