2010年8月27日金曜日

なんちゃってランレングス圧縮


view plainprint?
  1. #include <iostream>  
  2. #include <string>  
  3. #include <cstring>  
  4. #include <fstream>  
  5. using namespace std;  
  6.   
  7. void Compress(string inputFileName, string outputFileName);  
  8. void UnCompress(string inputFileName, string outputFileName);  
  9.   
  10. int main(int argc, char** argv)  
  11. {  
  12.     if (argc < 3)  
  13.         return 0;  
  14.   
  15.     if (! strcmp(argv[1], "nz"))  
  16.     {  
  17.         Compress(argv[2], argv[2]);  
  18.         cout << "Compressed file is " << argv[2] << ".nz" << endl;  
  19.     }  
  20.     else if (! strcmp(argv[1], "unz"))  
  21.     {  
  22.         string outputFileName(argv[2]);  
  23.         string::size_type index = outputFileName.rfind(".nz");  
  24.         if (index != string::npos)  
  25.             outputFileName = "Unz" + outputFileName.substr(0, index);  
  26.         else  
  27.             return 1;  
  28.   
  29.         UnCompress(argv[2], outputFileName);  
  30.         cout << "Extracting file is " << outputFileName << endl;  
  31.     }  
  32.   
  33.     return 0;  
  34. }  
  35.   
  36. void Compress(string inputFileName, string outputFileName)  
  37. {  
  38.     outputFileName += ".nz";  
  39.     ifstream fin(inputFileName.c_str(), ios::in | ios::binary);  
  40.     ofstream fout(outputFileName.c_str(), ios::out | ios::binary);  
  41.   
  42.     if (! fin || ! fout)  
  43.         return;  
  44.   
  45.     int delimiterPre = 0;  
  46.     int delimiterPost = 0;  
  47.     int rawByte, preByte, num = 0;  
  48.     preByte = fin.get();  
  49.   
  50.     while ((rawByte = fin.get()) != EOF)  
  51.     {      
  52.         if(rawByte != preByte || num == 255)  
  53.         {  
  54.             if (num > 1)  
  55.             {  
  56.                 fout.write((char*) &delimiterPre, sizeof(char));  
  57.                 fout.write((char*) &delimiterPost, sizeof(char));  
  58.                 fout.write((char*) &num, sizeof(char));  
  59.             }  
  60.             fout.write((char*) &preByte, sizeof(char));  
  61.             preByte = rawByte;  
  62.             num = 1;  
  63.         }  
  64.         else if (rawByte == preByte)  
  65.             num++;  
  66.   
  67.     }  
  68.     if (num > 1)  
  69.     {  
  70.         fout.write((char*) &delimiterPre, sizeof(char));  
  71.         fout.write((char*) &delimiterPost, sizeof(char));  
  72.         fout.write((char*) &num, sizeof(char));  
  73.     }  
  74.     fout.write((char*) &preByte, sizeof(char));  
  75.   
  76.     fin.close();  
  77.     fout.close();  
  78. }  
  79.   
  80. void UnCompress(string inputFileName, string outputFileName)  
  81. {  
  82.     ifstream fin(inputFileName.c_str(), ios::in | ios::binary);  
  83.     ofstream fout(outputFileName.c_str(),ios::out | ios::binary);  
  84.     if (! fin || ! fout)  
  85.         return;  
  86.   
  87.     int rawByte, preByte;  
  88.     preByte = fin.get();  
  89.   
  90.     while ((rawByte = fin.get()) != EOF)  
  91.     {  
  92.         if (preByte == 0 && rawByte == 0)  
  93.         {  
  94.             while ((preByte = fin.get()) == 0)  
  95.                 fout.write((char*) &preByte, sizeof(char));  
  96.   
  97.             rawByte = fin.get();  
  98.    
  99.             for (int i = 0; i < preByte; i++)  
  100.                 fout.write((char*) &rawByte, sizeof(char));  
  101.   
  102.             if ((preByte = fin.get()) == EOF)  
  103.                 break;  
  104.         }  
  105.         else  
  106.         {  
  107.             fout.write((char*) &preByte, sizeof(char));  
  108.             preByte = rawByte;  
  109.         }  
  110.     }  
  111.   
  112.     if (preByte != EOF)  
  113.          fout.write((char*) &preByte, sizeof(char));  
  114.   
  115.     fin.close();  
  116.     fout.close();  
  117. }  

上のコードでの実行に起因する損害に関して責任を持ちません．
 あと，世の中の高専生はもっと賢いです．こんなコードは書きません．

上のコードは１バイト単位でデータのランレングス圧縮を行うようなものです．
俺，実は学校でデータ圧縮に関して何かやらなきゃいけない立場なようで，
バイナリでデータを扱う練習がてら作ってみたものなんですが，
圧縮になるときと，ならないときが出てきちゃう，ダメダメなものになってしまいました．

ここで簡単にランレングス圧縮の説明ー．
文字列Zeeeeeeeingってなのを考えたとき，
連続した文字に注目して文字列中に数字が出てこないとして，
数字＋文字で数字の数だけ文字があることを表すとすれば
文字列Zeeeeeeeingのeは7eと省略でき，最終的に
Z7eingとすることで文字列長を１０から６に圧縮でき，
確かこんな操作を行う圧縮をランレングス圧縮と呼ばれる（たぶん）．

で，上のコードも１バイト読み取ってそんな操作を行っているんですが，
デリミターで問題？が生じた結果， 圧縮にならないときが生じてしまいました．
ここでデリミターは繰り返しがある位置を表す区切り文字のこととします．
上のコードではデリミターを0x0000にしています．
で0x0000 (文字の繰り返し回数) (繰り返し文字) と 4バイトでランレングス圧縮を試みてるんですが，
これだと5回以上連続で文字が出現しない限り，圧縮にならないことになります．
そこで，4回以下はそのまま出力すればいいやと思っていたら，
0x0000 の表記があった場合それがデリミターか単なる?0x0000なのか
区別がつかなくなることに気がつき，どうしようもなく，そのままにしてあります．
おそらく2回連続は良くある？ので３回以上はランレングス圧縮するようにすれば良くなるかもですが・・・．
で，最終的に上のコードが言いたいことは，１バイト単位でやってもそんな圧縮にならんってことです（たぶん）．

圧縮に関しては， 卒研より相当締切り日的なものが近く，
どうにかしなければならないので，今からで遅すぎますが，
どうにかして行きたいと思います．

ちなみに上のコードでC++で書いたHelloを出力する
実行ファイルを圧縮してみたところ，7783 bytesとから 6365 bytesと
見事に微妙に圧縮されました．
他のファイルではデリミッター問題？で元より増加してしまいました（ダメダメです）．

使い方
コンパイル
g++ -o RunLength このコードファイル名.cpp

圧縮 (例としてhelloファイルの圧縮)
./RunLength nz hello
でhello.nzってな圧縮ファイルが作成される．

解凍（伸長）
./RunLength unz hello.nz
でUnzhelloってな解凍ファイルが作成される．

helloとUnzhelloが同じファイルであることを切に願います．
投稿者 時刻:
ラベル:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)