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 条评论
登录 后参与评论

相关文章

来自专栏我是东东强

数据结构之线性表

线性表实现有两种方式,一种为顺序表,另一种为链表。本文分别介绍了顺序线性表、单向链表、双向链表和循环链表的基本结构,并给出了相应的C++类代码实现。

952
来自专栏朱慕之的博客

基础算法

0.创建类 BinaryTreeNode 1.创建方法:传入根结点 2.判断根节点是否为空 3.判断左右结点是否同时为空 4.用self调用此方法,将根节点的左...

651
来自专栏阿杜的世界

经典面试题之链表

721
来自专栏Jed的技术阶梯

普通树简介以及Java代码实现

2901
来自专栏tkokof 的技术,小趣及杂念

数学小记之数系

自然数即非负整数(包括 0 和 正整数),字母表示为 N(Natural number) :

994
来自专栏LeetCode

LeetCode 543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree....

880
来自专栏机器学习入门

LWC 63: 749. Contain Virus

Problem: A virus is spreading rapidly, and your task is to quarantine the infec...

1918
来自专栏JAVA高级架构

Java数据结构与算法解析——2-3树

二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,...

3407
来自专栏来自地球男人的部落格

[LeetCode] 39.Combination Sum

【原题】 Given a set of candidate numbers (C) (without duplicates) and a target ...

1957
来自专栏Java爬坑系列

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。

784

扫码关注云+社区