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

相关文章

来自专栏编程微刊

一个简易的选择小时(时分秒)的插件

1001
来自专栏海说

Spring IOC容器分析(4) -- bean创建获取完整流程

上节探讨了Spring IOC容器中getBean方法,下面我们将自行编写测试用例,深入跟踪分析bean对象创建过程。 测试环境创建 测试示例代码如下: pac...

2320
来自专栏逸鹏说道

.net采集网页方法大全(5种)

/// <summary>方法一:比较推荐 /// 用HttpWebRequest取得网页源码 /// 对于带BOM的网页很有效...

37717
来自专栏Porschev[钟慰]的专栏

得到真实外网IP、IP所在国家、省份、地区

实现方式:通过正则抓取IP显示网站中的数据。。。。 友情提示:这种方式效率不算高,如果用在WEB中,如果用得少可以用这种方式,如果常用,还是建议用IP库 #r...

1995
来自专栏DT乱“码”

MD5加密代码(工具类)

package com.test.system.util; import java.security.MessageDigest; import java.s...

1657
来自专栏jerryteng的专栏

打造高效的Mac开发环境

plugins=(composer cp iterm2 docker git git-extras git-flow go golang autojump sv...

2276
来自专栏飞扬的花生

在服务端发起一个Post请求

1.http://www.tuling123.com/openapi/api?key=9d2ff29d44b54e55acadbf5643569584&info...

3498
来自专栏

Ajax跨域访问代理类,支持GET和POST方法

支持GET和POST两种方式 使用方法:http://localhost:4817/AppContainer/HttpProxy.ashx?httpproxy_...

833
来自专栏码农阿宇

Duplicate entry '0' for key 'PRIMARY'的一种可能的解决办法

在MySQL设计好数据库往往数据库中插入数据的时候, 因为主键ID默认是不赋值的,只给其他项目赋值了,相关的SQL代码是这样的 StringBuilder ...

3114
来自专栏跟着阿笨一起玩NET

C#分析URL参数获取参数和值得对应列表(二)

832

扫码关注云+社区