最有效的方法find大词序中的K个最常见的词

input：一个正整数K和一个大文本。 文本实际上可以被视为单词序列。 所以我们不必担心如何把它分解成单词序列。
输出：文本中最常见的K个单词。

我的想法是这样的。

  1. 使用哈希表来logging所有单词的频率，同时遍历整个单词序列。 在这个阶段，关键是“文字”，其值是“文字频率”。 这需要O（n）时间。

  2. （字，词频）对; 关键是“词频”。 这需要O（n * lg（n））时间与正常sortingalgorithm。

  3. sorting后，我们只需要第一个K字。 这需要O（K）时间。

总的来说，总的时间是O（n + n lg（n）+ K），由于K肯定小于N，所以它实际上是O（n lg（n））。

我们可以改善这一点。 其实我们只是想顶K字。 换句话说，频率并不是我们所关心的。 所以，我们可以使用“部分堆sorting”。 对于步骤2）和3），我们不只是做分类。 相反，我们改变它

2“）build立一个以”word-frequency“作为关键字的（word，word-frequency）对。 需要O（n）时间来build立一个堆;

3'）从堆中提取顶部K个单词。 每个提取是O（lg（n））。 所以总的时间是O（k * lg（n））。

总而言之，这个解决scheme的耗时为O（n + k * lg（n））。

这只是我的想法。 我还没有find办法来改善步骤1）。
我希望一些信息检索专家能够更清楚地了解这个问题。

这可以在O（n）时间完成

解决scheme1：

脚步：

  1. 计算单词并对其进行哈希处理，最终将会出现在这样的结构中 

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

  2. 遍历散列并find最常用的单词（在本例中为“foo”100），然后创build该大小的数组

  3. 然后我们可以再次遍历散列，并使用单词出现次数作为数组索引，如果索引中没有任何内容，则创build一个数组，否则将其附加到数组中。 然后我们最终得到一个像这样的数组： 

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

  4. 然后从最后遍历数组，并收集k个单词。

解决scheme2：

脚步：

  1. 同上
  2. 使用最小堆并保持最小堆的大小为k，并且对于散列中的每个单词，我们将单词的出现次数与最小值进行比较，如果大于最小值，则删除最小值（如果min堆等于k），并将数字插入最小堆中。 2）rest简单的条件。
  3. 在遍历数组之后，我们只需将最小堆转换为数组并返回数组。

你不会得到比你所描述的解决scheme更好的运行时间。 你必须至less做O（n）工作来评估所有的单词，然后O（k）额外的工作来find最前面的k个术语。

如果您的问题集非常大，则可以使用分布式解决scheme（如map / reduce）。 让n个地图工作人员对每个文本的1 / n的频率进行计数，并且将每个单词发送给基于单词散列计算的m个缩减工作人员中的一个。 减数然后总结计数。 合并sorting的减速器的输出将给你最受欢迎的话语的顺序。

如果我们不关心如何sorting顶部K，那么解决scheme上的一个小的变化会产生一个O（n）algorithm，如果我们这样做的话，会产生一个O（n + k * lg（k））解决scheme。 我相信这两个边界在一个恒定的因素内是最佳的。

我们在遍历列表后再次进行优化，插入到哈希表中。 我们可以使用中位数algorithm来select列表中第K个最大的元素。 该algorithm可certificate为O（n）。

在select第K个最小的元素之后，我们按照快速sorting在该元素周围分割列表。 这显然也是O（n）。 关键点的左边的任何东西都在我们的K元素组中，所以我们完成了（当我们走时，我们可以简单地扔掉其他所有东西）。

所以这个策略是：

  1. 浏览每个单词并将其插入散列表：O（n）
  2. select第K个最小元素：O（n）
  3. 围绕该元素的分区：O（n）

如果要对K个元素进行sorting，只需在O（k * lg（k））时间内用任何有效的比较sorting就可以对它们进行sorting，得到总运行时间O（n + k * lg（k））。

O（n）时限在一个常数因子内是最优的，因为我们必须检查每个单词至less一次。

O（n + k * lg（k））的时间限制也是最优的，因为在小于k * lg（k）的时间内没有基于比较的方法对k个元素进行sorting。

如果你的“大词汇表”足够大，你可以简单地抽样并得出估计。 否则，我喜欢哈希聚合。

编辑 ：

通过样本我的意思是select一些页面的子集，并计算在这些页面中最频繁的单词。 如果您以合理的方式select页面并select具有统计意义的样本，那么您对最常见词汇的估算应该是合理的。

如果你有这么多的数据来处理它，那么这种方法实际上是合理的。 如果你只有几个简单的数字，你应该能够把数据撕下来，计算一个确切的答案，而不是冒汗，而不是麻烦计算一个估计。

您可以通过使用第一个字母单词进行分割来进一步缩短时间，然后使用下一个字符分割最大的多个单词集合，直到您有k个单词集合。 你将使用一个256字节的sorting树，并在叶子上有部分/完整的单词列表。 你需要非常小心，不要在任何地方造成string拷贝。

这个algorithm是O（m），其中m是字符数。 它避免了对k的依赖，这对于大k来说是非常好的[顺便说一下，你的发布运行时间是错误的，它应该是O（n * lg（k）），我不确定这是什么米]。

如果你同时运行这两种algorithm，你将得到我很确定的渐近最优的O（min（m，n * lg（k）））algorithm，但是我的平均速度应该更快，因为它不涉及散列或sorting。

