首页 手机软件 手机游戏 单机游戏 资讯文章 专题下载 游戏合集 文章合集 php下载 php教程 电脑软件
+ -
当前位置：首页 → 问答吧 → 基于静态huffman编码的压缩-PHP语言实现

基于静态huffman编码的压缩-PHP语言实现

时间：2010-07-29

来源：互联网



名词解释:哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。该方法依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。

实现过程:


1.计算每个字符在字符串中出现的频率作为构建huffman树的权重

2.构建huffman树

3.建立每个字符对应的编码表

4.重建字符串编码,既压缩字符串


5.解压时根据先前的huffman树和字符位长度还原字符串


  1. <?php   
  2. /**
  3. 基于静态huffman编码的压缩[PHP语言实现]
  4. author:        lajabs
  5. email:        aGl0dHlvQGdtYWlsLmNvbQ==

  7. 本文以PHP作为描述语言较详细讲解huffman树原理及应用
  8. 因保证程序可读性,故不做优化.

  10. */



  14. class huffman
  15. {
  16.         /**
  17.          * 压缩入口
  18.          * $str:待压缩的字符串
  19.          */
  20.         public function encode($str)
  21.         {
  22.                 $len=strlen($str);
  23.                 //计算每个字符权重值(出现的频度)<这边可以做成概率表>
  24.                 for($i=0;$i<$len;$i++)        $array[ord($str{$i})]++;

  26.                 $HuffmanArray=array();
  27.                 asort($array);
  28.                 /**
  29.                  * 构造huffman树,时间复杂度O(nlogn)
  30.                  * 选择两个使用频率较小<字符在字符串中出现的次数>的结点合并生成出一个树
  31.                  */
  32.                 while ($item1 = each($array))
  33.                 {
  34.                         $item2 = each($array);
  35.                         //构建huffman树
  36.                         $this->creat_tree($item1,$item2,$array,$HuffmanArray);
  37.                         //反复排序<优化这步可在构造树时用插入排序算法完成>
  38.                         asort($array);
  39.                 }


  42.                 $HuffmanArray=array_shift($HuffmanArray);
  43.                 //构建编码表<这步可优化为构建树时一同生成>
  44.                 $tab=null;
  45.                 $code_tab=$this->creat_tab($HuffmanArray,$tab);
  46.                 //压缩&转换整个字符串为二进制表达式
  47.                 $binary=null;
  48.                 for($i=0;$i<$len;$i++)        $binary.=$tab[ord($str{$i})];        
  49.                 //转化为压缩后的字符串
  50.                 $code=$this->encode_bin($binary);
  51.                 //静态huffman编码算法压缩后需保留huffman树
  52.                 return array('tree'=>$HuffmanArray,'len'=>strlen($binary),'code'=>$code);
  53.         }

  55.         /**
  56.          * 解压缩入口
  57.          * $huffman:解压所使用的huffman树
  58.          * $str:被压缩的字符
  59.          * $blen:压缩前的位长度
  60.          */
  61.         public function decode($huffman,$str,$blen)
  62.         {
  63.                 $len=strlen($str);
  64.                 $binary=null;
  65.                 //将编码解为二进制表达式
  66.                 for($i=0;$i<$len;$i++)        
  67.                 $binary.=str_pad(base_convert(ord($str{$i}),10,2),8,'0',STR_PAD_LEFT);
  68.                 //去除补码
  69.                 $binary=substr($binary,0,$blen);
  70.                 //从hufman树中配比相应的编码
  71.                 return $this->decode_tree($binary,$huffman,$huffman);
  72.         }

  74.         /**
  75.          * 将压缩后的二进制表达式再转为字符串
  76.          * $binary:二进制表达式字串
  77.          */
  78.         private function encode_bin($binary)
  79.         {
  80.                 $len=strlen($binary);
  81.                 //二进制转字符需要整8位,不足8位补0
  82.                 $blen=$len+8-$len%8;
  83.                 $binary=str_pad($binary,$blen,'0');
  84.                 $encode=null;
  85.                 //每8位转为一个字符
  86.                 for($i=7;$i<$blen;$i+=8)
  87.                 {
  88.                         $frag=substr($binary,$i-7,8);
  89.                         $encode.=chr(base_convert($frag,2,10));
  90.                 }
  91.                 return $encode;
  92.         }

  94.         /**
  95.          * 构造huffman树,使用贪婪算法选择最小的两个元素作为树的子节点
  96.          * $item1:权重最小的元素1
  97.          * $item2:权重次小的元素2
  98.          * $array:所有字符出现次数表<权重表>
  99.          * $HuffmanArray:保存生成的huffman树结构
  100.          */
  101.         private function creat_tree($item1,$item2,&$array,&$HuffmanArray)
  102.         {
  103.                 list($k,$v)=$item1;
  104.                 list($k2,$v2)=$item2;
  105.                 //假设当前树的左右节点为空节点
  106.                 $c1=$k;
  107.                 $c2=$k2;
  108.                 //判断两个元素若为树则直接作为节点并入主树
  109.                 if(isset($HuffmanArray[$k2]))
  110.                 {
  111.                         $c2=$HuffmanArray[$k2];        
  112.                         unset($HuffmanArray[$k2]);
  113.                 }
  114.                 if(isset($HuffmanArray[$k]))
  115.                 {
  116.                         $c1=$HuffmanArray[$k];
  117.                         unset($HuffmanArray[$k]);
  118.                 }
  119.                 //设置树结点权值
  120.                 $array[$k2]=$v+$v2;                                                        
  121.                 //合并节点后删除元素
  122.                 unset($array[$k]);
  123.                 //合并到huffman树中
  124.                 $HuffmanArray[$k2]=array(0=>$c1,1=>$c2);        
  125.         }


  128.         /**
  129.          * 广度优先遍历树,得到所有原字符对应的二进制表达式<01010...>
  130.          * $tree:已经构建好的huffman树
  131.          * $tab:编码表,保存所有字符对应的编码
  132.          * $a0:左遍历树的路径<11010...>
  133.          * $a1:右遍历树的路径
  134.          */
  135.         private function creat_tab($tree,&$tab,$a0=null,$a1=null)
  136.         {
  137.                 if($tree==null) return;
  138.                 //遍历左右子树
  139.                 foreach($tree as $node=>$ctree)
  140.                 {
  141.                         if(is_array($ctree))
  142.                         {
  143.                                 //判断未到达叶子节点时再向下遍历
  144.                                 $this->creat_tab($ctree,$tab,$a0.$node,$a1.$node);
  145.                         }
  146.                         else
  147.                         {
  148.                                 //遍历到叶子节点<原字符ascii码>时的所有路径,既二进制表达式,下同
  149.                                 $tab[$ctree]=${'a'.$node}.$node;
  150.                         }
  151.                 }
  152.         }

  154.         /**
  155.          * 使用进制表达式深度优先遍历树,0为左子树,1为右子树,而到根节点,即为二进制表达式所指向的原字符
  156.          * $binary:二进制表达式字串
  157.          * $huffman:huffman树
  158.          * $tree:当前所遍历的子树
  159.          * $i:指向二进制表达式字串的<指针>
  160.          * $code:解码后的字符串
  161.          */
  162.         private function decode_tree($binary,$huffman,$tree,$i=0,$code=null)
  163.         {
  164.                 $lr=$binary{$i};
  165.                 //遍历完成
  166.                 if($lr==null) return $code;
  167.                 //判断是否到根节点,根节点既为二进制表达式对应的原字符ascii码
  168.                 if(is_array($tree[$lr]))
  169.                 {
  170.                         //继续向下遍历子树
  171.                         return $this->decode_tree($binary,$huffman,$tree[$lr],$i+1,$code);
  172.                 }
  173.                 else
  174.                 {
  175.                         //将二进制表达式解码为原字符
  176.                         $code.=chr($tree[$lr]);
  177.                         return $this->decode_tree($binary,$huffman,$huffman,$i+1,$code);
  178.                 }
  179.         }
  180. }
  181. ?>
复制代码
测试代码:
  1. $str='
  2. 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".
  3. ';

  5. $huffman=new huffman();
  6. $obj=$huffman->encode($str);
  7. echo '压缩前的编码长度:',strlen($str),"\n";
  8. echo '压缩后的编码:',"\n";
  9. var_dump($obj['code']);
  10. 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".

作者: bs   发布时间: 2010-07-29

牛，学习了，感谢分享！

作者: 7758658   发布时间: 2010-07-29

膜拜..

但是php写算法效率真不行..

作者: TankMe   发布时间: 2010-07-29

似乎有点问题，用楼主的测试代码测试了出现：
Fatal error: Maximum function nesting level of '100' reached, aborting! in D:\wamp\www\test\7-29.php on line 168

递归层数超了100，函数栈爆了

作者: 7758658   发布时间: 2010-07-29

相关阅读 更多

热门阅读

热门下载

更多
关于本站 免责申明 联系我们

Copyright 2006-2020 php爱好者(phpfans.net) All Rights Reserved.备案号：湘ICP备2023016114号-2

本站为非盈利性网站，不接受任何广告。本站所有资源均由网友上传，如有侵权，请发邮件至 [email protected] phpfans.net