algorithm - 在大词序列中找到前K个频繁词的最有效方法

Question

输入：一个正整数 K 和一个大文本。文本实际上可以被视为单词序列。所以我们不必担心如何将其分解为单词序列。
输出：文本中出现频率最高的 K 个单词。

我的想法是这样的。

在遍历整个单词序列时，使用哈希表记录所有单词的频率。在这个阶段，key是“word”，value是“word-frequency”。这需要 O(n) 时间。
对 (word, word-frequency) 对进行排序；关键是“词频”。使用普通排序算法需要 O(n*lg(n)) 时间。
排序后，我们只取前 K 个单词。这需要 O(K) 时间。

总而言之，总时间是O(n+n lg(n)+K)，因为K肯定小于N，所以实际上是O(n lg(n))。

我们可以改进这一点。实际上，我们只想要前 K 个单词。其他词的频率与我们无关。所以，我们可以使用“部分堆排序”。对于步骤 2) 和 3)，我们不只是进行排序。相反，我们将其更改为

2') 以“word-frequency”为key，构建一堆(word, word-frequency) pair。构建堆需要 O(n) 时间；

3') 从堆中提取前 K 个单词。每次提取都是 O(lg(n))。因此，总时间为 O(k*lg(n))。

总而言之，这个解决方案花费时间 O(n+k*lg(n))。

这只是我的想法。我还没有找到改进步骤 1) 的方法。
我希望一些信息检索专家可以更多地阐明这个问题。

score 72 · Accepted Answer

这可以在 O(n) 时间内完成

解决方案1：

脚步：

计算单词并对其进行散列，最终将形成这样的结构

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

遍历哈希并找到最常用的单词（在本例中为“foo”100），然后创建该大小的数组
然后我们可以再次遍历哈希并将单词出现的次数作为数组索引，如果索引中没有任何内容，则创建一个数组，否则将其附加到数组中。然后我们最终得到一个数组，如：
```
  0   1      2            3                  100
[[ ],[cat],[burger],[like, meow, geek],[]...[foo]]
```
然后只从最后遍历数组，收集k个单词。

解决方案2：

脚步：

和上面一样
使用 min heap 并保持 min heap 的大小为 k，并且对于 hash 中的每个单词，我们将单词的出现与 min 进行比较，1）如果它大于 min 值，则删除 min（如果 min 的大小heap 等于 k) 并在最小堆中插入数字。2) 休息简单条件。
遍历完数组后，我们只需将最小堆转换为数组并返回数组即可。

score 22 · Accepted Answer

您不会获得比您描述的解决方案更好的运行时间。你必须做至少 O(n) 的工作来评估所有的词，然后 O(k) 额外的工作来找到前 k 个词。

如果您的问题集非常大，您可以使用分布式解决方案，例如 map/reduce。让 n 个 map 工作人员在每个文本的 1/n 处计算频率，并且对于每个单词，将其发送给基于单词哈希计算的 m 个 reducer 工作人员之一。然后减速器将计数相加。对 reducer 的输出进行合并排序将按受欢迎程度为您提供最流行的单词。

score 14 · Accepted Answer

如果我们不关心排名前 K的解决方案，您的解决方案的一个小变化会产生O(n)算法，如果我们这样做，则会产生O(n+k*lg(k))解决方案。我相信这两个界限在一个常数因子内都是最优的。

在我们遍历列表，插入哈希表之后，这里的优化再次出现。我们可以使用中位数算法来选择列表中第 K 个最大的元素。该算法可证明是 O(n)。

选择第 K 个最小的元素后，我们围绕该元素划分列表，就像在快速排序中一样。这显然也是 O(n)。枢轴“左侧”的任何东西都在我们的 K 个元素组中，所以我们完成了（我们可以简单地扔掉其他所有东西）。

所以这个策略是：

遍历每个单词并将其插入哈希表：O(n)
选择第 K 个最小的元素：O(n)
围绕该元素进行分区：O(n)

如果要对 K 个元素进行排序，只需在 O(k * lg(k)) 时间内使用任何有效的比较排序对它们进行排序，从而产生 O(n+k * lg(k)) 的总运行时间。

O(n) 时间界限在常数因子内是最优的，因为我们必须至少检查每个单词一次。

