https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%B3%E3%82%B8%E7%AC%A6%E5%8F%B7
レンジ符号ってほうは特許の問題がないみたい。
算術符号はすごくいい方法なのだと思うのだけど、特許問題がめんどくさいので近づかないほうがいい(らしい)。
いきなりこれをやるのはめんどいので、途中経過として、2種類の符号化表を圧縮しないタイプのファイル形式を定義して、それの圧縮、展開のコードを書くってのがいいのかな。
Deflate圧縮。fixedなほうのブロックは書けるようにしたんだけど、dynamicのほうのブロックは、ちょっとめんどくさいな。
literal/length用とdistance用の2種類のハフマンコード表を作る。それらの表は0から15までの数の列になる。で終わりのほうの0の連続は省略できる。
で、16が前の値の3から6回のくりかえしで、17が0の3から10回のくりかえしで、18が0の11から138のくりかえしとして、さらに表を短くできる。
その短くした表について、0から18までについてハフマン符号化する。
そうしてできた符号化表の符号化表と、それによって符号化された2つの表とをブロックの先頭につけ加えるみたいな話。
めんどい。
うわさんとのすたろうが会話してる。
のすたろう、なんで2回返事するの?
のすたろう、package-merge algorithmについて説明してください。
希少なコインを「使わざるを得なくなった」時に、収集家が「どのコインを使うか」を選ぶアルゴリズムが、ハフマン符号化のときに使えるという話。
パッケージ・マージ・アルゴリズムと呼ぶらしい。
https://qiita.com/ajinadai/items/9c02dc750bc017c93c8f
この記事に、わかりやすく書いてくれてた。
DeflateのRFCに「DeflateのHuffman符号はビット長が特定の長さを超えないという制約があるので、ちょっとややこしくなる。詳細はreferenceを見て」って書いてあるけど、referenceをたどるのがめんどくさいな。
たとえば「硬貨のみを使って、ある額を支払うときに何通りの組み合わせがあるか」という問題の解きかたが面白い。Haskellだと
foo _ 0 = 1
foo _ s | s < 0 = 0
foo [] _ = 0
foo ca@(c : cs) s = foo ca (s - c) + foo cs s
みたいになる(走らせてないのでバグあるかも)のだけど、ある硬貨のセットによる支払いの組み合わせの総数は、「特定のどれかの硬貨を使った場合の組み合わせの数」と「それを使わない場合の組み合わせの数」を足したものってのが基本的な考えかたになる。で、「使う硬貨の種類が0種類になる」かまたは「支払うべき金額が0になる」ところで計算が終わる。
なんか、ATプロトコルとATフィールドとをごっちゃにしてた。
リストの最後まで行ったら先頭にもどるタイプのデータは、つぎのように実装できる。
type Rot a = ([a], [a])
uncons :: Rot a -> (a, Rot a)
uncons (xs, []) = uncons (xs, xs)
uncons (xs, x : xs') = (x, (xs, xs'))
Deflate圧縮の実装、ちょっとめんどくさい感じがあって、で心理的に一番引っかかってるのが、マッチする長さを調べる部分なんだけど、入力を1バイトずつ取り出して、一致するかどうか調べる感じかな、と。
「読み込み位置」と「先読み中の位置」とを別々に管理できるようにしたほうが良さげ。つまり「先読みで読み込んだ部分」をバッファに保存しておいて、主となる読み込み部分は動かさない感じにする。そんな感じかな。
RFC 1951に書かれているDeflate圧縮のアルゴリズムについて。
もう今だと、だいたいパテントも切れてるみたいな話だけど、その当時パテントを気にしなくてもいいアルゴリズムとして記載されてたわけだけど、こんな感じ。
先頭3文字をキーにして、その文字列があらわれる位置を値にしてハッシュ表を用意する。チェインドなハッシュ表。つまり値は複数の位置を含むリンクトリストになっている。
読み込んでいる位置から3文字を先読みしてハッシュ表から位置を探す。複数の位置について、その後の入力に最も長くマッチするものを選ぶ。
で一文字進むのだけど、その時にハッシュ表に値を追加する。
これが基本的な感じ。あとは、決められた範囲よりも遠い値についてはハッシュ表から削除したほうが良さそう。
この基本に対して、圧縮率を上げるという側面と速度を上げるという側面とから、バリエーションがある。
圧縮率を上げるという側面を考えると、ある時点でマッチしたとしても、それで決めてしまわないで、もう一文字読み込んだ場合により長くマッチするかどうかを調べるというやりかたがある。
スピードを上げるという側面では、まず上記のバリエーションについて、ある程度以上長くマッチした場合には次の読み込み位置でのマッチは試さないというものがある。また、スピードがかなり重要という場面では、3文字のキーに対して、値が存在しないときだけ値を追加するとか、「長くマッチした」ものについてはハッシュ表に追加しないとかがある。
画像の圧縮にフーリエ変換を使うのは明らかに誤りだと思う。
もうすこしまともな非可逆圧縮はないのかな？