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

C'est une idée intéressante à rechercher et j'ai pu trouver ce document lié à Top-K. https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pd f

Il existe également une implémentation de ce système aquí .

Answer 2

Code le plus simple pour obtenir l'occurrence du mot le plus fréquemment utilisé.

 function strOccurence(str){
    var arr = str.split(" ");
    var length = arr.length,temp = {},max; 
    while(length--){
    if(temp[arr[length]] == undefined && arr[length].trim().length > 0)
    {
        temp[arr[length]] = 1;
    }
    else if(arr[length].trim().length > 0)
    {
        temp[arr[length]] = temp[arr[length]] + 1;

    }
}
    console.log(temp);
    var max = [];
    for(i in temp)
    {
        max[temp[i]] = i;
    }
    console.log(max[max.length])
   //if you want second highest
   console.log(max[max.length - 2])
}

Answer 3

Dans ces situations, je recommande d'utiliser les fonctions intégrées de Java. En effet, elles sont déjà bien testées et stables. Dans ce problème, je trouve les répétitions des mots en utilisant la structure de données HashMap. Ensuite, je transfère les résultats dans un tableau d'objets. Je trie les objets par Arrays.sort() et j'imprime les k premiers mots et leurs répétitions.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class TopKWordsTextFile {

    static class SortObject implements Comparable<SortObject>{

        private String key;
        private int value;

        public SortObject(String key, int value) {
            super();
            this.key = key;
            this.value = value;
        }

        @Override
        public int compareTo(SortObject o) {
            //descending order
            return o.value - this.value;
        }
    }

    public static void main(String[] args) {
        HashMap<String,Integer> hm = new HashMap<>();
        int k = 1;
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("words.in")));

            String line;
            while ((line = br.readLine()) != null) {
                // process the line.
                //System.out.println(line);
                String[] tokens = line.split(" ");
                for(int i=0; i<tokens.length; i++){
                    if(hm.containsKey(tokens[i])){
                        //If the key already exists
                        Integer prev = hm.get(tokens[i]);
                        hm.put(tokens[i],prev+1);
                    }else{
                        //If the key doesn't exist
                        hm.put(tokens[i],1);
                    }
                }
            }
            //Close the input
            br.close();
            //Print all words with their repetitions. You can use 3 for printing top 3 words.
            k = hm.size();
            // Get a set of the entries
            Set set = hm.entrySet();
            // Get an iterator
            Iterator i = set.iterator();
            int index = 0;
            // Display elements
            SortObject[] objects = new SortObject[hm.size()];
            while(i.hasNext()) {
                Map.Entry e = (Map.Entry)i.next();
                //System.out.print("Key: "+e.getKey() + ": ");
                //System.out.println(" Value: "+e.getValue());
                String tempS = (String) e.getKey();
                int tempI = (int) e.getValue();
                objects[index] = new SortObject(tempS,tempI);
                index++;
            }
            System.out.println();
            //Sort the array
            Arrays.sort(objects);
            //Print top k
            for(int j=0; j<k; j++){
                System.out.println(objects[j].key+":"+objects[j].value);
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

Pour plus d'informations, veuillez consulter le site https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TopKWordsTextFile.java . J'espère que cela vous aidera.

Answer 4

**

Implémentation en C++11 de la pensée ci-dessus

**

class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {

    unordered_map<int,int> map;
    for(int num : nums){
        map[num]++;
    }

    vector<int> res;
    // we use the priority queue, like the max-heap , we will keep (size-k) smallest elements in the queue
    // pair<first, second>: first is frequency,  second is number 
    priority_queue<pair<int,int>> pq; 
    for(auto it = map.begin(); it != map.end(); it++){
        pq.push(make_pair(it->second, it->first));

        // onece the size bigger than size-k, we will pop the value, which is the top k frequent element value 

        if(pq.size() > (int)map.size() - k){
            res.push_back(pq.top().second);
            pq.pop();
        }
    }
    return res;

}

} ;