DMC(Dynamic Markov Coding)のによるデータ圧縮プログラムを書いてみた - 遥かへのスピードランナー
最近Managing Gigabytes勉強会に参加しているのでせっかくなので、この本に載っているアルゴリズムを使ってプログラムを組んでみました。 今回実装したのは、「2.5 SYMBOLWISE MODELS」の後半で説明されている「Dynamic Markov Coding(DMC)」です。書籍の他に、元論文「G. Cormack and R. Horspool, "Data compression using dynamic Markov modelling,"」を参考にしました。 実装はC++で行い、ソースはgithubに置きました。（CentOS 5.2+gcc 4.1.2で動作確認済） http://github.com/thorikawa/MG/tree/master/dmc 以下、アルゴリズムの概要と実装上の工夫などをまとめてみます。 意見・指摘などは絶賛大歓迎です。 DM
Interpolative coding - tsubosakaの日記
今日のInterpolative codingの話が面白かったのと復号の部分のコードが必ずしも自明ではないかと思ったのでメモ。 Interpolative codingは長さと出てくる値の最小値、最大値が分かっている狭義単調増加な自然数のリストを圧縮する方法である。 ここで最大値とはリストの最大値ではなく、たとえば転置リストであれば最大の文書IDなど圧縮を行う際に出てきうる値の最大値である。 Interpolative codingの基本的な考え方としてはたとえば1から20までの数が表れるとわかっておりかつリストの長さが20であるということが分かっていれば、なにもデータがなくてもリストが[1..20]であるとわかるということに基づいている。 ここでは例で説明する。長さ7のリスト<7;3,8,9,11,12,13,17>を圧縮することを考える。またここで出てくる数の最大値は20であることが分
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
