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

Supposons que nous ayons une séquence de mots "ad" "ad" "boy" "big" "bad" "com" "come" "cold". Et K=2. comme vous l'avez mentionné "partitionnement en utilisant la première lettre des mots", nous obtenons ("ad", "ad") ("boy", "big", "bad") ("com" "come" "cold") "puis partitionner le plus grand ensemble de plusieurs mots en utilisant le caractère suivant jusqu'à ce que vous ayez k ensembles d'un seul mot". il partitionnera ("boy", "big", "bad") ("com" "come" "cold"), la première partition ("ad", "ad") est manquée, alors que "ad" est en fait le mot le plus fréquent.

Peut-être ai-je mal compris votre point de vue. Pouvez-vous détailler votre processus de partition ?

Answer 2

Je pense que ce problème peut être résolu par un algorithme O(n). Nous pourrions effectuer le tri à la volée. En d'autres termes, le tri dans ce cas est un sous-problème du problème de tri traditionnel puisqu'un seul compteur est incrémenté d'une unité à chaque fois que nous accédons à la table de hachage. Au départ, la liste est triée puisque tous les compteurs sont à zéro. Au fur et à mesure que nous incrémentons les compteurs dans la table de hachage, nous conservons un autre tableau de valeurs de hachage ordonnées par fréquence comme suit. Chaque fois que nous incrémentons un compteur, nous vérifions son index dans le tableau classé et nous vérifions si son nombre dépasse celui de son prédécesseur dans la liste. Si c'est le cas, nous échangeons ces deux éléments. Nous obtenons ainsi une solution qui est au plus O(n), où n est le nombre de mots dans le texte original.

Answer 3

Je me débattais aussi avec cela et j'ai été inspiré par @aly. Au lieu de trier après coup, nous pouvons simplement maintenir une liste pré-triée de mots ( List<Set<String>> ) et le mot sera dans l'ensemble à la position X où X est le nombre actuel du mot. En général, voici comment cela fonctionne :

1. pour chaque mot, le stocker en tant que partie de la carte de son occurrence : Map<String, Integer> .
2. puis, en fonction du comptage, le retirer de l'ensemble de comptage précédent et l'ajouter au nouvel ensemble de comptage.

L'inconvénient de cette méthode est que la liste peut être volumineuse - elle peut être optimisée par l'utilisation d'une fonction TreeMap<Integer, Set<String>> - mais cela entraînera des frais généraux supplémentaires. En fin de compte, nous pouvons utiliser un mélange de HashMap ou notre propre structure de données.

Le code

public class WordFrequencyCounter {
    private static final int WORD_SEPARATOR_MAX = 32; // UNICODE 0000-001F: control chars
    Map<String, MutableCounter> counters = new HashMap<String, MutableCounter>();
    List<Set<String>> reverseCounters = new ArrayList<Set<String>>();

    private static class MutableCounter {
        int i = 1;
    }

    public List<String> countMostFrequentWords(String text, int max) {
        int lastPosition = 0;
        int length = text.length();
        for (int i = 0; i < length; i++) {
            char c = text.charAt(i);
            if (c <= WORD_SEPARATOR_MAX) {
                if (i != lastPosition) {
                    String word = text.substring(lastPosition, i);
                    MutableCounter counter = counters.get(word);
                    if (counter == null) {
                        counter = new MutableCounter();
                        counters.put(word, counter);
                    } else {
                        Set<String> strings = reverseCounters.get(counter.i);
                        strings.remove(word);
                        counter.i ++;
                    }
                    addToReverseLookup(counter.i, word);
                }
                lastPosition = i + 1;
            }
        }

        List<String> ret = new ArrayList<String>();
        int count = 0;
        for (int i = reverseCounters.size() - 1; i >= 0; i--) {
            Set<String> strings = reverseCounters.get(i);
            for (String s : strings) {
                ret.add(s);
                System.out.print(s + ":" + i);
                count++;
                if (count == max) break;
            }
            if (count == max) break;
        }
        return ret;
    }

    private void addToReverseLookup(int count, String word) {
        while (count >= reverseCounters.size()) {
            reverseCounters.add(new HashSet<String>());
        }
        Set<String> strings = reverseCounters.get(count);
        strings.add(word);
    }

}

Answer 4

Je viens de découvrir l'autre solution à ce problème. Mais je ne suis pas sûr qu'elle soit correcte. Solution :

1. Utiliser une table de hachage pour enregistrer la fréquence de tous les mots T(n) = O(n)
2. Choisir les k premiers éléments de la table de hachage et les restituer dans un tampon (dont l'espace = k). T(n) = O(k)
3. À chaque fois, il faut d'abord trouver l'élément min actuel de la mémoire tampon, puis comparer l'élément min de la mémoire tampon avec les (n - k) éléments de la table de hachage, un par un. Si l'élément de la table de hachage est supérieur à l'élément min de la mémoire tampon, il faut abandonner l'élément min de la mémoire tampon et ajouter l'élément de la table de hachage. Ainsi, à chaque fois que nous trouvons l'élément min de la mémoire tampon, il faut T(n) = O(k), et parcourir l'ensemble de la table de hachage nécessite T(n) = O(n - k). La complexité temporelle totale de ce processus est donc T(n) = O((n-k) * k).
4. Après avoir parcouru toute la table de hachage, le résultat se trouve dans ce tampon.
5. Toute la complexité du temps : T(n) = O(n) + O(k) + O(kn - k^2) = O(kn + n - k^2 + k). Puisque, en général, k est vraiment plus petit que n. Pour cette solution, la complexité temporelle est donc T(n) = O(kn) . C'est un temps linéaire, lorsque k est très petit. Est-ce exact ? Je n'en suis pas sûr.

Answer 5

Essayez d'imaginer une structure de données spéciale pour aborder ce type de problèmes. Dans le cas présent, il s'agit d'un type d'arbre spécial, comme la trie, qui permet de stocker les chaînes de caractères d'une manière spécifique, très efficace. Ou alors, construisez votre propre solution en comptant les mots. Je suppose que ce TB de données serait en anglais alors nous avons environ 600,000 mots en général donc il sera possible de stocker seulement ces mots et de compter les chaînes qui se répètent + cette solution nécessitera une regex pour éliminer certains caractères spéciaux. La première solution sera plus rapide, j'en suis presque sûr.

http://en.wikipedia.org/wiki/Trie