圧縮の重要性 - KIWAM_KEN

パターン認識する予定でしたがちょっと変更します。

学部3年の時から今の研究室に配属されて、今まで僕自身いろいろな大規模データを扱ってきました。そして扱った数だけ研究室のサーバを吹っ飛ばしました（笑）

大規模なデータを扱う際には、サーバのメモリを考えてあげないとサーバ管理者にぶつぶつ言われることになります…汗

メモリをなるべく消費しないようにするには、プログラムの中身を工夫するのもいいですが、扱うデータを圧縮するという考えもあります。

今回は、数値の羅列を想定します。文字列の圧縮に関しては、様々なアルゴリズムがありますのでそちらを参考に。この本にも書かれていますよ。

[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB+DB PRESS plusシリーズ)

posted with amazlet at 11.10.01

伊藤直也田中慎司
技術評論社
売り上げランキング: 6600

Amazon.co.jp で詳細を見る

例えば、16*16のマス目に描かれた手書き文字があったとします。ここで、各マス目は256階調のグレースケールで表現されているとします。つまり、一つの文字を表すのに、784次元(16×16)のベクトルであらわすことができます。

このデータを素直に表現するならば、文字数×784の行列であらわされます。

ここで、文字数が少なければこのままでもいいかもしれませんが、これが数十万もの文字を読み込むことがあったとすれば、かなりのデータ量になりそうです。

そこで、データの特徴を利用して、このデータを圧縮することを考えます。このデータ、784次元のベクトルであらわされているとは言ったものの、ほとんどのマス目は使われていない。つまり、グレースケールで言えば「0」の部分がたくさんある行列（疎行列）になっています。ここで、0を保持しておくのは無駄なような気がします。そこで、0を消してしまうことで、データを圧縮します。

方法としては、

0 255 0 15 0 0 128 64 0 0

という10次元のベクトルを

2:255 4:15 7:128 8:64

と表現します。2番目のマス目は255、4番目のマス目は15・・・という風にしてあげるだけです。研究室では、これが通常のフォーマットとなっています。当たり前だと感じた方はそっとブラウザの戻るボタンをｒｙ

一見大して効果が見込めなさそうですが、各ベクトルが疎であればあるほど絶大な効果が生まれます。

この手書き文字データを10000*784の行列で素直に表すと17,852KBになります。これを先ほどのような表現にすると、11,435KBに圧縮することができます。ただし、その後の処理のために余計な数字を付け加えたりしているので、実質はもっと小さくなります。

正直今回の例で挙げたデータでは大したことないかもしれませんが、これがテキストデータをbag-of-wordsで…という話になると、相当効果があります。

プログラムはこんな感じで（fn2（2つめの引数）はラベルづけに使っているだけなので、今回の内容とは関係のない部分です。）

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

int Dm=10000, Dn=784;
int *VecA;
std::vector < vector <int> > MatA;
std::vector < vector <int> > MatB;

void readValue(char *fn1,char *fn2,char *fn3){
  ifstream fin;
  ofstream fout;
  int i, j, s, k, l, m;
  fin.open(fn1);
  if(!fin){
    cerr << "ERROR: Failed to open file" << endl;
    exit(1);
  }
  MatA.resize(Dm);
  MatB.resize(Dm);
  for(i = 0; i < Dm; i++){
    for(j = 0; j < Dn; j++){
      fin >> l;
      if(l != 0){
	MatA[i].push_back(j);
	MatB[i].push_back(l);
      }
    }
  }
  fin.close();
  fin.open(fn2);
  if(!fin){
    cerr << "ERROR: Failed to open file" << endl;
    exit(1);
  }
  VecA = new int[Dm];
  for(i = 0; i < Dm; i++){
    fin >> s >> k;
    VecA[i] = k;
  }
  fin.close();
  fout.open(fn3);
  fout << Dm << " " << Dn << endl;
  for(i = 0; i < Dm; i++){
    fout << MatA[i].size() << " ";
    for(j=0;j<MatA[i].size();j++){
      fout << MatA[i][j] << ":" << MatB[i][j] << " ";
    }
    fout << VecA[i] << endl;
  }
fout.close();
}

int main(int argc, char **argv){
  srand(time(0));
  readValue(argv[1],argv[2],argv[3]);
  cout << "print OK\n";
}

もしかしたらどこでも当然のようにこういった圧縮を行っているかもしれませんが、ちょっと圧縮についての書物（さっきの）を読んだりしていたので、書いてみました。