您的描述中有一个错误：计数需要O（n）个时间，但sorting需要O（m * lg（m）），其中m是唯一字的数量。 这通常比单词总数要小得多，所以可能应该优化哈希的构build方式。

你的问题是这样的 – http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/

使用Trie和最小堆来有效地解决它。

如果你所追求的是任何实际k和任何自然语言的文本中k个最频繁单词的列表，那么你的algorithm的复杂性是不相关的。

只需从您的文本中抽取几百万字，在几秒钟内就可以使用任何algorithm进行处理，最常用的计数将非常准确。

作为一个侧面说明，虚拟algorithm的复杂性（1.计数全部2.sorting计数3.采取最好的）是O（n + m * log（m）），其中m是你的不同单词的数量文本。 log（m）远小于（n / m），所以它仍然是O（n）。

实际上，漫长的一步正在计算。

  1. 使用哈希表来logging所有单词的频率，同时遍历整个单词序列。 在这个阶段，关键是“文字”，其值是“文字频率”。 这需要O（n）时间。这与上面所解释的每一个都是一样的

  2. 在将自身插入到hashmap中时，请将大小为10（k = 10）的Treeset（特定于java，每种语言都有实现）保留在前10个频繁的单词中。 直到尺寸小于10，继续添加。 如果大小等于10，如果插入的元素大于最小元素即第一个元素。 如果是删除它，并插入新的元素

要限制treeset的大小，请参阅此链接

假设我们有一个单词序列“ad”“ad”“boy”“big”“bad”“com”“come”“cold”。 而K = 2。 正如你所提到的“用第一个字母分隔”，我们得到了（“ad”，“ad”）（“boy”，“big”，“bad”）（“com”“come”“cold”）“使用下一个字符分割最大的多字集，直到您有k个单字集。 它将分区（“男孩”，“大”，“坏”）（“com”“come”“cold”），第一个分区（“ad”，“ad”）被错过，而“ad”最频繁的词。

也许我误解了你的观点。 你能详细介绍一下你的分区过程吗？

我相信这个问题可以通过O（n）algorithm来解决。 我们可以在飞行中进行sorting。 换句话说，在这种情况下，sorting是传统sorting问题的一个子问题，因为每次访问哈希表只有一个计数器增加一个。 最初，由于所有的计数器都是零，因此列表被sorting。 随着我们不断在散列表中增加计数器，我们按照以下方式logging另一个按频率sorting的散列值数组。 每次我们增加一个计数器，我们检查它在sorting数组中的索引，并检查它的数量是否超出了它在列表中的前辈。 如果是这样，我们交换这两个元素。 因此，我们得到的解决scheme至多是O（n），其中n是原始文本中的单词数量。

我也在为此苦苦挣扎，并受到@aly的启发。 我们可以维护一个预先sorting的单词List<Set<String>> （ List<Set<String>> ），而不是在之后sorting，而是将单词放在位置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); } }

我只是找出解决这个问题的另一种方法。 但我不确定是否正确。 解：

  1. 使用哈希表logging所有单词的频率T（n）= O（n）
  2. select哈希表的前k个元素，并将其恢复到一个缓冲区（其空间= k）。 T（n）= O（k）
  3. 每一次，我们首先需要find缓冲区的当前最小元素，并将缓冲区的最小元素与哈希表中的（n-k）个元素逐一进行比较。 如果哈希表的元素大于缓冲区的最小元素，则删除当前缓冲区的最小值，并添加哈希表的元素。 所以每次我们发现缓冲区中的最小值需要T（n）= O（k），并遍历整个哈希表需要T（n）= O（n-k）。 所以这个过程的整个时间复杂度是T（n）= O（（nk）* k）。
  4. 遍历整个哈希表后，结果在这个缓冲区中。
  5. 整个时间复杂度：T（n）= O（n）+ O（k）+ O（kn-k ^ 2）= O（kn + n – k ^ 2 + k）。 因为k总体上比n小。 所以对于这个解决scheme，时间复杂度是T（n）= O（kn） 。 那是线性时间，当k很小的时候。 这样对吗？ 我真的不确定。

试着想想特殊的数据结构来处理这类问题。 在这种情况下，特殊types的树像特里一样存储string，非常有效。 或者第二种方式来build立自己的解决scheme，如计算单词。 我猜这个TB的数据是英文的，所以我们一般有大约60万字，所以只能存储那些字和计算哪些string将被重复，这个解决scheme将需要正则expression式来消除一些特殊字符。 第一个解决scheme会更快，我很确定。

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

这是一个有趣的想法来search，我可以find这篇文章有关Top-K https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pd f

这里也有一个实现。

最简单的代码来获得最常用的单词的发生。 

  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]) }
  1. 利用高效的内存数据结构来存储单词
  2. 使用MaxHeap，find最常见的K个单词。

这是代码 

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

}

这里是unit testing 

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

有关更多信息，请参阅此testing用例

在这些情况下，我build议使用Java内置function。 因为它们已经经过了充分的testing和稳定。 在这个问题中，我通过使用HashMap数据结构来查找单词的重复。 然后，我将结果推送到一个对象数组。 我通过Arrays.sort（）对对象进行sorting，并打印前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 。 我希望它有帮助。 

 **

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

};

    Interesting Posts

    使用pythonsortingWord频率计数