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