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

Question

输入: 一个正整数K和一段大文本。该文本实际上可以看作是单词序列。因此我们不必担心如何将其分解为单词序列。
输出: 文本中出现频率最高的K个单词。

我的思路如下：

1. 遍历整个单词序列时，使用散列表记录所有单词的频率。在此阶段，键是“单词”，值是“单词频率”。这需要O(n)时间。

2. 对(word,word-frequency)对进行排序; 键是“word-frequency”。这需要使用普通排序算法的O(n*lg(n))时间。

3. 排序后，我们只需提取前K个单词。这需要O(K)时间。

总结一下，总时间复杂度为O(n+n*lg(n)+K)，由于K肯定小于N，因此实际上是O(n*lg(n))。

我们可以改进这个算法。实际上，我们只想要前K个单词。其他单词的频率与我们无关。因此，我们可以使用“部分堆排序”。对于步骤2）和3），我们不仅要进行排序，而是将它们改变为：

2'）以“word-frequency”作为键构建(word,word-frequency)对的堆。构建堆需要O(n)时间；

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

总结一下，这个解决方案的时间复杂度为O(n+k*lg(n))。

这只是我的想法。我还没有找到改进步骤1）的方法。
希望一些信息检索专家能够对这个问题进行更深入的探讨。

- Morgan Cheng

---

你会使用归并排序还是快速排序来进行O(n*logn)的排序？ - committedandroider

对于实际应用而言，Aaron Maenpaa的回答中的样本计数方法是最好的选择。这不像“最常见”的单词会从你的样本中隐藏起来。对于复杂度极客而言，它的时间复杂度为O(1)，因为样本的大小是固定的。你得不到精确的计数，但你也没有要求它们。 - Nikana Reklawyks

如果您想要对复杂性分析进行审查，那么我最好提一下：如果n是文本中单词的数量，而m是不同单词（我们称之为类型）的数量，则步骤1的时间复杂度为O(n)，但步骤2的时间复杂度为O(m.lg(m))，且m << n（您可能有数十亿个单词，但不到一百万个类型，请尝试一下）。因此，即使使用虚拟算法，它仍然是O(n + m lg(m)) = O(n)。 - Nikana Reklawyks

请在问题中添加一个假设，即我们有足够的主内存来容纳大文本中的所有单词。从10GB文件中查找k = 100个单词的方法将非常有趣（即所有单词都无法适合4GB RAM）！ - KGhatak

我投票关闭此问题，因为它没有提出一个问题。 - TylerH

Answer 1

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

解决方案1：

步骤：

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：

步骤：

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

- Chihung Yu

---

你的解法（1）是将标准的O(n lg n)比较排序替换为O(n)桶排序。你的方法需要额外的空间存储桶的结构，但比较排序可以原地进行。你的解法（2）运行时间为O(n lg k)，即O(n)用于遍历所有单词，O(lg k)用于将每个单词添加到堆中。 - stackoverflowuser2010

第一种解决方案需要更多的空间，但重要的是强调它实际上是O(n)时间复杂度。具体操作如下：1.将单词按频率存入哈希表中，O(n)；2.遍历频率哈希表，创建第二个按频率为键的哈希表。遍历哈希表是O(n)，将单词添加到频率列表中是O(1)。3.从最大频率开始向下遍历哈希表，直到达到k。最多是O(n)。总共= 3 * O(n) = O(n)。 - BringMyCakeBack

通常在计算单词数时，方案一中的桶数量被广泛高估（因为最常见的单词比第二和第三频率最高的单词要多得多），因此您的数组是稀疏且效率低下的。 - Nikana Reklawyks

你的解决方案＃1在k（频繁单词的数量）小于最常见单词的出现次数（即，在这种情况下为100）时无法正常工作。当然，实际上可能不会发生这种情况，但是我们不应该假设！ - One Two Three

@OneTwoThree 所提出的解决方案只是一个示例。数字将根据需求而定。 - Chihung Yu

Answer 2

您不太可能获得比您描述的解决方案更好的运行时间。您必须至少进行O(n)个单词的评估工作，然后再进行O(k)额外的工作来查找前k个术语。

如果您的问题集非常大，可以使用分布式解决方案，例如map/reduce。让n个映射工作者在每个文本的1/n上计算频率，并将每个单词根据其哈希发送到m个约减工作者之一。然后由约减工作者对计数进行求和，通过对约减器的输出进行归并排序，您可以按受欢迎程度的顺序获取最流行的单词。

- Arachnid

Answer 3

如果我们不关心排名前K，那么对您的解决方案进行小的变化可以得到一个O(n)算法；如果我们关心排名前K，则可以得到一个O(n+k*lg(k))的解决方案。我相信这两个界限在常数因子内是最优的。

