3.3 Huffman树
基本概念构造算法Huffman编码
前缀码字符编码图解代码实现（java） 非等概率随机数 3.3 Huffman树 基本概念
路径长度：两个结点之间路径上的分支数
树的外部路径长度：各叶结点到根结点的路径长度之和
树的内部路径长度：各非叶结点到根结点的路径长度之和
树的带权路径长度：树中所有叶子结点的带权路径长度之和
Huffman树定义:是一类带权（外部）路径（Weighted PathLength）长度最短的树
举例：求下面二叉树的带权路径长度
☑️ "权"大的叶结点深度小，它相对于总路径长度的花费最小，因此，其他叶结点如果"权"小，就会被推到树的较深处
构造算法❓ 如何构造Huffman树?
1️⃣ 根据给定的n个权值 { w 1 , w 2 . . . , w n } {w_1, w_2 ..., w_n} {w1,w2...,wn}，构造n棵二叉树的集合 F = { T 1 , T 2 , . . . , T n } F={T_1,T_2,...,T_n} F={T1,T2,...,Tn}，其中每棵二叉树中均只含一个带权值为 w i w_i wi的根结点,其左、右子树为空树;
2️⃣ 在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;
3️⃣ 从F中删去这两棵树，同时加入刚生成的新树;
4️⃣ (4)重复(2)和(3)两步，直至F中只含一棵树为止
Huffman编码 前缀码使用Huffman树编制的代码具有前缀特性prefix：一组代码中的任何一个代码都不是另一个代码的前缀
这种特性保证了代码串被反编码时不会有多种可能
字符编码利用Huffman树的特性为使用频率不同的字符编写不等长的编码，从而缩短整个文件的长度
This is isinglass
■ t的频度是1 h的频度是1 i的频度是4 s的频度是5
■ n的频度是1 g的频度是1 a的频度是1 I的频度是1
如果采用等长的编码形式，上面的八个字母则需要三位二进制编码
长度=15*3=45
按照上面字母出现的频度创建一个Huffman树
图解 代码实现（java）class Letter { char element;//字母 double weight;//字母出现的频率 public Letter(char element, double weight) { this.element = element; this.weight = weight; } public char getElement() { return element; } public void setElement(char element) { this.element = element; } public double getWeight() { return weight; } public void setWeight(double weight) { this.weight = weight; }}class HuffTreeNode { Letter letter; HuffTreeNode left;//左子结点 HuffTreeNode right;//右子结点 public Letter getLetter() { return letter; } public void setLetter(Letter letter) { this.letter = letter; } public HuffTreeNode getLeft() { return left; } public void setLeft(HuffTreeNode left) { this.left = left; } public HuffTreeNode getRight() { return right; } public void setRight(HuffTreeNode right) { this.right = right; }}public class HuffmanTree { //简单使用冒泡排序 private void sort(HuffTreeNode[] nodes) { int flags = 0; for (int i = 0; i < nodes.length-1; i++) { for (int j = 0; j < nodes.length-1-i; j++) { if (nodes[j].letter.weight > nodes[j + 1].letter.weight) { HuffTreeNode temp = nodes[j]; nodes[j] = nodes[j + 1]; nodes[j + 1] = temp; flags = 1;//不是有序的，flags设置为1； } } if (flags == 0) return; } } public HuffTreeNode generateHuffTree(Letter[] letters) { HuffTreeNode[] nodes = new HuffTreeNode[letters.length]; for (int i = 0; i < letters.length; i++) { nodes[i] = new HuffTreeNode(); nodes[i].letter = letters[i]; } while (nodes.length > 1) { sort(nodes); HuffTreeNode node1 = nodes[0]; HuffTreeNode node2 = nodes[1]; HuffTreeNode newTree = new HuffTreeNode(); Letter temp = new Letter('0',node1.getLetter().getWeight()+node2.getLetter().getWeight()); newTree.setLetter(temp); newTree.setLeft(node1); newTree.setRight(node2); HuffTreeNode[] nodes2 = new HuffTreeNode[nodes.length - 1];//新的结点数组，长度减一 for (int i = 2; i < nodes.length; i++) { nodes2[i - 2] = nodes[i]; } nodes2[nodes2.length - 1] = newTree; nodes = nodes2; } return nodes[0]; } public void print(HuffTreeNode root,String code){ if(root != null) { print(root.getLeft(),code+"0"); print(root.getRight(),code+"1"); if(root.getLeft() == null && root.getRight() == null) { String m=root.getLetter().getElement()+"频数:"+root.getLetter().getWeight()+" 哈夫曼编码："+code; System.out.println(m); } } } public static void main(String[] args) { Letter a = new Letter('a', 1); Letter g = new Letter('g', 1); Letter h = new Letter('h', 1); Letter l = new Letter('l', 1); Letter n = new Letter('n', 1); Letter t = new Letter('t', 1); Letter i = new Letter('i', 4); Letter s = new Letter('s', 5); Letter[] test = {a, g, h, l, n, t, i, s}; HuffmanTree huffmanTree = new HuffmanTree(); huffmanTree.print(huffmanTree.generateHuffTree(test),""); }}
n频数:1.0 哈夫曼编码：000t频数:1.0 哈夫曼编码：001i频数:4.0 哈夫曼编码：01a频数:1.0 哈夫曼编码：1000g频数:1.0 哈夫曼编码：1001h频数:1.0 哈夫曼编码：1010l频数:1.0 哈夫曼编码：1011s频数:5.0 哈夫曼编码：11
非等概率随机数 按照给定的概率生成相应的随机数
比如有1、2、3、4、5、6这6个数，编写一个随机发生器，使其能够按照如下概率（0.15、0.20、0.10、0.30、0.12和0.13）生成相应的6个数
1️⃣ 解决方法一：可以使用JavaAPI中的随机数生成函数，生成[0，1）之间的数，按照区间生成数字
2️⃣ 解决方法二：使用Huffman树减少比较次数
public static int randomGenerate() { double temp = Math.random(); int result=0; if (temp < 0.42) { if (temp < 0.22) { if (temp < 0.10) { result = 3; } else { result = 5; } } else { result = 2; } } else { if (temp < 0.72) { result = 4; } else { if (temp < 0.85) { result = 6; } else { result = 1; } } } return result; }