tek5​/rangecoder のバックアップソース(No.2) :: OSASK計画

• 差分^[1] を表示
• 現在との差分^[2] を表示
• tek5/rangecoder^[3] へ行く。

* tek5で使われているレンジコーダの原理を紹介するページ
-(by [[K]], 2004.09.19)
-l2d3とかtek0とかUC0とかは（まあ）分かるけど、レンジコーダってなによ、どうしてそんなもので小さくなるのよ、ってたまに聞かれるので、適当に説明。

*** 非常に大雑把な説明
-どんなデータもビットの集まりです。だから1ビットを出力するのに平均0.5ビットしか要しなければ、データは半分にできます。そんなうまい話があるもんか、というのは当然の疑問ですが、そんなうまい話があるのです。
-たとえば"0"のビットと"1"のビットの割合が半々だったとします。このとき、"0"を出力するのに1ビット要して、"1"を出力するのにもやはり1ビットを要します。これはあたりまえの結果で、とりあえず不思議はありません。
-今度は、"0"のビットがやたらと多くて、"1"のビットがあまり出現しないと分かっているとします。このとき、たった1つの"1"を出力するのに3bitも要する代償として、1つの"0"を出力するのに0.5ビットくらいしか使わないでいいということができるのです。
-本当はここから算術圧縮やその改良型であるところのレンジコーダを解説するべきなのですが、そういう高度なことは他のページのほうが詳しいですし、ここではそれを読みたくない（理解したくない）という人がなんとなく雰囲気をつかんでもらうことを意図しているので、他の（いいかげんな）説明で行きます。

*** 手法は違うけど、分かりやすそうな考えかた
-算術圧縮やレンジコーダの説明抜きで、1ビットをより少ないビットで出力する例を紹介します。これを読めば、きっとなんとなく分かったつもりにはなれます。
-まずここで、魔法のテーブルを考えます。
|デコード|1|01|001|0001|00001|000001|0000001|0000000|
|エンコード|000|001|010|011|100|101|110|111|
-このテーブルはこう使います。たとえば010001100000000000000000を出力したいときは、
--01_0001_1_0000000_0000000_000
-と分解して、
--001_011_000_111_111_111
-と出力します（後ろには適当に0を補った）。これなら24ビットを18ビットで出力できたことになります。
-この例ですと、"1"を出力するのに3bit要しますが、"0"は最小で0.429ビットで出力できています。これが1ビットをより少ないビットで出力できるという分かりやすい例だと思います。
-ちなみにレンジコーダのほうがもっと柔軟で拡張性のある考え方ですが、とにかく1ビットを1ビット未満の長さで出すという発想は同じなのです。

* こめんと欄
#comment

• tek5/rangecoder のバックアップ一覧^[6]
• tek5/rangecoder のバックアップソース(No. All)
  • 1: 2004-09-20 (月) 03:09:31^[7]
  • 2: 2004-09-20 (月) 03:09:31
  • 3: 2004-09-20 (月) 19:17:23^[8]
  • 4: 2004-09-20 (月) 21:54:01^[9]
  • 5: 2004-10-08 (金) 18:18:05^[10]
  • 6: 2004-10-08 (金) 18:18:05^[11]
  • 7: 2009-11-17 (火) 12:07:39^[12]
  • 現: 2024-01-08 (月) 12:59:04^[13] k-tan^[14]