Алгоритм подсчета Sorted строк (Homebrew "уник -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

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

Answer 3

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

Edit: Следующая вещь, мы будем получать downvoted для дыхания ...

Answer 4

Если вы просто хотите, чтобы распечатать его, ваш алгоритм нормально. Если вы хотите передать его другой функции, вы можете использовать, например, карту 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 5

использовать что-то вроде этого:

#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 6

Предполагая, что данные действительно состоит из строк ДНК длиной 3 (или более общей длины N где N является совсем маленький), вы можете сделать это очень эффективно с помощью таблицы д-граммовый, который является специализированным хеш-таблицы с размером таблицы 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 7

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

 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 8

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