PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(八)——赫夫曼树实现字符串编解码(理论)

(原创内容,转载请注明来源,谢谢)

一、树和森林

1、树的三种存储结构

1)双亲表示法——数组下标、值、上一级数组下标(根节点下标为负一)

2)孩子表示法

方法一:孩子链表——数组下标、值、下一级数组链表(无下一级指向null)

方法二:带父节点的子链表——结合双亲表示法和孩子链表,包含数组下标、值、上一级数组下标(根节点下标为负一)、下一级数组链表(无下一级指向null)。

3)孩子兄弟表示法——又称二叉树表示法或二叉链表表示法,链表包括左链域、右链域、值,左链域指向第一个孩子节点,右链域指向下一个兄弟节点。如果没有孩子或者下一个兄弟,则相应的指针指向null。

2、森林和二叉树的转换

采用上述的孩子兄弟表示法进行转换,每个树都可以找到唯一的二叉树与之对应。森林中,第二棵树的根节点指向第一棵树的下一个兄弟节点。

1)森林转二叉树的方法

假设F={T1,T2….Tm},当m=0时转成空二叉树。当m>0时,生成的二叉树B的根为T1,左孩子为T1的子树森林转换成的二叉树,右孩子为{T2…Tm}转换成的二叉树。

2)二叉树转森林的方法

假设二叉树B={root,左孩子,右孩子},当B为空时转成的森林为空。当B不为空时,根节点为森林的T1,左孩子为T1的子孩子转成的森林节点,右孩子为森林(T2..Tm)转成的二叉树。

3、树和森林的遍历

1)树有两种遍历方式:先根遍历——先访问根节点,后依次遍历子树;后根遍历——先依次遍历子树,再访问根节点。

2)森林的两种遍历:先序遍历——先访问第一棵树根节点,再遍历第一棵树除节点的子树,最后先序遍历除第一棵树的树;中序遍历——先中序遍历第一棵树根节点的子树森林,再访问其根节点,最后中序遍历除第一棵树外的森林。

二、赫夫曼树

1、赫夫曼树又称最优树,是一类带权路径长度最短的树。

2、节点的路径长度是从根到该节点经过的分支数目,树的路径长度是各根长度的和。

3、树的带权路径长度WPL=所有节点(节点路径长度*节点权值)的和。当权值确定时,最小的WPL为赫夫曼树。

4、赫夫曼算法

1)假设n个权值{w1,w2…..wn}构成的n棵二叉树集合F={T1,T2….Tn},每个Ti只有一个带权为wi的根节点,其左右子树都为空

2)在F中,选w最小的两棵树作为左右子树,合成一棵新的二叉树,并将权值置为其左右根节点的和。

3)在F中删除上述两个树,并把合成的新树加入F中。

4)重复2)、3)两个步骤,直到F只剩一棵树,就是赫夫曼树。

5、赫夫曼编码

概念:用一串数字表示一个字符。当一个字符的编码是另一个字符编码的前缀时,称为前缀编码。要对一串字符进行编码时,不应该出现前缀编码,否则解压的时候无法判断是哪个字符。

编码方式:将各字符出现的频率视为其权值,生成赫夫曼树。其后,从根节点开始,左右子树及其子树都按照左为0、右为1进行编码,即获得字符的编码。

下面将通过PHP实现通过赫夫曼树进行字符编码和解码的全过程,实现方式为:输入任意一串字符串,实现其编码,并输出字符串编码后的结果以及每个字符的编码。再将编码后的字符串和每个字符的编码当作输入,输出解码的结果。

关键点如下:

1)编码过程

1、根据用户输入的字符串,计算出每个字符的权值。

2、将权值-字符数组,针对权值进行从大到小的排序,方便后面逐个获取权值最小的树,本例采用快速排序的算法。

3、取数组的最后两个,即权值最小的两个树,合成一棵树,并重新计算权值。

4、将新生成的树,有序的插入原数组中,保证原数组仍是保持权值从大到小。

5、反复重复3-4两步,直至生成赫夫曼树。

6、针对生成的赫夫曼树的每个节点进行遍历,设往左为0,往右为1,计算出每个字符的编码结果。

7、根据6生成的编码结果,遍历输入的字符串,将每个字符转成对应的编码。

2)解码过程

1、根据用户输入的字符编码数组,进行数组键值互换,便于后续的匹配。

2、遍历编码后的字符串,逐个字符进行匹配,因为赫夫曼的编码每个字符是唯一的,因此只有匹配到某一个子串符合编码数组的内容,即暂存该结果。

3、重复2的过程,直至完成整个编码字符串的遍历。最后所有暂存的结果拼接起来即为编码的结果。

本实例主要采用的几个PHP内置函数:

1、is_object

该函数判断输入的内容是否是一个对象。

2、array_push($array,$content)

将$content插入到数组$array的最后。

3、array_pop($array)

获取$array数组的最后一个元素,并将该元素从该数组中删除。

4、round($num,$accuracy)

将浮点数$num保存$accuracy位小数。

5、current($array)

获取$array数组当前的元素。

6、is_array

判断输入的内容是否为数组。

7、empty($content)

判断$content是否为空,以下内容会被认为是空:array()、’’、0、0.0、’0’、null、false、$var(声明了变量但是没有赋值)。因此,empty等价于!isset($var) || $var == false。

用PHP实现通过赫夫曼树进行字符串编码和解码结果如下:

由于源代码太长,故放在下一篇文章中写出,请看下一篇文章的具体完整源代码实现赫夫曼树的字符串编码和解码。

——written by linhxx 2017.07.06

相关阅读:

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术博文

PHP实现经典算法

前提:分别用冒泡排序法,快速排序法,选择排序法,插入排序法将下面数组中的值按照从小到大的顺序进行排序。 $arr = array(1,43,54,62,21,6...

2614
来自专栏奔跑的蛙牛技术博客

Java中实现的简单算法 && 计算二分查找次数

如果采用其他方式对列表进行排序可以使用List接口的sort方法传入一个Comarable的一个对象

682
来自专栏数据结构与算法

P3742 umi的函数

题目背景 umi 找到了一个神秘的函数 f。 题目描述 这个函数接受两个字符串 s1,s2。这些字符串只能由小写字母组成,并且具有相同的长度。这个函数的输出是另...

3246
来自专栏编程理解

排序算法(九):桶排序

桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中,也就是根据元素值特性将集合拆分为多个区域,则拆分后形成的多个桶,从值域上看是处于有序状态的。对每个桶中...

682
来自专栏轮子工厂

快速搞定8大排序算法

892
来自专栏IT可乐

深入理解计算机系统(2.4)------整数的表示(无符号编码和补码编码)

  上一篇博客我们主要介绍了布尔代数和C语言当中的几个运算符。那么这一篇博客我们主要介绍在计算机中整数是如何表示的,诸如我们在编码过程中遇到的对数据类型进行强制...

2626
来自专栏闻道于事

JavaScript数字例子,二分法,冒泡排序

先看一下两个例子: 十个成绩,求总分,最高分,最低分 //输入10个成绩,求总分,最高,最低 var arr=new Array(67,45,5...

2855
来自专栏机器学习算法全栈工程师

归并排序

作者:柳行刚 编辑:徐 松 基本思想 归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并,得到完全有序的序列;即先使...

35210
来自专栏我是业余自学C/C++的

基数排序

1234
来自专栏猿人谷

位运算

位运算   位运算是把数字用二进制表示之后,对每一位上0或者1的运算。   理解位运算的第一步是理解二进制。二进制是指数字的每一位都是0或者1.比如十进制的2转...

1748

扫码关注云+社区