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

相关文章

来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

6688
来自专栏落花落雨不落叶

canvas画简单电路图

59911
来自专栏hbbliyong

WPF Trigger for IsSelected in a DataTemplate for ListBox items

<DataTemplate DataType="{x:Type vm:HeaderSlugViewModel}"> <vw:HeaderSlug...

4054
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.2K7
来自专栏芋道源码1024

熔断器 Hystrix 源码解析 —— 断路器 HystrixCircuitBreaker

本文主要基于 Hystrix 1.5.X 版本 1. 概述 2. HystrixCircuitBreaker 3. HystrixCircuitBreaker....

5287
来自专栏张善友的专栏

Miguel de Icaza 细说 Mix 07大会上的Silverlight和DLR

Mono之父Miguel de Icaza 详细报道微软Mix 07大会上的Silverlight和DLR ,上面还谈到了Mono and Silverligh...

2697
来自专栏我和未来有约会

Silverlight第三方控件专题

这里我收集整理了目前网上silverlight第三方控件的专题,若果有所遗漏请告知我一下。 名称 简介 截图 telerik 商 RadC...

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

c#实现打印功能

2632
来自专栏陈仁松博客

ASP.NET Core 'Microsoft.Win32.Registry' 错误修复

今天在发布Asp.net Core应用到Azure的时候出现错误InvalidOperationException: Cannot find compilati...

4818
来自专栏一个爱瞎折腾的程序猿

sqlserver使用存储过程跟踪SQL

USE [master] GO /****** Object: StoredProcedure [dbo].[sp_perfworkload_trace_s...

2000

扫码关注云+社区