O(n + k * lg(k)) 时间界限也是最优的，因为没有基于比较的方法可以在小于 k * lg(k) 的时间内对 k 个元素进行排序。

score 9 · Accepted Answer

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

编辑：

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

这种方法只有在您拥有如此多的数据以至于处理所有数据有点愚蠢时才真正合理。如果你只有几兆，你应该能够不费吹灰之力地撕开数据并计算出准确的答案，而不用费心计算估计值。

score 2 · Accepted Answer

您的问题与此相同-http ://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/

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

score 2 · Accepted Answer

您的描述中有一个错误：计数需要 O(n) 时间，但排序需要 O(m*lg(m))，其中 m 是唯一单词的数量。这通常比单词总数小得多，因此可能应该优化哈希的构建方式。

score 2 · Accepted Answer

您可以通过使用单词的第一个字母进行分区来进一步缩短时间，然后使用下一个字符对最大的多单词集进行分区，直到您有 k 个单单词集。您将使用一种 256 路树，在叶子处包含部分/完整单词的列表。您需要非常小心，不要在各处造成字符串副本。

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

如果你并排运行这两种算法，你会得到我很确定是渐近最优 O(min(m, n*lg(k))) 算法，但我的平均速度应该更快，因为它不涉及散列或排序。

score 2 · Accepted Answer

如果您所追求的是文本中任何实用k和任何自然语言的k个最常见单词的列表，那么您的算法的复杂性是不相关的。

只需从您的文本中抽取几百万个单词，在几秒钟内使用任何算法对其进行处理，最常见的计数将非常准确。

附带说明一下，虚拟算法的复杂性（1. 全部计数 2. 排序计数 3. 取最好的）是 O(n+m*log(m))，其中 m 是你的不同单词的数量文本。log(m) 远小于 (n/m)，所以它仍然是 O(n)。

实际上，长步是计数。

score 2 · Accepted Answer

利用内存高效的数据结构来存储单词
使用 MaxHeap，查找前 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;
    }

}

}

这是单元测试

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

有关更多详细信息，请参阅此测试用例

score 1 · Accepted Answer

在遍历整个单词序列时，使用哈希表记录所有单词的频率。在这个阶段，key是“word”，value是“word-frequency”。这需要 O(n) 时间。这与上面解释的每个相同
在将自身插入 hashmap 时，保留大小为 10(k=10) 的 Treeset（特定于 java，每种语言都有实现）以保留前 10 个常用词。直到大小小于 10，继续添加。如果大小等于 10，则如果插入的元素大于最小元素，即第一个元素。如果是，请将其删除并插入新元素

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

score 0 · Accepted Answer

尝试考虑特殊的数据结构来解决此类问题。在这种情况下，特殊类型的树（例如尝试以特定方式存储字符串）非常有效。或者第二种方法来构建自己的解决方案，比如计算单词。我猜这 TB 的数据是英文的，然后我们通常有大约 600,000 个单词，所以可以只存储这些单词并计算哪些字符串会重复 + 这个解决方案需要正则表达式来消除一些特殊字符。第一个解决方案会更快，我很确定。

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

score 0 · Accepted Answer

假设我们有一个单词序列“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”实际上是最常用的词。

也许我误解了你的意思。你能详细说明一下你的分区过程吗？

score 0 · Accepted Answer

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

这里也有一个实现。

score 0 · Accepted Answer

我也在为此苦苦挣扎，并受到@aly 的启发。我们可以只维护一个预先排序的单词列表（），而不是事后排序，List<Set<String>>并且该单词将位于位置 X 的集合中，其中 X 是单词的当前计数。一般来说，它是这样工作的：

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

这样做的缺点是列表可能很大 - 可以通过使用来优化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);
    }

}

score 0 · Accepted Answer

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

score 0 · Accepted Answer

我只是找出这个问题的其他解决方案。但我不确定它是否正确。解决方案：

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

score 0 · Accepted Answer

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

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

score 0 · Accepted Answer

**

上述思想的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;

}

};

score 0 · Accepted Answer

在这些情况下，我建议使用 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。我希望它有所帮助。

algorithm - 在大词序列中找到前K个频繁词的最有效方法

19 回答 19

Related

Reference