济南网站假设推广,网站上线前要做哪些准备,微信小程序支付功能开发,武威市建设局网站 放管服一、哈夫曼树
1.1 哈夫曼树的概念
给定一个序列#xff0c;将序列中的所有元素作为叶子节点构建一棵二叉树#xff0c;并使这棵树的带权路径长度最小#xff0c;那么我们就得到了一棵哈夫曼树#xff08;又称最优二叉树#xff09;
接下来是名词解释#xff1a;
权将序列中的所有元素作为叶子节点构建一棵二叉树并使这棵树的带权路径长度最小那么我们就得到了一棵哈夫曼树又称最优二叉树
接下来是名词解释
权节点的数值路径长度两节点间路径的边数带权路径长度节点的权值乘以该节点到根节点的路径长度即为该节点的带权路径长度。哈夫曼树的带权路径长度是树中所有叶子节点的带权路径长度之和。
例如下面这棵哈夫曼树 通过观察我们可以发现所有父节点的权值都是自身的两个子节点的权值之和。而为了要使树的带权路径长度最小我们要尽可能的让权值小的节点离根节点远让权值大的节点离根节点近。
因此我们引出哈夫曼树的构造算法。
1.2 哈夫曼树的构造算法
要将一个序列构造成一棵哈夫曼树我们首先需要对其进行升序排序 将排序好后的序列中的每个值看作一棵只有一个节点的树从中选出根节点权值最小的两棵树作为新树的左右子树并将这两棵树从序列中删除而新树的根节点的权值是这两棵树根节点的权值之和
哈夫曼树没有规定左右子树的顺序因此下面的例子中将10和18的位置对调也是正确的 将新树的根节点的权值放入序列中并重新进行升序排序重复上述步骤 至此就构建了一棵哈夫曼树
因为哈夫曼树没有规定左右子树的顺序因此一个序列可以构建出不同的哈夫曼树 二、哈夫曼编码
2.1 等长编码
假设我们要对一个字符串ABAACDC进行二进制编码
我们可以按顺序给每个字符设置一个编码A为0B为1C为10D为11
那么就可以将上面的字符串转化为0100101110
但是在解码的时候我们会发现这一串二进制序列可以解码为ACACDBA、ACABABDA等字符串出现了歧义。
这是因为我们在对字符进行编码的时候出现了一个字符是另一个字符的前缀的情况例如D可以用两个B来表示。
为了避免歧义我们可以采用等长编码的方案就是每个字符的编码都一样长例如A为00B为01C为10D为11这样就不会产生歧义了。
但是这种方案并不是一个最短的方案。
2.2 哈夫曼编码
统计字符出现的次数把字符定义成一个节点节点的权值就是它出现的次数。
例如上面A出现了3次B出现了1次C出现了2次D出现了1次
哈夫曼编码的核心思想就是让出现次数越多的字符编出来的码越短我们将全部节点构建成一棵哈夫曼树出现次数越少的字符对应的节点就越靠近树的底层编码也就越长出现次数越多的字符编码就越短。
对二叉树的边标号向左的边标为0向右的边标为1至此所有字符的编码就是从根节点到该字符节点路径上经过的标号例如A为1B为010C为00D为011这种编码方案就叫做哈夫曼编码。 构建哈夫曼树的时候所有的字符节点都是叶子节点不会出现一个字符出现在另一个字符的路径上也就不会出现一个字符是另一个字符的前缀这种造成歧义的情况
哈夫曼树的编码不是唯一的节点放置的左右也会造成字符编码的不同但是生成的编码长度一定都是一样的。
完.
