バイナリデータ中のランの度数分布をとる

はじめてのqiitaへの投稿．

適当なバイナリデータが与えられたときに，「ラン」の度数分布を計算したい．
ランの定義は以下の通り
たとえば 0000110000011111 という文字列を考える
このとき同じ文字が4回，2回，5回，5回と続くので度数分布 h[i] は
h[0]=0, h[1]=0, h[2]=1, h[3]=0, h[4]=1, h[5]=2 となる．

以下はバイナリデータを4バイト区切りで解釈してランの度数分布を求めるための c++ コード

/* run_count.cpp */

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

template<class UINT_T>
int run_count(string filename, int max=256){
  vector<uint32_t> hist(max,0);
  ifstream fin(filename);
  UINT_T buf, prev=max;
  uint32_t run = 0;

  if(!fin){
    cerr << filename << "cannot open" << endl;
    exit(-1);
  }

  bool first = true;
  while(!fin.eof()){
    fin.read((char*)&buf, sizeof(buf));
    if(buf!=prev){
      prev = buf;
      run++;
      if(run>=max){ run = max-1; }
      hist[run] += 1;
      run = 0;
    } else { run++; }
  }
  hist[run] += 1;

  hist[1] -= 1;  // this is to reduce the first dummy run

  for(int i=0;i<max;++i){
    cout << i << " " << hist[i] << endl;
  }
}

int main(){
  cout << "=== test.binary ===" << endl;
  run_count<uint32_t>("test.binary",64);

  cout << "=== toy.binary ===" << endl;
  run_count<uint32_t>("toy.binary",16);
}

適当なデータ生成プログラム

#include <random>
#include <fstream>

using namespace std;

void gen_data(uint32_t len,     // length of the data
              ostream &out      // output stream
              )
{
  uint32_t n, N=0;
  mt19937 gen(0);
  geometric_distribution<uint32_t> rand(0.3);
  int k=0;
  while(true){
    n = rand(gen);
    N += n;
    for(int i=0;i<n;++i){
      out.write((char*)&k, sizeof(uint32_t));
    }
    if(N>len) break;
    k++; k=k%2;
  }
}

void gen_data_toy(ostream &out      // output stream
                  )
{
  vector<int> x = {7,5,4};
  int k=0;

  for(auto xi : x){
    for(int i=0;i<xi;++i){
      out.write((char*)&k, sizeof(uint32_t));
    }
    k++; k=k%2;
  }
}

int main(){
  ofstream out("test.binary");
  gen_data(1000000, out);
  out.close();

  ofstream out2("toy.binary");
  gen_data_toy(out2);
}