rfc1951.ps

来自「中、英文RFC文档大全打包下载完全版 .」· PS 代码 · 共 920 行 · 第 1/4 页

1225 y(A)f(/\\)468 1282 y(0)55 b(1)441 1338 y(/)109 b(\\)414
1395 y(D)164 b(C)0 1482 y Fj(A)11 b(parser)f(can)h(decode)g(the)f(next)
g(symbol)g(from)h(an)f(encoded)h(input)e(stream)i(by)f(walking)f(down)h
(the)g(tree)h(from)g(the)f(root,)0 1538 y(at)h(each)h(step)e(choosing)g
(the)h(edge)g(corresponding)e(to)i(the)g(next)g(input)e(bit.)0
1625 y(Given)14 b(an)h(alphabet)e(with)h(known)f(symbol)h(frequencies,)
h(the)g(Huf)o(fman)g(algorithm)e(allows)h(the)g(construction)e(of)j(an)
0 1681 y(optimal)9 b(pre\256x)h(code)g(\(one)g(which)f(represents)g
(strings)f(with)h(those)g(symbol)g(frequencies)g(using)g(the)g(fewest)h
(bits)f(of)g(any)0 1738 y(possible)f(pre\256x)i(codes)g(for)g(that)f
(alphabet\).)15 b(Such)10 b(a)g(code)g(is)f(called)h(a)g(Huf)o(fman)h
(code.)j(\(See)d(reference)g([1])g(in)e(Chapter)0 1794
y(5,)i(references)i(for)e(additional)e(information)h(on)h(Huf)o(fman)h
(codes.\))0 1881 y(Note)e(that)g(in)g(the)g(\252de\257ate\272)i
(format,)f(the)f(Huf)o(fman)h(codes)f(for)h(the)f(various)g(alphabets)f
(must)h(not)g(exceed)h(certain)g(max-)0 1938 y(imum)g(code)f(lengths.)k
(This)9 b(constraint)g(complicates)h(the)g(algorithm)g(for)g(computing)
f(code)i(lengths)e(from)i(symbol)e(fre-)0 1994 y(quencies.)15
b(Again,)10 b(see)i(Chapter)f(5,)g(references)i(for)e(details.)0
2147 y Fb(3.2.2)45 b(Use)11 b(of)h(Huffman)g(coding)f(in)g(the)h
(\252de\257ate\272)g(format)0 2265 y Fj(The)f(Huf)o(fman)h(codes)f
(used)f(for)i(each)f(alphabet)g(in)f(the)h(\252de\257ate\272)h(format)g
(have)f(two)f(additional)g(rules:)68 2352 y Fg(\017)23
b Fj(All)13 b(codes)i(of)f(a)h(given)f(bit)g(length)f(have)i
(lexicographically)d(consecutive)h(values,)j(in)e(the)g(same)h(order)g
(as)f(the)114 2408 y(symbols)c(they)g(represent;)68 2495
y Fg(\017)23 b Fj(Shorter)11 b(codes)g(lexicographically)e(precede)i
(longer)g(codes.)0 2719 y(Deutsch)698 b(Informational)g([Page)12
b(6])p eop
%%Page: 7 7
7 6 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)0 195 y(W)l(e)h(could)f(recode)h(the)f(example)h(above)f(to)h
(follow)e(this)h(rule)g(as)h(follows,)e(assuming)h(that)g(the)g(order)h
(of)g(the)f(alphabet)g(is)0 252 y(ABCD:)114 339 y Fc(Symbol)56
b(Code)114 395 y(------)g(----)114 451 y(A)191 b(10)114
508 y(B)g(0)114 564 y(C)g(110)114 621 y(D)g(111)0 708
y Fj(I.e.,)13 b(0)e(precedes)g(10)g(which)f(precedes)i(1)n(1x,)f(and)g
(1)n(10)g(and)g(1)n(1)n(1)g(are)h(lexicographically)d(consecutive.)0
795 y(Given)j(this)f(rule,)i(we)f(can)h(de\256ne)f(the)g(Huf)o(fman)h
(code)f(for)h(an)f(alphabet)g(just)f(by)h(giving)f(the)h(bit)f(lengths)
g(of)h(the)h(codes)0 851 y(for)e(each)g(symbol)e(of)i(the)f(alphabet)g
(in)g(order;)h(this)e(is)h(suf)o(\256cient)g(to)g(determine)h(the)f
(actual)g(codes.)15 b(In)c(our)f(example,)h(the)0 908
y(code)f(is)g(completely)g(de\256ned)g(by)g(the)g(sequence)h(of)f(bit)g
(lengths)f(\(2,)i(1,)f(3,)h(3\).)k(The)c(following)d(algorithm)h
(generates)h(the)0 964 y(codes)j(as)h(integers,)g(intended)e(to)i(be)f
(read)i(from)f(most-)f(to)h(least-signi\256cant)d(bit.)22
b(The)14 b(code)g(lengths)e(are)i(initially)e(in)0 1021
y(tree[I].Len;)g(the)e(codes)h(are)h(produced)f(in)f(tree[I].Code.)0
1108 y(1\))h(Count)g(the)g(number)h(of)f(codes)g(for)g(each)h(code)g
(length.)i(Let)d(bl)p 1062 1108 14 2 v 16 w(count[N])g(be)g(the)g
(number)h(of)f(codes)g(of)g(length)f(N,)i(N)0 1164 y
Ff(>)p Fj(=)f(1.)0 1251 y(2\))g(Find)g(the)g(numerical)g(value)g(of)g
(the)g(smallest)f(code)h(for)h(each)f(code)h(length:)223
1338 y Fc(code)28 b(=)g(0;)223 1395 y(bl)p 280 1395 V
17 w(count[0])h(=)f(0;)223 1451 y(for)g(\(bits)g(=)g(1;)g(bits)g(<=)g
(MAX)p 934 1451 V 17 w(BITS;)h(bits++\))g Fg(f)332 1507
y Fc(code)f(=)g(\(code)g(+)g(bl)p 798 1507 V 17 w(count[bits-1]\))j(<<)
d(1;)332 1564 y(next)p 443 1564 V 17 w(code[bits])i(=)e(code;)223
1620 y Fg(g)0 1707 y Fj(3\))12 b(Assign)f(numerical)h(values)g(to)g
(all)g(codes,)g(using)f(consecutive)g(values)h(for)g(all)g(codes)g(of)g
(the)g(same)h(length)e(with)g(the)0 1764 y(base)i(values)f(determined)h
(at)g(step)g(2.)21 b(Codes)12 b(that)h(are)h(never)f(used)f(\(which)h
(have)g(a)g(bit)g(length)e(of)j(zero\))f(must)g(not)f(be)0
1820 y(assigned)e(a)h(value.)223 1907 y Fc(for)28 b(\(n)g(=)f(0;)55
b(n)28 b(<=)g(max)p 798 1907 V 17 w(code;)g(n++\))h Fg(f)332
1964 y Fc(len)f(=)f(tree[n].Len;)332 2020 y(if)h(\(len)g(!=)g(0\))g
Fg(f)441 2077 y Fc(tree[n].Code)i(=)e(next)p 961 2077
V 17 w(code[len];)441 2133 y(next)p 552 2133 V 17 w(code[len]++;)332
2190 y Fg(g)223 2246 y(g)0 2333 y Fj(Example:)0 2420
y(Consider)10 b(the)h(alphabet)g(ABCDEFGH,)g(with)g(bit)f(lengths)g
(\(3,)h(3,)h(3,)f(3,)h(3,)f(2,)h(4,)f(4\).)k(After)d(step)e(1,)i(we)f
(have:)0 2719 y(Deutsch)698 b(Informational)g([Page)12
b(7])p eop
%%Page: 8 8
8 7 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)114 195 y Fc(N)164 b(bl)p 362 195 14 2 v 16 w(count[N])114
252 y(-)g(-----------)114 308 y(2)g(1)114 364 y(3)g(5)114
421 y(4)g(2)0 508 y Fj(Step)11 b(2)g(computes)g(the)g(following)e(next)
p 649 508 V 16 w(code)i(values:)114 595 y Fc(N)164 b(next)p
416 595 V 17 w(code[N])114 651 y(-)g(------------)114
708 y(1)g(0)114 764 y(2)g(0)114 821 y(3)g(2)114 877 y(4)g(14)0
964 y Fj(Step)11 b(3)g(produces)g(the)g(following)e(code)i(values:)114
1051 y Fc(Symbol)29 b(Length)83 b(Code)114 1108 y(------)29
b(------)83 b(----)114 1164 y(A)191 b(3)218 b(010)114
1221 y(B)191 b(3)218 b(011)114 1277 y(C)191 b(3)218 b(100)114
1333 y(D)191 b(3)218 b(101)114 1390 y(E)191 b(3)218 b(110)114
1446 y(F)191 b(2)246 b(00)114 1503 y(G)191 b(4)g(1110)114
1559 y(H)g(4)g(1111)0 1712 y Fb(3.2.3)45 b(Details)11
b(of)g(block)g(format)0 1830 y Fj(Each)g(block)g(of)g(compressed)g
(data)g(begins)f(with)g(3)h(header)h(bits)e(containing)f(the)i
(following)e(data:)114 1917 y Fc(first)28 b(bit)192 b(BFINAL)114
1973 y(next)28 b(2)g(bits)137 b(BTYPE)0 2060 y Fj(Note)14
b(that)g(the)g(header)g(bits)g(do)g(not)f(necessarily)h(begin)f(on)h(a)
h(byte)f(boundary)m(,)g(since)g(a)h(block)f(does)f(not)h(necessarily)0
2117 y(occupy)d(an)g(integral)f(number)h(of)h(bytes.)0
2204 y(BFINAL)f(is)g(set)g(if)g(and)g(only)f(if)h(this)g(is)f(the)h
(last)g(block)f(of)h(the)g(data)g(set.)0 2291 y(BTYPE)g(speci\256es)g
(how)g(the)g(data)g(are)h(compressed,)f(as)g(follows:)114
2378 y Fc(00)27 b(-)h(no)g(compression)114 2434 y(01)f(-)h(compressed)i
(with)e(fixed)h(Huffman)g(codes)114 2491 y(10)e(-)h(compressed)i(with)e
(dynamic)i(Huffman)f(codes)114 2547 y(11)e(-)h(reserved)h(\(error\))0
2719 y Fj(Deutsch)698 b(Informational)g([Page)12 b(8])p
eop
%%Page: 9 9
9 8 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)0 195 y(The)i(only)f(dif)o(ference)h(between)f(the)h(two)f
(compressed)h(cases)g(is)f(how)g(the)h(Huf)o(fman)g(codes)g(for)g(the)f
(literal/length)e(and)0 252 y(distance)h(alphabets)g(are)i(de\256ned.)0
339 y(In)f(all)g(cases,)h(the)f(decoding)f(algorithm)g(for)h(the)g
(actual)g(data)g(is)g(as)g(follows:)114 419 y Fa(do)188
469 y(read)25 b(block)f(header)h(from)f(input)h(stream.)188
519 y(if)g(stored)f(with)h(no)g(compression)263 568 y(skip)g(any)f
(remaining)g(bits)h(in)g(current)f(partially)338 618
y(processed)g(byte)263 668 y(read)h(LEN)f(and)h(NLEN)f(\(see)h(next)f
(section\))263 718 y(copy)h(LEN)f(bytes)h(of)f(data)h(to)g(output)188
768 y(otherwise)263 817 y(if)g(compressed)f(with)g(dynamic)h(Huffman)f
(codes)338 867 y(read)g(representation)g(of)h(code)f(trees)h(\(see)413
917 y(subsection)e(below\))263 967 y(loop)i(\(until)f(end)h(of)f(block)
h(code)f(recognized\))338 1017 y(decode)g(literal/length)g(value)g
(from)h(input)f(stream)338 1066 y(if)h(value)f(<)h(256)413
1116 y(copy)f(value)g(\(literal)h(byte\))f(to)h(output)f(stream)338
1166 y(otherwise)413 1216 y(if)g(value)h(=)f(end)h(of)g(block)f
(\(256\))487 1266 y(break)h(from)f(loop)413 1316 y(otherwise)g(\(value)
g(=)h(257..285\))487 1365 y(decode)g(distance)f(from)g(input)h(stream)
487 1465 y(move)g(backwards)f(distance)g(bytes)g(in)h(the)g(output)487
1515 y(stream,)f(and)h(copy)g(length)f(bytes)g(from)h(this)487
1565 y(position)f(to)h(the)g(output)f(stream.)263 1614
y(end)h(loop)114 1664 y(while)f(not)h(last)f(block)0
1751 y Fj(Note)11 b(that)g(a)h(duplicated)f(string)f(reference)j(may)f
(refer)h(to)e(a)h(string)f(in)g(a)h(previous)e(block;)h(i.e.,)i(the)e
(backward)h(distance)0 1808 y(may)g(cross)f(one)h(or)g(more)g(block)f
(boundaries.)k(However)d(a)g(distance)f(cannot)g(refer)h(past)g(the)f
(beginning)f(of)h(the)h(output)0 1864 y(stream.)j(\(An)9
b(application)e(using)h(a)i(preset)e(dictionary)g(might)g(discard)h
(part)g(of)g(the)g(output)e(stream;)j(a)g(distance)e(can)h(refer)0
1921 y(to)f(that)f(part)h(of)g(the)g(output)f(stream)h(anyway\))g(Note)
g(also)f(that)h(the)g(referenced)h(string)e(may)h(overlap)g(the)g
(current)g(position;)0 1977 y(for)i(example,)h(if)g(the)f(last)f(2)h
(bytes)g(decoded)g(have)g(values)f(X)i(and)f(Y)-6 b(,)10
b(a)h(string)e(reference)j(with)d Ff(<)p Fj(length)g(=)h(5,)h(distance)
e(=)0 2034 y(2)p Ff(>)i Fj(adds)g(X,Y)-6 b(,X,Y)g(,X)12
b(to)f(the)g(output)e(stream.)0 2121 y(W)l(e)j(now)e(specify)h(each)h
(compression)e(method)h(in)f(turn.)0 2274 y Fb(3.2.4)45
b(Non-compr)o(essed)12 b(blocks)f(\(BTYPE=00\))0 2391
y Fj(Any)h(bits)f(of)i(input)e(up)h(to)g(the)g(next)g(byte)g(boundary)f
(are)j(ignored.)k(The)12 b(rest)h(of)f(the)g(block)g(consists)f(of)h
(the)g(following)0 2448 y(information:)0 2719 y(Deutsch)698
b(Informational)g([Page)12 b(9])p eop
%%Page: 10 10
10 9 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)168 195 y Fc(0)82 b(1)g(2)g(3)h(4...)114 252 y(+---+---+---+--)q
(-+=)q(====)q(====)q(===)q(====)q(====)q(===)q(====)q(====)q(=+)114
308 y(|)54 b(LEN)i(|)27 b(NLEN)56 b(|...)28 b(LEN)g(bytes)h(of)f
(literal)h(data...|)114 364 y(+---+---+---+--)q(-+=)q(====)q(====)q
(===)q(====)q(====)q(===)q(====)q(====)q(=+)0 451 y Fj(LEN)11
b(is)f(the)h(number)h(of)f(data)g(bytes)f(in)h(the)g(block.)j(NLEN)d
(is)g(the)f(one')n(s)h(complement)g(of)g(LEN.)0 605 y
Fb(3.2.5)45 b(Compr)o(essed)12 b(blocks)f(\(length)h(and)f(distance)h
(codes\))0 722 y Fj(As)h(noted)g(above,)h(encoded)f(data)h(blocks)e(in)
h(the)g(\252de\257ate\272)h(format)g(consist)e(of)i(sequences)f(of)g
(symbols)f(drawn)i(from)0 779 y(three)k(conceptually)e(distinct)h
(alphabets:)27 b(either)17 b(literal)h(bytes,)h(from)f(the)g(alphabet)f
(of)h(byte)g(values)f(\(0..255\),)j(or)0 835 y Ff(<)p
Fj(length,)10 b(backward)g(distance)p Ff(>)g Fj(pairs,)h(where)f(the)h
(length)e(is)h(drawn)g(from)h(\(3..258\))g(and)f(the)g(distance)g(is)f
(drawn)i(from)0 892 y(\(1..32,768\).)22 b(In)13 b(fact,)i(the)e
(literal)g(and)g(length)f(alphabets)g(are)i(mer)o(ged)g(into)f(a)h
(single)e(alphabet)g(\(0..285\),)j(where)e(val-)0 948
y(ues)d(0..255)g(represent)g(literal)f(bytes,)h(the)g(value)g(256)f
(indicates)g(end-of-block,)h(and)g(values)f(257..285)g(represent)h
(length)0 1004 y(codes)h(\(possibly)e(in)i(conjunction)e(with)h(extra)h
(bits)f(following)f(the)i(symbol)f(code\))i(as)f(follows:)250
1091 y Fc(Extra)410 b(Extra)h(Extra)114 1148 y(Code)28
b(Bits)g(Length\(s\))i(Code)e(Bits)h(Lengths)84 b(Code)28
b(Bits)g(Length\(s\))114 1204 y(----)g(----)g(------)138
b(----)29 b(----)f(-------)84 b(----)28 b(----)h(-------)141
1261 y(257)83 b(0)136 b(3)191 b(267)83 b(1)f(15,16)138
b(277)82 b(4)h(67-82)141 1317 y(258)g(0)136 b(4)191 b(268)83
b(1)f(17,18)138 b(278)82 b(4)h(83-98)141 1374 y(259)g(0)136
b(5)191 b(269)83 b(2)f(19-22)138 b(279)82 b(4)h(99-114)141
1430 y(260)g(0)136 b(6)191 b(270)83 b(2)f(23-26)138 b(280)82
b(4)55 b(115-130)141 1487 y(261)83 b(0)136 b(7)191 b(271)83
b(2)f(27-30)138 b(281)82 b(5)55 b(131-162)141 1543 y(262)83
b(0)136 b(8)191 b(272)83 b(2)f(31-34)138 b(282)82 b(5)55
b(163-194)141 1600 y(263)83 b(0)136 b(9)191 b(273)83
b(3)f(35-42)138 b(283)82 b(5)55 b(195-226)141 1656 y(264)83
b(0)109 b(10)191 b(274)83 b(3)f(43-50)138 b(284)82 b(5)55
b(227-257)141 1712 y(265)83 b(1)54 b(11,12)165 b(275)83
b(3)f(51-58)138 b(285)82 b(0)110 b(258)141 1769 y(266)83
b(1)54 b(13,14)165 b(276)83 b(3)f(59-66)0 1856 y Fj(The)12
b(extra)g(bits)f(should)g(be)h(interpreted)f(as)i(a)f(machine)g
(integer)g(stored)f(with)h(the)f(most-signi\256cant)g(bit)g(\256rst,)i
(e.g.,)g(bits)0 1912 y(1)n(1)n(10)e(represent)g(the)g(value)g(14.)0
2719 y(Deutsch)687 b(Informational)g([Page)11 b(10])p
eop
%%Page: 11 11
11 10 bop 0 46 a Fj(RFC)12 b(1951)320 b(DEFLA)-5 b(TE)10
b(Compressed)i(Data)f(Format)g(Speci\256cation)321 b(April)10
b(1996)277 195 y Fc(Extra)302 b(Extra)410 b(Extra)141
252 y(Code)28 b(Bits)h(Dist)55 b(Code)29 b(Bits)83 b(Dist)137
b(Code)28 b(Bits)h(Distance)141 308 y(----)f(----)h(----)55
b(----)29 b(----)55 b(------)111 b(----)28 b(----)h(--------)195
364 y(0)83 b(0)109 b(1)137 b(10)82 b(4)137 b(33-48)110
b(20)g(9)82 b(1025-1536)195 421 y(1)h(0)109 b(2)137 b(11)82
b(4)137 b(49-64)110 b(21)g(9)82 b(1537-2048)195 477 y(2)h(0)109
b(3)137 b(12)82 b(5)137 b(65-96)110 b(22)82 b(10)h(2049-3072)195
534 y(3)g(0)109 b(4)137 b(13)82 b(5)137 b(97-128)83 b(23)f(10)h
(3073-4096)195 590 y(4)g(1)f(5,6)110 b(14)82 b(6)109
b(129-192)84 b(24)e(11)h(4097-6144)195 647 y(5)g(1)f(7,8)110
b(15)82 b(6)109 b(193-256)84 b(25)e(11)h(6145-8192)195
703 y(6)g(2)f(9-12)h(16)f(7)109 b(257-384)84 b(26)e(12)55
b(8193-12288)195 760 y(7)83 b(2)54 b(13-16)84 b(17)e(7)109
b(385-512)84 b(27)e(12)28 b(12289-16384)195 816 y(8)83
b(3)54 b(17-24)84 b(18)e(8)109 b(513-768)84 b(28)e(13)28
b(16385-24576)195 873 y(9)83 b(3)54 b(25-32)84 b(19)e(8)g(769-1024)i
(29)e(13)28 b(24577-32768)0 1026 y Fb(3.2.6)45 b(Compr)o(ession)11
b(with)g(\256xed)h(Huffman)g(codes)g(\(BTYPE=01\))0 1143
y Fj(The)e(Huf)o(fman)h(codes)g(for)f(the)h(two)e(alphabets)h(are)h
(\256xed,)g(and)f(are)i(not)d(represented)i(explicitly)d(in)i(the)g
(data.)15 b(The)c(Huf)o(f-)0 1200 y(man)h(code)f(lengths)e(for)j(the)f
(literal/length)d(alphabet)j(are:)305 1287 y Fc(Lit)28
b(Value)110 b(Bits)219 b(Codes)305 1343 y(---------)111
b(----)219 b(-----)359 1400 y(0)28 b(-)f(143)137 b(8)273
b(00110000)30 b(through)986 1456 y(10111111)305 1513
y(144)e(-)f(255)137 b(9)273 b(110010000)30 b(through)986