« Tritonn (MySQL+Senna) の join を高速化 | メイン | Range Coder の展開速度を SSE で高速化 (してもらった) »
2008年02月22日
Range Coder の終了処理
CodeZine：高速な算術圧縮を実現する「Range Coder」（算術圧縮, データ圧縮, Range Coder）等を見ていると、多くの Range Coder の実装では、終了処理において冗長な出力をしているようです。
私の理解と記憶が正しければ、予測の上限値と下限値が異なる最初のビットまで出力すれば、残りのビットの出力は不要なはずです。Range Coder が一般化する以前の、ビット単位の操作を行っていた Jones 符号化器はそのような実装がされていたように思うのですが、Range Coder で速度を稼ぎ始めた時に、この点が見過ごされるようになったのでしょうか。
もちろんデータサイズが大きい際は、この点に起因する数バイトの無駄は問題はならないのですが、小さなデータを多数、静的テーブルを用いて圧縮するような場合は、無視できない影響が発生します。奥は Range Coder をちゃんと見たのは昨日が初めてなので、理解が間違っているかもしれませんが、備忘録をかねてブログエントリに起こしておきたいと思います。
21:56追記: CodeZine 上にある岡野原さんのコードは BSD ライセンスらしいので、奥の改変版を /lang/cplusplus/range_coder/range_coder.hpp - CodeRepos::Share - Trac にコミットしました。よろしければご覧ください。
投稿者 kazuho : 2008年02月22日 20:55 
トラックバック
このエントリーのトラックバックURL:
http://labs.cybozu.co.jp/cgi-bin/mt-admin/mt-tbp.cgi/1779
コメント
普通に考えると速度問題だと思います。とくにデコード速度。
rangeの値が小さくなったらストリームから読み込む、という
実装に「ファイル末尾だったら～」という条件判断を加える
のがいやだったのではないでしょうか。
まあファイルをまとめて読み込み、ファイル終端に相当する
場所のさらに後ろに数バイト0を書いておけば良いだけという
気もしますが。
ちなみにシンボル検索速度の関係で私の周りではあらゆる局
面で二値range codeばかりとなってしまいました。
おかげで「あれSSEなんて使って検索する場面あったっけ」
などと考え込んでしまいました…
投稿者 とみながたけひろ : 2008年03月03日 00:39