在我们遍历列表并将其插入哈希表之后，再次进行优化。我们可以使用中位数的中位数算法来选择列表中第K大的元素。该算法可证明其时间复杂度为O(n)。

在选择第K小的元素之后，我们像快速排序一样围绕该元素对列表进行分区。显然，这也是O(n)。在枢轴的“左侧”的任何内容都属于我们的K个元素组，所以我们完成了（我们可以随着操作丢弃其他所有内容）。

因此，这个策略是：

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

如果您想要排名前K个元素，只需使用任何高效的比较排序在O(k * lg(k))时间内对它们进行排序，从而得到总运行时间为O(n+k * lg(k))。

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

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

- Andrew

---

当我们选择第K小的元素时，被选择的是第K小的哈希键。在第3步的左侧分区中并不一定有正好K个单词。 - Prakash Murali

你无法在哈希表上运行“中位数的中位数”算法，因为它需要进行交换操作。你需要将数据从哈希表复制到一个临时数组中。因此，需要 O(n) 的存储空间。 - user674669

我不明白如何在O(n)时间内选择第K小的元素？ - Michael Ho Chum

请查看以下链接，了解在O(n)时间复杂度内找到第K小元素的算法 - http://www.wikiwand.com/en/Median_of_medians - Piyush

即使使用哈希表+最小堆，复杂度仍然相同。我没有看到任何优化。 - Vinay

Answer 4

如果您的“大词列表”足够大，您可以简单地采样并获得估计值。否则，我喜欢哈希聚合。

编辑：所谓采样是指选择一些页面子集，并计算这些页面中最频繁出现的单词。只要您合理选择页面并选择具有统计显着性的样本，您对最常见单词的估计应该是合理的。

如果您只有几兆数据，那么这种方法确实只有在处理全部数据变得有点傻的情况下才合理。此时，您应该能够轻松地浏览数据并计算精确答案，而不必费心去计算估计值。

- zacherates

---

有时候你需要重复做这件事情，例如如果你试图获取每个网站或主题的常用词列表。在这种情况下，“毫不费力”并不能真正解决问题。你仍然需要找到一种尽可能高效的方法来完成它。 - itsadok

+1 针对实际问题的答案，不涉及无关的复杂性问题。@itsadok：对于每次运行：如果它足够大，则对其进行采样；如果不是，则获得对数因子是无关紧要的。 - Nikana Reklawyks

Answer 5

1. 使用占用内存较少的数据结构来存储单词
2. 使用大根堆(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));
}

更多细节请参考此测试用例

。

- craftsmannadeem

Answer 6

你的描述中有误：计数需要 O(n) 时间，但排序需要 O(m*lg(m))，其中 m 是 唯一 单词的数量，通常远小于总单词数，因此最好优化哈希表的构建方法。

- martinus

Answer 7

如果你想获得文本中出现频率最高的前k个词，无论是哪种自然语言，对于任何实际的k值，那么算法的复杂度就不重要了。

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

顺便提一下，虚拟算法（1.计数所有 2.排序计数 3.取最佳）的复杂度为O(n+m*log(m))，其中m是文本中不同单词的数量。log(m)远小于(n/m)，因此它仍然是O(n)。

实际上，最耗时的步骤是计数。

- Nikana Reklawyks

Answer 8

您的问题与此相同 - http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/ 使用 Trie 和小根堆可有效解决它。

- Jitendra Rathor

Answer 9

您可以通过按单词的第一个字母进行分区，然后使用下一个字符对最大的多个单词集进行分区，直到您有k个单词集来进一步缩短时间。您需要使用一种具有256路树的排序，其中叶子节点是部分/完整单词列表。您需要非常小心，以免在各处造成字符串复制。

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

如果您同时运行两个算法，您将得到我相当确定的渐近最优O(min(m, n*lg(k)))算法，但我的平均速度应该更快，因为它不涉及哈希或排序。

- Strilanc

---

你所描述的数据结构被称为“字典树”。 - Nick Johnson

嗨，Strilanc。你能详细解释一下分区的过程吗？ - Morgan Cheng

这怎么可能不涉及排序呢？一旦你有了 Trie，如何提取出出现频率最高的 k 个单词。这根本没有意义。 - ordinary

Answer 10

1. 使用哈希表记录整个单词序列中所有单词的频率。在此阶段，键是“单词”，值是“单词频率”。这需要O(n)时间。这与上面每个人解释的相同。

2. 在哈希映射表中进行插入时，保持大小为10(k=10)的Treeset（特定于Java，在每种语言中都有实现），以保留前10个最常见的单词。直到大小小于10，继续添加。如果大小等于10，则如果插入的元素大于最小元素即第一个元素，则将其删除并插入新元素。

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

- M Sach