哈夫曼树的编码原理及实战分析

痛定思痛。 2022-10-22 02:57 3阅读 0赞

今天我们分享哈夫曼树的编码原理及实战：

首先我们通过一道面试题来引出哈夫曼树，试题如下：

问题：给定一段字符串，如何对字符串进行编码，可以使得该字符串的编码存储空间最少？

【例子】假设一段文本，包含58个字符，并且由以下7个字符构成:a,b,c,d,e,f,g；这7个字符出现的频次不同，如何对这7个字符进行编码，使得总编码空间最小。

一、、 常见解决思路：

1、【分析】

1)用等长ASCII编码：58×8=464位；

2)用等长3位编码：58×3=174位；

3)不等长编码：出现频次高的字符用的编码短些，出现频次低的编码长些。

【编码长度】 10×3+15×2+12×2+3×5+4×4+13×2+1×5=146位；

3、使用二叉树解决编码问题：

使用二叉树如何进行编码？

1)二叉左右分支：0、1

2)字符随便放？

4个频次最高的字符：

1011是什么字符串的编码呢？可能代表如下结果，如下图：

如何避免二义性？

字符只在叶节点上（就不会有二义性），即只代表一种结果：

解决方案如同：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

4、

5、

二、使用哈夫曼树的解决方案：

1、什么是哈夫曼树：

哈夫曼树： 构造一棵二叉树，该树的带权路径长度达到最小， 称为最优二叉树，也称为哈夫曼树(Huffman Tree)。

2、构造哈夫曼树方式

1)每次把权值最小的两棵二叉树合并。

2)左节点权值比右节点小。

3、如上面试题的解决方案：

【编码长度】 10×3+15×2+12×2+3×5+4×4+13×2+1×5=146位；

4、编码流程图演示：绿色节点是两个子节点的合并，里面没有具体值。

1)首次组合：最小频次的两个

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

2)第二次组合，依次取最小的频次的数据

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2][]

3)第三次构造，按照次思路继续操作

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 3][]

4)第四步流程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 4][]

5)第五步流程

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 5][]

6)第六步后完成编码

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 6][]

5、用java代码实现此树的编码：

public class NandaoHuffmanTree{
 //节点
 public static class Node<E> {
 E data; //数据
 int weight; //权重
 Node leftChild; //左子节点
 Node rightChild;//右子节点
 
 public Node(E data, int weight) {
 super();
 this.data = data;
 this.weight = weight;
 }
 
 public String toString() {
 return "Node[" + weight + ",data=" + data + "]";
 }
 }
 
 public static void main(String[] args) {
 List<Node> nodes = new ArrayList<Node>();
 //把节点加入至list中
 nodes.add(new Node("a", 10));
 nodes.add(new Node("b", 15));
 nodes.add(new Node("c", 12));
 nodes.add(new Node("d", 3));
 nodes.add(new Node("e", 4));
 nodes.add(new Node("f", 13));
 nodes.add(new Node("g", 1));
 //进行哈夫曼树的构造
 Node root = NandaoHuffmanTree.createTree(nodes);
 //打印哈夫曼树
 printTree(root);
 }
 
 /**
 * 构造哈夫曼树
 *
 * @param nodes
 * 节点集合
 * @return 构造出来的哈夫曼树的根节点
 */
 private static Node createTree(List<Node> nodes) {
 //如果节点node列表中还有2个和2个以上的节点
 while(nodes.size()>1){
 //什么是最小的，list表进行排序，增序的方式， 0,1，
 sort(nodes);//排序方式是增序的
 Node left = nodes.get(0);//权重最小的
 Node right = nodes.get(1);//权重第二小的
 //生成一个新的节点（父节点），父节点的权重为两个子节点的之和
 Node parent = new Node(null,left.weight+right.weight);
 //树的连接，让子节点与父节点进行连接
 parent.leftChild = left;
 parent.rightChild = right;
 nodes.remove(0);//删除最小的
 nodes.remove(0);//删除第二小的。
 nodes.add(parent);
 }
 return nodes.get(0); //返回根节点
 }
 /**
 * 冒泡排序，用于对节点进行排序（增序排序）
 *
 * @param nodes
 */
 public static void sort(List<Node> nodes) {
 if (nodes.size() <= 1)
 return ;
 /*循环数组长度的次数*/
 for (int i = 0; i < nodes.size(); i++){
 /*从第0个元素开始，依次和后面的元素进行比较
 * j < array.length - 1 - i表示第[array.length - 1 - i]
 * 个元素已经冒泡到了合适的位置，无需进行比较，可以减少比较次数*/
 for (int j = 0; j < nodes.size() - 1 - i; j++){
 /*如果第j个节点比后面的第j+1节点权重大，交换两者的位置*/
 if (nodes.get(j + 1).weight < nodes.get(j).weight) {
 Node temp = nodes.get(j + 1);
 nodes.set(j+1,nodes.get(j));
 nodes.set(j,temp);
 }
 }
 }
 return ;
 }
 
 /*
 * 递归打印哈夫曼树(先左子树，后右子树打印)
 */
 public static void printTree(Node root) {
 System.out.println(root.toString());
 if(root.leftChild !=null){
 System.out.print("left:");
 printTree(root.leftChild);
 }
 if(root.rightChild !=null){
 System.out.print("right:");
 printTree(root.rightChild);
 }
 }
 }

6、执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 7][]

到此哈夫曼树的编码原理及实战分析完成，下篇分析平衡二叉树，敬请期待！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221022/72765a9b89634b239c48d88f70cd771b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: /images/20221022/985815f893eb43b7970afed854586e33.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2]: /images/20221022/f186d21ccc0940e284f44f009c36b372.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 3]: /images/20221022/f355b54a61f5424cb391dd94f2c82f4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 4]: /images/20221022/d571580dfdb24e2f962e7ddd1b528a4b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 5]: /images/20221022/d37d38ba815f47deb0def68b630516d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 6]: /images/20221022/39a844ef467e4cd498d062b8887a6759.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 7]: /images/20221022/60707f497e2f4020ae626eb885baf6cd.png