一,介绍
1)构造赫夫曼树的算法是一个贪心算法,贪心的地方在于:总是选取当前频率(权值)最低的两个结点来进行合并,构造新结点。
2)使用最小堆来选取频率最小的节点,有助于提高算法效率,因为要选频率最低的,要么用排序,要么用堆。用堆的话,出堆的复杂度为O(logN),而向堆中插入一个元素的平均时间复杂度为O(1),在构建赫夫曼树的过程中,新生成的结点需要插入到原来的队列中,故用堆来维持这种顺序比排序算法要高效地多。
二,赫夫曼算法分析
①用到的数据结构分析
首先需要构造一棵赫夫曼树,因此需要二叉链表这种数据结构(类似于二叉树);其次,假设树中各个结点出现的频率保存在一维数组中,初始时,根据该数组构造出每个结点。
算法每次从选取两个频率最小的结点,构造出一个新结点,新结点的频率为这个结点的频率之和。那么如何选取频率最小的那两个结点呢?
一种方式是先将结点的频率排序,另一种方式是使用优先级队列(比如最小堆),这里我们使用优先级队列。
结点之间要能够比较(比较谁出现的频率小啊),故结点类需要实现Comparable接口,结点类(内部类)的定义如下:
private class BinaryNode implements Comparable<BinaryNode>{
int frequency;//出现的频率
BinaryNode left;
BinaryNode right;
BinaryNode parent; public BinaryNode(int frequency, BinaryNode left, BinaryNode right, BinaryNode parent) {
this.frequency = frequency;
this.left = left;
this.right = right;
this.parent = parent;
} @Override
public int compareTo(BinaryNode o) {
return frequency - o.frequency;
}
}
注意:这里需要一个parent指针。因为,在对各个结点进行编码的时候,需要根据儿子结点,向上遍历查找父亲结点。
对于赫夫曼树而言,需要知道树的指针,同时,我们还额外定义了一个属性,记录树中的结点个数
public class HuffmanCode{ private BinaryNode root;//root of huffman tree
private int nodes;//number of total nodes in huffman tree private class BinaryNode implements Comparable<BinaryNode>{ //........
②构造赫夫曼树的算法具体实现步骤
1)根据各个结点出现的频率来构造结点。初始时,根据每个频率构造一棵单结点的树
2)将结点放到优先级队列(最小堆)中保存起来,这样易于每次选取当前两个最小频率的结点
算法正式开始:
3)从优先级队列中弹出两个结点,再创建一个新的结点作为这两个结点的父亲,新结点的频率为这两个结点的频率之和,并把新结点插入到优先级队列中
4)重复步骤 3) 直到优先级队列中只剩下一个结点为止
最后剩下的这一个结点,就是已经构造好的赫夫曼树的根结点
注意,第 1) 步中构造的为赫夫曼树的叶子结点,而在第 3) 步中构造的结点全是非叶子结点。赫夫曼树中只有两个类型的结点,一种是叶子结点,另一种是度为2的非叶子结点
赫夫曼树中总结点的个数为:叶子结点的个数乘以2 再减去1
1) 和 2) 步骤的实现代码如下:
/**
* 根据各个结点的权值构造 N 棵单根节点的树
* @param frequency
* @return
*/
public List<BinaryNode> make_set(Integer[] frequency){
List<BinaryNode> nodeList = new ArrayList<HuffmanCode.BinaryNode>(frequency.length);
for (Integer i : frequency) {
nodeList.add(new BinaryNode(i, null, null, null));
}
nodes = frequency.length<<1 -1;//huffman 树中结点个数等于叶子结点个数乘以2减去1
return nodeList;
}
3) 和 4) 步骤的实现代码如下:
/**
*
* @param roots initial root of each tree
* @return root of huffman tree
*/
public BinaryNode buildHuffmanTree(List<BinaryNode> roots){
if(roots.size() == 1)//一共只有一个结点
return roots.remove(0);
PriorityQueue<BinaryNode> pq = new PriorityQueue<BinaryNode>(roots);
while(pq.size() != 1){
BinaryNode left = pq.remove();
BinaryNode right = pq.remove();
BinaryNode parent = new BinaryNode(left.frequency+right.frequency, left, right,null);
left.parent = parent;
right.parent = parent;
pq.add(parent);
}
return (root = pq.remove());//最后剩下的这个结点就是构造好的赫夫曼树的树根
}
三,赫夫曼编码
①如何编码?
编码的实现思路:
从赫夫曼树的叶子结点开始,依次沿着父结点遍历直到树根,如果该叶子结点是其父亲的左孩子,则编码为0,否则编码为1
对所有的叶子结点执行上面操作,就可以把各个结点编码了。
编码的思路类似于求解赫夫曼树中所有叶子结点的频率之和,也就是整个赫夫曼树的代价。求解赫夫曼树的代价的代码如下:
/**
*
* @param root huffman树的根结点
* @param nodeList huffman树中的所有叶子结点列表
* @return
*/
public int huffman_cost(List<BinaryNode> nodeList){
int cost = 0;
int level;
BinaryNode currentNode;
for (BinaryNode binaryNode : nodeList) {
level = 0;
currentNode = binaryNode;
while(currentNode != root){
currentNode = currentNode.parent;
level++;
}
cost += level*binaryNode.frequency;
}
return cost;
}
②如何解码?
解码就是根据0 ,1组成的'字符串' 去查找结点。步骤是:对于每个叶子结点,都从赫夫曼的根结点开始,取出每一位,如果是0,往左走;如果是1,往右走。直到遇到一个叶子结点, 此时取出的 0,1 位(二进制位)就是该结点的 编码了。
public Map<BinaryNode, String> huffmanDecoding(String encodeString) {
BinaryNode currentNode = root;
//存储每个叶子结点对应的二进制编码
Map<BinaryNode, String> node_Code = new HashMap<HuffmanCode.BinaryNode, String>();
StringBuilder sb = new StringBuilder();//临时保存每个结点的二进制编码
for (int i = 0; i < encodeString.length(); i++) { char codeChar = encodeString.charAt(i);
sb.append(codeChar);
if (codeChar == '0')
currentNode = currentNode.left;
else//codeChar=='1'
currentNode = currentNode.right;
if (currentNode.left == null && currentNode.right == null)// 说明是叶子结点
{
node_Code.put(currentNode, sb.toString());
sb.delete(0, sb.length());//清空当前结点,为存储下一个结点的二进制编码做准备
currentNode = root;//下一个叶子结点的解码,又从根开始
}
}
return node_Code;
}
第18行,当解码完一个叶子结点后,又从根结点开始解码下一个叶子结点。
四,赫夫曼编码的应用
①文件压缩
假设有8个字符如下:a,e,i,s,t,空格(space),换行(newline)。'a'出现的频率为10,'e'出现的频率为15……
由于有8个字符,故需要3bit才能完成表示这8个字符(2^3=8),比如 000 表示 'a';101 表示 空格字符(space)....
由于 'a' 出现了10次,故一共需要 3*10=30bit来存储所有的'a'
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAg0AAAFsCAIAAADAOh2hAAAgAElEQVR4nOzd+1tM2x8H8E81KXSlqFSkqFAqRSq6SCFUFCFEOUWiKOIgFCVJKCVJhNL9bmqapmlmmilzfDkXx3nk2hNPzTP/w/eHKZrbNiVmysfz+sXea/as2XvPeu+119oTsPlchBBCSBqQew0QQggpMswJhBBCRDAnEEIIEcGcQAghRGQscyL2wtGFjosQQggpvtSidDnkxEPW4/SHmQghhBRf1fN6OeQEQgihiQdzAiGEEBHMCYQQQkQwJxBCCBHBnEAIIUQEcwIhhBARzAmEEEJEMCcQQggRwZxACCFEBHMCIYQQEcwJhBBCRDAnEEIIEcGcQAghRARzAiGEEBHMCYQQQkTkmhP95Py7vx+MD/Fb77r6Qmm7vPcF+lEGqMUlZ2MTQzcGuLkdut0q9/og9HOx3pVdzY3/7WCg92rXrTXtcq/PSP2EnOhue1GUnn3s4Inw0MMRUSknk0ru1fR2s/lcdm9FcvLB8F3WkwD0Iwrb5L0vEJvPZX1sKHh49ui5qLBDYXtPHTmel3XnTybrOzf7uSHz8qHIaBctgEneGc3y/owjw+N0fGZ/Q3+3/OuJCLEG5HkcGf/kJZ6L3rlOD0DZvrBVesluhlitGAPyP7t+ZE70Uwpvhq20mWXisGJD9L4DKceOJh/YHe5ta6IKMN01q5YhKPby7ELMCfnjNLWe27nO0sh8oVtoaPiZI0cvxUUeCfZaZqgKMM3nVGX/d7/Fu2xvrfGXE22U/V4ejguMlQEAQF3XyMDA2MDASH+6nvZUEgj+6e0pwLNXoQ00JC5TAQAAkrqWzjRDA0PDSQAAOgaGRnq6OlMnCQ6kQVDehx9YDWrjpunEOfHxXqT/MoclBoKzTU1/poGxgcEsfS1NbeNla/Y9qBG66cKj3Tq12mXnmceffvgO/FE50fFn1s7levordp5ntItejQ5Qco7YO2U1DC7vSXciYU7I1eeGjMP20w0dd9wupfBE1nY11e618zhVI7p85D4UBMwcfzkh0NYUpAegFZRDEd451L9L048udc5qYMq7hogA88UZF4f1cWWljZ8Gr80pVWu1AMyTqwevVgfoVeQLu70WBTd0/LhqtFN3G36jP8Fl87nsjwWBBgA6a669G1zS8XdOuMtkAB3P2w2ML8X6axKcSTB9zdW3P3wH/pCcYLy46Gs4yXhnevVnyQVY72tLXnEG/9uT4TxJ8XOii/pvG13+1fgB+huSg/QnmQWkvmBLLsCjV3a2ML7/jT7e2Ww4XnOig3VgNoBW8E2K+Nr+jpY++d8ZQARY7+sf/yd0eovmhKDYx4aSf6V8C0QMdDS+6RxpNdrb98ySJSc+l0XOB9BZe/3d14XMvy+u1ASwPFgyvFEdYFBEz70f0lL9gJzofbTPlkSyjy7ula38OMiJ7pbGsIWO0Y9+fP/up2PeT7RSUV0Q1cH84e81rnOCc2iutJxA45DEnJAVj5Z3eNGiU2UjbY5lzomKaCvRnGDzW84tV4Zp67PfE7z2R7VUY54T7PKMJaqgH9hAl/UlIjnBY5H/rG/82EXwEsY7ctXftA4JqzjUV0/IgwHLobyk0ETulvS31//vSYuUXo5gR9N7Gmp6OoffK+vgnnbTBpi3X8re76a/bar6hy75zkN/R+Pfre28wXdv+O+7x4THVAc30X4S6O8Z1RwkHov8J7n1G+MWnNaXdeV/Utt5RDnB+kSr/R+5dUD+O0QaRlesucSc4HUxRM8xwiPO62z5q67+PeHp/Z5c9YxMHdobrH5WB0/K9r8YYJL/JlMl3BskODmHf1m4rD5qzfPmNsJDwPpErfmTSv/+O5AKQIac6G5/3VD/niO2nF1+baUmwOyT0nNCSjsja070V8ZYi+VEf03cIgC7+LLh3zgei/zP1+P+7ZbqdX35/8gtfUSnn0RjnRO990NNAczC7/fJ/JKhnKB+LD93YLmxumBESUnfMzL7lfDn6avNOBuwzNbUeLb+FADQsAopIQsOM6Vhj5uThT4JAGYEkzsotGOrLacAgE5wNoXPZfNZlSWHNnpamZjN0tcAgCmW+7PqRRq4fnLOuXVL3D3XhW0NDHK2tF62raC6nc9l9zck+RurAYDqnKV+Xh4b1ux6RB761nW3UBM3rFxku8rDebH+lJm2QXnlQ8esPTduhc0CfRUAMAq5/aG96JKvmQYA6PhWKM6sOGZhjBGAcRidNaIX0v/MORTm7e7n7rJigbGe9ozFXuElDaLfmb66jERvq9kzje2cPQM9lrk5um1db6shmhOst8UJoU4Llrq4r7LS19SziUgu+aCI93AYTyXnRHOx74psMkuWI86j3c3wd1yy2NnPxdJw6nSnLUmdHcIXDayqkigvu1kz5lov3ejr5bdyuW9AbG1F5j7vY8+62Hx63pGVNtb6KgBguCX/o+AlnSVX1i9ZbDwFAJSXpLwevjWpJ2dr496hL4t+ELmjrTNlm5eJ2tDXbunxvEbRtOA01B5es2Kpe8jm4D1rli22cDpwsayP20Y95Lty4fyF8+bZObisX7+f0sHmc9mfKk6Ge6/0tLVcZLXY2ze8gSb3YycRUU58ariWvNnLz2PFakfrubpaRlYex7Kqh1pexovkVXPUAYA039l9g5dHUNjlf740U99oZ2TOiepDojnR1VixZdbkOdsbBa1HZ2nWRsfFxlOHH3eClorXXpwT4mQ1x8LOyny2tgqoGfkefSh7Ez3mOUFnRc0G0NmeN4Lr054M50mg6bFptavjhnOX7zxvo72vz0lyngowfdetL19L5uvb4Svmrjh3q/4zl83nMl9e8ZsJsCD28dfQZpecMQOY5hG3adlK7y2JB/cEWy+If9A+0Jp7zNFs7eGcf9hsPpc9QE7frgdgEdP19UYk683tPcuMFh+5UTt4NtBzdukBzNrypIPN57J5T07YS0jpNvpBO8NF4eR2Fp/L5rXdOrZABTRXZtd+7eh8rjhgCaDvtXu3s6N/yL4zEb52C/fQRtYo/0CfHv82D2D6BsKerIiuxsfbF9ltuvC/wZuzrPelxzfqAUxflT9shK2vPH61zhSHsMy/v+xkTmPjAVt14Zz4+OjAcv2Fx+5SeFw2v7v5yW/WJNBcd7aSqMMnH4KcmOyZcL2pIK+pIKcqK60w+fcrR3atnmV3nfy1uZd6xBn3z9jrO+67/a6bzeey3twJtyeBtsepZ1/2D6sk3U1Hc+HOsidfzh/Gq4JIFw1Qd0x+Lbz9rzkh0Jrmqy6SE986OdmlSXMBNJ12+9qv8D94717VG2br87wDnhoAev51wy5leG258XaGznuv/jV4xFvrAqcDGEXeofK5rNfZ/oYABptyhU+hNnKIkeG6q2/kf+CkkZYTzH+vhThaBxTWDV738OjFmaumA0zzT6keavFZf5+yFu9PyNDOjCwnVK22XDxztvDK1drbmRfWWC32iqptEe4XUtP9pgodd8ktFbsiy2P2yv23XgvyrJvCOLPGfnX6SI7OGOdE8wM3NYA5p8ol3RSSoifDeRKo2IRe+WvYCNLn8ihLgLkRQ/0SVlGcMagvT3n15YVt6T5qYLR1+BeGXGCvBGC0LaV88FVdjAFuO22PMag5F7YIV3JGMJkxtHNbr2zV01h5qmpY8jP/y/st0GNXbRtL2t7/XBnnNNUktpj2Zcmn8ujFSqDulPi/L33V1uTlSgCz1t0amtA2wFGgiTFvrriqA1hGl8jcLjNenF2uM2OjyINC7wtCTAG0vC/9J+gKdJacW6iqufzUC+E+u+h9J/bji7ZTzMPufh3H6iw5a6UEao5ZdWMwbD6mBDkBRk6rgtb4Bq3xDfJdtd7dxdNxwSwNm+E5IeWId3TF22ia7qJ+HQSidx6yVAK1obOO3nl4waSpztkNwh+ccStcHyY5p/YM276rslhOMPIj9IXaCxlOTvKdJcpAmh+dVTvs6Hd0Rs8BMI5/NDT/sptc6jdda/gpzWUPUHJO+LjH5jXzuGw+p/KKnQpoeD0c3vZxKi/ZzT98nyb0WRSL5JzobzjtraW/M0+410jP228EoOFVTBEcaIk58e12ZuQ5EXT26KGkqLD9/isdjfXmOqw7mVkp1AlgFuw3+HZO9BaFzJmxrkZoIID+qr55JDPdxzgnGvNsAWD+pboRtIaSx7GpqZ6qw6Yzs4pT1q+/8GBYN6Xt8lp1mBGQO2y+M7nImSR8YNh8bjvjyLodR4uGXe80P3JXh+kbhybAMZ4dsyZpuD+QfvAk7f32jggT0pxIFpvN57L72x7XX4yNDfB0t3PavPsUo2PYpyCBUcjtj1K2LF+vkm0AwOZYlawDA8y7h4xA3z9HdI45p/yiFYCqU0ELi89lfygINAStLTmit/JFcqKvZK85afbvZR18LpvPae7KT74QtnHjUluPNaE3Sqly3znCpN938nHLHp4TEo84qzjBVGX+gUefuWw+l/Gm8mbB0V07VzktW+ZzKKn4A5fN78jbow+66669E3lfxq1wfVBzSXszfPuqYjnBvHPQcHh7IcvJSb7nrAr6QcJfFnbP5WWTQG9PweD+7689ak+a6neFLH3PsF5fXaUNk9zP1X05iwbqE32c456K39lXIBJzgkbdbQjTNtSJTo1lcOMtAVQ9LjbyuGxpOfGtdob9XfedOI2NMc66oGYfdvPNlxuzrKI442/nxPuba6aBwa6Mmu/opv+Q/sSs2Acj+BEOyTnRlr5aTdpjL8x35ZeTA211QDQn7knICSED7SWPYv2XacGw49d421EFzKM50ufDSdj7XVVXrAHmBiaErvNb6ea3Nvj3M1cZLWLjWoqdE2+uuE4GmBNWJOOdyk+lEeYAixOrxXKF1rrTAGBGVFEbn0vviDABJdubZNERe+GcYD4/YQVgtidiW4iH2xoP398O/F5e2qioM8qk5QTzbW356+ENoqQjPlB/zA7AMmjvgfXua1a6B4dEXr9R/GrYrMpPJXvNQWnpuQbRIWJBTrheGpYTaV4ScqJQKCdkOjnJ95dLyIk3V1zUh+XEqwsOJJh7toLw9gCjYL8BgNWhoRssHV3xLpsuin0WxSIpJzofHDcFsEp4ITbM23t/hwmA0baCj1y2tPtOw0lqZ9jflRNcNr+7pWazPsDM8Fstg0tY92TJCV7bjb1GAKA0w2plRMz5Jw2is3tkMMY5QaOEGgCoOCfVyj53ZSQ5wXx9/1T0quUbgqOLbietFutPEOTEQGvhjVBPb6/NZ9Nzc92G5Ty75LQZgHXiX9KHTyXsfWbBfgMAs22FxXW9BOOuip0Tvfe2GwOo2J36S7b5D++ur9ICcEppElvFfJ5oOTQuRSn30QB1t4dtoi8Xzglayw4DgDkH0u7+rVhzwCSSlhNiJB3x3qIQYwDL0AvUJ5K/ou9ueGuBmm+m2Eyw0eWETCenLDnR0XlwDoBVVhPxAeroirMEMIguovG5bD6r+KRbULXiTNaQTFJOtGf6awDYnv1PrPxAfYItwPQNOe+5bOKckNrOcNnfmxNcdt+jMLPhy2XLCT6X/akh89Qa6xmCp7xBxXjZ9oKKEd0VHOv5Tu9z100HUHUQuqFJbDAn7kjKic3DcqKz8naglblzRGUTnc+VfN9JSk7Qn13wtzNddjxHMEwt3B/klCVbABhup0h/gEBSTtw5aAgwP+4ZcQs72GrkK2ZO8Ok3tukAkOyvyjYe8C7HRxtg4dEKsTubDO5RCwCThBI6n0upXKNJ0J9YNZQTlJ0GAPNSaxVowEa6wZwQfR5bnKQj3ntvhwnAovhKaRdP73J8tGXsT7Sl+6qDYfAtwpyQ5eQczIknknIibDAnBJ/aIPreN9oUHjl5tTro+GT0cNlvb272/k3WHqr8DObE+crhOXFtsybAvNg/xNqu/prYhQDmEcWfuGzpOUHYznDZX3Lijow5sUbsPmRrsosyqDgOHejBnEj+Zk4MrmXVt6bHHvBeoA8AMzaUtcp+fTbmz08wCmNNAUAv9AaZqHfT3fZqaA54T4bzpK+n5pC29NVqMCPg5mAMcGoKfPQnW/7W/uW0bru8Vh30hO6Vk+85k0B/U5PQqc/486K3ofr8Ew+/5FDzI3d10P1yF7LlsfdUgDknSqX2IiXs/e66G4uVQM25oJlwX1NTPUlgGJSnoDnBbWsNMwEAg4Crr4lmo7I+tpD7ugcn22h4pPeIFqA2BE4DvcDGDjaf28E+OAekjk+QPNIFN7tZfyfZKoGa1+A9XwUnaDGn+l9v+UZJSUec9+TUUiVQX578r5SdLNixUscnhudEe6a/xrDvhQCz8KAhgN35wfZCppOTfH+56tAh++rNFRd1mBaaP/hlfHvNSxPAMurBt+4HUmoDpgPJ/lptVc6qFRk1ijYNQUKFq9ZqAcwWmnHDLkmaCzDF/QFVtPyH2/4zvnazJObEN9sZ9mBOgO1tyjeqJ8gJLe9MkfOhv+bwwq+3vwZzAhaf/9IBIs6JIczX2ZuMQCPghuwPjY7989is19mBcwBAwyWjTOplyKfHMYERdwQTXXoynCeB7g6RqbRt6avVYNr6G4Jxoc+VMQsA5n+dmcP85/LamQDqbmnD2izyPWcSTNtYP/zUZz8+bwEwJ6pzaPhhgJy6VQ9AzeU+dajCmV5aAFqe56XdfhHs/a+Tr7hsPpfBjbdWAli0n/Cxc2qqJwn0Rb7VioTXem2PMQBorE58JPWDdD4877OXwmTzOx+cmAug7pzbJNwJYN49bKy2KKpYsH/6HuyaA6DulPhM+LrszY0100DZNXVwULS/Js5eCWB+5E94FPy7CXJCzefKtx4ml3jEOeWpC5QA5p0skfKNYBXFGgOoOV6tFW5h265u0RHOCWZhjBGoLb84/N5If1PyRk0Ai8PcwR0uy8lJvr9cFXTX1wo/D/vmios6aIfktg6dHun+GgAa7rebvtHt+1QaYQlg7ufn6ntBWhwqEkFOGB99NHwklc6MMgNQX3Ve5LY5jRpmrD7/N8bgjHZBTgybFcaVpZ1hD+XEwhzyN6onyIkpK0Wmrra1hs8GpXknv/wJBkFOLDr9cqiMpJaK/vx2/t8ig68t51zVpu+8LftskR/y+07tXWd9zQBA3Sr8bFGPaOPLeFVwyH+WutVQo9+T4TwJSO5pwnMq2tJXqwHJMVnwffhUFjkPQNMt6QWHzWc3Nh3ftHnb4aNWSqC+5GJp29AFKfmeMwlUlxUNvxzofHRyDsBU19wGBp/b8W9B/N41W1PCLZVAbUV88cfBeZylaY5qAMrz/X9vbxt6MoVRWhjmE5XZMMBl81svuJOAZHdseMPHa7u+2wAA9DfG53/5TZhPDZmJa1Ynf2kOqKmeJOF5jYqnr/JUsDEAqNkFn6JRRZuD/pa8ZG+jKeaCLwDrdXagMYCOeyLn61MgNFb8UjOng/Qv3ThOTa7bFADl+f6JT+qpA1z2QEdV48lNnpb6AGB1+PHgbavu5qpNMwHAcFUcuXnosq6zpizKZ1OsrD/68rMMzouVdM9NmOQjznpzM2AWAOh7phY2Dl3r0P+8vm+z76EOJpvPZfx53lUDQHnOhqw7VR+62Pwu6v8Kju91nm8IwjnBbalYowWkRb8XkQe4bH5XK+dK+EZn3532UwBmH8gjCxo4GU5O8v3lqkByErlX/uaKizqouKV+GYKicxIc1AGU52y4/rB5sPXsbuOk7dy8Lf3l8K92V/W1JSQAvbD8cfH3RQQ5oSHSQeS1XgszANBakVXxNQN6y+I8jR3PPfp6Y/x1mpMqqDifGPYjyrK0M4M5YXJc+q0LAUFODJtcw3hXX5CzxVpDxSDgzOOvGSDICdMI5pc5ERJaKmp9kLXf8eL3X8K7u6UpwlLbfFeL9Pk+Yn7U78Wy3pcmHXKfPQWANGPB2oDQ44diL8ZGHgnx9TDX1dK38guJLa1t53Ob6yJ8vK2mAABMX7h6lf+lUhqfy+rJ27vZ1VITAEB3iZvnzoTi3s5H52xUAACmauvqzPY7dKunm/WuMMyWBKBqn1HD4FGuH12z3GYyAMBMG9eNmxKYgw0ZnXV4EQkAYMo0bZ35HtFPqCxee/5RKxUAVdfEwa89ry3/rIcBAABomJhbLjLV09W33n68YHAKWldd4SptAJg2z9HH2dbJbXcNlcXnsnvLEoNNBb9WrGY4x9xCX2umlW/ybcHjrKz/boZtdp0/FQBguqOb5+7EBwp705ZHL87bvWK+OgBJ38F9Y0xk9IX4mJN7g4OXzdXX0Lfz2HIh68vEbfofFzfZTYVJpi579x28ELtv/wbf0Ki0LobQLY4Byo0jdlMHR800pk5SNw2Iy3uev8kQACabe3r4Jtxq5nPZfOajrLUmgj04WX/2gtn6unqWQXG5r0b8uwI/UkfBMQ+7RdMFx9nE0cFp+5kySVMMiY84jXXK11zwUdX151mYGmpPt11zqOHLk1NdTdV7bTUHd9lUTVV1i9WHGutv7hW578Rlf6qI99IAAICpOjqTp5p7x1ForE+Vx1ZrAYDR/sLBi0Sik7MtJ2HNctspAAAzFrlsDDzKYLL53eTaL19G3QWrV21MEyRKdzP50EoTAADQMpxrO9/EQFvffkN8S5voTa3/MtwNrfazRvzreD8X8/651UtcHBaaC374Ydq8ZQ72Xlsuf+kDfapJ3ms9BVRNVgeFnzt6KHGHX1DAvvuVbcPvjg48SdmoAwDaC51cPe1sfPZk93R/q51hPbyy2X35TACAyXOd1q3ZXdEi8a4gtfk39+XzpwlOBHUdfcMZBiZGRhaWdr7+kXcff/05577Hx8I87IwAANQsl63cvPfaq26JLVXH8xPWADDZwNLDJ/DA9o1+NrMXuu160DCCR9x++N8p6m8ra7p88mLMvvg9YYmH42+kXq59WPNxVN1SHqOiJiUh43xmB+Vr37y3Nvvu9fJvXHt2t/2RdzYjMelxSdPX/GdW1lzK5Ard8WC8qci+c+pISvzxvGv3/hU53dkNzZcSL/2eXF5cIzSHpKu58+a5zPjDaafOl5c0Kt6DxCPBaX5akHot/kBixO6jUQfTk5If5d37kyHpbGaTnxZdyTuRkHMlj90q5YTrpnLzkjPj466kXGfTmHwuu5+cm3/2/IPc28za4b/fxXxTfj3/ZFxKQuLtG8WvZPu1znFqoK2kKuX4xSNHsi5c7WgR32+sDzU5BSfjLp44V1XRMsCVND4xuJ3i0rPxqSfOVjwmf7lD0k8pKsm4K9R9H7uTs7+tpCY1Me1IXGZyZnuzxMvhlpogS7+UegX+kS7ZdfRUF5QmH8s4m95UQZa43z6TC+7+fvTqxavUL9NMZW1nfjDxlqq7/WXp9cIzCRfijmRdyGiub5P7vFiE0NiRkhMK6HPFwaVmgXUy//onGlcwJxBSWOMlJ7ob73nPXDwhf3gfcdmYEwgpMMatcH0gOV1U5HkQfC7jebK7vo57IXlcPAqDRgFzAiGFxbgVrg9gFf9coQb2hTD/y9tjr6pkFVmssNM00HfDnEBIYQlyAiaZzl/gtTtvBD///lPw6A/zQpfMAABd34cUxf/xFTRqmBMIKSxOXfXZEwXXb3eSif/SnHzwOsrJBYXsppbP4+DBOvQ9MCcQQggRwZxACCFEBHMCIYQQEcwJhBBCRDAnEEIIEcGcQAghRARzAiGEEBHMCYQQQkQwJxBCCBHBnEAIIURkLHOi8VVLCbsCIYSQ4mt5S5NDToQdDdfS1UYIIaT4fr9+Rg45gRBCaOLBnEAIIUQEcwIhhBARzAmEEEJEMCcQQggRwZxACCFEBHMCIYQQEcwJJF1fQ27ekYgjEdGZGUWvOT+pGBqOx2p6XlFMKbhekp6UERdf3sQgKs+qaUg+fHzv3rMn02ithCXRD8TqbbhVmHggIWz3iaOnysopRH/bfHwcMswJJFEXuSnGY4mt645tIaEelloAqub+hQ0dP7YYEvPhbkSwl8f6FbazlABgRlRRm5SSzNcFBzYssvHZuHV/wEpbDQDS3F1p1Z/lXf9fzWfy9TPes6eSphiZL3KxMTckAcCkBUHpf0u4MBpHhwxzAknQ1h6zzHHL5Zddgv8yXl4LNgcAi7005o8rhgi0Vq/XJsiJjw8PeNoEPSIzBf/tJ2f+ZgoA5gkPaPKu+S9kgHwpbInroZR7PUOpMNBWkOw0BUDN/WyNSK9iXB0yzAkkpq9kn91s/2qh336hNu80AiC5na4e+DHFECE6K8pUak6wihOtTXfltgxf+KFox2wAVceTL7rkXvlfRnf7OyZTZGF/TawtgIbnlbfDl4+zQ4Y5gUR0NxZ56JjtLOwVXt5fE2cPAFaHn3J+QDH0DYynseZScoL1Kn3ldOMdrSKdM0556gIAsEypVti73r+Gtkur1WBGYO6HrwvH3SH7FXKC0/q6jdbfmnPucN7bH/1e4x/vSdJKda2AGxTRVeySM3MBSPY3yawxL4a+hfksfp7knOiuy3VS11l99Z3oSzrYB80AVFzP1fPkX/9f17tbgUYkM6G7SePvkE3gnGDXVsUFBXp4Bq3fGLraZroKad7eoj6510rhvb3mpQlzTpeLDzJT6/x1AfTD77SNeTH0LczniZaSc4KW6a8BlgdLxMc/P9zaoAdgGHzro/zr/2ti9VYkBRsb+J14JNSfHn+HbILmRH/TpUg7S//YvFccNp/L/lwRbQWam7PFrmqRKDoz0hTAKqtJ/DKf+SxhPgDJ8zJ5rIvJ/VMrPuYLKTnxqTTCAsDuVK34FehA7REbAFXn1B751/9X00o7GRrqYa2nornyQM5fLKHzfxwesomYEzzK1b1mM/3OVn6J6/d56/VI1pkNokNMSAy1IXAawMIcsoS1PZecSABLU5rGupjcP7Xik5oTH277zwBwPNsg4VXUi+4kgMVn/5N//X81tGd5qbd+j4nf6uM6A0DdcldS8fvuwbXj8JBNvJzoanywVk93xbm/v84ZYL44YUXSC2zskHfdxgFK+WoNgPlptRIy9WIW0IsAACAASURBVG2WhyZM8s5oHuticv/Uik9qTry7sUoLwCahUsLMMdqVDVNBzfXSG/nX/9fFo99Pd9cC0A683Cg4RuPwkE24nOgrCbck6UfcoQ5b2FLmo6Fsnfhn94960wmEWh+gC2Bw8J6ESdxvrriqw7TQfOpYF5P7p1Z80vsT+Rv1AUx23ukVf1Vbuo8azAi4+WEMKoBGb6DumKMygPXRZxw2f1wesomWE7Tm7TNBe20VfdjCjps7p4OGRwZOdpJBByfGDIDkkSZh2ODf8zZKyrbZZNZYF5P7p1Z8UnPic8UBSwDVZRdei7+qOclJSXnZWUWbPPPrYd6JNgTQ8auhs/nj8pBNsJxglyTNBbCKfz7sQZWeLB9dgFnbCySkNxLzLttHG8AwKE9sxgWtZYeBqkU0mz32xdC3DOZE5F2x+U7t1zZrAuhvamKIvqq3KMSYZH62An8fRd7oOaG6AAbbKYIHJsbfIZtgOdGRE6oLykuSvwZ1Z8nlDe6L1cF8X/EnuVdvPOC1pHirAxjuoIg+BPQ42UrD8XhF/w8ohr5FkBN6ewrEbtN1Nxa6qkm6ucfoirPUson/A59klLe+4l2zAXTXZA6OOoy/QzbRciJ3lx6A1dH/CfoT3ZSWmDX7L5z0UAXLmFKF/IEtBdRctlYLQCswo3F457e3ePcC08Da9h9UDBET5IT2trxW8bVvrvvqAuj4XHo1fASOefeIhcmePJwLLm/siiznyUBakFTa/mXheDtkEywnumqzl6iAksWxe1Qes6pyv6tTcOarpt8dACx+K2Bdjd4fnatgEwkUUX9toqc6gK5XTs3gmc1ry4t3sDmQS+b9sGKIkCAnlJefb5Cw0ziVWc7qALr+Z8sHnyTtbm6MsHcKvdGDczd+HtbHJ5WvOoUWDlDyU1cbKSkZh6ZVCV2njrNDNsFygst6nbNpNgAAqCqrmK1Pespi85oS7QEAZqzYlsRox1FTmXZjT364qxYAycR97eZI/5VLrZxiMmvEOmRjWwxJ8O7WtlUO9i4Oi231AQBAY46Tg72Lo/uJe0IDFTzqzWNLtABI5kt9w0M2rFts6b4r/U8c+/mp6JxTfk4W1qs3bks8mngtITLa322htoblqn3FlVTxdB9Xh2yi5QSbz+14WZR88WDcnTtVHwXJzKmrPptMfkKXd8XGGV5HWeW5uJMR4efOXOXQpebr2BZDo9dNfZpz5uL+vccO/15e0Yp9Nflg1VKyzmXG7kuIir2efoNWTyX6ReRxc8gmYE4ghBAaQ5gTCCGEiGBOIIQQIoI5gRBCiAjmBEIIISKYEwghhIhgTiCEECKCOYEQQogI5gRCCCEimBMIIYSIYE4ghBAigjmBEEKICOYEQgghIpgTCCGEiGBOIIQQIoI5gRBCiAjmBEIIISKYEwghhIhgTiDp+hpy845EHImIzswoes0ZdTFWH6WKU3Kn8WZG0fmE5ONX/5K+KSSCx2p6XlFMKbhekp6UERdf3sQYycs73lHaiP7uJvrxeNSC3NSSPlnLK+Yhw5xAEnWRm2I8lti67tgWEuphqQWgau5f2NAxqmJUcqTvBi93X7uZSgAwc2szQ96fbvz4cDci2Mtj/QrbWUoAMCOqqE1isYGm3100phjOWbDCzT3Qb8OuTRu3rXH3tDKYF5T7Qd4f4ZfGuH/OcYqmW/obsVXj6pBhTiAJ2tpjljluufyyS/BfxstrweYAYLGXxhxFsSH0GyE6mBOj01q9XpsgJ95c9Vka/HtubEiAo6X5DK3JKirqWjNtV4Zkl0kuj36GzoqbfvMMVUBdUk6Mq0OGOYHE9JXss5vtX00bvpDavNMIgOR2unpghMW+6nyYOBtzYnTorChT6TnRRg5dvD2bIu9KomG6GkpCnDYnpsfPlpgT4+uQYU4gEd2NRR46ZjsLe4WX99fE2QOA1eGnnJEUG45TlmyBOTE6jKex5lJzgv34vINz9hOWvCuJhnRTyJHOXpH571gPEyXmxDg7ZBM+JzrJf5TcYT6h8eRek3GC9yRppbpWwA2xKx12yZm5ACT7m2SW7MWEdFWmzsecGB3ms/h5UnOiJXmt7e66ioct+ddr7j543tqOZ7tcMf5M3eC2OfVvzmAfWkJOjLNDNoFzorPq0YGg3UHB4d5zJ4HR/rsKeNdPEb295qUJc06Xiw1Zc6l1/roA+uF32mQvJqSrKsMKc2J0mM8TLaXlxMc7mw0BQE1DV0MVAABAeabD7qNX/2COl8vVCeXjwwM+yyNbO9h8rtScGG+HbKLmBKP4gueS/VkN/Vw2n569XUfJIig8KbtRsUNbEdCZkaYAVllN4ucr81nCfACS52WyzMWEV3VVY06MFvOF9Jzgd9H7OEMHgkP5Iy8hwlEfAFStdze0KWa7M2ENNGeE23vfqB26fpLWnxhnh2xC5kR3c03wbOtdBYLpZTxK6rrpM1ZH5/yL0/a/jdoQOA1gYQ5ZwtqeS04kgKUpTTIXE16FOTF6hDkhrqupPMgQAIyC897Lv/K/jM6Syx6LI7PJX69Hh+dEZ0PHvWqpD1Io9CGbiDnxqTTCSmPx1Xomn9vxT250iMeGtLtkxXt0RTFRyldrAMxPq2WKr32b5aEJk7wzmmUuJrwKc2L0RpgTXDaPfN5TDUB7bTVd7pX/NXQ314XOViHNWGBlufirOfoAMMnAcq6JoToYb7v9cVwesgmYE9TGzXokqyNcanF2yIo1W091tCtgP05hUesDdAEMDt6jia99c8VVHaaF5lNlLia8CnNi9EacE/yuyjRLALC62oDn/88wQM485u8btEaYr5v1JIBp9v5rfIP8tl6vaB+fh2zi5QTr3hFjUJmzcr3HhpT8xn6512ec6eDEmAGQPNLERhe47H/P2ygp22aTWTIXE16FOTF6I88JblO+HYCSbV6z3Cv/C5M2PiGZwh6yiZcT1IsrSaDtceopS941GZ/eZftoAxgG5Yl1kGktOwxULaLZ7BEUEzKYE1vImBMjNpgTkbJP2+t8cHw2gGk4o1Pulf+FjSgnFPeQTbicGGg4thjAKIToPiAiwGtJ8VYHMNxBEfntDc7jZCsNx+MV/SMpJkSQE3qBTR3y/5jjjSAn9PYUiN3Nk6Lv0V5zULaPLf0s/8r/wjqLj5nKmhMKfMgmXE7wm88uVwZVx6SX3cMWcsic6mYcypZNc9laLQCtwAyhacS9xbsXmAbWto+02DCCnNBZV6Nww3SKT5AT2tvyWmUqz3yQbKemMnfnE4kHAv00zMIYI9lyQqEP2cTLCfaj0xYAKlanHg320D81ZB7z9TldQMaHJ2TUX5voqQ6g65VTMzjsxmvLi3ewOZArtA9lLPaVICeU7XLFhy7QNwhyQnn5+YZvncasjzWXE5y0VI18b9bQ5V3tXx4jb6/+N3NC8Q/ZxMsJLut13s7FJAD12e6+G7Z5OCxdHnK7Ah/GHtk+7MkPd9UCIJm4r90c6b9yqZVTTGaNWHdYxmKUulBnFwd7FztLQwAA0DSzcXGwd/P8jYIDFd/y7ta2VQ72Lg6LbfUBAEBjjpODvYuj+4l7Q6c04+6Zdb6RUYczzpy+cSxyv88CvUm6TpuONbdKmLKMfjb6ja06Yjkx/g7ZBMwJNp/L+liXV5i4/1j00YKCGpn/QggSwusoqzwXdzIi/NyZqxy61B6AjMXQj/O55d6jM4dPRuw+djA2Ky3vWQceBYXBKrl5MKGipk2kFzjeDtnEzAmEEEJjBXMCIYQQEcwJhBBCRDAnEEIIEcGcQAghRARzAiGEEBHMCYQQQkQwJxBCCBHBnEAIIUQEcwIhhBARzAmEEEJEMCcQQggRwZxACCFEBHMCIYQQEcwJhBBCRDAnEEIIEcGcQAghRARzAknX15CbdyTiSER0ZkbRa454AVYfpYpTcqfxZkbR+YTk41f/klBG9q0hCXispucVxZSC6yXpSRlx8eVNDMklu2kvClPSD+6N23fwauoNVpvC/gXNXwGrt+FWYeKBhLDdJ46eKiunDMjwqoH2iqb039MO/XY6uUTx/gTnxM4JVvn92IPFdR3yr8m400VuivFYYuu6Y1tIqIelFoCquX9hg8iepJIjfTd4ufvazVQCgJlbm6X9vWuZtoYk+HA3ItjLY/0K21lKADAjqkj8L72zPlScj3Iw0J85x8Fh8WJTXRIATLUKO1/aK+/K/4I+k6+f8Z49lTTFyHyRi425IQkAJi0ISv9b6oUR4/X90wfd5sya47B5+/6rFy5Vl5JlyZWfayLnBOuf8w4kUPVIa5J3TcadtvaYZY5bLr/sEvyX8fJasDkAWOylMSWVp98I0SHIiRFuDUnQWr1eW3JO0PISA3ffLqUM/QVm5uu7sX7TAcDk4F2qvKv9axkgXwpb4noo5V7PUCoMtBUkO00BUHM/WyOh9e9qrNnnoKdpGXb23psu+ddfuomcE+xPleeO70/pYsm/JuNLX8k+u9n+1bThC6nNO40ASG6nqyWc7p0PE2dLzYkRbw1JQGdFmUrpT4hj9WT56AJoeWe+lX/NfyXd7e+Yonf8+mtibQE0PK+IHotucmWIyaRpKzMr2uVf82+Y0DmBRqO7schDx2xnochdi/6aOHsAsDr8VLwHzSlLtpCSE6PYGpKA8TTWXOacYPOpl3zUAcyiOtlyr/kvr+3SajWYEZj7QWg548X5ldoqpjF3WuVfw2+b2DnRTfu7vOQVflVGgvckaaW6VsANiugqdsmZuQAk+5tkluiqrsrU+ZJzYjRbQxIwn8XPG0FOMPL26AGY7ceckLt3twKNSGYJD2hCy+k39+qD/sbrgk5Gfwe5h6HIUw8maE7wGKWFET5LpwEoL85rln99xpG317w0Yc7pcvFBZmqdvy6AfvgdsaaqqyrDSnJOjGZrSALm80TLEeQELXOjBkx1T++Rf81/ZazeiqRgYwO/E4+E+9Osf5Kd1GBWXHETK2X76jlTAAAANOa4Hc2oVLzJTuyJmhMdz7OOFTyoqds0HXQ31NHlXp9xhM6MNAWwymoSv8xnPkuYD0DyvEwWXdVVLSUnRrU1JAHzxUhy4mNhsBFM9klr5H3v+6LRaaWdDA31sNZT0Vx5IOcvlsj5Ty5yVQOSuZ/bYs+AqNwbt+kP80t/D109EwB0/JIqPsu//iImZk4ItDxeNRXMoznY9R4BakPgNICFOWQJa3suOZEAlqaIzR+TmhOj2hqSYEQ50VyxXhcMtz7pkHu1f1m0Z3mpt36Pid/q4zoDQN1yV1Lx++6htcyCAwYA2isuFAlNgR1ozgidCTDF9fYTRbsHNZFzojF3scok51Tseo8EpXy1BsD8tFoJZ+rbLA9NmOSd0Sy6SmpOjGprSIIR5ETvo3DrSfo7spqwM6EIePT76e5aANqBlxsHU4F2ed1kIC29KNY0sV5edJ0K4HC8sl/e1RY2gXOiszjBVMlwa/5HuddkPKHWB+gCGBy8RxNf++aKqzpMC80Xm5UvvT8xmq0hCWTNCR4tL3a+5sI9+e+6x+R90RgYqDvmqAxgffSZYHYfNdWTBJpekmYtU1I8VGGqR4aCTWiewDnRfi1QQ8kmoRJn6I9EByfGDIDkkSZh2ODf8zZKyrbZEuY7ScuJUW0NSSBbTnSWX/fQm7HieFen3CuMhmHeiTYE0PGrEYyV0jI3TAWVJedfSSxpAEr25/+Te52FTNyc4D05uURJzecK3tYYmXfZPtoAhkF5Yv0wWssOA1WLaLb4eM9gTmwhi813Gs3WkASDORF5V3pOdNU/CDCZbh/VSsfoVTD0nFBdAIPtFMEPEHQWJ5gAGO5oFf89AmbBfgPQ8rn6Tu51FjJxc6KvONQU9PYU4LTLkeG1pHirAxjuoIicxJzHyVYajscrJNw5FeSEXmCT2MDpaLaGJBDkhN6eAim36brJ9WGWelahta0YEgqnr3jXbADdNZlvBpe01vnrAsxNqhCbL0695DtF1SWpVsHugkzcnHib5a4BJsdK6XKvyXjTXLZWC0ArMENoVmVv8e4FpoG17ZJeIsgJnXU1EqYgj3xrSAJBTmhvy5P4+C6NFe9kaB5U2iw6X2CgveoZTdEmz/xi2BVZzpOBtCCp9Ovvc7wvCDICMNlxW/ghbXbPNZ8Z07yLWxQt7CduTrw8twhgduL9R48OhZy6jXefRqC/NtFTHUDXK6dm8MzmteXFO9gcyCVLnkIjyAllu1xJgw0j3hqSQJATysvPN4jtNObLKxtMSNM8t0ck7tt7JCz0wPbg8CD/0I1rAtyXWM2wSanE3+X9OVgfn1S+Eh4ZGqDkp642UlIyDk2rEnoqoquu0FcXlC3iClq+HFBea/YBy9khabWK18mesDnB+uuUNQDAzCX7zxfj3I+R7r2e/HBXLQCSifvazZH+K5daOcVk1og9/kOpC3V2cbB3sbM0BAAATTMbFwd7N8/fKIxRbA1J8O7WtlUO9i4Oi231B5/ZdXKwd3F0P3Fv8IZqX9kh50kg7R/JLvG5Qv8Q6URC55zyc7KwXr1xW+LRxGsJkdH+bgu1NSxX7SuupEq4JGI8uLrWZJKqid+ehDuZ6bdig/zc/M7l1ivk92LC5gS7v+l69sXb/+DEj9HidZRVnos7GRF+7sxVzncPjY7t1hBSUKxaSta5zNh9CVGx19Nv0OqphCMNjJ7SzJz4yGMHjuZn33+puI3VxM0JhBBCYwFzAiGEEBHMCYQQQkQwJxBCCBHBnEAIIUQEcwIhhBARzAmEEEJEMCcQQggRwZxACCFEBHMCIYQQEcwJhBBCRDAnEEIIEcGcQAghRARzAiGEEBHMCYQQQkQwJxBCCBHBnEAIIUQEcwJJ19eQm3ck4khEdGZG0WuOeAFWH6WKU3Kn8WZG0fmE5ONX/5JQRvZi6LvwmNVP0hKSInYdiYq9cb3kHf6503GA0VOWfScxKn7fwavpBX/j37ND40wXuSnGY4mt645tIaEelloAqub+hQ0dwsWo5EjfDV7uvnYzlQBg5tZmhsStyVgMjRa7vuqg17zJKpoz5jo6LLLWJwGAmsWmB08Y8q8bkmKgtSAjyM03IPJmZua9M5EhVlNU9JefLiAT/p1UecGcQBK0tccsc9xy+eXgNSnj5bVgcwCw2EtjSipPvxGiI0MAyFgMjUhXQ/Fme5/dZ9upQ6nQ1dwS66gBoL701J/Yq1BIvNYb+y1NtqbV9n9ZyHx40VEd1JekVdDlXj0xmBNITF/JPrvZ/tW04QupzTuNAEhup6slXO90PkycLUMAyFgMjQyrr50melA45ResAKa4l9J+xDui79TaFGKk5XjqL+EU/1x52EEZtLxS/+2Wew1FYE4gEd2NRR46ZjsLe4WX99fE2QOA1eGn4qMLnLJkCxkCQMZiaAw0F7upwXT/hg651wSJabvir6Fi/3uNaLp3199aNgnUnAsp8q6hqImdE120lxV3KWX1H7H3LTPek6SV6loBNyiiq9glZ+YCkOxvklli+7kydb4MASBjMfT92nP2zCBZRhT1/ug3QiPXe3+HCUzZcK1FbBXzf4mWADrb8lrlXklhEzUnuptbjm/y914XEbrBTg3AaEMpRax1Q5K8vealCXNOl3eIraLW+esC6IffaRNd1VWVYSVLTshWDH0fHrM0d62xiccxlsTBJCRv73J8tGGq/3WxSzEu+32e33QAx7MNcq+ksImZEzRGjMNcjzMvOGw+l/m2JPVi3MWnLLnXalygMyNNAayymsRjlfksYT4AyfMyWXRVV7VsOSFbMTRa7x8cP+Tvbq+rou0UWdvUzpN3fZBEH+8GGwEsPFreL7aq936oKYDNsSoFm/U0IXOiIy9Mj+SYVI/fk5GjNgROA1iYQ5awtueSEwlgaUqT6CrMCcXQW5tTlJJ4PiJ48xJ9ADXbwFMMOnajFU9rqq86gHXsU7boqg/5G/UBHM4oWts1IXOCURA1E0jWES34JRkxSvlqDYD5abVM8bVvszw0YZJ3RrPoKswJRdPdSj++Qgdgmk/qvzg4p3BaqgOmA2j4nq74PGw5j/7gup8BgIbEW1JyNSFzgtvBTXScDECat/lunQJORlZk1PoAXQCDg/do4mvfXHFVh2mh+VTRVZgTCqir6oqNMoDVpVp82k7hDLRcCTMGAM1lQYfv3rpDK7peEBvka++80UETwDK9TsJVmlxNzJxg87tbmqMdNABA2zWtVKxdQ1J1cGLMAEgeaWKDEFz2v+dtlJRtsyXMd8KcUEA0SqgBgM52hZs8g9h8LrufnHN2jeV0AAAA9VnuwYmtlPL0BUpgGcMRux8lbxM1J7hsPreNddLTEAA0nDMqsVchq3fZPtoAhkF5H0VX0Vp2GKhaRLPFT+LBANhCliknvlUMjY3WOn9dAINoSV1DpCi6O97T2gQD2n0P95iDxvpLjQo2OMGe2DnB5nMZf13eYASg5Z3RI//KjA+8lhRvdQDDHRSRWZWcx8lWGo7HK8QnaQwGgF5gE/FTXTIWQ2OCdTd2FoC2b1mbvGuCZNFZkrxYbbLdIZYi/hrgBM8JNr+7Ic9RBSwOSXiKGEnWXLZWC0ArMEPouqa3ePcC08DadkkvEQSAzroaOuGWZSyGxkDHH6eWTQWVJTEP+uRfGfQtnNp7AcZq+j53mhRzMGni5URnWV5YUGJG1afBA1CWYqU2e3u+2F0UJFV/baKnOoCuV05Nu2AJry0v3sHmQC5Zco9YEADKdrniQxejKIZGgseoe9YifFu1q4kcv2q2ktJc/5TnCnenG4lgfaxMi3OcpmW15b7o7zErjomXE6wHZx2mgPLcyJTclvzU5I22i70T8MHUEWL15Ie7agGQTNzXbo70X7nUyikms+azaDFKXaizi4O9i52lIQAAaJrZuDjYu3n+RmGMohgajU8VJ7bbmtu7rT8QFZt1+sjJ0A2+87S05nomZjz+oHA/J4cG8dpL6zOTr8WGbnO2MDF12JOY+49CJ/rEywkum9/Vwsm/mHU4/Nih4/fuN4q1bkgmvI6yynNxJyPCz525ysEnURRa+1/3ruSfjEmM+O3CmdTqB1Uf8JkJxfa5/vKFA9Gpp1JqK5olDPgpnAmZEwghhMYM5gRCCCEimBMIIYSIYE4ghBAigjmBEEKICOYEQgghIpgTCCGEiGBOIIQQIoI5gRBCiAjmBEIIISKYEwghhIhgTiCEECKCOYEQQogI5gRCCCEimBMIIYSIYE4ghBAigjmBEEKICOYEkoDVR6nilNxpvJlRdD4h+fjVvzhE5fsacvOORByJiM7MKHotvaSMxdAY6CY3n0/uZMm7Gr8imb873bQXhSnpB/fG7Tt4NfUGq40p75oTwJxAElDJkb4bvNx97WYqAcDMrc3S/pB1F7kpxmOJreuObSGhHpZaAKrm/oXifw5exmJobLTRDztoTHV50Cb3mvyCZPnusD5UnI9yMNCfOcfBYfFiU10SAEy1Cjtf2iv/+ks08XOC+alTkYNasdFvhOgQ5ERbe8wyxy2XXw7+NWbGy2vB5gBgsZfGHEUxNCbof5xbu0hfBdQwJ+SK4LtDy0sM3H27lMIbXMJ8fTfWbzoAmBy8S5V/zSWY4DnRwYm1dTxY8ln+NRmfOh8mzpaaE30l++xm+1fThi+kNu80AiC5na4eGGExNBaYL7O2uK9JeBhhijkhZ4TfHTGsniwfXQAt78y3cq+5BBM7J1j34+fob8qmyL8m4xSnLNlCyrne3VjkoWO2s1Ckp9xfE2cPAFaHn3JGUgyNAda7uxGrlkeQ29tZUZgT8kbw3ZGIeslHHcAsqpMt75pLMJFzgvU2L9CQZHm5Hu87jVZXZep8yec670nSSnWtgBtiGcwuOTMXgGR/k8ySvRj6fv0NyaGOgfeeMPhcOuaE/En/7kjGyNujB2C2H3PiJ2KVZAY422gAgP5yD48Nq9aduaeYN/4UW1dVhpXkc/3tNS9NmHO6XHwsmlrnrwugH36nTfZi6Hsx7iW5OZ+8LzjJMScUgPTvjmS0zI0aMNU9vUfuNZdgouYEl83vrs+xU4b5cc/wzsaodVVLOdfpzEhTAKusJvHeAPNZwnwAkudlsszF5P0xx7uuxpJgu8CkyqFxOMwJBSD1uyPZx8JgI5jsk9bI+873/SEmcE7Qc3bowrT12e/lXpPxS+q5Tm0InAawMIcs4VU9l5xIAEtTmmQuJu+POb7R2YnuziHXXnd/XTIsJ+gvS+68wAcpfr6R5URzxXpdMNz6pEPe1ZZs4uZEf+VBK4DFiVU4o2b0pJ7rlPLVGgDz02oljP28zfLQhEneGc0yF5P3xxzHWG9ubZunomJkYbnY6ivLaQAwyXiumbm+GhhsJct46wONoZHkRO+jcOtJ+juymhSyM8GeyDnxNstDE3RD83FY4jtI70/UB+gCGBy8RxN/1ZsrruowLTSfKnMxeX/M8aur4fG+DcFrfIOErPa1mASg6+rtG7RmbdSZkj651/MXJHNO8Gh5sfM1F+7Jf9c9Fu/7Q0zYnOjgHJoLsCCrAafTfAep53oHJ8YMgOSRJmF04d/zNkrKttlklszF5P0xJxocn1AAMuZEZ/l1D70ZK453dcq7wkQmbE60Vq3TAh2/WrrcazKeDZ7rW8RvXLzL9tEGMAzK+yj6KlrLDgNVi2g2ewTF0JjCnFAA0r87w8rUPwgwmW4f1UpX8KulCZsTDTcXA5hHc7AZ+h6Cc10vsElseI3XkuKtDmC4gyLy2xucx8lWGo7HK/pHUgyNKTrjNxPMCTmT/t0Z1E2uD7PUswqtbVXwkGBP3Jxgl5w2A7BNeiX3moxrgnNdZ12NhG5Zc9laLQCtwAyhmXy9xbsXmAbWto+0GBpDtNZdhpgTckb03WHzuTRWvJOheVBps+gUj4H2qmc0RXs0eKLmBKsozhjA9tQ/3Wx+Z3VZfDy5TfFDW/EIznVlu1xJowj9tYme6gC6Xjk17YIlvLa8eAebA7lk3siLobHT1hSkjzkh+JxExQAAIABJREFUZ0TfHebLKxtMSNM8t0ck7tt7JCz0wPbg8CD/0I1rAtyXWM2wSalUtJ9Snqg50VWdtVgFQMtumf3iBe7Hb9ThTwGOBKUu1NnFwd7FztIQAAA0zWxcHOzdPH+jCN1sZfXkh7tqAZBM3NdujvRfudTKKSazRmxXy1gMjZXWaj9tzAk5+fZ3p6/skPMkkPaPZJf4vEvun0LERM0JLruv9kpa1L7kczn/Y2JP4gfidZRVnos7GRF+7sxVjvThOBmLobHQ3nnuQEZ2xUfFnWeJxpeJmxMIIYTGAuYEQgghIpgTCCGEiGBOIIQQIoI5gRBCiAjmBEIIISKYEwghhIhgTiCEECKCOYEQQogI5gRCCCEimBMIIYSIYE4ghBAigjmBEEKICOYEQgghIpgTCCGEiGBOIIQQIoI5gRBCiAjmBJKA1Uep4pTcabyZUXQ+Ifn41b84ROX7GnLzjkQciYjOzCh6LaHkyLaGhuOxmp5XFFMKrpekJ2XExZc3MaSWZFY/SUtIith1JCr2xvWSdwr3tzN/HazehluFiQcSwnafOHqqrJwyILUko6cs+05iVPy+g1fTC/7ulHvNpcGcQBJQyZG+G7zcfe1mKgHAzK3NDCklu8hNMR5LbF13bAsJ9bDUAlA19y9s6Bjl1pCYD3cjgr081q+wnaUEADOiitokFGPXVx30mjdZRXPGXEeHRdb6JABQs9j04InUUEE/yGfy9TPes6eSphiZL3KxMTckAcCkBUHpf4tdGw20FmQEufkGRN7MzLx3JjLEaoqK/vLTBWTpoSJHmBOIAP1GiA5By97WHrPMccvll4OXroyX14LNAcBiL405iq0hAq3V67Ul50RXQ/Fme5/dZ9upQ6nQ1dwS66gBoL701J/Yq/iJBsiXwpa4Hkq51zOUCgNtBclOUwDU3M/WDA8AXuuN/ZYmW9Nq+78sZD686KgO6kvSKuhy/yBiMCcQgc6HibOltux9JfvsZvtX04YvpDbvNAIguZ2ulnBZRLg1RIjOijKV0p9g9bXTRPc2p/yCFcAU91LamLw7kk13+zsmU2Rhf02sLYCG55W3Xxe2NoUYaTme+ks4xT9XHnZQBi2v1H+75f1BRGFOIAKcsmQLKS17d2ORh47ZzsJe4eX9NXH2AGB1+Kn4IATB1tA3MJ7Gmku97yRBc7GbGkz3b+iQe81/eW2XVqvBjMDcD1+XXPHXULH/vUY03bvrby2bBGrOhRR511mUgudEF+1lxV1KWf1HoeBlfmh41NU2mNufqWW0h5WEo3aM963NvRxy3eGDjeKXV930ntr7LQ+r3koaXP3UWtFx78HfTJb8d4V89n9l6nzJLTvvSdJKda2AGxTRl7BLzswFINnfJIvtNOlbQ9/CfBY/bwQ50Z6zZwbJMqKo97veFI2Bd7cCjUhmCQ9oX5b03t9hAlM2XGsRK8z8X6IlgM62vFa5V1uYwuZEd3PL8U3+3usiQjfYqQEYbSilsPhdzbSk7X5WGiDYy90UWrz7LAAAACO/u6JTQTr+unkowsd945p1of6rnHRUVOfsprGGF2j/Iz0syMs7NMhzPgnAJIQ8rP36VHf59y0Be7du9jdXhVlCq34hXVUZVpJb9rfXvDRhzunyDrFXUev8dQH0w++I30mXujX0LczniZYy5gSPWZq71tjE4xhL4igR+nlYvRVJwcYGficeDQ/sdzk+2jDV/7rYNRaX/T7PbzqA49kGeddchILmBI0R4zDX48wLDpvPZb4tSb0Yd/Epi91XcT4jo+TFZWc1MDpcTKbHLLX12J2dk1sUsXgygFFI/scvW+DUFocsXux9qLGFweey+ezSs+agvebau69vQaUdWm639hSHyeZz2QPtle2l9X1Daz+WxK53DCkhMwaPnJLpnn0HKpp/vV5FV7WUlp3OjDQFsMpqEt8nzGcJ8wFInpfJMm8NfRPzhQw58f7B8UP+7va6KtpOkbVN7Tz5V/uX1Uo7GRrqYa2nornyQM5fLKGvyce7wUYAC4+W94u9sPd+qCmAzbEqBZv1pJg50ZEXpkdyTKqXdKIz/jhqAWCdeiV8fUDSH4IZx4zbkTMBzPaz2Ww+l83vbioPmjPL49Qz9tCr6Dk7dFXsT34ZXGX9l7Vh7pytje0S3p3Xlh0+xzymiDpYMn3ljJkup241ih/UiU9qy05tCJwGsDCHLOFVPZecSABLU5pk3hr6Jplyorc2pygl8XxE8OYl+gBqtoGnGPRf7+JGIdCe5aXe+j0mfquP6wwAdctdScXvv4xOt6b6qgNYxz5li77wQ/5GfQCHMxKbPjlSzJxgFETNBJJ1RIuEs5xaH6AL6guC1oY3fWnlu2syrQAMd7Qy2Xwu89UVXwNtt/wnXyceDDQcsyPphRVQB5d05EcZa6xIEhtH4rL5XDojcq6WXeLzLjafXV99aN06/yNkqugchl+F1JadUr5aA2B+Wq2EPfM2y0MTJnlnNMu8NfRNMuXEV92t9OMrdACm+aT+i1Nj5YpHv5/urgWgHXi5cajBaakOmA6g4Xu64rNQyQfX/QwANCTekpIrxcwJbgc30XEyAGne5rt1IrOJG3LtlAA0fVLqvrbynMfnLQDmx/3BYfNZxcfMVIy23Pow7FVvr3trKVtdbRCkDutVuruWmkOe+EArV9CVUbFNKO8pOfWbu9u+pOJ3CjdH7SeS3p+oD9AFMDh4jyb+qjdXXNVhWmg+VeatoW8aYU5w2fyuqis2ygBWl2rxaTs5G6g75qgMYH302ZfnKlquhBkDgOayoMN3b92hFV0viA3ytXfe6KAJYJlep2gXpgqaE2x+d0tztIMGAGi7ppUOa3FYRbGzALR9K4bPXKLf2KoDhltufeSye4tCZoHW1pvDJwxQ6wOmwRT3ksGXkB96TIE5v7EkPSXf93C3GajM93Bf53+4vvmX/4JJbdk7ODFmACSPNLFBCC773/M2Ssq22RLmO2FOjNrIc4JLo4QaAOhsV7jJM78e5p1oQwAdvxr614X95JyzayynC6bhqM9yD05spZSnL1ACyxiO2P0oeVPYnOCy+dw21klPQwDQcM6oHOpVtKX7qoPmqow3w0r2Pdg9B/QjCqh8bgc7xgzAMr1+WCBTr2zWBjAIaRZM/2DdPWQESvbn/5P0pj2XHEmg6Xe2rG80FZ5wBlv2LeLTvd5l+2gDGAblfRR9Fa1lh4GqRTRb/FyXvjX0LYM5EXlX9pxorfPXBTCIltTnQz8VPSdUF8BgO0V8Blp3x3tam2Dss+/hHnPQWH+pUcEGJ9gKnhNsPpfx1+UNRgBa3hk9XDafy+6vPmQNMGxEms3ntjYGz5xqG8thswcnZSrb32n9spbemejnZ6UOpuEMQQei/VqQFijZnXsl4e2YL05YAuj/NoJv44QmaNn1ApvEHtfitaR4qwMY7hA99TmPk600HI9XSBj2l7419C2CnNDbUyB2N08a1l1Bz7usTe6V/9X1Fe+aDaC7JvMNQbHOkuTFapPtDkm8zyFvip4TbH53Q56jClgcEjzf+z7Pb7rwt6Wv9IDjtEWnSwUXTdSGwOkAlpcGb/Cx3hUd2LLj/LVlqjD3wGBvjnErXB/AeHe70LMUjE8cFp/L/jfFThlIK5Ibhkd6f2vp0zZFu2P4Uwhadp11w/vLQ5rL1moBaAVmCF3+9BbvXmAaWCtpIhnh1hAxQU5oy/wEVscfp5ZNBZUlMQ+wZyxn7Ios58lAWpBU2i61DKf2XoCxmr7PHem/ByxXCpgTnWV5YUGJGVWfBvdgWYqV2uztgmcjWP+cXQRgmdEw2Gp/qk3eaWW9L6thqHvB/OusPQmUFu6786Gb9jwn0sd2c1lL7fX/t3efX01lexjHfxTFAigICg6iAgo2MIiKiFIsWEDGNjasoGJhxIKgIiriYEHEgqACoqgUKaGaEEpCCCHcjDrOqHPX2F3igqz8D/dFQg/H6OBNwIf1eeNhJ+yA5JuzzzlkEtHowPKcCyc3BJdUce56DiIy35LIUT7B1WbdXDtn45mCJqn4c86uCUR6E4IFyrURwbMrgSsW7Sqr/CHPL1Q8s+tOTVJ1zL+pMMJrAJGJdyJb+Qsgq0o+5DxldxJH9Y4z470BI0UndGdFl3T63sqERY/LO57rISnjHJo3WkfHxj/mqdatdPdhog+P8v7uuDfQzLsZu2Ckjo5VwNn8z93dKu/sfhdTY4df7nb+Q8vaQws7Ibp30nkQ6drsjEkqvxl7epmj0/ywlitLqys2WZK+44nEVE5S7MWgZf4L1ifnVLb/zZFVXN6muERbX1ffaklSAV/eUJgwkYhopMuapCyeTCpuzA1fOoxId8RMb7+NS9ym2Tltirr3XnFeUwOncIt9P6KBY6av8F+y1MXRe310/Q+3ns4rCnB1c2a5TbW3JCIio7FT3JxZ7l47eB2+FaJXNwNnGxPpj/JYvHKn/9wZDtND4tldfh/UvDdQ4e2NdfOcWW7OTo7mRERkOGa6M8vNxePIHeXSaGPukfWOtix3393BoQnHDxwN8PMZZ2xs4xURl/3+Rz5VTwME9ZFLp9tNWLBsXcTBiMthO/f4u08aYmg/b3tGXmXnuvOziuNPXw4NWOdqN8raeWtE0nOtLroWdkIqlkvK62/+lrAv8PCv4XfulrZ73uFmuBuQIWtT4K7fImOK2Z2/+wqfOSmph3bHxt54KlS8bhX+lRSZklbU2G5MEy/9/vG9h4OCz8YkPRF2fHnbUPUkJebC3sDIw6fLSrrfVQSpWC4Vy2py8k7tPxoUeCrqUj2u6tIM/p93Lt48GhIRtONMVGzBvfz3uGZCU0SFvIRT8aHbw4JDr5y/Wl1cqfLK6s/FF87s3hMbGVOYy+0NF/BqZye6U58dbUc6U0+81PhMAAB+FL2rE4Jr64eS6dKr7zQ+EwCAH0Wv6oSME+lCZBd8v/H7fy0AAJBLxb2sEx/vBliT7qyYUo3PBADgh9F7OiGrK6+PdO5H+m4RGS8ry9/wq3rD8R8AgN6u13Si5snZzQG+S9a2CNgYJdHGCxcBAPqYXtMJAADQCHQCAACYoBMAAMAEnQAAACboBAAAMEEnAACACToBAABM0AkAAGCCTgAAABN0AgAAmPw4nRCxS08Gbpk/c86S40/qNT0ZAIBe48fohKwq+Zi/X0jwWpf+RJOO/oX3g/wC0Sdefn1maun1uPTosNPhl/5UXVY1hyl9KklKPhB0IGhPfFz6P0h1j5KJyp7mZvBSrmSePxG3/9DDMqHGpwRfJKsteHQ27ETQpgPBoVevZL7V3nch/DE6ocS/vNKIjLzj37RuET28G7o3o0hr375cUyo5O338vD18po7QIaIRa7iq38hazWFiuYRTFuI5zXH2hnVrAzztjYn62fqnae+7xvc+728Hrfb29J3j+JMOEQ0PTq/S+JSAibg4f6/3uIF6RsNtXJwnTzDXJyIDuxX3Hmln4H+oTnBPzCAasyX9k3KL6Hm0sz718zxbpvm5aSfB1bVDGQOg1rAqfshMl18uvFC+XBK+uLzalojstlXXavoB9jUVBb5D0AltJynJWMlauPkkv7KlChJueaiLIdGAGZHPtHGv4kfqRGNWoC3purV7m6PGvFPhu2IkIs3PTUvV3Y8YrUYnGId9ytw+dbR/QXX7jZXcjSOJ9N2PF6h8l3n4VgJRsDU6ofVEn/jVnf/n1z8840A0yCOr+nt8xX/pR+rE2yvzjMl8Wwp+hdRWn3PaTo1OMAxrKE33HDp2Y9rHjtub2PtZROSw7z84UNGThP8JtUUneiduhrsBDfMvqdH4TLrSZCeEb4sf/M6vVfyzWZAvuJ/7ptt9LsE/7AxeVtHHdoegm/iFz4Uitb9c7dMIeyL7+JLato0N1X89zPxb3JOz6lMkebHj1ehE98Nkj07MHWD881Ve55uIM6NsiPRZ1znq/wThi2ofHxqHTvRK/MStw/Xtg9I/fu8v9C000gkJh3Nk9SK7QUTGqxJ5cqngyW/LHPSJiIZ6n/6r85Oy4MmlnUErVmxf7e3Qj0ZvuPVBKpaLcu8Fuo7UIfvg+41tI2vqI9eezxa0fJXS3K2zWA4zw5S/M1Vlq8zI2CefL5ZLxTJhVlrQwhmmRLpOydwemlXfI8mPc1CnE90Oe3PZ24jGHH/Y9ZB1ZZG/CZF5YCqe0XqQ4sUQOtHLyGqzkhZbjfI8LNLSI3aa6MSHrKiLCQ//iHHSoeHB6bynMYtZLivPJ1xLmDeE9J1TeO0HV9Uc9JizPu5FvVgurWD7DdUZvfxwyLmcAxuPHlw7WZdoUvgfrc/gkvwLEw1sgu62HKYWNxeHOQ0Yd4atOFhUemuaHtnsrheL5dKapwmHU+6xi1YMIxO/IkGPzOryy763VyEpUK8T3Q0T1O60JnJIKOu601D7OGw8kb7XBY7mH2bfUfsHOtGrvLsX/qu/B8tEb8j0nYVlfJmm59MNja07CSX7bIjGRSeFrfTeVc4XyaXif8466+lMSeK2jhG9Tl453i6Aq1iwayhL9zQd6R5cxBXKpWK5hH1pEpGJX1HLct7nglCWDtGEsCct5WjM3DbRdlO14jB1XUaYNQ1wP/e6bQ7l2fMGk+2eenHPzaqP+bedqCxZbko0KZGj4lavzk3XJ5oRg5PNehA60ct8LExMj4mIDlq9cpo5kYHj8kihQAtXYjXWicqyVWZk4LjVd2VameJggOjZMQedwZ7ZrYf76zLCbQ1dj+U3S8WfOVdP+s4NCLv1qm39p+rRanMih5bjDVXlG20th+mRoVfLPdT+ETltysZU5XofP97fkEa3nRQrlktLk5z0+rvGvurJWfUt/7YTvIcLDInGny2s7XqrNwmeRtR/fhxX8w+z70Aneq2GCkH4nKFEpgtjX2rd84nGOsG5PVOfyHTOoazPyi18QaCVntUWfstZqu9Tllvo259lc2pOrl48d/XVTF7HnTLR85OOOjRiV3q1XCpuLonyd9lWEDtnMFlHZAnkUrFcUpAwy/FolvJwRXNJmBPpup5uOylWXpcRZq1juebmh56cVd/yr/cnin82IbLYe6e6661eX5w9gEwDblZq/mH2HehEbybJvzhFl8jhXKG2LU5oqhN194+MIRowK5XbupPFfeAxUN8p6oXyn3z+NivSG73Ea27AgesvVZ09+f6GnxkN8k0ol0vLC9a6bL/ObSo74qKrvG6uiX3I2/WgtOWGH26vHknDNt1q96zEv7zcUGdKWF5zj86qT/m3naipDxlLpO95VsVBiJfRU3R0Ha/hfKeehE70atW8AAuioeuTKzQ9k0401Qn+pZ8NaaD7mb9bj/3W55y20xnme+2dcgzn9nQ9MvK4VsDv7k4as4JsiaadKP6YtdvH9/RfErG8NnWvJf20PuWjtPJRAGtDfFnri/1X52b0I9vovLZQyx4dnaZjsPAit2dn1acoA/ALR61OqBj29trCIUSWq5K7nA9WXb7Bop/dHrFY7cnAlyk7sfM2OtEbVRT5mxBZ7FG1/61RGupEc3GYI5Hj4Xav5QVXVhuT/Z5M5YKPpOCiA9Hw1QzPUDJO5DSiiaHJSb7e5/MUZ15y0l376045+pR91N/zoKTdAWrpflvSd0mraLv5p4wAazLb2u6yux6ZVZ+iCIDZ8jLma3+6HyYrj5k/gMhyA6/TCX/12acdDF3Cc5s0/hj7FEUnzLamYDWvFxLdDv2JaIhPTpWmZ9KZhjrxPmW5RcdVoOaSMCfSm9O2QFF6g6VL+tOSO6xLCP/JzXndepCn6vyiATRyjpffntaLU6orN1uS0YyNbo67U9rvu1Vx1pqT0YJcftsc3iR4GNKowy0HMHpsVn2JIgBDl7AF3zyMm7PYmMh4eVxp+wM5HzM2T7ReXsj/msnAlyk6MWSd1i1cwBfV/B45czDpTQu59+m7f62vpaFO/B3D0iP7C8Vtp8F8TF9rRXouITHn1s7bFJXdKK0R7bUl0pu6565yyaKOnbNjwcq9ya9aF4X4l1cZE9ls5rV7df/ilCMR2ay//qbD1Qy8XB8jMpx3Pzc5fsvmtGKhXCp+cWoy0eiIuw8e/Lo28ha3x2bVlygCoDs1ifkoAuOwpsIIrwFEJt6JbOVinawq+ZDzlN1JnL58CoBmKDqhOyu6BN9brSUTFj0uF3TYKCnjHJo3WkfHxj/mqTauxGqmE3xBoBUZLcxr93Ly4511VkRGdvOiEgsVl1jLKhL3OegTGYybsSDA18PdyXXXmawOy9w1yVus7fald9jFfpPgNdJ+S3nnBRBero8hEQ1xWBRzs6RJKpZLRX9GTiAiGjFtV3TG24aem1VfwCsKcHVzZrlNtbckIiKjsVPcnFnuXjt4wm8YJnp1M3C2MZH+KI/FK3f6z53hMD0knv25h+f8Q3t7Y908Z5abs5OjORERGY6Z7sxyc/E4cgcHKrROY+6R9Y62LHff3cGhCccPHA3w8xlnbGzjFRGX/V5LX25qz98BrOeIc0oaO26UCfNLz4Yd3xF87rfkZ13/qmt9UVli5+foxuLEwsKuB5lFrzNOJV7Laf9jaCq7cu23W8/renpWoIqsJifv1P6jQYGnoi7Va+OVRAD/T/w/71y8eTQkImjHmajYgnv577V64Vp7OgEAANoInQAAACboBAAAMEEnAACACToBAABM0AkAAGCCTgAAABN0AgAAmKATAADABJ0AAAAm6AQAADBBJwAAgAk6AQAATHqyE+xnJam8OwAAoP3K/svTQCfWBK8jfOADH/jAR2/4OHQ+XAOd4PxT8VDKBgAA7VfxVt03HsbxCQAAYIJOAAAAE3QCAACYoBMAAMAEnQAAACboBAAAMEEnAACACToBAABM0AkAAGCCTgAAABN0AgAAmKATAADABJ0AAAAm6AQAADBBJwAAgAk6AQAATNAJAABggk4AAAATdEIF0ducS0mHduxdPn/B7DVsdd8aEACgT9LWTsgkws/imi+oF32fry58nhxxas/GJWZEuqy0Cs1/NwBAGzXw/1ucVXMnOT8hNini1/NXC5u6jJEJ2XVsTmPX24o5/7kdlxh2OO+RsJv7F71KP5H6kK/5h6mlnZAUJEzVIyIivUGGQ4abW1ib9yciMrawHmFmZjzIgIiIyGx5ac33m0Zl6Yph6AQAdKvmVvhiTz8v95kWOkQ0cl3Khy5j3t/wMyOiAcPGjLF1muw4Y7L9xDFWVubG/YmIyGhO5BOx6jv/8GCv+6BBCy5yNf8wtbMTzSXHFkxaEnvl3ss65R7D2+s+Q4kmhOYocy2peJIWfWDWxO23Kr/bNPiVmy3RCQD4ondJS0y76cSnhxHbPJxnTLKfYGPjOJnlNcdz1c/rjhw+lZUQMs92QRqnVuUdNrKj1ow31yMDdKJbMkG+hFfTfkvnTiiGCQvE3Bq17lNS+bJK8JXT4PO3/oROAMAXNWZvt+umE6o1cB4ut/c5nt91nUouFTdz4nbOWBgXv9UOnfgqKjuhroby0i2TXPY8ULFEyASdAAC1NBX8OvFrOvH+doDT5J1CkYpPyfi3wt1cw9N4n7K3oxNfR41OiD5VsJ8Luh4RqpEedx9CNG5Xt51o4hc/eVT+ufN2dAIA1NJcuH+y+p0QZ0Y7Wa2+VCbr+ql6dqq/85YLRU3KfRR04mswdaKOnRe63N/TY7H7NNYoE5MR9n474v6oU362qeSEv5UBEfUbM2Opt6ffok0PWhcERXmZvy7zchg19idzQyIaZL8robjd/aMTAKCW5uIwJ7U78fraktH2O2rrun6qih8y23tX2nupWI5OfIPuOtHMjd81xWHz2XzlvkJDhfCo1wii4fNP/VGvHCN7dITVZX+iuSLpsMvYxfsSn4vFcqm4mXN+vRmRXYik7dwDdAIA1NJconYnxDmxTmZeJwubO3+q9mXCylkLIx+3PAWhE19NdSfqCxJnG4/8+drbDoMrytZbEhn6xyl361R1gl+91YoMXNPKW7dw77kb0PDVHGHbGHQCANShfife3VxuZeaTU9V5e2Nu2NKpv+RWtF0T1r4TjZwMXokGL6TozZ34mBFgTSYBNzqfGtvE3u9E1H/m6b8bxPJuOiE8sGTDwfR3bVu4DzwG0LBlJW0XZKATAKAWdTshKUp2HWz5c+K7jttlVYm7x+jpj7B1crBv5TjWhIgMLMbaW5sPJIvg21Wae4C9uBOC2p2jiOzjSrqcgFybtteSaMQarlAs72bdqcPPmJ/5INR/pjGhEwDwDdTsRBN7P6v/8KDUTs/4tS8uBwYs9lm1qIMVc2wNiMynea9a5LNm3TGxqpOj/l96cSd4OfMNiabc4HUZL8m/4EA0dGmhQCxn7ERzRdrVAK/53itPnk9Kcsf+BAB8C/U6UVO310bX1E/xvPRFOD7x1Vo6kd2+E3mLjIjszrC7nAtb//DMOCLrbTV1Ynm3nRA8PuM/1XpmeGJho1TMsO6Uik4AACNlJ9beYupE3YNjY8l4/sXX6t0nOvHVFJ0Yvyez3VUONeKQsUSDll7kdB5fk7RpGFmsSlacXqaqE8Jnv823HDD+yP3WHUDuA48BZOJX1KkT5Hir6/4KAEA7ik60Pueo9DkvZCLpTI8qUnHZhCqNWYG26MRXUXRibODdTx2+jzvsiQa5nfhT0mHwx4yNYw3GHclSnh6g6IRNULvbirOj7YjGBNe1nILWzIldY0Zk4Ha3svV+FJ2YlMjR/MMHAG2m6ISp77V33Y6pfRY5RZcsdt+pVvM+P94NsEYnvoqiE8bz49+0397AyV1pQWS8ODKrrQG1D2Jdrebuu9u2A1hxxkOf9KceftxyRYW87sHRMUSDZyeVCOXSmpcph7YtWhMTaK9DBnMOZXxoUAxTdGJUeNbX/mEoAPixKDqhyzrxoqG7Mdz7HgNJx/FGubr3+SFlhSU6oZ5qwb55c5xZLtaKPyVuMnkqy23WqgfclrOM63JTVjkYUT9b9xWH94WeDl67ftGyiLgCdWaiAAABS0lEQVTsD+1/WpKitHlDiMh0nMtCV8fp7pvZldWifZP1iYgGmQ4ZOt5zz6NKkYx/86CDHlG/2RG5TaL7F1d6zBpBRDTQZvqSRZtzy7/Te10AQK/FT9ztxnJzZrk6mBMR0WB7R5abs7NvcGrnAxW1qbstiAZ7Zlere+fvkhabohM96HNlDjfhxMWI4/dSMv9R+cfcxSXccxHnjp1+mMH+qEhIQ9XvySfjIk5kZ5a1HRuvzWOfi5fWav4RAUCf0lD99OaxIzuipSr+XIdqnx5GRUVc/l2oDa9Q+0QnAADgu0EnAACACToBAABM0AkAAGCCTgAAABN0AgAAmKATAADABJ0AAAAm6AQAADDpyU4Ehe8cPnIEAABov6jrpzTQicJnpbcrMwAAQPuV/VfdN03AuhMAADBBJwAAgAk6AQAATNAJAABggk4AAACT/wFYOuv3nduenwAAAABJRU5ErkJggg==" alt="" />
经过计算,一共需要174个bit来存储上面的字符。
而若使用赫夫曼编码,则只需要146个bit来存储上面的编码,原因是:对于那些出现频率高的字符,赫夫曼编码使用较短的位来存储,而对于那些出现频率低的字符,可能需要较长的位来存储。
程序运行后得到下面的结果:
可以看出,只出现了三次的 's' 字符,它的赫夫曼编码为11011,长度为5bit。而出现了15次的字符 'e' 的赫夫曼编码为 10,长度为2bit
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAb8AAADECAIAAACA47iTAAAcoElEQVR4nO2dOc7zSJKGdS4a7cxddJVx2TfoSxStOkIBfQACDbTTZpvjagyJZMaeGzfpffABVb9IZkZuLyOTZMbjtfDv//zf+jf9+dcLtDH9+dc///Vf/OFv178//vd/Ho/H429//+NsS37w77GOdqhnX6Ce+MPfd/9BPfcC6ok//H33H9RzL6Ce+MPfd/9BPfdi+vMv/OEPf1/8B/UEAIAaoJ4AAFAD1BMAAGqAegIAQA1QTwAAqAHqCQAANdxJPafn4zGM8zmZz+PweDynEzN/rKVn/7wHp1bgZUj7cN/+fOro+FFupJ7zONxSPY0r83s7O/P4YTI9Hxu1AlhVgWvO24XHqfD7JtW3qpPG69ufO6S23JT9ZPzOMD21xllTfmRkcGV4QdYDDeqpV9n1aLHzPPWcxyE9kf1zZ97dJbV+etblXquePLfD1HMeh8fzKQ1oot+tb6dB53WvnM6gFpAmeq4b1ATrfFDPTM5TzxNdz5553U09352ld243Vs9M07UE+G+3XcXpoZ7zOCxJMFeW3WCko/5ugul9cBhn0ku3k5OrN1v5rCe9irRFmnelnUt+azIjrTdlWGfWuFIa0THXf5Np0mMYRCHya0+tFrcmM7xcWq28kF4FujWfphCop1IoOcx5zzHs5bY/J7X1PqkZKWUd1e1M6kvvoF5n5qmZTROPHa01/M6QupPKmeKnTfqlILjGy3qa0gbSUtNbomTgsHLWqqexMiJug6QliaP+KTjrT7KkyUBgVZOeR1JdTpvHp5p1kZ00ScXstQlDEW1RT+Ug/Wd+7RnVYtdk6CDQKtIq265Ap+ZZFq566oViNZZcYfcNCrmEn/cpCxvqaS/1j6qtPj2ZZo6Bwbwzy9SMpvHGjqmSQWeQY4ecq/men39bI8vqV2z1gF0uU7MqMH/gONWQq56LVqgVyGorcU31yrIVTJxg9Dbepc3GJabl2yndFyuHWET5SnNCH/XMqz2jWuyaDFxPJe2kjvwK9HoIzyR/5k4LRcdb2DfsPIR8yj6cnh8ftfpzOJX1OnOamt80/thx1DN/xYHbRq8WLpF9FxAWBgPTlD1hV93A4WN5PWCrp1wsto1ScnikuqvPqoypzYvWu9Pb2L/phNfocI6dSmf2+7fnyOzue+bVnlEtdk1mzNW0KdU2BTIr0O0hPMFIPdW2TmznxTD6Bi+G6Cju0PKlyzi6/b/bubI6c5iafXgH9dT8lASzq4fGRwNTVT21AosGjmVdqe8ZeDJm+Q0ri4qRp55vS9Pq9NQza3nDOdtYy8i48mD1tKolqEmzWM3qGXpanwQ19aTTL62t1yzIOHD6BiuFJ+4Hqmd2Z95bPf3OIKHJONq7s3qaFXioeiYXS63wLdHrIfPiYvWk19Pz8u3UzVRvp2GXylBPzZ/qq55mtXhjyZ0Hlc6w0sSyh6KinubsS5l/vB8LGLLn3Q9Vh5doNrmQa6J/VPl/o0IKOnOQWmaLO0IXTIo5YvEkd6S19CvfDRF9+2D1TNLwlir4VGceB9u13kE90/mb5zQEdvKlGjY2c+/EGeopu8Ae6qlWSzyWRJ2lbcCXS0hd2xXo1DyvJFrN5ioXb+tPXQyDYaE8Xys/sYS68ayo9F/uUU1JZWU+p7LO7KfG675cPd3OoNxy0oRK1LOpX2mVolfgeeqp1wEZ8mSlwxz7ZcXIUs8062GcldSz7EzOfVd5/myTk6OexJDn1N/3NKvFH0uiipw6Ur1EuwKdmidJEK3mp3ptzQdaeP56jSXkZHozJfZLV8I/aq/X8GvyO7OXmjs3zlZPao8cRvYsoUg9XeNlPQXrnlYFXkk9AdiDAhf/OPx1h+xViWsSqGcR2u2pO/VuTTtQT3BhoJ5H01M9+yZmZ3GWeEI9wZVZJ2lnjQ+Nb1XP/AehJ7Ktu79e6uLMkUA9ASjjW9XzLpBF0VNvq4F6/gMAAIAGfE8AAKgB6gkAADVAPQEAoAaoJwAA1NCunskGejdhngvtLb4gYhpFlXXPAwCwL4Xqqb7+mvvCKv88PvrdZH1lwX4zZHl3jaa7veug7NPiU/NmhPU2mvZdG150AeBmlKnn9Ew+15/ST2XH9UNT5UPcROvYT6s2jdL1+kScUq7YPsqdrS9g16+75zlJQJfAeZpY5mk516ymJDOjGJqdMvWXEljN/qgm695k7XkBANiNIvUkoz4VkGEcn8k/Qi2iH8AaURrFvkYxqgYpUkjIcDx99SUlSHKTk/G3kq53mPSmQ9JOr2xWT3i1AOxCgXquEvHWKFXz6HdUy3V8VNOztGv060LUpIJ0NMVV9F5ZqcxQXVnwx7KHUnKGlhLdvqbFqdxTPfUFEp67dkt90fsvvGZwP7LVcxPL6fl4jmRCrA/79UI5Cya7OVrqFqqn1EohQ59NEp10FjePbPf1viT5SXumk2Sv+p56welt47PjmdxUi2x9eUn1/CzeTmw3Rpm31ivkVpEA3I5M9ZSflloeI0f7KJXqijFxj9cWh3FmD/yJUUsuejqu8Vlubyf1lO8s6OpJNgClJ+tlsnxjzdMuVrLVY+d72fKC8N1K0yIBcGsKn7lvMpGpnmSH1G0PU8UD0y5tmrkn6pnsNevum736nlMqu8M4q4uY5Q/qpXqO43Oc2YMlRT2TxNSNaD0PM/I9nbl1BrZ6rhrJDThg3zIADqD6qdE8DsNgyEeyZvd8PgemnuwFpbe4KW8tdVLPNGVjWTYTPvucUx3MfWdLvW8IvRSbzlv7k/s/BkeSE6rlzFLPpEq0XfTJ2i+0FNySoqdGbAgPw/CRp+Q/ZBY7jnMqmixWyepSvdMahnGi+Xkzb3XQ8VM/dqVPYOKBaq0k2NgvrLJHUuq6rEhCUU8ZKkMLKVGpnk0Y6ulEoBDvBxjeNAAXpzQi8SJb0zg8x9FXz3meqcvpPbwRR1cN0X1Q9Vfy41u5iBQZ6pn1zpL9HuuDu1LkorRklu9JTb+/etIsmQGTDB2k/ATA5an9UnN60shXpkuYqid5LZRqjPpO6Drxy1TP8H0pWz2Tpz7puwX665iuId6XU9mvat1aPXmG+sxdJAL1BDejXD0/jtqwTsrtmfvn9EQ99TE8z/Lt0c0xy1fP6M3SHdSTvvfva2fdi65CWXSpsTUylKbO657OQvI6mQj0FoA7UP7GkiWbtnrqTilBTNz1r3eoRf5rpNpJe/ieUi7cYraqp7VI6AhQoI57PXO3TWNlwLwd3JNc33MmH3mvr/oR9Xx+PAvd91RYP5UXOpI+oTJ9GeFnPi33NfllB/X8JEGDzWsWygVW4xMc8/4jLlGXbEWq5Kwu73vqrZK/dOBbBMAdqJm5LyLF1Im+Mrn+6u28tg1Bco14up/je/JvKbWd8wrV8+1m60LISmDIoNQ6y/fM89EBAJehVD3JK5+aMKZbL1XhP5u3rxpzpui6lLOLBVyY2WfqAIBfBHvLAwBADVBPAACoAeoJAAA1QD0BAKAGqCcAANQA9QQAgBq+MSJxY7xf+rZpcK72fpaSv0n0shQA4Kp8YURi7VvGsg+p+cfrviHafh3Z5cHubADcle+KSJxex+z2FEoko7xsr2RFz1ry4GFH+HZCNB2RU4mXDAA4kW+KSFwT7/d9YmZIYv4t/uM5kmBD8zRN48BDZtKJfEZm+H4JgDvwTRGJl+1+2IeUml6x7SfDqbNYCyXfk64lIGvAuv3+nnlZm98XsJRdr8j6o1FYjfprW1Lez+Zrlugsq/Ys0a34pojE+s7tfrzfaEV0HodhnPijHRrg6blWTIbyHaaesxsxuOUoWdgVO9S1XNuS8n42X7NEZ1m1X4nuxzdFJNbUM4r3m5WZV1BjezfzSVg8c+/SqyY3YnDjUWe3zsZrW1Lez+Zrlugsq3Yq0R35pojEUj3jeL/ZyZnnmCL5/j1wSHtP1bUMnJ5aflQMH2N5uvzalpT3s/maJTrLqiNKdCO+KSKxPnPnGWbo1Tw+h5yQ40tSnj/5nFL3V7wKKq0pLnZoY8+ROZO30z7/src/Lri2JeX9bL5mic6y6pAS3YhvikgsRIy0c7JUE6un9Cg1mRuGrTNJD1frHeFqxOPxePCKWK6qclL3G5nbqNHecC2+tiXl/Wy+ZonOsuqQEt2Ib4pIbPme9Gxylqlmwq8ekhvBmmBqxDym7qqtnuIZVvDDa70tVHW3fUYm9TfKPBfj2paU97P5miU6y6pDSnQjvikisVBP1VkTAiYJ3NPNNWVGJEl3Vc8WOo9MbaGLzueqr21JeT+br1mis6w6okQ34psiEmerZ9Ru2QrG0koks2nmfmX1NJ66iiQqrm1JeT+br1mis6w6oEQ34ssiEp+rnjSJrN6RlZXxYDOL7iOT/TqPg9qwNde2pLyfzdcs0VlW7V+iG/FFEYmJUJtqnTFx/wr1VGstvSNVH32xmlbndlXXtqS8n83XLNFZVu1ak3fjeyISu75nngdMPWzbbMeIJKN+6gkAuCDfEpG4IwUGWFuBZn2z+ckM+3sCcE+wtzwAANQA9QQAgBqgngAAUAPUEwAAaoB6AgBADVBPAACoAeoJfoP8d8MaI1qv+V0tUjfoDdQT3BrrW0GF6Zn1CYOWoraPEL9G3xorM0PtNOt3cBVOUc+oLxqX7PZpLPmCDP31wrBdVF/mx1pGrGqxO5D6FZtIMPq8N01490jd4DJAPbXNXcE1UDWFtpWlnsbuiV56tRGtX8dG6gaXoWyPpXBfvzwq1LNggra7LT/LIknR3nt71afmAi7qyRYra/YPWLb+SYry2QVHKG6a9tGRulvwWrDt6E9Sop7DwBr3C9SzoRQ/xaf+q6LUtsBDaZlbcjNNE9Ij5/xBjCljx0U+3z8+Unclfgu2HP1dStTzOYpti9heSMp06JWebnamvD2QdJq8HlM9l+cAiWVy/2YnX7O8er0RE8yUF6OYd2TXx7Ya9zQKkFVjU0OU2lZmf3tte+b+br31QTt/Bi6N1NQziGgt+3yux6iNFqqX5sRda8uM7PwWrD76yxSpJwmgQVSAdkVey7yjsuHW4rkw6cleKgo9hFXB1lUwUgbXZre8kXp6KXOjhPByS7aHFVIsahZ8tdYR4tmymbPK9Hxvyf3JhSiar57kcQ3tHHIZQKpndkTrgyN1VzkKm/l9d2L+YQrVM+lziQooDlw6pNThZatJyWS6eeLt+p7kSHqmb3NheaVcmikLo2hWrs+nSTpL2L6XmLXCLf78q/dqsrx3BWq1/Zzc8FPBzNkfNmltcmuUk3C6vLBvpO4q3zMtJNSzF6XquXWebdSog3YbP3Ikpb8EyhvR6uf46mkk69vsl9dXz6A2CpWXQcyo0zdfPWmbdx1mynTFm88zzZR3eW1RUdxCyD0hqWXeuqxFdo7U3QbUsyPF6rn2JKae2g0yRz2tKXR+G7Wsmdapp29zi3oGteGrZyhZrsRnYasnTbCz7zl/4rGSSsxVz0Q+1//LeDDOVU1XT9pgR0TqbgTq2ZFy9VwmQL7vmfxW7HvWUuOH9vI9mRkdfU834yLfMzGEvljYNHPXqr1jo75S/dGfRupCSOba691p5IuhZlLWAqb22lR6dO9I3Y1APTtSo57vBp9y1z350XcbNE4hDYoTq1JPP5ugvPphc83UN4q2SzxfThzFqkGgjh/9mbu6WleRK3mqIhPQRc5/emgEVMlWT+vqj0TOge9Ji2Xl83qpkbpfWPe8DlXq+ZrHYXg+2YMSJhD6w4x5HB7D8znww5VtQjuX+9REp049fZt5eZnjkaa8HiZLbPlOr2wXOrCETsgMi9Cto7/qrbBMcYvftPGfk+viE4in3AVESSpLPZOJuyWbtnraLn56lmgoPHO/DHXqqU3XtBfYlIPLkqmc25qTHBc65zxm3TO2eTs2jLNwzhKbn5OSk5lypJ7iYqUAVT6guh5rFMlIfDmjIGfp5smYg5rIWcH6PhckH2DyN+zjXsgE/OBI3ardWfgt2HL0h8EeSwfQ+/2dJk4zpthzyQxmzZP8yKOxlPvYFhk/i/bJ+/QtEa0PiNQNLgbU8wAupJ59n+eU0LRaZ6cqnVHxSeYR7B+pG1wPqOcBXEY991GwiO15yrH5ArAvUM8DOF89Gx8WAQAkUE8AAKgB6gkAADVAPQEAoAaoJwAA1AD1BL8BIhKD3kA9wa0p+Do38+t+LcXorQn59dwr/93aZBeTrN/BVUBMzVf8cSO4CohIDC4E1LP7Rr6gG6qm0Lay1NP4TtNLDxGJQRmISHz6m+z3wd7og4jVbtWpuYCLeiIicQwVdnXju72b8LtAROKzvvu+F5/6V2PS0kW/vl+DIiJxL+RG2mKHNPMo0EFEYmeHumFEROLl6nXztXBcdb7RBdsI2zP3d+shIvF6jdxfNBF+5yiwQERiCivDljgrg2uzW95IPb2UuVFCeLklR0QkrjmnDEQk5peWyqeQR7IU5x8FJohI7O2OLCJopFJq2lxYXimXZsrqhItNB6xRpUk6S9i+l5i1orDHRk7y3hWo1fbzhIjErFd9/rX2Hf8osEFE4oq95X2b/fL66hnURqHyMogZdaMjVs+dXo5QpivefJ5pprzLa4uK4hZCFCWpZd66rEWuF5GYFjwZl9tjMfMosEFE4gr19G1uUc+gNnz1DDu8K/FZBOq514xvRkTiJlR/kvuexlFgg4jEfXxPZkZH39PNuMj3TAzZBCW5VFI0c/+k0d9f2fRHfxqpCyFdhl7uTj8akVgZGszjtI8CE0QkrlBPP5ugvPphc83UN4q2SzzbStyMqqFhqmcsnbVTevJURSagixwiEivXyKfqZq+DeGaBiMQ16unbzMvLHI805fUwXbTPdnplu9CBdWRE4tjtVd1ZH0QkFrVa88ydtxwfKf5RYICIxFXqGdm8HRvGr49IrC/WKjJnmeTkys5GRGLF7lxI+bQlELffAAn2WDqAS63An2ZM8RwDEYkv1G2AAtTzAC6knuctaO3xGqjqjCIiMTgIqOcBXEY991GwiO15yrH5ArAvUM8DOF89Gx8WAQAkUE8AAKgB6gkAADVAPQEAoAaoJwAA1AD1BL8BIhKD3kA9wa0p+Kow8+t+LcXorQn59dwr/93aZBeTrN/BVUBMzVf8cSO4CohIDC4E1BPbwF4XVVNoW1nqaXyn6aWHiMSgDEQkPv1N9vtgbfSh+FK7oLmAi3oiInEMFXb7lgNfIhNEJMZGhjl86l+NSKye2W3DVrJVByISVyM30ha7zGa1L9hARGJnh7phRETi5ep187V4dPV154NthO2Z+7v1EJF4vUbuL5oIf0H7ggVEJKawMmyJszK4NrvljdTTS5kbJYSXW3JaROKuAxARifmlpfIpxNOIYgP1LAIRib3dkcXcJpVS0+bC8kq5NFMWRtGsXGdSk3SWsH0vMWslzKYP8t4VqNX284SIxKxXff6lTRGgnkUgInHF3vK+zX55ffUMaqNQeRnEjLrptTm6WpZeclCmK958nmmmvMtri4riFkL0Jqll3rqsRe4WkVhUAdQzE0QkrlBP3+YW9Qxqw1fPcCruSnwW2TP3viNwRkTiJlRvE75nM4hI3Mf3ZGZ09D3djIt8z8QQ+mJhz5l7niFFbPqjP43UhZAuQy93J0QkTgzAumcjiEhcoZ5+NkF59cPmmqlvFG2X+DlQ4oRUDZG80aUWYqr83oE8VVHHu1JfiEisXCOfuRuLF1DPTBCRuEY9fZt5eZnjkaa8HqZL+tlOr2wXOrCOiUhM0TV8meIWj3r/ObkuPohIrKXEpym6zw71zAcRiavUM7J5OzaMXx+RmE/79bSXswpylm4eIhIrdudCyud0murB9HNgj6UD6Lo40cppxhT7NYhIfKFuAxSgngdwIfXs/ECngFqPKUgVEYnBaUA9D+Ay6rmPgkVsz1OOzReAfYF6HsD56tn4sAgAIIF6AgBADVBPAACoAeoJAAA1QD0BAKAGqCf4DRCRGPQG6gluTcHXuZlf92spRm9NyK/nXvnv1ia7mGT9Dq4CYmq+4o8bwVVARGJwIaCe8cZE4CxUTaFtZamn8Z2mlx4iEoMyEJH49DfZ74O10YcicrvcjjQXcFFPRCTOL6LePFT2MSIyQETis777vhef+tcj1u54B0JE4l64Lahss41REYOIxM4OdcOIiMTL1evma0qeu/rvwTbC9sz93XqISLxc47SgvncyHNAIRCSmsDJsibMyuDa75Y3U00uZGyWEl1tyTETivVc/EJGYX1rjKGzmO4EgSBbwPgMQkdjbHVlE0Eil1LS5sLxSLs2UhVE0K9dj0CSdJWzfS8xa2ZKSrlRH5L0rUKvt5wkRiVkheQvRPjdvwVvgfAYgInHF3vK+zX55ffUMaqNQeRnEjLrRkTEzmHl0kC4o0xVvPs80U97ltUVFcQshipLUMm9d1iLXi0gsCmmpJx21cD4DEJG4Qj19m1vUM6gNXz3DDu9KfBZ56yrdR96MiMS9sNWTdgn4nhkgInEf35OZ0dH3dDMu8j0TQ+iLha0zdy2bjuq56Y/+NFIXQroMvdydfjQiMclXNI4ycDoOyy8GEYkr1NPPJiivfthcM/WNou0Sq1biZlQNjSz11Jdfp8rvHchTFZmALnKISGyhtqD+zB3iGYGIxDXq6dvMy8scjzTl9TBdtM92emW70IF1fERia9lzmeIWv2njPyfXxQcRiU30FqS/Voyj3wQRiavUM7J5OzaMvxaR2FP+spylm4eIxIrdWbgtKEoPtzML7LF0AJdagT/NmOI5BiISX6jbAAWo5wFcSD3PW9BqWq2zU0VEYnAaUM8DuIx67qNgEdvzlGPzBWBfoJ4HcL56Nj4sAgBIoJ4AAFAD1BMAAGqAegIAQA1QTwAAqAHqCb4FxBwGxwL1BBen4LvBzO/3tRSj9yLk93Gv/Ldnk31Ksn4H9wAxNV/xx43gOBBzGNwGqCe2gT0TVVNoa1jqaXyJ6aWHmMOgJ4hIfPqb7HdA8aX2ykebHr/3JEXM4ewiWiPTO0pvCvbtqjzlrwURibGRYSl92wIxh3vxaRcj5rB/VG6zLfagrUz5m0FEYmeHumFERGKVvg57sFGwPXN/tw9iDi/XrBvkyX4RHlV2R05uGtUpfzeISExhZdgSZ2VwbXbLG6mnlzI3Sggvt6R3RGKjCM0g5jC/tMYV2My3m0c7KsTTiHFTnvKXg4jE3u7IYvaSSqlpc2F5pVyaKQujaFauM6lJOkvYvpd4CfVB3p0Ctdp+nhBzmBWyTONon/v8S5teQD0ZiEhcsbe8b7NfXl89g9ooVF4GMaN48t2yuJKDMiHx5vNMM+V9XFtUFDcJohlJPfL2Y3V+t5jD/lFaacmoVZ55QT1TEJG4Qj19m1vUM6gNXz3Dqbgr8QXsME5mxBzuRa160i4B3zMDRCTu43syMzr6nm7GRb5nYgh97bBs5p6XVRGb/ujPG3UhJHPt9f6DmMNV654PpUNg3TMAEYkr1NPPJiivfthcM/WNou0SPwdK3Iymbq6aOVV+0TCnT1XUMavUCGIOW1RonP7M3Vj4gHquICJxjXr6NvPyMrckTXk9TBbg8p1e2S502PWOSKzmmv5aPuoRc9iqycOeufNfrXEE9WQgInGVekY2b8eG8QsiEvOJvX71clZB2tLNQ8xhxe4s1DVzMsWzj75Y3Thdqjzl7wV7LB1A18WJVnY0ptj7QMzhC3UMUAzU8wAupJ6dH/cQmlbr7FQRcxhcFKjnAVxGPffRt/R5Su+UAbguUM8DOF89uzwsAgCkQD0BAKAGqCcAANQA9QQAgBqgngAAUAPUEwAAaoB6AgBADVBPAACo4f8BdFy8YVnj4qAAAAAASUVORK5CYII=" alt="" />
②最优二叉查找树
假设有这样一种情况,某些东西经常出现,比如英语中的: is 、a、hello、you、.....这样的单词经常看到,而有些单词很冷门。
我们把那些经常需要查询的单词(用到的单词)放到赫夫曼树的顶部(即给它们以较短的赫夫曼编码),那在查找它们时,只需要经过少量的几次比较就可以找到了。这就是优化了的二叉查找树。
即把查找频率高的单词放到离树根近的地方,这样就不需要每次都查找到叶子结点后,才能找到要想的单词。
五,完整代码
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set; public class HuffmanCode { private BinaryNode root;// root of huffman tree
private int nodes;// number of total nodes in huffman tree private class BinaryNode implements Comparable<BinaryNode> {
int frequency;// 出现的频率
BinaryNode left;
BinaryNode right;
BinaryNode parent; public BinaryNode(int frequency, BinaryNode left, BinaryNode right,
BinaryNode parent) {
this.frequency = frequency;
this.left = left;
this.right = right;
this.parent = parent;
} @Override
public int compareTo(BinaryNode o) {
return frequency - o.frequency;
} public boolean isLeftChild() {
return parent != null && parent.left == this;
} public boolean isRightChild() {
return parent != null && parent.right == this;
}
} /**
*
* @param roots
* initial root of each tree
* @return root of huffman tree
*/
public BinaryNode buildHuffmanTree(List<BinaryNode> roots) {
if (roots.size() == 1)// 只有一个结点
return roots.remove(0);
PriorityQueue<BinaryNode> pq = new PriorityQueue<BinaryNode>(roots);//优先级队列保存所有叶子结点
while (pq.size() != 1) {
BinaryNode left = pq.remove();//频率最小的先出队列
BinaryNode right = pq.remove();
BinaryNode parent = new BinaryNode(
left.frequency + right.frequency, left, right, null);//构造父结点
left.parent = parent;
right.parent = parent;
pq.add(parent);//新构造好的根结点插入到优先级队列中
}
return (root = pq.remove());
} /**
* 根据各个结点的权值构造 N 棵单根节点的树
*
* @param frequency
* @return
*/
public List<BinaryNode> make_set(Integer[] frequency) {
List<BinaryNode> nodeList = new ArrayList<HuffmanCode.BinaryNode>(
frequency.length);
for (Integer i : frequency) {
nodeList.add(new BinaryNode(i, null, null, null));
}
nodes = frequency.length << 1 - 1;// huffman 树中结点个数等于叶子结点个数乘以2减去1
return nodeList;
} /**
*
* @param root
* huffman树的根结点
* @param nodeList
* huffman树中的所有叶子结点列表
* @return
*/
public int huffman_cost(List<BinaryNode> nodeList) {
int cost = 0;
int level;
BinaryNode currentNode;
for (BinaryNode binaryNode : nodeList) {
level = 0;
currentNode = binaryNode;
while (currentNode != root) {
currentNode = currentNode.parent;
level++;
}
cost += level * binaryNode.frequency;
}
return cost;
} public String huffmanEncoding(List<BinaryNode> nodeList) {
StringBuilder sb = new StringBuilder();
BinaryNode currentNode;
for (BinaryNode binaryNode : nodeList) {
currentNode = binaryNode;
while (currentNode != root) {
if (currentNode.isLeftChild())
sb.append("0");// 左孩子编码为0
else if (currentNode.isRightChild())
sb.append("1");// 右孩子编码为1
currentNode = currentNode.parent;
}
}
return sb.toString();
} public Map<BinaryNode, String> huffmanDecoding(String encodeString) {
BinaryNode currentNode = root;
//存储每个叶子结点对应的二进制编码
Map<BinaryNode, String> node_Code = new HashMap<HuffmanCode.BinaryNode, String>();
StringBuilder sb = new StringBuilder();//临时保存每个结点的二进制编码
for (int i = 0; i < encodeString.length(); i++) { char codeChar = encodeString.charAt(i);
sb.append(codeChar);
if (codeChar == '0')
currentNode = currentNode.left;
else
currentNode = currentNode.right;
if (currentNode.left == null && currentNode.right == null)// 说明是叶子结点
{
node_Code.put(currentNode, sb.toString());
sb.delete(0, sb.length());//清空当前结点,为存储下一个结点的二进制编码做准备
currentNode = root;//下一个叶子结点的解码,又从根开始
}
}
return node_Code;
} // for test purpose
public static void main(String[] args) {
Integer[] frequency = { 10, 15, 12, 3, 4, 13, 1 };//各个结点的初始频率
HuffmanCode hc = new HuffmanCode();
List<BinaryNode> nodeList = hc.make_set(frequency);//构造各个单节点树
hc.buildHuffmanTree(nodeList);//构建huffman tree
int totalCost = hc.huffman_cost(nodeList);//计算huffman tree的代价
System.out.println(totalCost);
String encodeStr = hc.huffmanEncoding(nodeList);//将各个叶子结点进行huffman 编码
System.out.println("编码后的字符串" + encodeStr); //根据编码字符串解码
Map<BinaryNode, String> decodeMap = hc.huffmanDecoding(encodeStr);
Set<Map.Entry<BinaryNode, String>> entrys = decodeMap.entrySet();
for (Map.Entry<BinaryNode, String> entry : entrys) {
BinaryNode node = entry.getKey();
String code = entry.getValue();
System.out.println("Node's frequency=" + node.frequency + " : " + code);
}
}
}
六,参考资料
《数据结构与算法分析》Mark Allen Wiess著