2010年8月27日金曜日

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


#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
using namespace std;

void Compress(string inputFileName, string outputFileName);
void UnCompress(string inputFileName, string outputFileName);

int main(int argc, char** argv)
{
    if (argc < 3)
        return 0;

    if (! strcmp(argv[1], "nz"))
    {
        Compress(argv[2], argv[2]);
        cout << "Compressed file is " << argv[2] << ".nz" << endl;
    }
    else if (! strcmp(argv[1], "unz"))
    {
        string outputFileName(argv[2]);
        string::size_type index = outputFileName.rfind(".nz");
        if (index != string::npos)
            outputFileName = "Unz" + outputFileName.substr(0, index);
        else
            return 1;

        UnCompress(argv[2], outputFileName);
        cout << "Extracting file is " << outputFileName << endl;
    }

    return 0;
}

void Compress(string inputFileName, string outputFileName)
{
    outputFileName += ".nz";
    ifstream fin(inputFileName.c_str(), ios::in | ios::binary);
    ofstream fout(outputFileName.c_str(), ios::out | ios::binary);

    if (! fin || ! fout)
        return;

    int delimiterPre = 0;
    int delimiterPost = 0;
    int rawByte, preByte, num = 0;
    preByte = fin.get();

    while ((rawByte = fin.get()) != EOF)
    {    
        if(rawByte != preByte || num == 255)
        {
            if (num > 1)
            {
                fout.write((char*) &delimiterPre, sizeof(char));
                fout.write((char*) &delimiterPost, sizeof(char));
                fout.write((char*) &num, sizeof(char));
            }
            fout.write((char*) &preByte, sizeof(char));
            preByte = rawByte;
            num = 1;
        }
        else if (rawByte == preByte)
            num++;

    }
    if (num > 1)
    {
        fout.write((char*) &delimiterPre, sizeof(char));
        fout.write((char*) &delimiterPost, sizeof(char));
        fout.write((char*) &num, sizeof(char));
    }
    fout.write((char*) &preByte, sizeof(char));

    fin.close();
    fout.close();
}

void UnCompress(string inputFileName, string outputFileName)
{
    ifstream fin(inputFileName.c_str(), ios::in | ios::binary);
    ofstream fout(outputFileName.c_str(),ios::out | ios::binary);
    if (! fin || ! fout)
        return;

    int rawByte, preByte;
    preByte = fin.get();

    while ((rawByte = fin.get()) != EOF)
    {
        if (preByte == 0 && rawByte == 0)
        {
            while ((preByte = fin.get()) == 0)
                fout.write((char*) &preByte, sizeof(char));

            rawByte = fin.get();
 
            for (int i = 0; i < preByte; i++)
                fout.write((char*) &rawByte, sizeof(char));

            if ((preByte = fin.get()) == EOF)
                break;
        }
        else
        {
            fout.write((char*) &preByte, sizeof(char));
            preByte = rawByte;
        }
    }

    if (preByte != EOF)
         fout.write((char*) &preByte, sizeof(char));

    fin.close();
    fout.close();
}


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

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

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

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

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

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

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

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

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

helloとUnzhelloが同じファイルであることを切に願います.

0 件のコメント:

コメントを投稿