📄 chp9.htm
字号:
<p style='margin:0cm;margin-bottom:.0001pt;text-align:justify;text-justify:
inter-ideograph;line-height:18.0pt'><span lang=ZH-CN style='font-size:10.5pt'>本章的最后，我们将以</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>JPEG</span><span
lang=ZH-CN style='font-size:10.5pt'>压缩编码标准为例，看看上面的几种编码方法在实际的压缩编码中是怎样应用的。</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'><o:p></o:p></span></p>
<h2 style='text-align:justify;text-justify:inter-ideograph'><span
style='font-family:"Times New Roman"'>9.1 </span><span lang=ZH-CN
style='mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>哈夫曼编码</span><span
style='font-family:"Times New Roman"'><o:p></o:p></span></h2>
<p style='margin:0cm;margin-bottom:.0001pt;text-align:justify;text-justify:
inter-ideograph;line-height:18.0pt'><span lang=ZH-CN style='font-size:10.5pt'>哈夫曼</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>(Huffman)</span><span
lang=ZH-CN style='font-size:10.5pt'>编码是一种常用的压缩编码方法，是</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>Huffman</span><span
lang=ZH-CN style='font-size:10.5pt'>于</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>1952</span><span lang=ZH-CN style='font-size:
10.5pt'>年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。举个例子：假设一个文件中出现了</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>8</span><span
lang=ZH-CN style='font-size:10.5pt'>种符号</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>S0,S1,S2,S3,S4,S5,S6,S7</span><span lang=ZH-CN
style='font-size:10.5pt'>，那么每种符号要编码，至少需要</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>3</span><span lang=ZH-CN style='font-size:10.5pt'>比特。假设编码成</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>000,001,010,011,100,101,110,111(</span><span
lang=ZH-CN style='font-size:10.5pt'>称做码字</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>)</span><span lang=ZH-CN style='font-size:10.5pt'>。那么符号序列</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>S0S1S7S0S1S6S2S2S3S4S5S0S0S1</span><span
lang=ZH-CN style='font-size:10.5pt'>编码后变成</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>000001111000001110010010011100101000000001</span><span
lang=ZH-CN style='font-size:10.5pt'>，共用了</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>42</span><span lang=ZH-CN style='font-size:10.5pt'>比特。我们发现</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>S0</span><span
lang=ZH-CN style='font-size:10.5pt'>，</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>S1</span><span lang=ZH-CN style='font-size:10.5pt'>，</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>S2</span><span
lang=ZH-CN style='font-size:10.5pt'>这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使得</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>S0</span><span
lang=ZH-CN style='font-size:10.5pt'>，</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>S1</span><span lang=ZH-CN style='font-size:10.5pt'>，</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>S2</span><span
lang=ZH-CN style='font-size:10.5pt'>的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>S0</span><span
lang=ZH-CN style='font-size:10.5pt'>到</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>S7</span><span lang=ZH-CN style='font-size:10.5pt'>的码字分别</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>01,11,101,0000,0001,0010,0011,100</span><span
lang=ZH-CN style='font-size:10.5pt'>，那么上述符号序列变成</span><span style='font-size:
10.5pt;font-family:"Times New Roman"'>011110001110011101101000000010010010111</span><span
lang=ZH-CN style='font-size:10.5pt'>，共用了</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>39</span><span lang=ZH-CN style='font-size:10.5pt'>比特，尽管有些码字如</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>S3</span><span
lang=ZH-CN style='font-size:10.5pt'>，</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>S4</span><span lang=ZH-CN style='font-size:10.5pt'>，</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>S5</span><span
lang=ZH-CN style='font-size:10.5pt'>，</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>S6</span><span lang=ZH-CN style='font-size:10.5pt'>变长了</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>(</span><span
lang=ZH-CN style='font-size:10.5pt'>由</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>3</span><span lang=ZH-CN style='font-size:10.5pt'>位变成</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>4</span><span
lang=ZH-CN style='font-size:10.5pt'>位</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>)</span><span lang=ZH-CN style='font-size:10.5pt'>，但使用频繁的几个码字如</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>S0</span><span
lang=ZH-CN style='font-size:10.5pt'>，</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>S1</span><span lang=ZH-CN style='font-size:10.5pt'>变短了，所以实现了压缩。</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'><o:p></o:p></span></p>
<p style='margin:0cm;margin-bottom:.0001pt;text-align:justify;text-justify:
inter-ideograph;line-height:18.0pt'><span lang=ZH-CN style='font-size:10.5pt'>上述的编码是如何得到的呢？随意乱写是不行的。编码必须保证不能出现一个码字和另一个的前几位相同的情况，比如说，如果</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>S0</span><span
lang=ZH-CN style='font-size:10.5pt'>的码字为</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>01</span><span lang=ZH-CN style='font-size:10.5pt'>，</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>S2</span><span
lang=ZH-CN style='font-size:10.5pt'>的码字为</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>011</span><span lang=ZH-CN style='font-size:
10.5pt'>，那么当序列中出现</span><span style='font-size:10.5pt;font-family:"Times New Roman"'>011</span><span
lang=ZH-CN style='font-size:10.5pt'>时，你不知道是</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>S0</span><span lang=ZH-CN style='font-size:10.5pt'>的码字后面跟了个</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>1</span><span
lang=ZH-CN style='font-size:10.5pt'>，还是完整的一个</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>S2</span><span lang=ZH-CN style='font-size:10.5pt'>的码字。我们给出的编码能够保证这一点。</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'><o:p></o:p></span></p>
<p style='margin:0cm;margin-bottom:.0001pt;text-align:justify;text-justify:
inter-ideograph;line-height:18.0pt'><span lang=ZH-CN style='font-size:10.5pt'>下面给出具体的</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>Huffman</span><span
lang=ZH-CN style='font-size:10.5pt'>编码算法。</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'><o:p></o:p></span></p>
<p style='margin:0cm;margin-bottom:.0001pt;text-align:justify;text-justify:
inter-ideograph;line-height:18.0pt'><span style='font-size:10.5pt;font-family:
"Times New Roman"'>(1)</span><span style='font-size:7.0pt;font-family:"Times New Roman"'>
</span><span lang=ZH-CN style='font-size:10.5pt'>首先统计出每个符号出现的频率，上例</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>S0</span><span
lang=ZH-CN style='font-size:10.5pt'>到</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>S7</span><span lang=ZH-CN style='font-size:10.5pt'>的出现频率分别为</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>4/14</span><span
lang=ZH-CN style='font-size:10.5pt'>，</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>3/14</span><span lang=ZH-CN style='font-size:
10.5pt'>，</span><span style='font-size:10.5pt;font-family:"Times New Roman"'>2/14</span><span
lang=ZH-CN style='font-size:10.5pt'>，</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>1/14</span><span lang=ZH-CN style='font-size:
10.5pt'>，</span><span style='font-size:10.5pt;font-family:"Times New Roman"'>1/14</span><span
lang=ZH-CN style='font-size:10.5pt'>，</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>1/14</span><span lang=ZH-CN style='font-size:
10.5pt'>，</span><span style='font-size:10.5pt;font-family:"Times New Roman"'>1/14</span><span
lang=ZH-CN style='font-size:10.5pt'>，</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>1/14</span><span lang=ZH-CN style='font-size:
10.5pt'>。</span><span style='font-size:10.5pt;font-family:"Times New Roman"'><o:p></o:p></span></p>
<p style='margin:0cm;margin-bottom:.0001pt;text-align:justify;text-justify:
inter-ideograph;line-height:18.0pt'><span style='font-size:10.5pt;font-family:
"Times New Roman"'>(2)</span><span style='font-size:7.0pt;font-family:"Times New Roman"'>
</span><span lang=ZH-CN style='font-size:10.5pt'>从左到右把上述频率按从小到大的顺序排列。</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'><o:p></o:p></span></p>
<p style='margin:0cm;margin-bottom:.0001pt;text-align:justify;text-justify:
inter-ideograph;line-height:18.0pt'><span style='font-size:10.5pt;font-family:
"Times New Roman"'>(3)</span><span style='font-size:7.0pt;font-family:"Times New Roman"'>
</span><span lang=ZH-CN style='font-size:10.5pt'>每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'><o:p></o:p></span></p>
<p style='margin:0cm;margin-bottom:.0001pt;text-align:justify;text-justify:
inter-ideograph;line-height:18.0pt'><span style='font-size:10.5pt;font-family:
"Times New Roman"'>(4)</span><span style='font-size:7.0pt;font-family:"Times New Roman"'>
</span><span lang=ZH-CN style='font-size:10.5pt'>重复</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>(3)</span><span
lang=ZH-CN style='font-size:10.5pt'>，直到最后得到和为</span><span style='font-size:
10.5pt;font-family:"Times New Roman"'>1</span><span lang=ZH-CN
style='font-size:10.5pt'>的根节点。</span><span style='font-size:10.5pt;font-family:
"Times New Roman"'><o:p></o:p></span></p>
<p style='margin:0cm;margin-bottom:.0001pt;text-align:justify;text-justify:
inter-ideograph;line-height:18.0pt'><span style='font-size:10.5pt;font-family:
"Times New Roman"'>(5)</span><span style='font-size:7.0pt;font-family:"Times New Roman"'>
</span><span lang=ZH-CN style='font-size:10.5pt'>将形成的二叉树的左节点标</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>0</span><span
lang=ZH-CN style='font-size:10.5pt'>，右节点标</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>1</span><span lang=ZH-CN style='font-size:10.5pt'>。把从最上面的根节点到最下面的叶子节点途中遇到的</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>0,1</span><span
lang=ZH-CN style='font-size:10.5pt'>序列串起来，就得到了各个符号的编码。</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'><o:p></o:p></span></p>
<p style='margin:0cm;margin-bottom:.0001pt;text-align:justify;text-justify:
inter-ideograph;line-height:18.0pt'><span lang=ZH-CN style='font-size:10.5pt'>上面的例子用</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>Huffman</span><span
lang=ZH-CN style='font-size:10.5pt'>编码的过程如图</span><span style='font-size:10.5pt;
font-family:"Times New Roman"'>9.1</span><span lang=ZH-CN style='font-size:
10.5pt'>所示，其中圆圈中的数字是新节点产生的顺序。可见，我们上面给出的编码就是这么得到的。</span><span style='font-size:
10.5pt;font-family:"Times New Roman"'><o:p></o:p></span></p>
<p class=a style='margin:0cm;margin-bottom:.0001pt;line-height:18.0pt'><!--[if gte vml 1]><v:shapetype
id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t"
path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f">
<v:stroke joinstyle="miter"/>
<v:formulas>
<v:f eqn="if lineDrawn pixelLineWidth 0"/>
<v:f eqn="sum @0 1 0"/>
<v:f eqn="sum 0 0 @1"/>
<v:f eqn="prod @2 1 2"/>
<v:f eqn="prod @3 21600 pixelWidth"/>
<v:f eqn="prod @3 21600 pixelHeight"/>
<v:f eqn="sum @0 0 1"/>
<v:f eqn="prod @6 1 2"/>
<v:f eqn="prod @7 21600 pixelWidth"/>
<v:f eqn="sum @8 21600 0"/>
<v:f eqn="prod @7 21600 pixelHeight"/>
<v:f eqn="sum @10 21600 0"/>
</v:formulas>
<v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/>
<o:lock v:ext="edit" aspectratio="t"/>
</v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" alt="" style='width:389.25pt;
height:247.5pt'>
<v:imagedata src="./chp9.files/image001.gif" o:href="http://www-scf.usc.edu/~flv/ipbook/chap09.files/image001.gif"/>
</v:shape><![endif]--><![if !vml]><img width=519 height=330
src="./chp9.files/image001.gif" v:shapes="_x0000_i1025"><![endif]></p>
<p align=center style='margin:0cm;margin-bottom:.0001pt;text-align:center;
line-height:18.0pt'><b><span lang=ZH-CN style='font-size:10.5pt'>图</span></b><b><span
style='font-size:10.5pt;font-family:"Times New Roman"'>9.1
Huffman</span></b><b><span lang=ZH-CN style='font-size:10.5pt'>编码的示意图</span></b><span
style='font-size:10.5pt;font-family:"Times New Roman"'><o:p></o:p></span></p>
<p style='margin:0cm;margin-bottom:.0001pt;text-align:justify;text-justify:
inter-ideograph;line-height:18.0pt'><span lang=ZH-CN style='font-size:10.5pt'>产生</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>Huffman</span><span
lang=ZH-CN style='font-size:10.5pt'>编码需要对原始数据扫描两遍。第一遍扫描要精确地统计出原始数据中，每个值出现的频率，第二遍是建立</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'>Huffman</span><span
lang=ZH-CN style='font-size:10.5pt'>树并进行编码。由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因而得到广泛的应用。</span><span
style='font-size:10.5pt;font-family:"Times New Roman"'><o:p></o:p></span></p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -