哈夫曼编码算法的仿真和比较.rar_哈夫曼

<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/6265d2e14c65f412591966bd/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6265d2e14c65f412591966bd/bg1.jpg"><div class="c x0 y1 w2 h2"><div class="t m0 x1 h3 y2 ff1 fs0 fc0 sc0 ls0 ws0">哈夫曼编码算法的仿真和比较</div><div class="t m0 x2 h3 y3 ff1 fs0 fc0 sc0 ls0 ws0">哈夫曼树</div><div class="t m0 x2 h4 y4 ff1 fs1 fc0 sc1 ls0 ws0">哈夫曼树（<span class="ff2">Human Tree</span>）也是一种特殊的二叉树，这种树的所有叶子结点都带有权值，从中构造</div><div class="t m0 x2 h4 y5 ff1 fs1 fc0 sc1 ls0 ws0">出带权路径长度最短的二叉树，即哈夫曼树。</div><div class="t m0 x2 h5 y6 ff1 fs2 fc0 sc0 ls0 ws0">哈夫曼树的定义</div><div class="t m0 x2 h6 y7 ff3 fs3 fc0 sc1 ls0 ws0"> <span class="ff1">设二叉树具有<span class="_ _0"> </span></span>n<span class="_"> </span><span class="ff1">个带权值的叶子结点</span>,<span class="_ _1"></span><span class="ff1">那么从根结点到各个叶子结点的路径长度与</span></div><div class="t m0 x2 h6 y8 ff1 fs3 fc0 sc1 ls0 ws0">相应结点权值的乘积的和<span class="ff3">,</span>叫做二叉树的带权路径长度<span class="ff3">,</span>记作<span class="ff3">:</span></div></div><div class="c x3 y9 w3 h7"><div class="t m0 x0 h8 ya ff4 fs4 fc0 sc1 ls0 ws0">WPL<span class="ff5">=</span></div><div class="t m0 x4 h9 yb ff5 fs5 fc0 sc1 ls0 ws0">∑</div><div class="t m0 x5 ha yc ff4 fs6 fc0 sc1 ls0 ws0">i<span class="_ _2"> </span><span class="ff5">=<span class="_ _1"></span><span class="ff6">1</span></span></div><div class="t m0 x6 hb yd ff4 fs6 fc0 sc1 ls0 ws0">n</div><div class="t m0 x7 hc ya ff4 fs4 fc0 sc1 ls0 ws0">w</div><div class="t m0 x8 hb ye ff4 fs6 fc0 sc1 ls0 ws0">i</div><div class="t m0 x9 hc ya ff4 fs4 fc0 sc1 ls0 ws0">×<span class="_ _2"></span>l</div><div class="t m0 xa hb ye ff4 fs6 fc0 sc1 ls0 ws0">i</div></div><div class="c x0 y1 w2 h2"><div class="t m0 x2 h6 yf ff1 fs3 fc0 sc1 ls0 ws0">其中<span class="ff3">,</span>为第<span class="_ _0"> </span><span class="ff3">i<span class="_ _0"> </span></span>个叶子结点的权值<span class="ff3">,l<span class="_ _0"> </span></span>为第<span class="_ _0"> </span><span class="ff3">i<span class="_ _0"> </span></span>个叶子结点的路径长度。如图<span class="_ _3"> </span><span class="ff3">6.19<span class="_"> </span></span>所示的二</div><div class="t m0 x2 h6 y10 ff1 fs3 fc0 sc1 ls0 ws0">叉树<span class="ff3">, </span>它的带权路径长度值<span class="_ _3"> </span><span class="ff3">W<span class="_ _4"></span>PL=1×3+3×3+2×2+4×1=2<span class="_ _1"></span>0 </span></div><div class="t m0 x2 h6 y11 ff1 fs3 fc0 sc1 ls0 ws0">如果给定一组具有确定权值的叶子结点<span class="ff3">· </span>可以构造出不同的带权二叉树， 它们的带</div><div class="t m0 x2 h6 y12 ff1 fs3 fc0 sc1 ls0 ws0">权路径长度并不相同<span class="ff3">· </span>我们把其中具有最小带权路径长度的二叉树称为哈夫曼树<span class="ff3">·.</span></div></div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div> </body> </html>