rfc1951.ps

来自「RFC 的详细文档！」· PS 代码 · 共 920 行 · 第 1/4 页

(fman)g(codes)g(\(BTYPE=10\))44 b(.)23 b(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)
g(.)g(.)g(.)g(.)g(.)42 b(10)68 1371 y(3.3)70 b(Compliance)40
b(.)23 b(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)
g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f
(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)42 b(12)0 1427 y(4)104
b(Compression)11 b(algorithm)f(details)40 b(.)23 b(.)g(.)h(.)f(.)g(.)g
(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)
g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)42 b(12)0 1484
y(5)104 b(References)24 b(.)f(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)
g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)42
b(13)0 1540 y(6)104 b(Security)11 b(Considerations)26
b(.)d(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)
g(.)g(.)g(.)42 b(13)0 1597 y(7)104 b(Source)12 b(code)35
b(.)23 b(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)
g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)42 b(13)0 1653
y(8)104 b(Acknowledgements)33 b(.)23 b(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h
(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)
g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)42
b(14)0 1710 y(9)104 b(Author)r(')n(s)9 b(Address)40 b(.)23
b(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g
(.)g(.)g(.)h(.)f(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)g(.)h(.)f(.)g(.)g(.)
g(.)g(.)g(.)g(.)g(.)42 b(14)0 1886 y Fh(1)60 b(Intr)o(oduction)0
2022 y Fd(1.1)50 b(Purpose)0 2139 y Fj(The)11 b(purpose)f(of)i(this)e
(speci\256cation)g(is)g(to)h(de\256ne)h(a)f(lossless)e(compressed)i
(data)g(format)h(that:)68 2226 y Fg(\017)23 b Fj(Is)12
b(independent)f(of)i(CPU)g(type,)g(operating)e(system,)i(\256le)g
(system,)f(and)h(character)g(set,)g(and)f(hence)h(can)g(be)g(used)114
2283 y(for)e(interchange;)68 2370 y Fg(\017)23 b Fj(Can)13
b(be)f(produced)g(or)g(consumed,)h(even)g(for)f(an)h(arbitrarily)e
(long)h(sequentially)e(presented)i(input)f(data)h(stream,)114
2426 y(using)f(only)h(an)g Fe(a)h(priori)e Fj(bounded)g(amount)i(of)f
(intermediate)h(storage,)f(and)h(hence)g(can)g(be)g(used)f(in)g(data)h
(com-)114 2483 y(munications)c(or)i(similar)g(structures)f(such)h(as)g
(Unix)f(\256lters;)0 2719 y(Deutsch)698 b(Informational)g([Page)12
b(2])p eop
%%Page: 3 3
3 2 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)68 195 y Fg(\017)23 b Fj(Compresses)10 b(data)g(with)f(ef)o
(\256ciency)i(comparable)g(to)f(the)g(best)f(currently)h(available)g
(general-purpose)f(compres-)114 252 y(sion)h(methods,)h(and)g(in)f
(particular)h(considerably)e(better)i(than)g(the)g(\252compress\272)g
(program;)68 337 y Fg(\017)23 b Fj(Can)11 b(be)g(implemented)g(readily)
g(in)g(a)g(manner)h(not)e(covered)h(by)g(patents,)g(and)g(hence)g(can)h
(be)f(practiced)g(freely;)68 423 y Fg(\017)23 b Fj(Is)10
b(compatible)g(with)f(the)h(\256le)h(format)f(produced)g(by)g(the)g
(current)h(widely)e(used)h(gzip)f(utility)m(,)g(in)h(that)g(conforming)
114 479 y(decompressors)g(will)g(be)h(able)h(to)e(read)i(data)f
(produced)f(by)h(the)g(existing)f(gzip)g(compressor)n(.)0
564 y(The)h(data)g(format)h(de\256ned)f(by)g(this)f(speci\256cation)g
(does)h(not)f(attempt)h(to:)68 649 y Fg(\017)23 b Fj(Allow)10
b(random)h(access)g(to)g(compressed)g(data;)68 735 y
Fg(\017)23 b Fj(Compress)10 b(specialized)g(data)h(\(e.g.,)h(raster)f
(graphics\))f(as)h(well)f(as)h(the)g(best)f(currently)g(available)g
(specialized)g(al-)114 791 y(gorithms.)0 876 y(A)e(simple)f(counting)g
(ar)o(gument)h(shows)f(that)g(no)h(lossless)e(compression)h(algorithm)g
(can)h(compress)g(every)g(possible)f(input)0 933 y(data)14
b(set.)23 b(For)15 b(the)e(format)i(de\256ned)f(here,)h(the)f(worst)f
(case)i(expansion)d(is)i(5)g(bytes)f(per)h(32K-byte)f(block,)h(i.e.,)i
(a)e(size)0 989 y(increase)f(of)g(0.015\045)f(for)i(lar)o(ge)f(data)g
(sets.)20 b(English)11 b(text)h(usually)g(compresses)g(by)h(a)g(factor)
h(of)f(2.5)g(to)f(3;)i(executable)0 1046 y(\256les)d(usually)f
(compress)h(somewhat)g(less;)f(graphical)g(data)h(such)g(as)g(raster)h
(images)f(may)g(compress)g(much)h(more.)0 1197 y Fd(1.2)50
b(Intended)12 b(audience)0 1313 y Fj(This)h(speci\256cation)g(is)g
(intended)g(for)h(use)g(by)g(implementors)f(of)h(software)g(to)f
(compress)h(data)g(into)f(\252de\257ate\272)i(format)0
1369 y(and/or)10 b(decompress)h(data)h(from)f(\252de\257ate\272)h
(format.)0 1454 y(The)e(text)f(of)i(the)e(speci\256cation)g(assumes)h
(a)h(basic)e(background)g(in)h(programming)g(at)g(the)g(level)f(of)h
(bits)f(and)h(other)g(prim-)0 1511 y(itive)g(data)h(representations.)j
(Familiarity)c(with)h(the)f(technique)h(of)g(Huf)o(fman)g(coding)f(is)h
(helpful)f(but)h(not)f(required.)0 1662 y Fd(1.3)50 b(Scope)0
1778 y Fj(The)11 b(speci\256cation)g(speci\256es)g(a)h(method)f(for)h
(representing)e(a)i(sequence)g(of)f(bytes)g(as)h(a)g(\(usually)e
(shorter\))h(sequence)g(of)0 1834 y(bits,)f(and)h(a)h(method)f(for)g
(packing)f(the)h(latter)g(bit)f(sequence)h(into)f(bytes.)0
1986 y Fd(1.4)50 b(Compliance)0 2102 y Fj(Unless)7 b(otherwise)h
(indicated)f(below)m(,)h(a)h(compliant)e(decompressor)h(must)g(be)h
(able)f(to)g(accept)h(and)f(decompress)g(any)g(data)0
2158 y(set)h(that)g(conforms)g(to)g(all)g(the)g(speci\256cations)f
(presented)g(here;)i(a)g(compliant)e(compressor)h(must)g(produce)g
(data)g(sets)g(that)0 2214 y(conform)i(to)g(all)g(the)g
(speci\256cations)f(presented)g(here.)0 2366 y Fd(1.5)63
b(De\256nitions)11 b(of)h(terms)h(and)f(conventions)f(used)0
2482 y Fj(Byte:)k(8)c(bits)f(stored)g(or)i(transmitted)e(as)h(a)g(unit)
g(\(same)g(as)h(an)f(octet\).)k(For)d(this)e(speci\256cation,)g(a)i
(byte)e(is)h(exactly)g(8)g(bits,)0 2538 y(even)g(on)g(machines)g(which)
f(store)g(a)i(character)g(on)e(a)i(number)f(of)g(bits)f(dif)o(ferent)h
(from)g(eight.)j(See)e(below)m(,)f(for)g(the)g(num-)0
2594 y(bering)f(of)i(bits)e(within)f(a)j(byte.)0 2719
y(Deutsch)698 b(Informational)g([Page)12 b(3])p eop
%%Page: 4 4
4 3 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(String:)k(a)d(sequence)g(of)h(arbitrary)e(bytes.)0
345 y Fd(1.6)50 b(Changes)12 b(fr)o(om)h(pr)o(evious)f(versions)0
461 y Fj(There)e(have)h(been)f(no)g(technical)g(changes)g(to)f(the)h
(de\257ate)h(format)g(since)f(version)f(1.1)h(of)h(this)e
(speci\256cation.)14 b(In)c(version)0 517 y(1.2,)i(some)f(terminology)e
(was)i(changed.)k(V)-5 b(ersion)11 b(1.3)g(is)g(a)g(conversion)f(of)h
(the)g(speci\256cation)f(to)h(RFC)h(style.)0 689 y Fh(2)60
b(Compr)o(essed)14 b(r)o(epr)o(esentation)f(overview)0
820 y Fj(A)f(compressed)f(data)h(set)f(consists)f(of)i(a)g(series)g(of)
f(blocks,)h(corresponding)d(to)j(successive)f(blocks)f(of)i(input)e
(data.)17 b(The)0 877 y(block)10 b(sizes)h(are)h(arbitrary)m(,)f
(except)g(that)g(non-compressible)e(blocks)h(are)i(limited)e(to)h
(65,535)f(bytes.)0 961 y(Each)j(block)e(is)h(compressed)h(using)e(a)i
(combination)e(of)i(the)f(LZ77)g(algorithm)f(and)i(Huf)o(fman)g
(coding.)18 b(The)13 b(Huf)o(fman)0 1018 y(trees)c(for)h(each)g(block)e
(are)i(independent)e(of)h(those)g(for)g(previous)f(or)i(subsequent)d
(blocks;)i(the)g(LZ77)f(algorithm)h(may)g(use)0 1074
y(a)j(reference)g(to)f(a)g(duplicated)f(string)g(occurring)g(in)h(a)h
(previous)e(block,)g(up)h(to)g(32K)f(input)g(bytes)h(before.)0
1159 y(Each)h(block)f(consists)f(of)i(two)g(parts:)k(a)c(pair)g(of)g
(Huf)o(fman)g(code)g(trees)g(that)g(describe)f(the)h(representation)f
(of)h(the)g(com-)0 1215 y(pressed)7 b(data)h(part,)h(and)f(a)g
(compressed)g(data)g(part.)14 b(\(The)8 b(Huf)o(fman)h(trees)e
(themselves)h(are)g(compressed)g(using)f(Huf)o(fman)0
1272 y(encoding.\))19 b(The)13 b(compressed)f(data)h(consists)e(of)h(a)
h(series)g(of)g(elements)f(of)h(two)f(types:)17 b(literal)12
b(bytes)g(\(of)h(strings)e(that)0 1328 y(have)e(not)g(been)g(detected)g
(as)g(duplicated)e(within)h(the)h(previous)f(32K)g(input)g(bytes\),)h
(and)g(pointers)f(to)h(duplicated)e(strings,)0 1385 y(where)13
b(a)f(pointer)g(is)g(represented)g(as)g(a)h(pair)f Ff(<)p
Fj(length,)h(backward)f(distance)p Ff(>)p Fj(.)18 b(The)13
b(representation)e(used)h(in)g(the)g(\252de-)0 1441 y(\257ate\272)h
(format)h(limits)d(distances)h(to)g(32K)h(bytes)f(and)g(lengths)g(to)g
(258)g(bytes,)h(but)f(does)g(not)g(limit)g(the)h(size)g(of)f(a)i
(block,)0 1498 y(except)d(for)g(uncompressible)f(blocks,)g(which)h(are)
h(limited)e(as)h(noted)g(above.)0 1582 y(Each)h(type)g(of)h(value)f
(\(literals,)g(distances,)g(and)g(lengths\))f(in)h(the)g(compressed)g
(data)g(is)g(represented)g(using)f(a)i(Huf)o(fman)0 1638
y(code,)g(using)e(one)h(code)h(tree)g(for)f(literals)g(and)g(lengths)f
(and)h(a)h(separate)f(code)h(tree)f(for)h(distances.)18
b(The)12 b(code)h(trees)f(for)0 1695 y(each)g(block)e(appear)h(in)g(a)h
(compact)f(form)h(just)e(before)h(the)g(compressed)g(data)g(for)h(that)
e(block.)0 1867 y Fh(3)60 b(Detailed)13 b(speci\256cation)0
2000 y Fd(3.1)50 b(Overall)12 b(conventions)0 2115 y
Fj(In)f(the)g(diagrams)g(below)m(,)g(a)h(box)e(like)h(this:)114
2200 y Fc(+---+)114 2256 y(|)82 b(|)27 b(<--)h(the)g(vertical)i(bars)e
(might)h(be)f(missing)114 2312 y(+---+)0 2397 y Fj(represents)11
b(one)g(byte;)f(a)h(box)g(like)g(this:)114 2482 y Fc(+==============)q
(+)114 2538 y(|)382 b(|)114 2594 y(+==============)q(+)0
2719 y Fj(Deutsch)698 b(Informational)g([Page)12 b(4])p
eop
%%Page: 5 5
5 4 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(represents)h(a)g(variable)g(number)g(of)g(bytes.)0
282 y(Bytes)g(stored)g(within)f(a)i(computer)f(do)g(not)g(have)h(a)g
(\252bit)f(order)r(\272,)g(since)h(they)f(are)h(always)f(treated)g(as)h
(a)g(unit.)j(However)n(,)0 339 y(a)d(byte)f(considered)f(as)i(an)g
(integer)e(between)i(0)f(and)g(255)g(does)g(have)h(a)f(most-)h(and)f
(least-signi\256cant)e(bit,)j(and)f(since)g(we)0 395
y(write)f(numbers)g(with)f(the)h(most-signi\256cant)e(digit)h(on)g(the)
h(left,)h(we)f(also)g(write)g(bytes)f(with)g(the)h(most-signi\256cant)e
(bit)i(on)0 451 y(the)h(left.)16 b(In)11 b(the)g(diagrams)h(below)m(,)f
(we)g(number)h(the)f(bits)f(of)h(a)h(byte)f(so)g(that)g(bit)f(0)i(is)e
(the)i(least-signi\256cant)d(bit,)i(i.e.,)h(the)0 508
y(bits)e(are)i(numbered:)114 595 y Fc(+--------+)114
651 y(|76543210|)114 708 y(+--------+)0 795 y Fj(W)n(ithin)g(a)h
(computer)n(,)h(a)f(number)h(may)f(occupy)g(multiple)e(bytes.)20
b(All)13 b(multi-byte)e(numbers)i(in)g(the)f(format)i(described)0
851 y(here)d(are)h(stored)e(with)g(the)h(least-signi\256cant)e(byte)i
(\256rst)f(\(at)i(the)e(lower)h(memory)h(address\).)i(For)e(example,)f
(the)g(decimal)0 908 y(number)g(520)g(is)f(stored)h(as:)223
995 y Fc(0)218 b(1)114 1051 y(+--------+-----)q(---)q(+)114
1108 y(|00001000|00000)q(010)q(|)114 1164 y(+--------+-----)q(---)q(+)
141 1221 y(\303)g(\303)141 1277 y(|)g(|)141 1333 y(|)g(+)28
b(more)g(significant)j(byte)d(=)f(2)h(x)g(256)141 1390
y(+)f(less)i(significant)h(byte)e(=)g(8)0 1543 y Fb(3.1.1)45
b(Packing)11 b(into)g(bytes)0 1661 y Fj(This)c(document)g(does)g(not)f
(address)i(the)f(issue)f(of)i(the)f(order)h(in)f(which)g(bits)f(of)i(a)
g(byte)f(are)h(transmitted)e(on)i(a)g(bit-sequential)0
1717 y(medium,)13 b(since)g(the)f(\256nal)g(data)h(format)g(described)f
(here)h(is)f(byte-)g(rather)h(than)f(bit-oriented.)18
b(However)n(,)13 b(we)g(describe)0 1774 y(the)d(compressed)h(block)f
(format)h(in)f(below)m(,)g(as)h(a)g(sequence)g(of)f(data)h(elements)f
(of)h(various)f(bit)g(lengths,)f(not)h(a)h(sequence)0
1830 y(of)f(bytes.)k(W)l(e)d(must)f(therefore)g(specify)g(how)f(to)h
(pack)g(these)g(data)g(elements)g(into)f(bytes)g(to)h(form)g(the)g
(\256nal)g(compressed)0 1886 y(byte)h(sequence:)68 1973
y Fg(\017)23 b Fj(Data)8 b(elements)h(are)g(packed)f(into)g(bytes)f(in)
i(order)f(of)h(increasing)e(bit)h(number)h(within)e(the)h(byte,)h
(i.e.,)h(starting)d(with)114 2030 y(the)k(least-signi\256cant)e(bit)h
(of)h(the)g(byte.)68 2117 y Fg(\017)23 b Fj(Data)12 b(elements)g(other)
g(than)g(Huf)o(fman)h(codes)f(are)h(packed)f(starting)f(with)h(the)g
(least-signi\256cant)e(bit)i(of)g(the)g(data)114 2173
y(element.)68 2260 y Fg(\017)23 b Fj(Huf)o(fman)11 b(codes)g(are)h
(packed)f(starting)f(with)g(the)h(most-signi\256cant)e(bit)i(of)g(the)g
(code.)0 2347 y(In)j(other)f(words,)h(if)f(one)g(were)i(to)e(print)f
(out)h(the)g(compressed)h(data)f(as)h(a)g(sequence)f(of)h(bytes,)f
(starting)f(with)h(the)g(\256rst)0 2404 y(byte)d(at)h(the)g(*right*)e
(mar)o(gin)i(and)g(proceeding)f(to)g(the)h(*left*,)f(with)g(the)h
(most-signi\256cant)e(bit)h(of)h(each)g(byte)f(on)h(the)f(left)0
2460 y(as)k(usual,)g(one)g(would)e(be)i(able)g(to)g(parse)g(the)f
(result)g(from)i(right)e(to)g(left,)i(with)d(\256xed-width)h(elements)h
(in)f(the)h(correct)0 2517 y(MSB-to-LSB)d(order)f(and)g(Huf)o(fman)h
(codes)f(in)f(bit-reversed)h(order)g(\(i.e.,)h(with)e(the)h(\256rst)g
(bit)f(of)h(the)g(code)g(in)g(the)g(relative)0 2573 y(LSB)i
(position\).)0 2719 y(Deutsch)698 b(Informational)g([Page)12
b(5])p eop
%%Page: 6 6
6 5 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 Fd(3.2)50 b(Compr)o(essed)13 b(block)f(format)0
313 y Fb(3.2.1)45 b(Synopsis)11 b(of)g(pr)o(e\256x)h(and)g(Huffman)g
(coding)0 430 y Fj(Pre\256x)c(coding)f(represents)g(symbols)f(from)j
(an)e Fe(a)h(priori)e Fj(known)g(alphabet)h(by)g(bit)g(sequences)g
(\(codes\),)i(one)e(code)h(for)g(each)0 487 y(symbol,)13
b(in)f(a)h(manner)h(such)e(that)g(dif)o(ferent)h(symbols)f(may)h(be)g
(represented)g(by)f(bit)g(sequences)h(of)g(dif)o(ferent)f(lengths,)0
543 y(but)e(a)i(parser)f(can)h(always)e(parse)i(an)f(encoded)g(string)f
(unambiguously)e(symbol-by-symbol.)0 630 y(W)l(e)i(de\256ne)g(a)h
(pre\256x)f(code)f(in)h(terms)g(of)f(a)i(binary)e(tree)h(in)f(which)g
(the)h(two)f(edges)g(descending)g(from)h(each)g(non-leaf)g(node)0
687 y(are)i(labeled)f(0)g(and)h(1)f(and)g(in)g(which)g(the)g(leaf)h
(nodes)e(correspond)h(one-for)o(-one)g(with)g(\(are)h(labeled)f(with\))
f(the)h(symbols)0 743 y(of)g(the)g(alphabet;)f(then)g(the)h(code)g(for)
g(a)g(symbol)f(is)h(the)g(sequence)f(of)h(0')n(s)g(and)f(1')n(s)h(on)f
(the)h(edges)g(leading)f(from)h(the)g(root)0 799 y(to)g(the)g(leaf)g
(labeled)g(with)f(that)g(symbol.)15 b(For)c(example:)495
886 y Fc(/\\)383 b(Symbol)111 b(Code)468 943 y(0)55 b(1)355
b(------)111 b(----)441 999 y(/)e(\\)437 b(A)164 b(00)414
1056 y(/\\)137 b(B)409 b(B)191 b(1)386 1112 y(0)55 b(1)546
b(C)137 b(011)359 1169 y(/)109 b(\\)519 b(D)137 b(010)332