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

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

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT可乐

深入理解计算机系统(3.4)------算术和逻辑操作

  上一篇博客  我们介绍了几种数据传送指令,包括MOV,MOVS,MOVZ,PUSH和POP等,理解起来也不算难。本篇博客我们来接着看汇编语言的算术与逻辑运算...

1779
来自专栏闵开慧

总结5种比较高效常用的排序算法

1 概述     本文对比较常用且比较高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性...

3417
来自专栏C/C++基础

基数排序简介及其并行化

  基数排序号称线性时间排序算法中性能最好,速度最快的排序算法。本文将简要概括其算法思想,串行代码及其并行化。

591
来自专栏IT开发技术与工作效率

Java经典编程50题(面试笔试机试)

https://blog.csdn.net/alias_fa/article/details/52985112

14923
来自专栏Android Note

移除Kotlin代码中的感叹号(!!)

883
来自专栏斑斓

编程实践 | Scala亮瞎Java的眼(一)

这是我在11月15日成都OpenParty分享的一个题目,确有标题党的嫌疑。Scala自然不是无所不能,Java也没有这么差劲,我只希望给Java程序员提供另外...

3175
来自专栏calmound

Set Matrix Zeroes

问题:将数组中的某个值为0的元素所在行和列的其他值都为0 分析;遍历数组找到某一值为0然后遍历他的上下左右直到边界,要用while而不能用搜索,因为搜索过去新节...

3315
来自专栏数据结构与算法

清北集训Day3T1(转换)

这题可能是我与正解里的最近的一次了,可以还是sb的把正解叉了。 正解其实比较显然:因为f(x)只有81个取值,所以我们可以枚举f(x),然后计算x,再判断x是否...

3337
来自专栏函数式编程语言及工具

Akka(21): Stream:实时操控:人为中断-KillSwitch

 akka-stream是多线程non-blocking模式的,一般来说,运算任务提交到另外线程后这个线程就会在当前程序控制之外自由运行了。任何时候如果需要终...

2196
来自专栏机器人网

只会G代码不会宏,就别说你是数控师傅

一、变量 普通加工程序直接用数值指定G代码和移动距离;例如,GO1和X100.0。使用用户宏程序时,数值可以直接指定或用变量指定。当用变量时,变量值可用程序或用...

2654

扫描关注云+社区