c++ - 数据流中频繁元素和 Top-k 元素的高效计算

Question

这是该算法的pseduo代码。

以下是我是如何实现的。

#include <iostream>
#include <fstream>
#include <string>
#include <map>

typedef std::map<std::string, int> collection_t;
typedef collection_t::iterator collection_itr_t;

collection_t T;

collection_itr_t get_smallest_key() {
    collection_itr_t min_key = T.begin();
    collection_itr_t key     = ++min_key;
    while ( key != T.end() ) {
        if ( key->second < min_key->second )
            min_key =  key;
        ++key;
    }
    return min_key;
}
void space_saving_frequent( std::string &i, int k ) {
    if ( T.find(i) != T.end())
        T[i]++;
    else if ( T.size() < k ) {
        T.insert(std::make_pair(i, 1 ));
    } else {
        collection_itr_t j = get_smallest_key();
        int cnt = j->second + 1;
        T.erase(j);
        T.insert(std::make_pair(i, cnt));
    }
}
int main ( int argc, char **argv) {
    std::ifstream ifs(argv[1]);
    if ( ifs.peek() == EOF ) 
        return 1;
    std::string line; 
    while( std::getline(ifs,line) ) {
        std::string::size_type left   = line.rfind('=') + 1;
        std::string::size_type length = line.length();
        std::string i     = line.substr(left, length - left - 1);  
        space_saving_frequent(i, 5);
    }
    ifs.close();
    return 0;
}

原文链接:http://dimacs.rutgers.edu/~graham/pubs/papers/freqcacm.pdf

但是代码不工作，我无法弄清楚我哪里错了。

Answer 1

如果计数最少的项目是两个或更多，您可以通过选择(例如，存储在您的数据结构中的索引最低的项目，或者在计数最低的项目中随机选择一个等)来任意打破平局。

如果您想将您的实现与引用实现进行比较，请查看您会发现的 Cormode 和 Hadjieleftheriou 的实现 here .代码比你的更复杂，因为你实际上并没有实现流摘要数据结构。他们的代码还包括其他几种频繁项算法的实现，作者比较了这些算法的性能。在大多数情况下，空间节省被证明是最好的算法，关于几个指标，如精度、召回率、更新速度、使用的空间等。您还将找到一篇讨论该实验比较的论文。这篇论文的改进版本后来出现在 ACM 的 Communications 中。 Here您可以访问 pdf 版本。