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

相关文章

扫码关注云+社区