Concevoir un algorithme, trouver le mot le plus fréquemment utilisé dans un livre

Question

Une question d'entrevue:

Trouvez le mot le plus fréquemment utilisé dans un livre.

Mon idée:

Utilisez une table de hachage, traverse et marquer la table de hachage.

Si la taille du livre est connue, si un mot est utilisé> 50%, ignorez les nouveaux mots de la traversée suivante et ne comptez que les mots anciens. Que faire si la taille du livre est inconnue?

Il s'agit du temps et de l'espace O (n) et O (n).

De meilleures idées?

Merci

Answer 1

Habituellement Heap est la structure de données qui convient bien quand nous devons déterminer quelque chose comme plus/moins utilisé.

Même Python;s Counter.nlargest qui est utilisé à ces fins est mis en œuvre via la structure de données de tas.

Binary Heap structure de données a la complexité suivante

CreateHeap - O(1) 
FindMin - O(1) 
deleteMin - O(logn) 
Insert - O(logn) 

J'ai couru un comparition sur Hash (en utilisant le dictionnaire par défaut en Python) et Heap (en utilisant Collections.Counter.nlargest en python) et le Hash est carénage légèrement mieux que Heap.

>>> stmt1=""" 
import collections, random 
somedata=[random.randint(1,1000) for i in xrange(1,10000)] 
somehash=collections.defaultdict(int) 
for d in somedata: 
    somehash[d]+=1 
maxkey=0 
for k,v in somehash.items(): 
    if somehash[maxkey] > v: 
     maxkey=k 
""" 
>>> stmt2=""" 
import collections,random 
somedata=[random.randint(1,1000) for i in xrange(1,10000)] 
collections.Counter(somedata).most_common(1) 
""" 
>>> t1=timeit.Timer(stmt=stmt1) 
>>> t2=timeit.Timer(stmt=stmt2) 
>>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=10)/10) 
38168.96 usec/pass 
>>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=10)/10) 
33600.80 usec/pass 

Answer 2

Il y a une généralisation de votre Optimization si la taille du livre est connu et tout mot que vous avez vu a un compte> le nombre restant de mots + Le décompte suivant le plus élevé, votre mot le plus élevé de comptage en cours est la réponse.

Answer 3

Pour déterminer la complexité, je pense que vous devez considérer deux variables, n = nombre total de mots, m = nombre de mots uniques. J'imagine que la complexité du meilleur cas sera proche de O (n log (m)) pour la vitesse, et O (m) pour le stockage, en supposant chaque fois que vous itérez sur n mots, et construisez et recherchez basé sur une table de hachage ou une autre structure de ce type qui contient éventuellement m éléments.

Answer 4

Votre solution est correcte, rapide et probablement la meilleure/la plus facile d'un point de vue pratique.

Les solutions de l'autre affiche présentent des complexités temporelles plus importantes que votre solution. Pour un hachage, comme vous l'utilisez, la complexité temporelle est en effet O (n). Chaque insertion est O (1) et il y a n mots, donc la phase d'insertion coûte O (n). Itérer à travers et trouver le maximum est alors O (n). L'espace est également O (n) comme vous l'avez mentionné. Notez que vous ne pourrez pas terminer votre algorithme plus tôt en utilisant la solution de Chris car la recherche dans votre table de hachage est coûteuse et vous n'avez aucun moyen de l'effectuer en O (1) après chaque insertion.

Un tas coûtera plus cher dans le temps car vous devez maintenir le tas pendant chaque insertion. Une insertion de segment est O (log (n)) et donc le coût total d'insertion sera O (nlog (n)).

Answer 5

Ceci est en fait un exemple classique de map reduce.L'exemple dans la page wikipedia vous donnera le nombre de mots de chaque mot unique, mais vous pouvez facilement ajouter une étape dans l'étape de réduction qui garde la trace du mot courant le plus courant (avec une sorte de mutex à traiter problèmes de concurrence).

Si vous disposez d'un cluster distribué de machines ou d'un ordinateur hautement parallélisé, cela fonctionnera beaucoup plus rapidement qu'avec la table de hachage.

Answer 6

Si vous avez affaire à un livre, alors vous connaissez le vocabulaire et les fréquences approximatives des mots. Même si vous ne recevez pas cette information à l'avance, vous pouvez obtenir une bonne estimation en scannant un échantillon aléatoire.

Pour la réponse exacte, j'utiliserais une fonction de hachage parfaite des k mots les plus courants. Une fonction de hachage parfaite requiert une mémoire O (k) et garantit une recherche O (1) dans le pire des cas.

Pour les mots peu courants, j'utiliserais une file d'attente prioritaire implémentée comme un tas ou un arbre auto-équilibré. Une table de hachage régulière pourrait également être un bon choix.