rfc1951.ps

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

1569 y(111111111)305 1625 y(256)e(-)f(279)137 b(7)273
b(0000000)30 b(through)986 1682 y(0010111)305 1738 y(280)e(-)f(287)137
b(8)273 b(11000000)30 b(through)986 1795 y(11000111)0
1882 y Fj(The)13 b(code)g(lengths)e(are)j(suf)o(\256cient)e(to)h
(generate)g(the)g(actual)f(codes,)i(as)f(described)f(above;)h(we)h
(show)e(the)g(codes)h(in)f(the)0 1938 y(table)g(for)g(added)g(clarity)m
(.)18 b(Literal/length)10 b(values)i(286-287)f(will)g(never)h(actually)
g(occur)g(in)g(the)g(compressed)g(data,)h(but)0 1995
y(participate)d(in)h(the)g(code)g(construction.)0 2082
y(Distance)g(codes)g(0-31)g(are)h(represented)f(by)g
(\(\256xed-length\))f(5-bit)h(codes,)g(with)g(possible)e(additional)h
(bits)g(as)h(shown)g(in)0 2138 y(the)h(table)g(shown)g(in)g(Paragraph)h
(3.2.5,)g(above.)19 b(Note)12 b(that)g(distance)g(codes)g(30-31)g(will)
f(never)i(actually)f(occur)g(in)g(the)0 2195 y(compressed)f(data.)0
2348 y Fb(3.2.7)45 b(Compr)o(ession)11 b(with)g(dynamic)g(Huffman)h
(codes)g(\(BTYPE=10\))0 2465 y Fj(The)g(Huf)o(fman)h(codes)g(for)f(the)
h(two)f(alphabets)f(appear)i(in)f(the)g(block)g(immediately)g(after)h
(the)f(header)h(bits)f(and)g(before)0 2522 y(the)f(actual)h(compressed)
f(data,)i(\256rst)e(the)h(literal/length)d(code)j(and)f(then)h(the)f
(distance)g(code.)17 b(Each)12 b(code)g(is)f(de\256ned)h(by)0
2578 y(a)f(sequence)g(of)g(code)g(lengths,)f(as)h(discussed)e(in)i
(Paragraph)g(3.2.2,)h(above.)j(For)c(even)g(greater)h(compactness,)e
(the)h(code)0 2719 y(Deutsch)688 b(Informational)f([Page)12
b(1)n(1])p eop
%%Page: 12 12
12 11 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(length)k(sequences)g(themselves)g(are)i(compressed)f
(using)e(a)i(Huf)o(fman)h(code.)26 b(The)15 b(alphabet)f(for)h(code)g
(lengths)f(is)g(as)0 252 y(follows:)195 339 y Fc(0)28
b(-)g(15:)g(Represent)h(code)g(lengths)g(of)f(0)f(-)h(15)305
395 y(16:)g(Copy)g(the)g(previous)i(code)e(length)h(3)e(-)h(6)f(times.)
414 451 y(The)h(next)g(2)g(bits)g(indicate)h(repeat)g(length)577
508 y(\(0)f(=)g(3,)f(...)i(,)e(3)h(=)f(6\))495 564 y(Example:)57
b(Codes)29 b(8,)f(16)f(\(+2)i(bits)f(11\),)768 621 y(16)g(\(+2)g(bits)g
(10\))h(will)f(expand)h(to)768 677 y(12)f(code)g(lengths)i(of)d(8)h
(\(1)g(+)f(6)h(+)f(5\))305 734 y(17:)h(Repeat)h(a)e(code)h(length)h(of)
f(0)g(for)g(3)f(-)h(10)g(times.)414 790 y(\(3)f(bits)i(of)f(length\))
305 847 y(18:)g(Repeat)h(a)e(code)h(length)h(of)f(0)g(for)g(11)g(-)f
(138)h(times)414 903 y(\(7)f(bits)i(of)f(length\))0 990
y Fj(A)11 b(code)f(length)g(of)h(0)f(indicates)g(that)g(the)g
(corresponding)f(symbol)h(in)g(the)h(literal/length)d(or)j(distance)e
(alphabet)h(will)g(not)0 1047 y(occur)j(in)f(the)g(block,)h(and)f
(should)f(not)h(participate)g(in)g(the)g(Huf)o(fman)h(code)g
(construction)d(algorithm)i(given)f(earlier)n(.)20 b(If)0
1103 y(only)12 b(one)g(distance)g(code)h(is)f(used,)h(it)f(is)g
(encoded)g(using)f(one)i(bit,)f(not)g(zero)h(bits;)f(in)g(this)g(case)h
(there)g(is)f(a)h(single)e(code)0 1159 y(length)f(of)i(one,)g(with)e
(one)i(unused)e(code.)17 b(One)11 b(distance)g(code)h(of)f(zero)h(bits)
f(means)h(that)f(there)g(are)i(no)e(distance)g(codes)0
1216 y(used)g(at)g(all)g(\(the)g(data)g(is)f(all)h(literals\).)0
1303 y(W)l(e)h(can)f(now)g(de\256ne)g(the)g(format)h(of)f(the)g(block:)
188 1383 y Fa(5)25 b(Bits:)g(HLIT,)f(#)h(of)g(Literal/Length)e(codes)i
(-)f(257)h(\(257)g(-)f(286\))188 1433 y(5)h(Bits:)g(HDIST,)f(#)h(of)f
(Distance)h(codes)f(-)h(1)199 b(\(1)25 b(-)g(32\))188
1483 y(4)g(Bits:)g(HCLEN,)f(#)h(of)f(Code)h(Length)f(codes)h(-)g(4)124
b(\(4)25 b(-)g(19\))188 1583 y(\(HCLEN)g(+)g(4\))f(x)h(3)g(bits:)f
(code)h(lengths)f(for)h(the)f(code)h(length)263 1632
y(alphabet)f(given)h(just)f(above,)h(in)f(the)h(order:)f(16,)h(17,)f
(18,)263 1682 y(0,)h(8,)g(7,)f(9,)h(6,)g(10,)f(5,)h(11,)g(4,)f(12,)h
(3,)g(13,)f(2,)h(14,)g(1,)f(15)263 1782 y(These)h(code)f(lengths)g(are)
h(interpreted)f(as)h(3-bit)f(integers)263 1832 y(\(0-7\);)g(as)h
(above,)f(a)h(code)g(length)f(of)h(0)g(means)f(the)263
1881 y(corresponding)g(symbol)g(\(literal/length)g(or)g(distance)g
(code)263 1931 y(length\))g(is)h(not)g(used.)188 2031
y(HLIT)g(+)g(257)f(code)h(lengths)f(for)h(the)f(literal/length)g
(alphabet,)263 2081 y(encoded)g(using)h(the)f(code)h(length)f(Huffman)h
(code)188 2180 y(HDIST)g(+)g(1)f(code)h(lengths)f(for)h(the)f(distance)
h(alphabet,)263 2230 y(encoded)f(using)h(the)f(code)h(length)f(Huffman)
h(code)188 2330 y(The)g(actual)f(compressed)g(data)h(of)g(the)f(block,)
263 2380 y(encoded)g(using)h(the)f(literal/length)g(and)h(distance)f
(Huffman)263 2429 y(codes)188 2529 y(The)h(literal/length)f(symbol)g
(256)h(\(end)f(of)h(data\),)263 2579 y(encoded)f(using)h(the)f
(literal/length)g(Huffman)g(code)0 2719 y Fj(Deutsch)687
b(Informational)g([Page)11 b(12])p eop
%%Page: 13 13
13 12 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)g(code)g(length)f(repeat)i(codes)f(can)g(cross)g
(from)g(HLIT)g(+)g(257)g(to)g(the)g(HDIST)g(+)g(1)g(code)g(lengths.)k
(In)c(other)g(words,)g(all)0 252 y(code)h(lengths)f(form)i(a)f(single)f
(sequence)h(of)g(HLIT)g(+)g(HDIST)g(+)g(258)g(values.)0
406 y Fd(3.3)50 b(Compliance)0 524 y Fj(A)14 b(compressor)f(may)h
(limit)f(further)h(the)f(ranges)g(of)h(values)f(speci\256ed)h(in)f(the)
g(previous)g(section)f(and)i(still)e(be)i(compli-)0 580
y(ant;)e(for)h(example,)g(it)f(may)h(limit)e(the)h(range)h(of)f
(backward)g(pointers)f(to)h(some)h(value)f(smaller)g(than)g(32K.)g
(Similarly)m(,)h(a)0 637 y(compressor)e(may)h(limit)e(the)h(size)g(of)g
(blocks)f(so)h(that)f(a)i(compressible)e(block)g(\256ts)h(in)g(memory)m
(.)0 724 y(A)f(compliant)g(decompressor)g(must)g(accept)g(the)g(full)g
(range)h(of)f(possible)e(values)i(de\256ned)g(in)g(the)g(previous)g
(section,)f(and)0 780 y(must)i(accept)g(blocks)f(of)h(arbitrary)g
(size.)0 957 y Fh(4)60 b(Compr)o(ession)14 b(algorithm)f(details)0
1091 y Fj(While)f(it)h(is)f(the)h(intent)e(of)i(this)f(document)h(to)f
(de\256ne)h(the)g(\252de\257ate\272)h(compressed)e(data)h(format)g
(without)e(reference)k(to)0 1147 y(any)f(particular)g(compression)f
(algorithm,)h(the)g(format)g(is)g(related)g(to)g(the)g(compressed)g
(formats)g(produced)f(by)h(LZ77)0 1204 y(\(Lempel-Ziv)7
b(1977,)h(see)g(reference)h([2])f(below\);)g(since)f(many)h(variations)
f(of)g(LZ77)g(are)i(patented,)f(it)f(is)g(strongly)f(recom-)0
1260 y(mended)11 b(that)g(the)f(implementor)h(of)g(a)h(compressor)e
(follow)g(the)h(general)g(algorithm)f(presented)g(here,)i(which)f(is)f
(known)0 1317 y(not)h(to)f(be)i(patented)e(per)i(se.)k(The)11
b(material)g(in)g(this)f(section)h(is)g(not)f(part)h(of)h(the)f
(de\256nition)f(of)h(the)g(speci\256cation)f(per)i(se,)0
1373 y(and)f(a)h(compressor)e(need)i(not)e(follow)g(it)h(in)f(order)i
(to)e(be)i(compliant.)0 1460 y(The)h(compressor)f(terminates)h(a)g
(block)f(when)g(it)g(determines)h(that)f(starting)f(a)i(new)g(block)f
(with)g(fresh)h(trees)f(would)g(be)0 1516 y(useful,)f(or)g(when)g(the)g
(block)f(size)h(\256lls)g(up)g(the)f(compressor)r(')n(s)g(block)h(buf)o
(fer)n(.)0 1603 y(The)h(compressor)g(uses)g(a)g(chained)g(hash)g(table)
g(to)g(\256nd)g(duplicated)f(strings,)g(using)g(a)h(hash)g(function)f
(that)h(operates)g(on)0 1660 y(3-byte)d(sequences.)15
b(At)10 b(any)g(given)f(point)g(during)g(compression,)g(let)h(XYZ)g(be)
g(the)g(next)f(3)h(input)f(bytes)g(to)h(be)g(examined)0
1716 y(\(not)e(necessarily)h(all)f(dif)o(ferent,)i(of)f(course\).)15
b(First,)9 b(the)g(compressor)g(examines)g(the)f(hash)h(chain)g(for)g
(XYZ.)14 b(If)c(the)f(chain)0 1773 y(is)h(empty)m(,)g(the)g(compressor)
g(simply)g(writes)f(out)h(X)g(as)g(a)h(literal)e(byte)h(and)g(advances)
g(one)g(byte)g(in)f(the)h(input.)k(If)d(the)f(hash)0
1829 y(chain)f(is)f(not)g(empty)m(,)i(indicating)d(that)h(the)h
(sequence)g(XYZ)f(\(or)n(,)i(if)f(we)g(are)h(unlucky)m(,)e(some)h
(other)g(3)g(bytes)f(with)g(the)h(same)0 1886 y(hash)h(function)e
(value\))i(has)g(occurred)g(recently)m(,)h(the)e(compressor)h(compares)
h(all)e(strings)g(on)g(the)h(XYZ)g(hash)f(chain)h(with)0
1942 y(the)h(actual)g(input)f(data)h(sequence)g(starting)e(at)j(the)e
(current)i(point,)e(and)h(selects)f(the)h(longest)f(match.)0
2029 y(The)i(compressor)f(searches)i(the)e(hash)h(chains)f(starting)f
(with)h(the)h(most)f(recent)i(strings,)e(to)g(favor)h(small)g
(distances)e(and)0 2086 y(thus)d(take)i(advantage)f(of)g(the)g(Huf)o
(fman)h(encoding.)14 b(The)8 b(hash)g(chains)g(are)h(singly)e(linked.)
13 b(There)c(are)g(no)f(deletions)f(from)0 2142 y(the)i(hash)g(chains;)
f(the)h(algorithm)f(simply)h(discards)f(matches)h(that)g(are)h(too)e
(old.)14 b(T)m(o)9 b(avoid)f(a)i(worst-case)f(situation,)e(very)0
2199 y(long)j(hash)h(chains)f(are)i(arbitrarily)e(truncated)h(at)g(a)h
(certain)f(length,)f(determined)h(by)g(a)g(run-time)g(parameter)n(.)0
2286 y(T)m(o)i(improve)h(overall)f(compression,)h(the)f(compressor)h
(optionally)d(defers)j(the)f(selection)g(of)h(matches)g(\(\252lazy)g
(match-)0 2342 y(ing\272\):)i(after)c(a)h(match)f(of)g(length)f(N)h
(has)g(been)g(found,)g(the)g(compressor)f(searches)i(for)f(a)g(longer)g
(match)g(starting)e(at)i(the)0 2398 y(next)d(input)f(byte.)14
b(If)c(it)f(\256nds)f(a)i(longer)f(match,)h(it)f(truncates)g(the)g
(previous)f(match)h(to)g(a)h(length)e(of)h(one)h(\(thus)e(producing)g
(a)0 2455 y(single)h(literal)g(byte\))g(and)h(then)f(emits)g(the)h
(longer)f(match.)15 b(Otherwise,)9 b(it)h(emits)f(the)h(original)e
(match,)j(and,)f(as)g(described)0 2511 y(above,)h(advances)g(N)g(bytes)
g(before)g(continuing.)0 2719 y(Deutsch)687 b(Informational)g([Page)11
b(13])p eop
%%Page: 14 14
14 13 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(Run-time)i(parameters)i(also)e(control)f(this)g
(\252lazy)i(match\272)g(procedure.)19 b(If)13 b(compression)f(ratio)g
(is)g(most)g(important,)g(the)0 252 y(compressor)d(attempts)g(a)g
(complete)h(second)e(search)i(regardless)f(of)g(the)h(length)e(of)h
(the)g(\256rst)h(match.)15 b(In)9 b(the)g(normal)g(case,)0
308 y(if)j(the)f(current)h(match)g(is)g(\252long)f(enough\272,)g(the)h
(compressor)g(reduces)g(the)f(search)h(for)g(a)h(longer)e(match,)i
(thus)d(speeding)0 364 y(up)f(the)h(process.)k(If)c(speed)g(is)f(most)g
(important,)g(the)h(compressor)f(inserts)g(new)g(strings)f(in)i(the)f
(hash)g(table)h(only)e(when)i(no)0 421 y(match)i(was)g(found,)f(or)h
(when)f(the)h(match)g(is)f(not)g(\252too)h(long\272.)k(This)11
b(degrades)g(the)h(compression)e(ratio)i(but)f(saves)g(time)0
477 y(since)g(there)g(are)h(both)e(fewer)i(insertions)d(and)i(fewer)h
(searches.)0 654 y Fh(5)60 b(Refer)o(ences)0 788 y Fj([1])12
b(Huf)o(fman,)g(D.)g(A.,)h(\252A)f(Method)f(for)g(the)h(Construction)d
(of)j(Minimum)g(Redundancy)f(Codes\272,)h(Proceedings)f(of)g(the)0
844 y(Institute)e(of)j(Radio)f(Engineers,)f(September)i(1952,)e(V)-6
b(olume)11 b(40,)h(Number)f(9,)g(pp.)k(1098-1)n(101.)0
931 y([2])f(Ziv)g(J.,)h(Lempel)g(A.,)g(\252A)g(Universal)e(Algorithm)f
(for)j(Sequential)e(Data)h(Compression\272,)h(IEEE)f(T)n(ransactions)f
(on)0 988 y(Information)d(Theory)m(,)i(V)-6 b(ol.)14
b(23,)e(No.)j(3,)c(pp.)k(337-343.)0 1075 y([3])9 b(Gailly)m(,)g(J.-L.,)
i(and)e(Adler)n(,)g(M.,)i(ZLIB)f(documentation)d(and)i(sources,)g
(available)g(in)g(ftp://ftp.uu.net/pu)o(b/archiv)o(ing)o(/)0
1131 y(zip/doc/)0 1218 y([4])24 b(Gailly)m(,)i(J.-L.,)i(and)c(Adler)n
(,)j(M.,)i(GZIP)24 b(documentation)e(and)i(sources,)j(available)c(as)h
(gzip-*.tar)f(in)h(ftp://)0 1275 y(prep.ai.mit.edu/pub/gnu/)0
1362 y([5])15 b(Schwartz,)h(E.)g(S.,)g(and)f(Kallick,)g(B.)h
(\252Generating)e(a)h(canonical)f(pre\256x)h(encoding.\272)25
b(Comm.)j(ACM,)15 b(7,3)g(\(Mar)n(.)0 1418 y(1964\),)c(pp.)k(166-169.)0
1505 y([6])c(Hirschber)o(g)f(and)g(Lelewer)n(,)i(\252Ef)o(\256cient)e
(decoding)g(of)g(pre\256x)h(codes,\272)g(Comm.)16 b(ACM,)c(33,4,)f
(April)f(1990,)g(pp.)15 b(449-)0 1561 y(459.)0 1738 y
Fh(6)60 b(Security)13 b(Considerations)0 1872 y Fj(Any)e(data)g
(compression)f(method)h(involves)e(the)i(reduction)f(of)h(redundancy)g
(in)f(the)h(data.)k(Consequently)m(,)10 b(any)h(corrup-)0
1928 y(tion)h(of)g(the)h(data)f(is)g(likely)f(to)i(have)f(severe)h(ef)o
(fects)g(and)g(be)f(dif)o(\256cult)g(to)g(correct.)20
b(Uncompressed)12 b(text,)h(on)f(the)h(other)0 1985 y(hand,)e(will)f
(probably)g(still)g(be)h(readable)g(despite)f(the)h(presence)h(of)f
(some)g(corrupted)g(bytes.)0 2072 y(It)g(is)f(recommended)i(that)e
(systems)g(using)f(this)h(data)h(format)g(provide)f(some)h(means)g(of)g
(validating)e(the)h(integrity)g(of)g(the)0 2128 y(compressed)h(data.)k
(See)d(reference)h([3],)e(for)h(example.)0 2305 y Fh(7)60
b(Sour)o(ce)14 b(code)0 2439 y Fj(Source)8 b(code)g(for)g(a)h(C)f
(language)f(implementation)g(of)h(a)g(\252de\257ate\272)h(compliant)e
(compressor)h(and)f(decompressor)h(is)g(avail-)0 2495
y(able)j(within)f(the)h(zlib)f(package)h(at)h(ftp://ftp.uu.net/pu)o
(b/archi)o(ving)o(/zip)o(/zlib)o(/.)0 2719 y(Deutsch)687
b(Informational)g([Page)11 b(14])p eop
%%Page: 15 15
15 14 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 Fh(8)60 b(Acknowledgements)0 329 y Fj(T)n(rademarks)12
b(cited)f(in)f(this)g(document)h(are)h(the)f(property)f(of)h(their)g
(respective)g(owners.)0 416 y(Phil)d(Katz)g(designed)f(the)h(de\257ate)
h(format.)15 b(Jean-Loup)7 b(Gailly)g(and)h(Mark)h(Adler)f(wrote)h(the)
f(related)g(software)g(described)0 472 y(in)j(this)f(speci\256cation.)k
(Glenn)c(Randers-Pehrson)h(converted)g(this)f(document)h(to)f(RFC)j
(and)e(HTML)g(format.)0 649 y Fh(9)60 b(Author)q(')n(s)15
b(Addr)o(ess)0 783 y Fj(L.)c(Peter)h(Deutsch)114 870
y Fc(Aladdin)29 b(Enterprises)114 926 y(203)f(Santa)g(Margarita)i(Ave.)
114 983 y(Menlo)e(Park,)h(CA)f(94025)114 1096 y(Phone:)h(\(415\))f
(322-0103)i(\(AM)e(only\))114 1152 y(FAX:)83 b(\(415\))28
b(322-1734)114 1208 y(EMail:)h(<ghost@aladdin.)q(com>)0
1295 y Fj(Questions)9 b(about)i(the)f(technical)h(content)f(of)h(this)f
(speci\256cation)g(can)i(be)f(sent)g(by)g(email)g(to:)114
1382 y Fc(Jean-Loup)29 b(Gailly)g(<gzip@prep.a)q(i.mi)q(t.ed)q(u>)i
(and)114 1439 y(Mark)d(Adler)h(<madler@alumni.)q(cal)q(tech)q(.edu)q(>)
0 1526 y Fj(Editorial)9 b(comments)j(on)e(this)h(speci\256cation)f(can)
h(be)g(sent)g(by)g(email)g(to:)114 1613 y Fc(L.)27 b(Peter)i(Deutsch)g
(<ghost@aladd)q(in.c)q(om>)i(and)114 1669 y(Glenn)d(Randers-Pehr)q(son)
j(<randeg@alumni.)q(rpi)q(.edu)q(>)0 2719 y Fj(Deutsch)687
b(Informational)g([Page)11 b(15])p eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF