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

相关文章

来自专栏前端儿

三角形面积

输入每行是一组测试数据,有6个整数x1,y1,x2,y2,x3,y3分别表示三个点的横纵坐标。(坐标值都在0到10000之间) 输入0 0 0 0 0 0表示输...

1002
来自专栏葡萄城控件技术团队

Spread for Windows Forms高级主题(5)---数据处理

使用表单的API处理数据 你可以将数据以有格式或无格式字符串或者数据对象的形式填充到单元格中。将数据填充到单元格的最好方式取决于你想添加字符串数据还是数据对象,...

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

洛谷P3377 【模板】左偏树(可并堆)

题目描述 如题,一开始有N个小根堆,每个堆包含且仅包含一个数。接下来需要支持两种操作: 操作1: 1 x y 将第x个数和第y个数所在的小根堆合并(若第x或第y...

2464
来自专栏猿人谷

习题3.13

题目(习题3.13):读一组整数到vector对象,计算并输出每对相邻元素的和。如果读入元素个数为奇数,则提示用户最后一个元素没有求和,并输出其值。然后修改程序...

1777
来自专栏移动端开发

用OC和Swift一起说说二叉树

前言:    一:在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subt...

2125
来自专栏从零开始的linux

python条件判断

if判断 a= 1 if a>10: print 'a大于10' print 'a小于10' a = -20 if a > 10: prin...

3329
来自专栏书山有路勤为径

旋转数组查找

给定一个排序数组nums(nums中有无重复元素),且nums可能以某个未知下 标旋转,给定目标值target,求target是否在nums中出现,若出现返回所...

692
来自专栏kalifaの日々

POJ2431-最优队列(最小堆)解法

这道题有一个坑,就是给出的加油站到终点的距离不一定是降序排列好了的。 所以得到input之后要先对数据进行排序。我直接用了#include<algorithm>...

3297
来自专栏章鱼的慢慢技术路

2016年第七届蓝桥杯C/C++B组省赛题目解析

2936
来自专栏软件开发 -- 分享 互助 成长

二维数组简介与使用

前言 本文将探讨一下关于二维数组在内存中的存储和二维数组在参数传递时的使用。 一、二维数组在内存中的存储 如果定义一个这样的二维数组int a[3][4]={{...

18210

扫码关注云+社区