/
628.txt
345 lines (266 loc) · 17.3 KB
/
628.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
* 仕様書
[REFS[
- [5] '''[CITE@en[RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3]] ([TIME[2016-01-10 18:30:17 +09:00]] 版) <https://tools.ietf.org/html/rfc1951>'''
-- [7] [CITE@en[RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3]] ([TIME[2016-01-10 18:30:17 +09:00]] 版) <https://tools.ietf.org/html/rfc1951#section-1>
-- [25] [CITE@en[RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3]] ([TIME[2016-07-03 09:57:20 +09:00]]) <https://tools.ietf.org/html/rfc1951#section-2>
-- [26] [CITE@en[RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3]] ([TIME[2016-07-03 09:57:20 +09:00]]) <https://tools.ietf.org/html/rfc1951#section-3>
]REFS]
* アルゴリズム
[12] [RUBYB[入力データ]@en[input data]]は、[[ブロック]]の連なりです。 [SRC[>>25]]
[14] [RUBYB[圧縮データ集合]@en[compressed data set]]は、
[[ブロック]]の[[系列]]です。 [SRC[>>25]]
[20] [[圧縮されたデータ部分]]は、[[要素]]の[[系列]]です。各[[要素]]は、
[RUBYB[リテラルバイト群]@en[literal bytes]]か、
[RUBYB[重複列への指示子]@en[pointer to duplicated strings]]かのいずれかです。 [SRC[>>25]]
[21] [[指示子]]は、[RUBYB[長さ]@en[length]]と、[RUBYB[前方向の距離]@en[backward distance]]との組で表されます。 [SRC[>>25]]
[17] [[距離]]は、 32KB [[以下]]です。すなわち、[[指示子]]は、[[入力データ]]の
32KB 前までの[[ブロック]]の[RUBYB[列]@en[string]]を参照できます。 [SRC[>>25]]
[22] [[長さ]]は、 258 バイト[[以下]]です。 [SRC[>>25]]
[23] [[リテラル]]と[[長さ]]は、[[ハフマン符号木]]を使って[[ハフマン符号]]で表します。 [SRC[>>25]]
[24] [[距離]]は、別の[[ハフマン符号木]]を使って[[ハフマン符号]]で表します。 [SRC[>>25]]
[19] [[ハフマン木]]自体も、[[ハフマン符号化]]により圧縮します。 [SRC[>>25]]
** ビット列の表現
[27] [[DEFLATE]] の出力は[[バイト列]]です。
[[バイト]]内の[[ビット順]]は規定されておらず [SRC[>>26]]、
[[プラットフォーム]]や[[プロトコル]]に依存します。
[29] [[多バイト]]の値は、重みの小さな[[バイト]]から順に並べた[[バイト列]]
[SRC[>>26]] ([[小エンディアン]]) とします。
[28] [RUBYB[データ要素]@en[data element]]を[[バイト列]]にする際には、
[[バイト]]の重みの小さな[[ビット]] ([[LSB]]) から順に詰めていきます。 [SRC[>>26]]
[30] [[ハフマン符号]]''以外''のデータ要素は、
当該データ要素の LSB から順に詰めていきます。 [SRC[>>26]]
[31] [[ハフマン符号]]は、重みの大きな[[ビット]] ([[MSB]])
から順に詰めていきます。 [SRC[>>26]]
** ハフマン符号化
[32] [RUBYB[接頭辞符号化]@en[prefix coding]]は、
事前に与えられた[RUBYB[字母]@en[alphabet]]の[RUBYB[記号]@en[symbol]]を、
ビット列 (符号) として表現するものです。ここで、ビット列は記号ごとに長さが異なりますが、
構文解析器が常に曖昧無く記号を認識できるようにします。 [SRC[>>26]]
[33] 接頭辞符号は、[[二分木]]を使って定義します。
[[枝]]が [N[0]] または [N[1]] のいずれかを表すこととします。
[[枝]]がいずれかの[[記号]]を表すこととします。
[[根]]から[[葉]]までの[[枝]]の値を順番に並べたものが、[[符号]]を表します。 [SRC[>>26]]
[35] 構文解析器は、[[二分木]]の[[根]]から順に入力の[[ビット]]に従い進むことで、
記号を得ることができます。 [SRC[>>26]]
[EG[
[34] 次の[[木]]は、次の表のような[[符号]]を表しています。
[PRE[
/\
0 1
/ \
B /\
0 1
/ \
A /\
0 1
/ \
C D
]PRE]
,* 記号 ,* 符号
, A , [CODE[10]]
, B , [CODE[0]]
, C , [CODE[110]]
, D , [CODE[111]]
]EG]
[36] [[ハフマン算法]]により、[[字母]]とその[[頻度]]から最適な接頭辞符号を得られます。
頻度が高いほど身近な[[符号]]となります。これを[[ハフマン符号]]といいます。 [SRC[>>26]]
;; [37] ただし [[DEFLATE]] では[[符号]]長の上限があるので、少し複雑になります。 [SRC[>>26]]
[38] [[DEFLATE]] では次の2つの制限があります [SRC[>>26]]。
[FIG(list)[
- [39] ある[[ビット長]]のすべての[[符号]]は、
その表現する[RUBYB[[[記号]]]@en[symbol]]と同じ順序で[RUBYB[辞書的]@en[lexicographically]]に連続した値となっていること。
- [40] 短い[[符号]]が、長い[[符号]]よりも辞書的に前にあること。
]FIG]
[42] この制限を設けることで、[[記号]]に対応する[[ビット長]]の[[リスト]]を示すだけで、
[[符号]]を記述できます [SRC[>>26]]。
[EG[
[41] 先程の例 (>>34) では、[[符号]]は [CODE[0]] < [CODE[10]] < [CODE[110]] = [CODE[111]]
と[[符号]]の長さの順が[[符号]]の順序と一致しています (>>40)。
また C < D と[[記号]]の順序と同じ長さの[[符号]]の順序が一致しています。
[43] [[記号]]群 (A, B, C, D) を表すこの[[符号]]群は、
各[[符号]]の[[ビット長]]から (2, 1, 3, 3) と表すことができます。
(この[[ビット長]]の組によって表される[[符号]]は一意に定まります。)
]EG]
[44] [VAR[N]] 個の[[記号]]について、[[符号]]の[[ビット長]]の[[リスト]][VAR[長さ群]]から、
対応する[[符号]]を [VAR[n]] [[ビット]]の[[整数]]の[[リスト]]として得るには、
次のようにします。 [SRC[>>26]]
[FIG(steps)[
= [45] [VAR[符号群]]を、[[空リスト]]に設定します。
= [46] [VAR[個数群]]を、[[空リスト]]に設定します。
= [49] [ [N[0]], [VAR[n]] ] の各[VAR[長さ]]について、
== [50] [VAR[個数群]] [ [VAR[長さ]] ] を、 [N[0]] に設定します。
= [47] [VAR[長さ群]]の各[VAR[長さ]]について、
== [48] [VAR[個数群]] [ [VAR[長さ]] ] を、 [N[1]] [[インクリメント]]します。
= [51] [VAR[符号]]を、 [N[0]] に設定します。
= [55] [VAR[次符号群]]を、[[空リスト]]に設定します。
= [52] [ [N[1]], [VAR[n]] ] の各[VAR[長さ]]について、順に、
== [53] [VAR[符号]]を、 ([VAR[符号]] + [VAR[個数群]] [ [VAR[長さ]] - 1 ]) [[<<]] 1 に設定します。
== [54] [VAR[次符号群]] [ [VAR[長さ]] ] を、[VAR[符号]]に設定します。
= [56] [ [N[0]], [VAR[N]] ] の各[VAR[記号]]について、
== [57] [VAR[長さ]]を、[VAR[長さ群]] [ [VAR[記号]] ] に設定します。
== [58] [VAR[長さ]]が [N[0]] 以外なら、
=== [59] [VAR[符号群]] [ [VAR[記号]] ] を、[VAR[次符号群]] [ [VAR[長さ]] ] に設定します。
=== [60] [VAR[次符号群]] [ [VAR[長さ]] ] を [N[1]] [[インクリメント]]します。
= [61] [VAR[符号群]]を返します。
]FIG]
** ブロック
[62] [[入力データ]]の[RUBYB[ブロック]@en[block]]の大きさは任意に決められますが、
[N[65535]] [[バイト]][[以下]]でなければなりません。[SRC[>>25]]
[63] [[圧縮データ集合]]の[RUBYB[ブロック]@en[block]]は、
入力データの各[[ブロック]]に対応します。 [SRC[>>25]]
;; [66] [[ブロック]]境界と[[バイト]]境界は一致しないかもしれません。 [SRC[>>26]]
[64] 圧縮済みデータの[[ブロック]]は、3ビットのヘッダーから始まります。 [SRC[>>26]]
[65] 第1ビット [F[BFINAL]] は、データ集合の最後のブロックかどうかを表します。
設定されていれば、最後です。 [SRC[>>26]]
[67] 第2ビットと第3ビットの [F[BTYPE]] は、圧縮方法を表します。 [SRC[>>26]]
[FIG(switch)[
: [CODE[00]] : 無圧縮。
[[ヘッダー]]を含む[[バイト]]の残りの[[ビット]]は、あっても無視します。
その次の2バイトは、 [CODE[LEN]] と呼び、このブロックのデータのバイト数を表します。
その次の2バイトは、[CODE[NLEN]] と呼び、 [CODE[LEN]] の[[1の補数]]とします。
その次の [VAR[LEN]] バイト分が、この[[ブロック]]の[[リテラル]]データとします。
: [CODE[01]] : [RUBYB[固定ハフマン符号]@en[fixed Huffman codes]]圧縮
: [CODE[10]] : [RUBYB[動的ハフマン符号]@en[dynamic Huffman codes]]圧縮
: [CODE[11]] : 予約 (誤り)
]FIG]
[15] 各[[ブロック]]は、 [[LZ77]] [[アルゴリズム]]と[[ハフマン符号化]]の組み合わせにより、
[[圧縮]]します。 [SRC[>>25]]
[18] [[ブロック]]は、[[圧縮]]されたデータ部分の表現を説明する[[ハフマン符号木]]と、
[RUBYB[圧縮されたデータ部分]@en[compressed data part]]との2つの部分の組です。 [SRC[>>25]]
[16] 各[[ブロック]]の[[ハフマン木]]は、互いに独立です。 [SRC[>>25]]
*** ブロックで用いるハフマン符号の記号
[102] 符号化された[[ブロック]]では、2種類の[[ハフマン符号]]を使います。
[103] [[リテラル]][[バイト]]と[[長さ]]の[[符号]]では、
次のように[[記号]]の意味を設定します。 [SRC[>>26]]
[FIG(list)[
- [ [N[0]], [N[255]] ] - [[リテラル]]な[[バイト]]
- [N[256]] - [RUBYB[ブロック末]@en[end-of-block]]
- [ [N[257]], [N[285]] ] - 長さ
]FIG]
[100] 長さの指定の場合には、続く数ビット分の「[RUBYB[余分なビット列]@en[extra bits]]」
によって実際の長さを求めます。 [SRC[>>26]]
[PRE[
Extra Extra Extra
Code Bits Length(s) Code Bits Lengths Code Bits Length(s)
---- ---- ------ ---- ---- ------- ---- ---- -------
257 0 3 267 1 15,16 277 4 67-82
258 0 4 268 1 17,18 278 4 83-98
259 0 5 269 2 19-22 279 4 99-114
260 0 6 270 2 23-26 280 4 115-130
261 0 7 271 2 27-30 281 5 131-162
262 0 8 272 2 31-34 282 5 163-194
263 0 9 273 3 35-42 283 5 195-226
264 0 10 274 3 43-50 284 5 227-257
265 1 11,12 275 3 51-58 285 0 258
266 1 13,14 276 3 59-66
]PRE]
[104] [[距離]]の[[符号]]でも、同様に余分なビット列によって実際の距離の値を求めます。
[SRC[>>26]]
[PRE[
Extra Extra Extra
Code Bits Dist Code Bits Dist Code Bits Distance
---- ---- ---- ---- ---- ------ ---- ---- --------
0 0 1 10 4 33-48 20 9 1025-1536
1 0 2 11 4 49-64 21 9 1537-2048
2 0 3 12 5 65-96 22 10 2049-3072
3 0 4 13 5 97-128 23 10 3073-4096
4 1 5,6 14 6 129-192 24 11 4097-6144
5 1 7,8 15 6 193-256 25 11 6145-8192
6 2 9-12 16 7 257-384 26 12 8193-12288
7 2 13-16 17 7 385-512 27 12 12289-16384
8 3 17-24 18 8 513-768 28 13 16385-24576
9 3 25-32 19 8 769-1024 29 13 24577-32768
]PRE]
[101] 余分なビット列は、 [[MSB]] から順に並べたものと解釈します。 [SRC[>>26]]
*** 固定ハフマン符号
[106] 固定ハフマン符号を用いる [CODE[01]] において、
リテラルバイトと長さを表す[[ハフマン符号]]は、
次のような[[ビット長]]を持つものとします。 [SRC[>>26]]
[FIG(list)[
- [ [N[0]], [N[143]] ] - 8ビット
- [ [N[144]], [N[255]] ] - 9ビット
- [ [N[256]], [N[279]] ] - 7ビット
- [ [N[280]], [N[287]] ] - 8ビット
]FIG]
;; [107] ただし、 [N[286]] と [N[287]] は実際には使われません。 [SRC[>>26]]
[108] 距離を表す [ [N[0]], [N[31]] ] は、そのまま5ビット固定長で表します。
(その次に余分なビット列が続きます。) [SRC[>>26]]
;; [109] [N[30]] と [N[31]] は実際には使われません。 [SRC[>>26]]
** 復号
[68] [VAR[入力ストリーム]]の[[復号]]は、次のようにします。 [SRC[>>26]]
ただし、[VAR[入力ストリーム]]から読むとは、現在位置から指定された長さのビット列を返し、
現在位置をその次のビットまで進めることをいいます。
[FIG(steps)[
= [74] [VAR[出力]]を、空バイト列に設定します。
= [90] 繰り返し、
== [69] [VAR[BFINAL]] を、[VAR[入力ストリーム]]から1ビット読んだ結果に設定します。
== [70] [VAR[BTYPE]] を、[VAR[入力ストリーム]]から2ビット読んだ結果に設定します。
== [92] [VAR[BTYPE]] が [CODE[11]] なら、
===
@@
== [71] [VAR[BTYPE]] が [CODE[00]] なら、
=== [72] [VAR[入力ストリーム]]の現在の[[バイト]]の残りの[[ビット]]をすべて読みます。
=== [73] [VAR[LEN]] と [VAR[NLEN]] を得ます。
=== [75] [VAR[入力ストリーム]]から [VAR[LEN]] [[バイト]]読んだ結果を、
[VAR[出力]]の末尾に追加します。
== [76] それ以外なら、
=== [77] [VAR[BTYPE]] が [CODE[10]] なら、
==== [78] 符号木の表現を読みます。
=== [79] 繰り返し、
==== [80] [VAR[値]]を、[VAR[入力ストリーム]]から[[リテラル]]と長さの値を復号した結果に設定します。
==== [81] [VAR[値]] < [N[256]] なら、
===== [82] [VAR[出力]]の末尾に[VAR[値]]を追加します。
==== [83] それ以外なら、
===== [84] [VAR[値]] = [N[256]] (end of block) なら、
====== [85] 繰り返し (>>79) を終えます。
===== [86] それ以外なら [ [N[257]], [N[285]] ]、
====== [87] [VAR[入力ストリーム]]から距離を復号します。
====== [93] [VAR[位置]]を、[VAR[出力]]の長さ - [VAR[距離]]に設定します。
======
@@ [94] [VAR[位置]]が[[負]]の時、...
====== [95] 繰り返し、
======= [98] [VAR[出力]] [ [VAR[位置]] ] を、[VAR[出力]]の末尾に追加します。
======= [99] [VAR[位置]]を [N[1]] [[インクリメント]]します。
======= [88] [VAR[距離]]を [N[1]] [[デクリメント]]します。
======= [96] [VAR[距離]]が [N[0]] なら、
======== [97] 繰り返し (>>95) を終えます。
== [89] [VAR[BFINAL]] が設定されていれば、繰り返し (>>90) を終えます。
= [91] [VAR[出力]]を返します。
]FIG]
* 文脈
[1] [[DEFLATE]] は次の場面で用いられています。
[FIG(short list)[
- [[zlib]]
- [[gzip]]
- [[ZIP]]
- [[LHA]]
]FIG]
* 適合性
[8] [[圧縮器]]は、[[仕様]]にすべて従うデータ集合を生成しなければなりません [SRC[>>7]]。
[6] [RUBYB[[[展開器]]]@en[decompressor]]は、
特に定める場合を除き、
[[仕様]]に[[適合]]する任意のデータ集合を[[受理]]し[RUBYB[[[展開]]]@en[decompress]]できなければなりません。 [SRC[>>7]]
* 関連
[3] [[HTTP]] の[[内容符号化]] [CODE(HTTP)@en[[[deflate]]]]
については、 [[zlib]] を参照。
* 歴史
[9] [[DEFLATE]] は [DFN[[[RFC 1591]]]] によって定義されています。
[10] [[RFC 1591]] は第1.3版となっていますが、第1.1版から技術的内容は変わっていません [SRC[>>7]]。
;; [11] 第1.0版には言及がなく、存在したのか不明です。
[105] 当時としては一般的なスタイルの[[仕様書]]ですが、現代的には読みづらく厳密さが足りないといえます。
細部の規定が不十分だったり、似て非なる用語が (おそらく意図せず) 混在していたり、
同じことを異なる表現で解説しているだけなのか、別個の規定なのかはっきりしない似た記述が複数存在したり。
[2] [CITE@en[RFC 6713 - The 'application/zlib' and 'application/gzip' Media Types]]
([TIME[2015-09-27 13:20:11 +09:00]] 版)
<https://tools.ietf.org/html/rfc6713>
[FIG(quote)[
[FIGCAPTION[
[4] [CITE[zlib 入門]]
([TIME[2007-02-14 08:49:05 +09:00]] 版)
<https://oku.edu.mie-u.ac.jp/~okumura/compression/zlib.html>
]FIGCAPTION]
> zlib の圧縮アルゴリズムは PKZIP 2.x の deflate アルゴリズムで, もともとは私と吉崎栄泰さんが LHA のために開発したものをハッシュで高速化したものです(zlib のソースコード中に,ほんのちょっとですが私の名前が入っています)。 その後,LHA もハッシュを使うようになりましたので,LHA と gzip/zlib/Zip の実質的な相違はなくなりました。
]FIG]
[13] [CITE@en-US[Efficient XML Interchange (EXI) Format 1.0]]
( ([TIME[2011-03-10 23:00:15 +09:00]] 版))
<http://www.w3.org/TR/2011/REC-exi-20110310/#CompressedStreams>