首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

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

作者头像
用户1327360
发布2018-03-07 10:32:07
7330
发布2018-03-07 10:32:07
举报
文章被收录于专栏:决胜机器学习决胜机器学习

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数据结构(一)——顺序结构线性表

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-07-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 决胜机器学习 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 相关阅读:
    • PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)
      • PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)
        • PHP数据结构(七) ——串与实现KMP算法
          • PHP数据结构(六) ——树与二叉树之概念及存储结构
            • PHP数据结构(六) ——数组的相乘、广义表
              • PHP数据结构(五) ——数组的压缩与转置
                • PHP数据结构(四) ——队列
                  • PHP数据结构(三)——运用栈实现括号匹配
                    • PHP数据结构(二)——链式结构线性表
                      • PHP数据结构(一)——顺序结构线性表
                      领券
                      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档