東大の演習問題に挑戦(2) - 圧縮・解凍編

GCC

もう一個いっとこー

課題2-A：データを圧縮・解凍するプログラムを実装せよ。

が・ガンバリマス。

方針

超簡単なランレングス符号でいっときます。

  • aaaaというデータがあったら、[4 a]として保存。1個の場合はaとします。
  • 日本語は考えないということで、数にあたるデータなら、バイトの1個目をフラグにしておきます。

サボりすぎ!?

圧縮

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int c, d;
    int n = 1;

    c = getchar();

    while (c != EOF) {
        d = getchar();

        if (c == d)
            n++;
        else {
            if (n != 1)
                putchar(n | 0x80);
            putchar(c);
            n = 1;
        }

        c = d;
    }

    return EXIT_SUCCESS;
}

こんだけ。すげー簡単。

解凍

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int c, d, i;

    while ((c = getchar()) != EOF) {
        if ((c & 0x80) == 0x80) {
            d = getchar();
            for (i = 0; i < (c & ~0x80); i++)
                putchar(d);
        } else
            putchar(c);
    }

    return EXIT_SUCCESS;
}

短いな。

早速

圧縮だけ。

% ./compress
abbcccddddeeeee
a&#65533;b&#65533;c&#65533;d&#65533;e

バイナリになりました。

圧縮&解凍もしてみる。

% ./compress | ./uncompress
abbcccddddeeeee
abbcccddddeeeee

元に戻った!!

課題とか

  • あんまり長いデータだと元に戻りません(汗
  • あ、文字側にフラグを付けた方がよかったかも。
  • バイナリファイルの取扱いがイマイチよくわかってない事が判明。
  • バイナリ上で混在するデータを取り扱えるようになりたいなぁと思う。

まだまだ修行が足りません。

次は飛ばそうかと

スパムフィルタは、

  • 実装方法(どんなデータを、どのようにフィルタリングしたらよいか)がよくわからない。
  • 類似の問題に出会っているのかわからない。

という理由でトバス。「いかにして問題をとくか」がすげー役立ってるな。


簡単にやるなら、grep -vか。○○にマッチしたら表示しない。受け取らない位しか発想出来ない。

追記 1

おぉっと。C言語による最新アルゴリズム辞典のハフマン符号の所に、0と1で入出力するライブラリがありました。

bitio.c

使えそう。写経しよう。

追記 2

追記1を使って、発展バージョンを考えると、

  • 例えばa-zA-Zを固定長6ビットに符号化。
  • ついでに連長フラグを1ビット。
  • で、連長個数、7(任意)ビット割り当てる。

と出来そうだ。更に圧縮可能。


もうちょっと発展バージョンを考えると、

  • 符号化には符号化テーブル(木)を作成する。ハフマンとか。SICPに書いてある。
  • 連長圧縮ではなく辞書テーブル(木)を使う方法。LZ法とか。組んだことが無い。

もうちょっと発展バージョンは、「木が必要」なのでスゲー大変だ。数学の山がわんさか出てくる。深く突っ込むとヤバイヨ〜。


LZ法は今度やろうと思う。