Алгоритм подсчета отсортированных строк (доморощенный "uniq -c")

Question

У меня есть следующие отсортированные данные:

AAA
AAA
TCG
TTT
TTT
TTT

Я хочу сосчитать вхождения каждой строки:

AAA 2
TCG 1
TTT 3

Я знаю, что могу сделать это, используя uniq -c, но здесь мне нужно выполнить дополнительную обработку всего кода C ++, который у меня есть.

Я застрял с этой конструкцией (измененной согласно предложению 'pgras'):

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
using namespace std;


int main  ( int arg_count, char *arg_vec[] ) {
    if (arg_count !=2 ) {
        cerr << "expected one argument" << endl;
        return EXIT_FAILURE;
    }

    string line;
    ifstream myfile (arg_vec[1]);


    if (myfile.is_open())
    {
        int count;
        string lastTag = "";

        while (getline(myfile,line) )
        {
            stringstream ss(line);
            string Tag;

            ss >> Tag; // read first column
            //cout << Tag << endl; 

            if (Tag != lastTag) {
               lastTag = Tag;
               count = 0;
            }
            else {
                count++;
            }

             cout << lastTag << " " << count << endl;
        }
        cout << lastTag << " " << count << endl;
        myfile.close();

    }
    else {cout << "Unable to open file";}
    return 0;
}

Это печатает этот неправильный результат:

AAA 0
AAA 1
TCT 0
TTT 0
TTT 1
TTT 2
TTT 2

Answer 1

Вы должны сбросить счетчик, когда тег отличается от lastTag, и увеличить, если он такой же ... Если тег отличается, вы можете обработать предыдущий тег с соответствующим значением счетчика (перед сбросом счетчика) ...

Answer 2

Если вы просто хотите распечатать его, ваш алгоритм в порядке. Если вы хотите передать его другой функции, вы можете использовать, например, карту STL.

map<string, int> dict;

while(getline(myfile,line)) {
          string Tag;
          stringstream ss(line);
          ss >> Tag;
          if (dict.count(Tag) == 0) 
               dict[Tag] = 1;
           else
               dict[Tag]++;
}    

Answer 3

Предполагая, что ваши данные действительно состоят из цепочек ДНК длиной 3 (или более общей длины N , где N довольно мала), вы можете сделать это очень эффективно, используя -gram таблица, которая является специализированной хеш-таблицей с размером таблицы 4 ^N и следующей функцией хеширования:

// Disregard error codes.
int char2dna_lookup[] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x0  – 0xF
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x10 – 0x1F
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x20 – 0x2F
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x30 – 0x3F
    0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, // A    – P
    0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // Q    – 0x5F
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x60 – 0x6F
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x70 – 0x7F
}

unsigned int hash(string const& dna) {
    unsigned int ret = 0;

    for (unsigned int i = 0; i < dna.length(); ++i)
        ret = ret * 4 + char2dna_lookup[dna[i]];

    return ret;
}

Теперь вы можете очень эффективно индексировать ваш массив.

ifstream ifs("data.txt");
string line;

if (not ifs >> line)
    exit(1);

unsigned* frequencies = new unsigned int[line.length()];

frequencies[hash(line)] = 1;

while (ifs >> line)
    ++frequencies[hash(line)];

// Print the frequencies …

delete[] frequencies;

В качестве альтернативы используйте для таких задач библиотеку, такую ​​как SeqAn .

Answer 4

Используйте что-то вроде этого:

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


std::ostream& operator << ( std::ostream& out, const std::pair< std::string, size_t >& rhs )
{
    out << rhs.first << ", " << rhs.second;
    return out;
}

int main() 
{
    std::ifstream inp( "mysorted_data.txt" );
    std::string str;
    std::map < std::string, size_t > words_count;
    while ( inp >> str )
    {
        words_count[str]++;
    }

    std::copy( 
        words_count.begin(), 
        words_count.end(), 
        std::ostream_iterator< std::pair< std::string, size_t > >( std::cout, "\n" ) );

    return 0;
}

Answer 5

Я думаю, что все, что вам нужно сделать, это заменить это

        if (Tag != lastTag) {
           lastTag = Tag;
           count = 0;
        }
        else {
            count++;
        }

        cout << lastTag << " " << count << endl;

с этим:

        if (Tag != lastTag) {
            if (lastTag != "") {  // don't print initial empty tag
                cout << lastTag << " " << count << endl;
            }
            lastTag = Tag;
            count = 1; // count current
          } else {
            count++;
        }

Answer 6

#include <map>
#include <string>
#include <algorithm>
#include <iterator>
#include <iostream>

class Counter
{   private: std::map<std::string,int>&   m_count;
    public:  Counter(std::map<std::string,int>& data) :m_count(data){}
        void operator()(std::string const& word)
        {
            m_count[word]++;
        }};
class Printer
{   private: std::ostream& m_out;
    public:  Printer(std::ostream& out) :m_out(out) {}
        void operator()(std::map<std::string,int>::value_type const& data)
        {
            m_out << data.first << " = " << data.second << "\n";
        }};

int main()
{
    std::map<std::string,int>       count;

    for_each(std::istream_iterator<std::string>(std::cin),
             std::istream_iterator<std::string>(),
             Counter(count)
            );

    for_each(count.begin(),count.end(),
             Printer(std::cout)
            );
}

Answer 7

Использование строкового потока только для получения тега кажется излишним - я бы, вероятно, использовал string :: substr. Кроме того, как вы думаете, что не так с вашим кодом? Что вы хотите улучшить?

Редактировать: Следующая вещь, нам будет отказано в дыхании ...

Answer 8

Ваш код выглядит синтаксически слегка нарушенным (ifstream, ...), но общий алгоритм, на мой взгляд, является надежным. Читайте строки и увеличивайте счетчик каждый раз, когда строка совпадает с предыдущей. Могут быть некоторые граничные условия, которые нужно учитывать (что, если на входе всего одна строка?), Но вы поймете их во время тестирования.