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

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

上のコードでの実行に起因する損害に関して責任を持ちません．

 あと，世の中の高専生はもっと賢いです．こんなコードは書きません．

上のコードは１バイト単位でデータのランレングス圧縮を行うようなものです．

俺，実は学校でデータ圧縮に関して何かやらなきゃいけない立場なようで，

バイナリでデータを扱う練習がてら作ってみたものなんですが，

圧縮になるときと，ならないときが出てきちゃう，ダメダメなものになってしまいました．

ここで簡単にランレングス圧縮の説明ー．
文字列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が同じファイルであることを切に願います．

5五将棋ってなボードゲームがあります

5五将棋 （Minishogi） の初期配置

現在ゲーム情報学で取り扱われているゲームの一つに

5五将棋と呼ばれる物があります．英語名ではMinishogiらしく，

その名の通り， 上図のような普通の？将棋を小さくしたようなボードゲームです．

今年日本で開催されるComputer Olympiad 2010でもShogi (5×5) 部門として開催されるようです．

UEC杯も開催されていて， 今年は12月4日に開催が予定されています．

囲碁は11月27日， 28日なので， 囲碁よりも遅い日程なんすね．

ルールは将棋と （駒の動きとか）は同じですが，細かいルールは

電通大の伊藤研究室が運営されてる5五将棋PORTALをご参照ください．

ゲームの探索空間は10⁶⁰より少ない程度だと考えられていて，

オセロより少ない位だと考えられているそうです．俺にはオセロより難しく見えるけど・・・．

今の状況として， 柿木さんが作成されているK55が強いみたいです．

確か学習ベースでRLGOみたいに， 自己対戦により評価方法を学習しているらしい．

噂によれば， 指せば指すほど強く（勝ち方を学習する）らしく， K55に勝つには一発勝負が大事とか・・・．

ちなみに上の図は，Qt 4.6.3 LGPL版で作成しているもので， 手抜き感maxですが作成してます．

理由は， Qtの導入です・・・． 前x3回のブログでQtに関する書籍少ないと書きましたが，

サンプルが結構充実してたりするんで， 何とかなりそうです．

AOJ Volume 0 Problem 0077 : Run Length

#include <iostream>
using namespace std;

int main()
{
    char ch, n;
    while (cin.get(ch))
    {
        n = '1';
        if (ch == '@')
            cin >> n >> ch;

        for (int i = 0; i < n - '0'; ++i)
            cout << ch;
    }

    return 0;
} 

まともに解きすぎてると思う．
もっと柔らかく思いつきたい．

てへっ

Hello with Qt

IDEの一つ，Qt Creatorを使ってみました．
動作は意外にサクサクしていて，雰囲気はVisual Studioと同じ感じでした．
QtってLGPLになってから結構普及したんだと思うのですが，実際どうなんだろう．
書籍は少ないし，やっぱ国内はVisual Studioで十分ってことなのかなぁ・・・。

AOJ Volume 1 Problem 0105 : Book Index

#include <iostream>
#include <string>
#include <set>
#include <map>
using namespace std;

int main()
{
    int n;
    string str;
    map<string, set<int> > m;
    map<string, set<int> >::iterator p;

    while (cin >> str>> n)
        m[str].insert(n);

    for (p = m.begin(); p != m.end(); p++)
    {
        cout << p->first << endl;
        set<int>::iterator q = (p->second).begin();
        for (; q != (p->second).end(); )
        {
            cout << *q;
            cout << (++q != (p->second).end() ? ' ' : '\n');
        }
    }

    return 0;
}

 一つの書き方としてありかも．
あと， 書き方を変えてみました． こっちの方が一般的？
確かFuegoも書き方はこんな感じだったと思う．
いろいろ見て， 見習っていきたい．

HTTP/1.1 400 Bad Request

これのお蔭で結構時間を無駄にした．
バグは単純なもので，GET要求の中でHTTP/1.1のところをHTTP1.1ってしてた・・・．
ま，これで当分はこのミスをしないってことで．

 時間は大切に．

AOJ Volume 5 Problem 0501 : Data Conversion

#include <iostream>
#include <map>
using namespace std;

int main() {
    int n;
    while (cin >> n, n) {
        map<char, char> conversion;
        map<char, char>::iterator p;
        for (int i = 0; i < n; i++) {
            char pre, post;
            cin >> pre >> post;
            conversion[pre] = post;
        }

        cin >> n;
        for (int i = 0; i < n; i++) {
            char ch;
            cin >> ch;
            p = conversion.find(ch);
            cout << (p == conversion.end() ? ch : p->second);
        }
        cout << endl;
    }

    return 0;
}

mapを使ってキーが見つからない場合はマップの末尾を指す反復子を返すことを利用している．
全然，コンピュータ囲碁プログラムの話題ができなくて，テーマ変わっちゃいそうですが，今必死に考え中です・・・．