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

相关文章

来自专栏云霄雨霁

子字符串查找----Boyer-Moore算法(从右向左匹配)

860
来自专栏鸿的学习笔记

函数式编程阅读笔记

当我们要从一个不可变的list里删除元素或者添加元素怎么办?当增加元素时,你取出来的值的引用就是在原始表中增加元素,而不去修改原来的数据结构。也就是复用。

581
来自专栏Leetcode名企之路

【Leetcode】55. 跳跃游戏

给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1:

713
来自专栏IT可乐

Java数据结构和算法(九)——高级排序

  春晚好看吗?不存在的!!!   在Java数据结构和算法(三)——冒泡、选择、插入排序算法中我们介绍了三种简单的排序算法,它们的时间复杂度大O表示法都是O(...

3396
来自专栏数据小魔方

左手用R右手Python系列之——迭代器与迭代对象

接触过Python的小伙伴儿肯定都知道,Python中关于迭代器和可迭代对象运用的很广泛。迭代器可以以一种非常友好的方式使用在循环中,不仅节省内存,还能优化代码...

3498
来自专栏塔奇克马敲代码

不相交集类

1325
来自专栏深度学习自然语言处理

【珍藏版】长文详解python正则表达式

想要使用python的正则表达式功能就需要调用re模块,re模块为高级字符串处理提供了正则表达式工具。模块中提供了不少有用的函数,比如:compile函数、ma...

362
来自专栏有趣的django

4.python迭代器生成器装饰器

基本概念 1.容器(container) 容器是一种把多个元素组织在一起的数据结构,容器中的元素可以逐个地迭代获取,可以用in, not in关键字判断元素是否...

2758
来自专栏云霄雨霁

字符串排序----三向字符串快速排序

870
来自专栏desperate633

详解排序算法--堆排序选择排序堆排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩...

563

扫描关注云+社区