名词解释:哈夫曼编码(HuffmanCoding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。该方法依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 实现过程: 1.计算每个字符在字符串中出现的频率作为构建h
名词解释:哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。该方法依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。
实现过程:
1.计算每个字符在字符串中出现的频率作为构建huffman树的权重
2.构建huffman树
3.建立每个字符对应的编码表
4.重建字符串编码,既压缩字符串
5.解压时根据先前的huffman树和字符位长度还原字符串
<?php
/**
基于静态huffman编码的压缩[PHP语言实现]
author: lajabs
email: aGl0dHlvQGdtYWlsLmNvbQ==
本文以PHP作为描述语言较详细讲解huffman树原理及应用
因保证程序可读性,故不做优化.
*/
class huffman
{
/**
* 压缩入口
* $str:待压缩的字符串
*/
public function encode($str)
{
$len=strlen($str);
//计算每个字符权重值(出现的频度)<这边可以做成概率表>
for($i=0;$i<$len;$i++) $array[ord($str{$i})]++;
$HuffmanArray=array();
asort($array);
/**
* 构造huffman树,时间复杂度O(nlogn)
* 选择两个使用频率较小<字符在字符串中出现的次数>的结点合并生成出一个树
*/
while ($item1 = each($array))
{
$item2 = each($array);
//构建huffman树
$this->creat_tree($item1,$item2,$array,$HuffmanArray);
//反复排序<优化这步可在构造树时用插入排序算法完成>
asort($array);
}
$HuffmanArray=array_shift($HuffmanArray);
//构建编码表<这步可优化为构建树时一同生成>
$tab=null;
$code_tab=$this->creat_tab($HuffmanArray,$tab);
//压缩&转换整个字符串为二进制表达式
$binary=null;
for($i=0;$i<$len;$i++) $binary.=$tab[ord($str{$i})];
//转化为压缩后的字符串
$code=$this->encode_bin($binary);
//静态huffman编码算法压缩后需保留huffman树
return array('tree'=>$HuffmanArray,'len'=>strlen($binary),'code'=>$code);
}
/**
* 解压缩入口
* $huffman:解压所使用的huffman树
* $str:被压缩的字符
* $blen:压缩前的位长度
*/
public function decode($huffman,$str,$blen)
{
$len=strlen($str);
$binary=null;
//将编码解为二进制表达式
for($i=0;$i<$len;$i++)
$binary.=str_pad(base_convert(ord($str{$i}),10,2),8,'0',STR_PAD_LEFT);
//去除补码
$binary=substr($binary,0,$blen);
//从hufman树中配比相应的编码
return $this->decode_tree($binary,$huffman,$huffman);
}
/**
* 将压缩后的二进制表达式再转为字符串
* $binary:二进制表达式字串
*/
private function encode_bin($binary)
{
$len=strlen($binary);
//二进制转字符需要整8位,不足8位补0
$blen=$len+8-$len%8;
$binary=str_pad($binary,$blen,'0');
$encode=null;
//每8位转为一个字符
for($i=7;$i<$blen;$i+=8)
{
$frag=substr($binary,$i-7,8);
$encode.=chr(base_convert($frag,2,10));
}
return $encode;
}
/**
* 构造huffman树,使用贪婪算法选择最小的两个元素作为树的子节点
* $item1:权重最小的元素1
* $item2:权重次小的元素2
* $array:所有字符出现次数表<权重表>
* $HuffmanArray:保存生成的huffman树结构
*/
private function creat_tree($item1,$item2,&$array,&$HuffmanArray)
{
list($k,$v)=$item1;
list($k2,$v2)=$item2;
//假设当前树的左右节点为空节点
$c1=$k;
$c2=$k2;
//判断两个元素若为树则直接作为节点并入主树
if(isset($HuffmanArray[$k2]))
{
$c2=$HuffmanArray[$k2];
unset($HuffmanArray[$k2]);
}
if(isset($HuffmanArray[$k]))
{
$c1=$HuffmanArray[$k];
unset($HuffmanArray[$k]);
}
//设置树结点权值
$array[$k2]=$v+$v2;
//合并节点后删除元素
unset($array[$k]);
//合并到huffman树中
$HuffmanArray[$k2]=array(0=>$c1,1=>$c2);
}
/**
* 广度优先遍历树,得到所有原字符对应的二进制表达式<01010...>
* $tree:已经构建好的huffman树
* $tab:编码表,保存所有字符对应的编码
* $a0:左遍历树的路径<11010...>
* $a1:右遍历树的路径
*/
private function creat_tab($tree,&$tab,$a0=null,$a1=null)
{
if($tree==null) return;
//遍历左右子树
foreach($tree as $node=>$ctree)
{
if(is_array($ctree))
{
//判断未到达叶子节点时再向下遍历
$this->creat_tab($ctree,$tab,$a0.$node,$a1.$node);
}
else
{
//遍历到叶子节点<原字符ascii码>时的所有路径,既二进制表达式,下同
$tab[$ctree]=${'a'.$node}.$node;
}
}
}
/**
* 使用进制表达式深度优先遍历树,0为左子树,1为右子树,而到根节点,即为二进制表达式所指向的原字符
* $binary:二进制表达式字串
* $huffman:huffman树
* $tree:当前所遍历的子树
* $i:指向二进制表达式字串的<指针>
* $code:解码后的字符串
*/
private function decode_tree($binary,$huffman,$tree,$i=0,$code=null)
{
$lr=$binary{$i};
//遍历完成
if($lr==null) return $code;
//判断是否到根节点,根节点既为二进制表达式对应的原字符ascii码
if(is_array($tree[$lr]))
{
//继续向下遍历子树
return $this->decode_tree($binary,$huffman,$tree[$lr],$i+1,$code);
}
else
{
//将二进制表达式解码为原字符
$code.=chr($tree[$lr]);
return $this->decode_tree($binary,$huffman,$huffman,$i+1,$code);
}
}
}
?> $str='
In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".
';
$huffman=new huffman();
$obj=$huffman->encode($str);
echo '压缩前的编码长度:',strlen($str),"\n";
echo '压缩后的编码:',"\n";
var_dump($obj['code']);
echo '解压后的字符:',$huffman->decode($obj['tree'],$obj['code'],$obj['len']);压缩前的编码长度:587压缩后的编码:string(330) "sp閉h颚?6鵞+王d挓吷s霒zk洚磗脎|t?*?;娳9蹴??>楏4O3 5 F凣rRuＪ解压后的字符:In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".
