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

相关文章

来自专栏程序员互动联盟

【答疑解惑第六讲】数组与指针区别在哪?

存在问题: 小伙伴都说指针和数组不好学,总是搞不太清楚?两者到底有啥区别? 解决方案: 很多初学者朋友总是对数组和指针模模糊糊,搞不清楚。对他们之间的联系与区...

34111
来自专栏码云1024

python简明笔记

通过 for 语句我们可以使用 for 循环。Python 里的 for 循环与 C 语言中的不同。这里的 for 循环遍历任何序列(比如列表和字符串)中的每一...

5328
来自专栏琦小虾的Binary

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

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

3166
来自专栏数据分析

char varchar nchar nvarcharar到底有多大区别

首先说明下,ASP.NET MVC系列还在龟速翻译中。 工作好多年,基础知识甚是薄弱,决定以后在coding(cv操作)的时候尽量多google下,然后总结下来...

2776
来自专栏iOS技术杂谈

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

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

4506
来自专栏闻道于事

问题整理

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

2884
来自专栏NetCore

.NET反射、委托技术与设计模式

1 反射技术与设计模式   反射(Reflection)是。NET中的重要机制,通过放射,可以在运行时获得。NET中每一个类型(包括类、结构、委托、接口和枚举...

2099
来自专栏决胜机器学习

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

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

33610
来自专栏逢魔安全实验室

UAF Writeup - pwnable.kr

0x00 UAF — pwnable.kr是一个韩国的CTF练习的网站,有很多经典的CTF题目供爱好者练习。 UAF(Use After Free)释放后重用...

3496
来自专栏增长技术

Swift体验2

使用if和switch做条件判断,使用for-in,for,while,do-while做循环 操作。括号中的条件或循环变量是可选的。括号的身体是必需的。

1113

扫码关注云+社区