今回は遥か昔に失われた化石programを紹介します。これはかつてDO++というweb siteで公開されていたもので、最新版は2004/11/28です。
時は流れ2010年代初頭にsite消滅。web archiveでもprogramは入手不能のようです。
そんなどうでもいいかもしれない歴史的背景はさておき、本題にすり替えていきます。
現在の入手先
執筆者のgithub
ただし、原作者も示唆している通り、bugがあります。修正して頂ける方は大歓迎
概要
SP partial decodable compression
SPはStatic PPMを用いたData圧縮programです。従来のData圧縮法と比較し次の特徴があります。
- 全体を復元せずに任意の部分のみを復元可能
- 大きいfileに対して圧縮率はbzip2と同程度。小さいfileではgzipと同程度
- 復元処理の計算量、領域量は従来の高圧縮率の手法(BWTやPPM)と比較して小さい
問題点と対策
非歪みData圧縮法として主流の一角を成している PPM法は、全て動的、つまりDataを調べていくとともに圧縮に用いられるmodelも変わっていくものである。
それに対し静的PPM法は、最初にDataを調査し、model化をした後にそのmodelを圧縮されたDataと一緒に出力し、Dataを圧縮、復元する際には同じmodelを用いてPPMを行うというものである。
この静的PPM法という技法がなぜ今まで用いられなかったかというと、modelを出力すると、この部分が非常に大きくなるためと考えられる。
例として、静的 Order-2 PPM を考えると、この場合のmodel化は、ある文字が出現した際に、次にどのような文字がでてくるかという確率構造を調べるというものである。
これを通常の文字で考えた場合 256 の文字それぞれの次に 256 種類の文字が出現する可能性があるためこれを全て出力するには 256 x 256 個の確率情報が必要である。これと同様に OrderN であると、最悪 256 の n 乗個の確率情報が必要であり、このmodelを出力しようとすると非常に大きなoverheadとなる。そのため今までPPMというのは動的であるというのが主流であった。
model化したDataを効率よく出力する方法がある。これは、文字の出現確率と出現順位は反比例するという Zipfの法則に基づいており、確率情報を最小二乗法で近似し、関数で出力するというものである。
abababacacadad
一例として上述のDataの場合、a の次に b が 3/7、cが 2/7、d が 2/7 の確率で出現するという情報がmodel化の際に必要である。
そこで、文字の出現確率の対数をとり、これを最小二乗法で近似し、この傾き、切片の情報、そして文字の順番を出力する。この際に必要なのは文字の順番、傾き、切片だけである。実際にこの考えを用いた圧縮programを作ってみたところ非常に良い結果がみられた 。Order3 の静的 PPM 法で、LHA や ZIP に匹敵する性能を見せている。
任意位置からの復元方法
一定間隔置きに前のDataとの依存関係が無いData圧縮をし、その位置をindex情報として保持しておく。復元する時は、復元したい場所の直前の、依存関係が無いDataまでindexで移動し、そこから復元する。
余談
なぜ今更こんな化石を掘り起こしたかと言うと、約15年前に死亡したPCから奇跡的にDataを取り出せたからです。
それはともかく静的PPMの例は1993?、1997年に既に登場している模様。その実装がこれ。