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

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

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

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

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

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

由于需要分两篇来讲,本篇主要讲解编码的底层实现过程,即权值数组排序、赫夫曼树合成过程、合成的子树插入权值数组的过程、通过赫夫曼树获取字符编码的过程。

源代码如下:

<?php
//定义节点
class Node{
         public $left = null;
         public $right = null;
         public $data = null;
}
//假设一串字符包含{a,b,c,d,e,f}六个字符种类,
//其中每个字符出现的频率分别是{0.12,0.31,0.05,0.21,0.13,0.18}
classHuffmanTree{
         //格式array(0=>array(w1,val1),1=>array(w2,val2)..n=>array(wn,valn))
         //一一对应
         private function getHuTree($arr){
                   //采用快速排序,将频率从大到小排列,便于使用array_pop
                   $arr =$this->getQuickSorted($arr);
                   //循环实现赫夫曼算法
                   while(count($arr)>2){
                            $newTree = newNode();
                            //获取数组当前最小的第一个字符所在的数组
                            $left =array_pop($arr);
                            //如果$left[1]存放的是合成的树,则直接指向新的树
                            //否则,新建一个节点,用于存放val的值
                            if(!is_object($left[1])){
                                     $leftNode =new Node();
                                     $leftNode->data= $left[1];
                                     $newTree->left= $leftNode;                              
                            }else{
                                     $newTree->left= $left[1];
                            }
                            //获取数组当前最小的第二个字符所在的数组,操作过程同上
                            $right =array_pop($arr);
                            if(!is_object($right[1])){
                                     $rightNode= new Node();
                                     $rightNode->data= $right[1];
                                     $newTree->right= $rightNode;                                  
                            }else{
                                     $newTree->right= $right[1];
                            }
                            //计算合成后的权值
                            $newPrioty =$left[0] + $right[0];
                            $newArr =array($newPrioty, $newTree);
                            ///调用函数把合成后的二叉树数组加入原数组中
                            $arr =$this->getNewSorted($arr, $newArr);
                   }
                   $huffmanTree = new Node();
                   //合并最后两个节点,规则同上
                   if(!is_object($arr[0][1])){
                            $leftNode = newNode();
                            $leftNode->data =$arr[0][1];
                            $huffmanTree->left= $leftNode;                                
                   }else{
                            $huffmanTree->left= $arr[0][1];    
                   }                
                   if(!is_object($arr[1][1])){
                            $rightNode = newNode();
                            $rightNode->data= $arr[1][1];
                            $huffmanTree->right= $rightNode;                                    
                   }else{
                            $huffmanTree->right= $arr[1][1];  
                   }                          
                   return $huffmanTree;
         }
         //合成的树按顺序插入数组的函数
         //由于每次都是最小的两个数相加,因此倒序进行比较w
         //格式 $arr =array(0=>array(w1,val1),1=>array(w2,val2)..n=>array(wn,valn))
         //    $newArr = array(wx, object $tree);
         private function getNewSorted($arrAll,$newArr){
                   $len = count($arrAll);
                   if($len<=0 ||!is_array($newArr)){
                            return $arrAll;
                   }
                   for($i=$len-1;$i>=0;$i--){
                            //当第i个时比新的小或等,则新的数组插入第i+1的位置
                            if(current($arrAll[$i])>=current($newArr)){
                                     $i = $i +1;
                                     break;
                            }
                   }
                   //如果i最大,则从第一个位置插入
                   if($i<0){
                            $i = 0;
                   }
                   //挪动i之后的位置
                   $arrAll[$len] = 0;
                   for($j=$len;$j>$i;$j--){
                            $arrAll[$j] =$arrAll[$j-1];//每个数往后挪一位
                   }
                   $arrAll[$i] = $newArr;
                   return $arrAll;
         }
         //排序函数:对w进行快速排序
         //格式 $arr =array(0=>array(w1,val1),1=>array(w2,val2)..n=>array(wn,valn))
         private function getQuickSorted($arr){
                   $len = count($arr);
                   if($len<=1){
                            return $arr;
                   }
                   $midW = current($arr[0]);
                   $arrBigRight = array();
                   $arrSmallLeft = array();
                   //快速排序
                   for($i=1;$i<$len;$i++){
                            if(current($arr[$i])< $midW){
                                     array_push($arrSmallLeft,$arr[$i]);
                            }else{
                                     array_push($arrBigRight,$arr[$i]);
                            }
                   }
                   $arrSmallLeft =$this->getQuickSorted($arrSmallLeft);
                   $arrBigRight =$this->getQuickSorted($arrBigRight);
                   $newArr = array();
                   //大的先入栈,从大到小排序
                   if(!empty($arrBigRight)){
                            foreach($arrBigRightas $arrTemp){
                                     array_push($newArr,$arrTemp);
                            }
                   }                          
                   array_push($newArr, $arr[0]);
                   if(!empty($arrSmallLeft)){
                            foreach($arrSmallLeftas $arrTemp){
                                     array_push($newArr,$arrTemp);
                            }
                   }       
                   return $newArr;
         }
         //输出编码结果
         //递归方式,逐个查看每个节点
         private functiongetCharEncodedRecu(Node $tree, array $codeStack=array()){
                   //当data不空时,其为叶子节点,则直接返回拼接好的字符串
                   if($tree->data != null){
                            returnarray($tree->data => implode('',$codeStack));
                   }else{
                            //当data空时,表示是树,分别把其左右两个子树再次调用本方法,获取结果
                            //左子树调用时加一个0,右子树加一个1
                            array_push($codeStack,0);
                            $res1 =$this->getCharEncodedRecu($tree->left, $codeStack);
                            array_pop($codeStack);
                            array_push($codeStack,1);
                            $res2 =$this->getCharEncodedRecu($tree->right, $codeStack);
                            return $res1+$res2;
                   }
         }

——written by linhxx 2017.07.06

相关阅读:

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

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

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

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

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

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

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

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

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

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

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

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

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

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