算法:计算单词列表频率的更好方法

这个问题实际上很简单，但我想在开始编码之前听到一些想法。给定一个文件，每行都有一个单词，计算最频繁的数字n。

我脑海中浮现的第一件事，也是唯一一件事使用std::map .我知道C++同胞们会说unordered_map太合理了。

我想知道是否可以在算法方面添加任何内容，或者这基本上只是"谁选择最佳数据结构就赢了"类型的问题。我已经在互联网上搜索了它并阅读了哈希表和优先级队列可能会提供具有 O（n） 运行时间的算法，但我认为实现起来会很复杂

有什么想法吗？

用于此任务的最佳数据结构是 Trie：

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

它将胜过用于计算字符串的哈希表。

这个问题有许多不同的方法。它最终取决于场景和其他因素，例如文件的大小（如果文件有十亿行），那么HashMap将不是一种有效的方法。以下是您可以根据您的问题执行的一些操作：

如果您知道唯一单词的数量非常有限，则可以使用TreeMap或在您的情况下使用std::map。
如果单词数非常大，则可以构建一个trie并在另一个数据结构中保留各种单词的数量。这可能是大小为 n 的堆（最小/最大取决于您想要执行的操作）。因此，您不需要存储所有单词，只需存储必要的单词即可。

如果我有很多选择，我不会从std::map（或unordered_map）开始（尽管我不知道其他约束可能适用）。

您在这里有两个数据项，您使用一个作为时间的关键部分，但另一个作为另一部分时间的键。为此，您可能需要像Boost Bimap或Boost MultiIndex这样的东西。

以下是使用 Bimap 的一般思路：

#include <boost/bimap.hpp>
#include <boost/bimap/list_of.hpp>
#include <iostream>
#define elements(array) ((sizeof(array)/sizeof(array[0])))
class uint_proxy {
    unsigned value;
public:
    uint_proxy() : value(0) {}
    uint_proxy& operator++() { ++value; return *this; }
    unsigned operator++(int) { return value++; }
    operator unsigned() const { return value; }
};
int main() {    
    int b[]={2,4,3,5,2,6,6,3,6,4};
    boost::bimap<int, boost::bimaps::list_of<uint_proxy> > a;
    // walk through array, counting how often each number occurs:
    for (int i=0; i<elements(b); i++) 
        ++a.left[b[i]];
    // print out the most frequent:
    std::cout << a.right.rbegin()->second;
}

目前，我只打印出最常用的数字，但迭代 N 次以打印出 N 次最常见的数字是相当微不足道的。

如果你只是对前N个最常用的单词感兴趣，并且你不需要它精确，那么你可以使用一个非常聪明的结构。我是通过Udi Manber听说的，它的工作原理如下：

您创建一个包含 N 个元素的数组，每个元素跟踪一个值和一个计数，您还保留一个索引到该数组的计数器。此外，您还具有从值到该数组的索引的映射。每次使用值（如文本流中的单词）更新结构时，您首先检查映射以查看该值是否已在数组中，如果是，则增加该值的计数。如果不是，则递减计数器指向的任何元素的计数，然后递增计数器。

这听起来很简单，算法没有任何内容使它看起来会产生任何有用的东西，但对于典型的真实数据，它往往做得很好。通常，如果您希望跟踪前 N 个东西，您可能希望使这个结构的容量为 10*N，因为其中会有很多空值。使用詹姆士王圣经作为输入，以下是此结构列出的最常见的单词（排名不分先后）：

0 : in
1 : And
2 : shall
3 : of
4 : that
5 : to
6 : he
7 : and
8 : the
9 : I

以下是前十个最常用的单词（按顺序）：

0 : the ,  62600
1 : and ,  37820
2 : of ,  34513
3 : to ,  13497
4 : And ,  12703
5 : in ,  12216
6 : that ,  11699
7 : he ,  9447
8 : shall ,  9335
9 : unto ,  8912

你可以看到它对前 10 个单词中的 9 个是正确的，并且它只使用了 50 个元素的空间。根据您的用例，此处节省的空间可能非常有用。它也非常快。

这是我用 Go 编写的 topN 的实现：

type Event string
type TopN struct {
  events  []Event
  counts  []int
  current int
  mapped  map[Event]int
}
func makeTopN(N int) *TopN {
  return &TopN{
    counts: make([]int, N),
    events: make([]Event, N),
    current: 0,
    mapped: make(map[Event]int, N),
  }
}
func (t *TopN) RegisterEvent(e Event) {
  if index, ok := t.mapped[e]; ok {
    t.counts[index]++
  } else {
    if t.counts[t.current] == 0 {
      t.counts[t.current] = 1
      t.events[t.current] = e
      t.mapped[e] = t.current
    } else {
      t.counts[t.current]--
      if t.counts[t.current] == 0 {
        delete(t.mapped, t.events[t.current])
      }
    }
  }
  t.current = (t.current + 1) % len(t.counts)
}

给定一个文件，每行都有一个单词，计算最频繁的数字n。 ... 我已经在互联网上搜索了它，并读到哈希表和优先级队列可能会提供 O（n） 的算法

如果您的意思是 *n* 相同，那么不，这是不可能的。但是，如果您只是根据输入文件大小表示时间线性，那么带有哈希表的简单实现将执行您想要的操作。

可能存在具有次线性记忆的概率近似算法。

相关内容

最新更新

热门标签：