「ゲームプログラミング/画像ファイルの作成プログラム」の版間の差分

削除された内容 追加された内容
→‎ASCII文字の英文の圧縮の原理: ハフマン符号との関連
1,151 行
|}
 
 
一方、距離符号の拡張ビットの対応表は、別に定められている。下記のように 0x00 ~ 0x1D の距離で 1 ~ 32768 の距離に対応させています。
このように下段の大きい数値ほど拡張ビット数も増えている理由は、使用頻度の高いと考えられている短い一致長さほど、保存に要する容量も小さくすることで、より効率的に圧縮できる、というアイデアである。なお、このようなアイデア(使用頻度の高いものにほど短い符号を割りえてることで容量節約するアイデア)を「'''ハフマン符号'''」という。
 
数学書などでの「ハフマン符号」の説明では、確率論などを使って厳密に 使用頻度 が定式化されたりするが、しかし本ページで語るような実際の応用では、そんなに厳密に確率計算する必要はない。実際、上記の対応表も、別に確率方程式などから算出されたわけではないだろうし、表のどこにも確率計算は無い。
 
 
拡張ビットでは、表現できる値からの不足分の数値を表記する。
 
たとえば基準値 0x10A では 13~14の表現範囲だが、これで14を表現したい場合、
 
13に1をプラスすれば1になるので、
:0x10A 1
のように表現される。0x10Aの拡張ビット数は「1」と決まっているので、10A の次の「1」と書かれた1ビットを読み取った時点で、自動的に拡張ビットの終わりだと判断される。
 
 
さて一方、(一致長さの符号ではなく)距離符号の拡張ビットの対応表は、別に定められている。下記のように 0x00 ~ 0x1D の距離で 1 ~ 32768 の距離に対応させています。
 
{| class="wikitable"
1,198 ⟶ 1,213行目:
 
:※ 0x1B と 0x1C とで拡張ビット数が違うのは誤差ではなく仕様。
 
== 拡張ビットの一覧 ==
{| class="wikitable"
|+ 長さ符号の拡張ビットの対応表
!  値 !! 一致長さ !! 拡張ビット数
|-
! 0x101 (257)
|  3 ||  0
|-
! 0x102 (258)
|  4 ||  0
|-
! 0x103 (259)
|  5 ||  0
|-
! 0x (260)
|  6 ||  0
|-
! 0x (261)
|  7 ||  0
|-
! 0x (262)
|  8 ||  0
|-
! 0x (263)
|  9 ||  0
|-
! 0x (264)
|  10 ||  0
|-
 
! 0x (265)
|  11~12 ||  1
|-
! 0x (266)
|  13~14 ||  1
|-
! 0x (267)
|  15~16 ||  1
|-
! 0x (268)
|  17~18 ||  1
|-
 
! 0x (269)
|  19~21 ||  2
|-
! 0x (270)
|  23~26 ||  2
|-
! 0x (271)
|  27~30 ||  2
|-
! 0x (272)
|  31~34 ||  2
|-
 
! 0x (273)
|  35~42 ||  3
|-
! 0x (274)
|  43~50 ||  3
|-
! 0x (275)
|  51~58 ||  3
|-
! 0x (276)
|  59~66 ||  3
|-
 
 
! 0x (277)
|  67~82 ||  4
|-
! 0x (278)
|  83~98 ||  4
|-
! 0x (279)
|  99~114 ||  4
|-
! 0x (280)
|  115~130 ||  4
|-
 
 
! 0x (281)
|  131~162 ||  5
|-
! 0x (282)
|  163~194 ||  5
|-
! 0x11B (283)
|  195 ~ 226 ||  5
|-
 
! 0x11C (284)
|  227 ~ 257 ||  5
|-
 
 
! 0x11D (285)
|  258 ||  0
|-
|}