ランレングス圧縮におけるWyle符号とか

・・・・イケマセン、また少しあいてしまいました。
復活しなきゃーと思うんですが、先週は遊びほうけすぎてまだまだリハビリ失敗なので、先週末になんかやってた話とかで誤魔化そうとか。。。

ある日のこと

とある圧縮の本を見ていたら最初のほうにランレングス圧縮のことが書いてあって、そのビット表現としてWyle符号のことが書いてありました。

詳解 圧縮処理プログラミング

Wyle符号とは可変長表現の１つで、MHのよーなかんじでランレングスにおいて頻度高そうな「小さい値」に少ないビットを割り当てる方法です。
要するに必要となるビット長に応じて語頭条件を満たすプリフィックスを追加するだけ。そこにあったのはこんなの。

符号	値
0xx	1〜4
10xxx	5〜8
110xxxx	9〜16

　　　 :
　　　 :

ある意味イケテマセン。

勘のいい人ならピンと来たかもなのですが、この符号表だと要するに後ろのビット列は単純に普通のbinaryで、必要bit数-2個の1がついているだけになってます。更にランレングス用に0は無いものとして扱ってるみたい。

反論

なんつーか、このままだともったいない。 10000 〜 10011とか無駄にしてるわけです。なんだろうハードで実装しやすいように？
まあ詰めてみようかと。そうしたら

符号	値
0xx	1〜4
10xxx	5〜12
110xxxx	13〜28

　　　 :
　　　 :

当然だけどより大きな値でも縮まるはずで有利なはず。はてはてソフトウェアの本のはずなのになぜこんなもったいない事を。。。何か問題があるんだろうか？　というのを検証してみたくて、昼休みにソッコーで書きました。

方針

めんどくさいので bitstringも使わずに単純に文字列で二進数吐かせて、換算するってー手抜きで（時間無かったの＞＜）。対象は２値画像。ImageMagickであらかじめ変換しておきます。あとrunlength符号方式は0, 1交互に数値を並べるという方式。
この条件で8bit固定のもの(Fixed)と、本で紹介されていた普通のWyle(Wyle)、詰めたmodified-Wyle(Myle)、で比べてみました。

実装

def format(x, digits):
    return ("{0:0>%db}" % digits).format(x)

def effective_bits(x):
    b = 0
    while x:
        x >>= 1
        b += 1
    return b

def wyle(x):
    """
    return wyle coded bit-string.

    Example:
    >>> wyle(1)
    '001'
    >>> wyle(10)
    '1101010'
    >>> wyle(59)
    '11110111011'
    >>> wyle(20)
    '111010100'
    """
    b = effective_bits(x)

    if b <= 2:
        b = 0
    else:
        b -= 2
    return "1"*b + "0" + format(x, b+2)

def elyw(s):
    """
    do reverse conversion wyle coding

    Example:
    >>> elyw( '001')
    1
    >>> elyw( '1101010')
    10
    >>> elyw( '11110111011')
    59
    >>> elyw( '111010100')
    20
    """
    return int(s[s.find('0'):], 2)

def myle(x):
    """
    return modified wyle coded bit-string.

    Example:
    >>> myle(1)
    '001'
    >>> myle(10)
    '10110'
    >>> myle(59)
    '111011111'
    >>> myle(20)
    '1101000'
    """
    mask = 4  # 0b11
    b = 0
    while x >= mask:
        x -= mask
        mask *= 2
        b += 1

    return "1" * b + "0" + format(x, b+2)

def elym(s):
    """
    do reverse conversion modified wyle coding

    Example:
    >>> elym( '001')
    1
    >>> elym( '10110')
    10
    >>> elym( '111011111')
    59
    >>> elym( '1101000')
    20
    """
    b = s.find('0')
    if b:
        diff = (2**b-1)*4
    else:
        diff = 0

    return int(s[b:],2)+diff

def length(s):
    return s.find('0')+2

def _test():
    import doctest
    doctest.testmod()

if __name__ == "__main__":
    _test()

なんつー安易な関数名w　わかりにくい*1

まずは、とりあえずこんな画像を使ってみました。
＊フォントにこちらhttp://moonglow.moo.jp/index.html　のWontaフォントを使わせてもらってます。
＊＊　リンクウェアだったの忘れてた！！！ごめんなさいごめんなさい

普通にbitmapなら696x160/8=13.6KBなファイル。こんな感じ。

　　　[      fixed,       wyle,     myle ]
サイズ['2.48KB', '2.46KB', '2.12KB']
比率　['18.23%', '18.10%', '15.60%']

へえ、結構fixedがんばるなあ。逆変換スクリプトも書いてみて、ちゃんと元に戻る事を確認。なんか当たり前なんだけど嬉しい

バリエーション

フォントっぽい

400x400/8=19.5KB

['17.86KB', '10.75KB', '9.62KB']
['91.42%', '55.05%', '49.25%']

イラストっぽい

640x480/8=37.5KB

['17.91KB', '14.29KB', '12.62KB']
['47.77%', '38.10%', '33.66%']

自然画っぽい

480x640/8=37.5KB

['20.35KB', '13.57KB', '12.24KB']
['54.28%', '36.20%', '32.65%']

雑感

へー、単純にwyleにするだけでかなり効果あるんだなー。とか思いました。wyle->myleは確かに労するだけの価値があるか微妙。
あと中にはもっと上手い事

符号	値
0xx	1〜4
10xx	5〜8
110xxx	9〜16

　　　　 :
　　　　 :

として、より小さい場合に有利にしているのもあるみたいです。FAXとかだと効いてきそう。

結論

は先延ばし

*1:本来 wyleも myleも　fixedと違って 0 は不要ですが、勘違いしていたので 0を含んでしまってます。ごめんなさいごめんなさい。本来はもうほんのすこし小さくできるかも。（誤差ですが）