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