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

Il y a un bug dans votre description : Le comptage prend O(n) temps, mais le tri prend O(m*lg(m)), où m est le nombre d'objets à trier. unique mots. Ce nombre est généralement beaucoup plus petit que le nombre total de mots, de sorte qu'il convient probablement d'optimiser la façon dont le hachage est construit.

Answer 2

Votre problème est le même que celui-ci http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/

Utilisez Trie et min heap pour le résoudre efficacement.

Answer 3

Si ce que vous cherchez est la liste des k les mots les plus fréquents dans votre texte pour toute k et pour toute langue naturelle, la complexité de votre algorithme n'est pas pertinente.

Juste échantillon disons, quelques millions de mots de votre texte, traitez-les avec n'importe quel algorithme en quelques secondes et les comptages les plus fréquents seront très précis.

Soit dit en passant, la complexité de l'algorithme fictif (1. compter tout 2. trier les comptes 3. prendre le meilleur) est O(n+m*log(m)), où m est le nombre de mots différents dans votre texte. log(m) est beaucoup plus petit que (n/m), donc il reste O(n).

En pratique, la longue étape consiste à compter.

Answer 4

1. Utiliser une structure de données efficace en termes de mémoire pour stocker les mots
2. Utilisez MaxHeap, pour trouver les K mots les plus fréquents.

Voici le code

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

import com.nadeem.app.dsa.adt.Trie;
import com.nadeem.app.dsa.adt.Trie.TrieEntry;
import com.nadeem.app.dsa.adt.impl.TrieImpl;

public class TopKFrequentItems {

private int maxSize;

private Trie trie = new TrieImpl();
private PriorityQueue<TrieEntry> maxHeap;

public TopKFrequentItems(int k) {
    this.maxSize = k;
    this.maxHeap = new PriorityQueue<TrieEntry>(k, maxHeapComparator());
}

private Comparator<TrieEntry> maxHeapComparator() {
    return new Comparator<TrieEntry>() {
        @Override
        public int compare(TrieEntry o1, TrieEntry o2) {
            return o1.frequency - o2.frequency;
        }           
    };
}

public void add(String word) {
    this.trie.insert(word);
}

public List<TopK> getItems() {

    for (TrieEntry trieEntry : this.trie.getAll()) {
        if (this.maxHeap.size() < this.maxSize) {
            this.maxHeap.add(trieEntry);
        } else if (this.maxHeap.peek().frequency < trieEntry.frequency) {
            this.maxHeap.remove();
            this.maxHeap.add(trieEntry);
        }
    }
    List<TopK> result = new ArrayList<TopK>();
    for (TrieEntry entry : this.maxHeap) {
        result.add(new TopK(entry));
    }       
    return result;
}

public static class TopK {
    public String item;
    public int frequency;

    public TopK(String item, int frequency) {
        this.item = item;
        this.frequency = frequency;
    }
    public TopK(TrieEntry entry) {
        this(entry.word, entry.frequency);
    }
    @Override
    public String toString() {
        return String.format("TopK [item=%s, frequency=%s]", item, frequency);
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + frequency;
        result = prime * result + ((item == null) ? 0 : item.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        TopK other = (TopK) obj;
        if (frequency != other.frequency)
            return false;
        if (item == null) {
            if (other.item != null)
                return false;
        } else if (!item.equals(other.item))
            return false;
        return true;
    }

}   

}

Voici les tests unitaires

@Test
public void test() {
    TopKFrequentItems stream = new TopKFrequentItems(2);

    stream.add("hell");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("hero");
    stream.add("hero");
    stream.add("hero");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("home");
    stream.add("go");
    stream.add("go");
    assertThat(stream.getItems()).hasSize(2).contains(new TopK("hero", 3), new TopK("hello", 8));
}

Pour plus de détails, voir ce cas de test

Answer 5

1. utiliser 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". Cela prend O(n) temps. C'est la même chose que ce qui a été expliqué ci-dessus.

2. Lors de l'insertion dans le hashmap, conservez le Treeset (spécifique à Java, il existe des implémentations dans tous les langages) de taille 10 (k=10) pour conserver les 10 mots les plus fréquents. Jusqu'à ce que la taille soit inférieure à 10, continuez à l'ajouter. Si la taille est égale à 10, si l'élément inséré est supérieur à l'élément minimal, c'est-à-dire au premier élément. Dans l'affirmative, il est supprimé et un nouvel élément est inséré.

Pour limiter la taille du jeu d'arbres, voir ce lien