La méthode la plus efficace pour trouver les K mots les plus fréquents dans une grande séquence de mots

Question

Entrée : Un nombre entier positif K et un grand texte. Le texte peut en fait être considéré comme une séquence de mots. Nous n'avons donc pas à nous préoccuper de la manière de le décomposer en séquence de mots.
Sortie : Les K mots les plus fréquents dans le texte.

Mon raisonnement est le suivant.

1. utilise une table de hachage pour enregistrer la fréquence de tous les mots tout en parcourant l'ensemble de la séquence de mots. Dans cette phase, la clé est "mot" et la valeur est "fréquence des mots". Cette opération prend O(n) temps.

2. trier la paire (mot, fréquence des mots) ; la clé est "fréquence des mots". Cette opération prend O(n*lg(n)) avec un algorithme de tri normal.

3. Après le tri, nous ne retenons que les K premiers mots. Cela prend O(K) temps.

En résumé, le temps total est de O(n+n). lg(n)+K) Puisque K est sûrement plus petit que N, il s'agit en fait de O(n lg(n)).

Nous pouvons améliorer cela. En fait, nous ne voulons que les K premiers mots. La fréquence des autres mots ne nous intéresse pas. Nous pouvons donc utiliser le "tri partiel dans le tas". Pour les étapes 2) et 3), nous ne nous contentons pas de trier. Au lieu de cela, nous le modifions pour qu'il soit

2') construire un tas de paires (mot, fréquence des mots) avec "fréquence des mots" comme clé. La construction d'un tas prend O(n) temps ;

3') extraire les K premiers mots du tas. Chaque extraction est O(lg(n)). Le temps total est donc O(k*lg(n)).

En résumé, cette solution coûte O(n+k*lg(n)).

Ce n'est que mon avis. Je n'ai pas trouvé de moyen d'améliorer l'étape 1).
J'espère que des experts en recherche d'information pourront nous éclairer sur cette question.

Answer 1

Cette opération peut être réalisée en O(n) temps

Solution 1 :

Les étapes :

1. Compter les mots et les hacher, ce qui aboutira à la structure suivante

   var hash = {
     "I" : 13,
     "like" : 3,
     "meow" : 3,
     "geek" : 3,
     "burger" : 2,
     "cat" : 1,
     "foo" : 100,
     ...
     ...

2. Traverser le hachage et trouver le mot le plus fréquemment utilisé (dans ce cas "foo" 100), puis créer le tableau de cette taille

3. Ensuite, nous pouvons parcourir à nouveau le hachage et utiliser le nombre d'occurrences des mots comme index du tableau, s'il n'y a rien dans l'index, créer un tableau, sinon l'ajouter au tableau. Nous obtenons alors un tableau du type

     0   1      2            3                  100
   [[ ],[cat],[burger],[like, meow, geek],[]...[foo]]

4. Il suffit ensuite de parcourir le tableau à partir de la fin et de collecter les k mots.

Solution 2 :

Les étapes :

1. Idem que ci-dessus
2. Pour chaque mot du hachage, nous comparons les occurrences des mots avec la valeur minimale, 1) si elle est supérieure à la valeur minimale, nous supprimons la valeur minimale (si la taille du hachage minimal est égale à k) et nous insérons le nombre dans le hachage minimal. 2) reste des conditions simples.
3. Après avoir parcouru le tableau, nous convertissons simplement le min heap en tableau et renvoyons le tableau.

Answer 2

Vous n'obtiendrez pas une durée d'exécution généralement meilleure que la solution que vous avez décrite. Vous devez effectuer au moins O(n) pour évaluer tous les mots, puis O(k) supplémentaire pour trouver les k premiers termes.

Si votre problème est vraiment gros, vous pouvez utiliser une solution distribuée telle que map/reduce. Demandez à n travailleurs map de compter les fréquences sur 1/nth du texte chacun, et pour chaque mot, envoyez-le à l'un des m travailleurs reducer calculés sur la base du hachage du mot. Les réducteurs font ensuite la somme des comptages. Un tri par fusion sur les résultats des réducteurs vous donnera les mots les plus populaires par ordre de popularité.

Answer 3

Une petite variation de votre solution permet d'obtenir un O(n) si l'on ne se soucie pas de classer les K premiers, et un algorithme de O(n+k*lg(k)) solution si nous le faisons. Je pense que ces deux limites sont optimales à un facteur constant près.

L'optimisation intervient à nouveau après avoir parcouru la liste, en l'insérant dans la table de hachage. Nous pouvons utiliser la fonction médiane des médianes pour sélectionner le Kème élément le plus grand de la liste. Il est prouvé que cet algorithme est O(n).

Après avoir sélectionné le Kème élément le plus petit, nous partitionnons la liste autour de cet élément, comme dans le tri sélectif. Cette opération est évidemment aussi O(n). Tout ce qui se trouve du côté "gauche" du pivot fait partie de notre groupe de K éléments, et nous avons donc terminé (nous pouvons simplement jeter tout le reste au fur et à mesure).

Cette stratégie est donc la suivante :

1. Examinez chaque mot et insérez-le dans une table de hachage : O(n)
2. Sélectionner le Kème élément le plus petit : O(n)
3. Partition autour de cet élément : O(n)

Si vous souhaitez classer les K éléments, il suffit de les trier à l'aide d'un tri par comparaison efficace en O(k * lg(k)), ce qui donne un temps d'exécution total de O(n+k * lg(k)).

La limite de temps O(n) est optimale à un facteur constant près car nous devons examiner chaque mot au moins une fois.

La limite de temps O(n + k * lg(k)) est également optimale car il n'existe aucun moyen basé sur la comparaison pour trier k éléments en moins de k * lg(k) temps.

Answer 4

Si votre "liste de grands mots" est suffisamment importante, vous pouvez simplement échantillonner et obtenir des estimations. Dans le cas contraire, j'aime l'agrégation par hachage.

Editar :

Par échantillon, j'entends choisir un sous-ensemble de pages et calculer le mot le plus fréquent dans ces pages. Pour autant que vous sélectionniez les pages de manière raisonnable et que vous choisissiez un échantillon statistiquement significatif, vos estimations des mots les plus fréquents devraient être raisonnables.

Cette approche n'est vraiment raisonnable que si vous disposez d'une telle quantité de données qu'il est ridicule de les traiter toutes. Si vous ne disposez que de quelques mégaoctets, vous devriez être en mesure d'analyser les données et de calculer une réponse exacte sans vous casser la tête, plutôt que de prendre la peine de calculer une estimation.

Answer 5

Vous pouvez encore réduire le temps en partitionnant en utilisant la première lettre des mots, puis en partitionnant le plus grand ensemble de plusieurs mots en utilisant le caractère suivant jusqu'à ce que vous ayez k ensembles d'un seul mot. Vous utiliseriez une sorte d'arbre à 256 voies avec des listes de mots partiels/complets aux feuilles. Il faudrait faire très attention à ne pas provoquer des copies de chaînes de caractères partout.

Cet algorithme est O(m), où m est le nombre de caractères. Il évite de dépendre de k, ce qui est très bien pour les grands k [d'ailleurs, le temps d'exécution affiché est erroné, il devrait être O(n*lg(k)), et je ne suis pas sûr de ce que cela représente en termes de m].

Si vous exécutez les deux algorithmes côte à côte, vous obtiendrez ce qui, j'en suis presque sûr, est un algorithme O(min(m, n*lg(k)) asymptotiquement optimal, mais le mien devrait être plus rapide en moyenne parce qu'il n'implique pas de hachage ou de tri.