Java教程

JAVA第26天——赫夫曼编码（一）——基础知识

本文主要是介绍JAVA第26天——赫夫曼编码（一）——基础知识，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Huffman编码

一、赫夫曼（Huffman）树

  • 又叫最优二叉树：是一种带权路径最小的树。
  • 路径长度：例如：根节点到左孩子就是一个路径长度。
  • 树的路径长度：从树根到每一个节点的路径长度之和。
  • 树的带权路径长度：树中所有叶子节点的带权路径之和，记作WPL。
  • WPL最小：当WPL最小时的二叉树，称为最优二叉树或赫夫曼树。
  • 图例：

在这里插入图片描述

二、前缀编码

  • 若要设计长短不等的编码，则必须是任意一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。
  • 图例：

在这里插入图片描述

三、赫夫曼编码

  • 由赫夫曼树，得到的前缀编码，就是赫夫曼编码。
  • 赫夫曼树没有度为1的节点。
  • n个叶子节点，一定有2*n-1个节点。
  • 赫夫曼编码：从叶子节点出发，走一条从叶子到根的路径。
  • 解码（译码）：从根出发，走一条从根到叶子的路径。
  • 设计时应该用，三叉链表。
  • Huffman 算法
    给定 w1, w2, … , wi
    （1）作 t 片树叶，分别以 w1, w2, … , wi 作为权。
    （2）在所有入度为0的顶点（不一点是树叶）中选取两个权最小的顶点，添加一个新分支，它以这2个顶点为儿子，其权等于这两个儿子的权之和。
    （3）重复（2），直到只有1个入度为0的顶点为止。
    WPL等于所有分支点的权之和。
这篇关于JAVA第26天——赫夫曼编码（一）——基础知识的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航