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

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

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

公众号规定不能超过3000字,只能分两篇,见谅。

由于需要分两篇来讲,本篇接上篇的内容,假定已经获取到编码的结果,利用该结果实现对字符串的编码和解码的过程。

本篇主要讲解针对输入字符串进行各字符权值数组的计算、调用方法获取字符编码结果、根据编码结果实现对字符串的编码、根据权值数组实现对被编码的字符串进行解码。

源代码如下:

<?php 

 //编码函数 输入一串字符串,
 //返回每个字符的编码array('char1'=>'encoded1','char2'=>'encoded2'....)
 //以及整个字符串的编码结果
         public function getStringEncoded($str){
                   $len = strlen($str);
                   if($len <= 0){
                            return false;
                   }
                   if(1 == $len){
                            return array($str=> '0');
                   }
                   //计算每个字符的数量
                   $arrChar = array();
                   for($i=0;$i<$len;$i++){
                            if(isset($arrChar[$str[$i]])){
                                     $arrChar[$str[$i]]++;
                            }else{
                                     $arrChar[$str[$i]]= 1;
                            }
                   }
                   //根据数量计算权值
                   $arrWeight = array();
                   $i = 0;
                   foreach($arrChar as $key=> $val){
                            $arrWeight[$i++] =array(round($val/$len, 2), $key);
                   }
                   //获取每个字符的编码结果
                   $huffmanTree =$this->getHuTree($arrWeight);
                   $charCode =$this->getCharEncodedRecu($huffmanTree);
                   //根据每个字符的编码结果,获取字符串的编码结果
                   $resStr = '';
                   for($i=0;$i<$len;$i++){
                            $resStr .=$charCode[$str[$i]];
                   }
                   $resArr =array('char'=>$charCode, 'str'=>$resStr);
                   return $resArr;
         }
         //解码函数,输入编码字符串和每个字符的编码,返回结果字符串
         public functiongetStringDecoded($encodedStr, $charCode){
                   $charCode =array_flip($charCode);//把数组的键值互换
                   $decodedStr = '';
                   $tmpCode = '';
                   for($i=0;$i<strlen($encodedStr);$i++){
                            $tmpCode .= $encodedStr[$i];
                            if(isset($charCode[$tmpCode])){
                                     $decodedStr.= $charCode[$tmpCode];
                                     $tmpCode ='';                            
                            }
                   }
                   return $decodedStr;
         }
}
//给定任意字符串,返回每个字符的编码结果,以及字符串的编码结果
$huffmanTreeEntity= new HuffmanTree();
$str ='aabjbjkdixxkdlx';
$res = $huffmanTreeEntity->getStringEncoded($str);
echo '输入的字符串是【'.$str.'】<br />编码结果是【'.$res['str'].'】<br/>';
echo '其中每个字符的编码分别是:';
print_r($res['char']);
echo '<br/><br />';
$decodedStr =$huffmanTreeEntity->getStringDecoded($res['str'], $res['char']);
echo '将编码后的字符串【'.$res['str'].'】解码后的结果是【'.$decodedStr.'】';

题外话:为了编写本代码,我调试了两天,主要在于从赫夫曼树获取字符编码的方法。因为采用赫夫曼树对字符进行编码时,每个字符都会在赫夫曼树的叶子节点上。因此,刚开始编写代码的时候,我尝试采用遍历二叉树的方法,试图通过遍历获取叶子节点的路径,进而获取字符的编码。

我尝试了二叉树的三种遍历方式,在此过程中我还细微调整了几次生成的赫夫曼树的数据结构,但始终无法正确获取编码。后在调试过程中发现,主要原因在于,二叉树遍历的回溯的过程中,会跳过已经遍历的叶子节点,因此无法正确编码。

因此,我放弃遍历二叉树,转而采用递归的方式,对每个节点逐个进行遍历,方式类似于图的广度优先算法。后续问题变迎刃而解。

——written by linhxx 2017.07.06

相关阅读:

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

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

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

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

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

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

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

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

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

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

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闻道于事

问题整理

  相关子查询,无关子查询 所谓相关子查询,是指求解相关子查询不能像求解普通子查询那样,一次将子查询求解出来,然后求解父查询。相关子查询的内层查询由于与外层查询...

30440
来自专栏我是攻城师

理解Java8的数据类型和运行时数据区域

Java虚拟机包含对对象的显式支持,对象要么是动态分配的类实例,要么是静态数组,对对象的引用我们可以叫做指针或者引用,一个对象可以有多个引用,对象总是通过引用的...

16430
来自专栏iOS开发随笔

iOS Swift基础语法(二)

11830
来自专栏iOS技术杂谈

Java8 Lambda表达式与Stream API (二): Stream API的使用你要知道的Java8 匿名内部类、函数式接口、lambda表达式与Stream API都在这里

你要知道的Java8 匿名内部类、函数式接口、lambda表达式与Stream API都在这里 转载请注明出处 https://cloud.tencent.co...

54760
来自专栏小勇DW3

迭代器模式以及对内部类的运用

上一篇文章写了static的作用,其中有部分是介绍了内部类和静态内部类,下面就结合设计模式中的迭代器模式,介绍一下内部类的好处;

8330
来自专栏玄魂工作室

Python黑帽编程2.4 流程控制

Python黑帽编程2.4 流程控制 本节要介绍的是Python编程中和流程控制有关的关键字和相关内容。 2.4.1 IF …..ELSE 先上一段代码: ...

29040
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之用两个栈实现队列(九度OJ1512)

题目描述: 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 输入: 每个输入文件包含一个测试样例。 对于每个测试样例,第一...

21250
来自专栏琦小虾的Binary

map 学习(上)——C++中 map 的使用

map 学习(上)——C++中 map 的使用 欠下数据结构的债,迟早是要还的…… 最近写毕业论文过程中,需要用到哈希表的数据结构,此外空闲时间在刷 Leetc...

45360
来自专栏决胜机器学习

PHP数据结构(十八) ——直接插入排序

PHP数据结构(十八)——直接插入排序 (原创内容,转载请注明来源,谢谢) 一、概述 插入排序分为直接插入排序、其他插入排序、希尔排序。其他插入排序又分为折半...

358100
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版3.5节栈布局之-fomit-frame-pointer编译选项

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

8020

扫码关注云+社区

领取腾讯云代金券