在一个大的单词序列中查找前K个高频词的最有效方法

获取最常用单词出现次数的最简代码。

 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])
}

**

以上思路的C++11实现

**

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;

}

};

在这些情况下，我建议使用Java内置功能。因为它们已经经过充分测试和稳定。在这个问题中，我使用HashMap数据结构找到单词的重复出现次数。然后，我将结果推送到对象数组中。我通过Arrays.sort()对对象进行排序，并打印前k个单词及其重复出现次数。

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();
        }
    }

}

更多信息，请访问https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TopKWordsTextFile.java。希望能对您有所帮助。

尝试思考特殊的数据结构来处理这种问题。在这种情况下，使用像trie这样的特殊树来以特定的方式存储字符串非常高效。或者第二种方法是建立自己的解决方案，比如计数单词。我猜这个TB的数据会是英文，那么一般有大约60万个单词，所以只需要存储那些重复出现的字符串并计数，同时这个解决方案需要使用正则表达式来消除一些特殊字符。第一个解决方案会更快，我很确定。

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

我刚刚找到了另一种解决这个问题的方法。但我不确定它是否正确。 解决方案：

1. 使用哈希表记录所有单词的频率 T(n) = O(n)
2. 选择哈希表的前k个元素，并将它们存储在一个缓冲区中（其空间为k）。T(n) = O(k)
3. 每次，首先需要找到当前缓冲区的最小元素，然后将缓冲区的最小元素与哈希表的（n-k）个元素逐一比较。如果哈希表的元素大于缓冲区的这个最小元素，则删除当前缓冲区的最小元素，并添加哈希表的元素。因此，每次在缓冲区中找到最小元素需要T(n) = O(k)，遍历整个哈希表需要T(n) = O(n-k)。因此，该过程的整体时间复杂度为T(n) = O((n-k)*k)。
4. 遍历整个哈希表后，结果就在这个缓冲区中。
5. 整个时间复杂度：T(n) = O(n) + O(k) + O(kn-k^2) = O(kn+n-k^2+k)。由于k通常远小于n，因此对于这个解决方案，时间复杂度为T(n) = O(kn)。当k非常小时，这是线性时间。这样说对吗？我真的不确定。

这是一个有趣的搜索想法，我找到了与Top-K相关的论文https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf

此外，还有一个实现在这里。

假设我们有一个单词序列 "ad" "ad" "boy" "big" "bad" "com" "come" "cold"，并且 K=2。根据您提到的“使用单词的第一个字母进行分区”，我们得到了 ("ad", "ad") ("boy", "big", "bad") ("com" "come" "cold")。"然后使用下一个字符对最大的多个单词集进行分区，直到你有k个单个单词集。"这将会将("boy", "big", "bad") ("com" "come" "cold") 进行分区，第一个分区("ad", "ad") 被忽略了，而 "ad" 实际上是最常见的单词。
也许我误解了您的意思。您能详细说明一下您分区的过程吗？

我相信这个问题可以通过O(n)的算法来解决。我们可以实时进行排序。换句话说，在这种情况下，排序是传统排序问题的一个子问题，因为每次访问哈希表时只有一个计数器会增加一次。最初，列表已经排序，因为所有计数器都是零。当我们不断增加哈希表中的计数器时，我们还会维护一个按频率排序的哈希值数组。每次增加一个计数器时，我们检查它在排名数组中的索引，并检查其计数是否超过列表中前一个元素的计数。如果是这样，我们交换这两个元素。通过这样的方法，我们得到的解决方案最多是O(n)，其中n是原始文本中单词的数量。

我也曾经为此苦恼，受到了@aly的启发。我们可以维护一个预排序的单词列表(List<Set<String>>)，并且单词将在集合中的位置X处，其中X是当前单词的计数。一般来说，它的工作原理如下：

1. 对于每个单词，将其存储为其出现次数的映射的一部分：Map<String, Integer>。
2. 然后，根据计数，从先前的计数集中删除它，并将其添加到新的计数集中。

这种方法的缺点是列表可能很大 - 可以通过使用TreeMap<Integer, Set<String>>进行优化，但这会增加一些开销。最终，我们可以使用HashMap或自己的数据结构的混合。

代码如下：

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);
    }

}