首页 > 代码库 > 数据结构：哈夫曼编码（php版）

数据结构：哈夫曼编码（php版）

2024-08-05 03:47:14   225人阅读

演示网址：http://huffman.sinaapp.com/

源文件下载地址：http://xiaocao.u.qiniudn.com/work/huffman-2013-12-19.zip



概述下：

    哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。     简单的，就是靠权值排序，然后，转码，最优保存。

实现功能：

  • 保存译码：在服务器端保存源字符串，命名为：”Encording.txt”

  • 保存编码：在服务器端保存压缩后压缩码，命名为：”Decording.txt”

  • 保存哈夫曼树：在服务器端保存哈夫曼树数组，命名为：”Huffman.txt”

  • 浏览器本地保存：在本地缓存输入历史。并且实现自行选择本地版本。

开始实现

一、先看整个程序流程图

二、接下来是哈夫曼流程图

三、程序包含文件

前台表单提交页面，后台表单处理页面，以及哈夫曼压缩，解压缩系统。包含两个主文件：huffman.php和index.php（另外还包含style.css控制样式，huffman.js保存缓存和控制交互。) 　　
|--index.php(处理基本表单，数据保存) |--huffman.php(压缩，解压缩) |--style.css(控制样式) |--huffman.js(保存缓存和控制交互)

源码：

huffman.php 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<?php
/*  先介绍几个php内置函数：
     asort()函数对数组进行排序并保持索引关系。主要用于对那些单元顺序很重要的结合数组进行排序。
     array_shift() 函数删除数组中的第一个元素，并返回被删除元素的值。
     str_pad(string, long, 补充元素, 类型) 函数把字符串填充为指定的长度
     base_convert() 函数在任意进制之间转换数
     substr(string, start, end) 方法可在字符串中抽取从 start 下标开始的指定数目的字符。
*/
 
/*=========================================================*/
/*=========================================================*/
/*=========================================================*/
 
/*
基于静态huffman编码的压缩,要保存的文件有huffmantree（数组）, binary（字符串）
本文以PHP作为描述语言较详细讲解huffman树原理及应用
*/
?>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
<?php
class huffman
{
     /*
      * 压缩入口
      * $str:待压缩的字符串
      */
     public function encode( $str )
     {      
         $len = strlen ( $str );
         //计算每个字符权重值(出现的频度)
         //ord()，是php内置ASCII转化函数，将字符转化成ASCII码
         for ( $i =0; $i < $len ; $i ++) $array [ord( $str { $i })]=0; //初始化数组
         for ( $i =0; $i < $len ; $i ++)
             $array [ord( $str { $i })]++;
         $HuffmanArray = array ();
         //asort()函数对数组进行排序并保持索引关系。主要用于对那些单元顺序很重要的结合数组进行排序。
         asort( $array );
         /**
         * 构造huffman树,时间复杂度O(nlogn)
         * 选择两个使用频率较小<字符在字符串中出现的次数>的结点合并生成出一个树
         */
         //循环创建哈夫曼树数组
         while ( $item1 = each( $array ))
         {      
             $item2 = each( $array );
             $this ->creat_tree( $item1 , $item2 , $array , $HuffmanArray );
             asort( $array );
         }
         //array_shift() 函数删除数组中的第一个元素，并返回被删除元素的值。
         $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 );
     }


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 解压缩入口
* $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 );
     return $this ->decode_tree( $binary , $huffman , $huffman );
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 将压缩后的二进制表达式再转为字符串
* $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);
         //base_convert() 函数在任意进制之间转换数字
         $encode .= chr ( base_convert ( $frag ,2,10));
     }
     return $encode ;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
  * 构造huffman树,使用贪婪算法选择最小的两个元素作为树的子节点
  * $item1:权重最小的元素1
  * $item2:权重次小的元素2
  * $array:所有字符出现次数表<权重表>
  *$HuffmanArray:保存生成的huffman树结构
*/
private function creat_tree( $item1 , $item2 ,& $array ,& $HuffmanArray )
{     
     list( $key , $weight )= $item1 ;
     list( $key2 , $weight2 )= $item2 ;
     //假设当前树的左右节点为空节点
     $c1 = $key ;
     $c2 = $key2 ;
     //判断两个元素若为树则直接作为节点并入主树
     if (isset( $HuffmanArray [ $key2 ]))
     {
         $c2 = $HuffmanArray [ $key2 ];       
         unset( $HuffmanArray [ $key2 ]);
     }
     if (isset( $HuffmanArray [ $key ]))
     {
         $c1 = $HuffmanArray [ $key ];
         unset( $HuffmanArray [ $key ]);
     }
     //设置树结点权值
     $array [ $key2 ]= $weight + $weight2 ;                                                       
     //合并节点后删除元素
     unset( $array [ $key ]);
     //合并到huffman树中
     $HuffmanArray [ $key2 ]= array (0=> $c1 ,1=> $c2 );
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* 广度优先遍历树,得到所有原字符对应的二进制表达式<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 ;
         }
     }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
     /**
     * 使用进制表达式深度优先遍历树,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 );
         }
     }
}
?>


下面是js缓存源码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
$( document ).ready( function (){
 
/*函数写的比较乱，慢慢改进*/
 
//flag是用来判断，是否需要添加缓存计数
var flag= true ;
 
function get_Storage(key){
     return window.localStorage.getItem(key);
}
 
function set_Storage(key, value){
     return window.localStorage.setItem(key, value);
}
 
/*初始化函数*/
function init(){
     var node = new huffman();
     $( "#submited" ).click( function (event){
         var value = http://www.mamicode.com/$( "#node" ).val();
         if (value!= ‘‘ ){
             node.set($( "#node" ).val());
         }
     });
     //显示选取的文件，添加到div中
     $( ‘#local‘ ).click( function (event){
         var len= get_Storage( "length" );
         var text= "" ;
         for ( var i = 1; i <= len; i++){
             text += ‘<button type="button" class="item btn btn-primary" data=http://www.mamicode.com/‘ +i+ ‘>‘ +get_Storage(i)+ ‘</button><br><br>‘ ;
         }
         //如果有内容就显示，否则，提示用户添加
         if (len){
             $( ‘#modal-body‘ ).html(text);
         }
         //选择本地缓存设置
         $( ‘.item‘ ).click( function (event){
             var id = $( this ).attr( "data" );
             $( "#node" ).val(get_Storage(id));
             //设置flag标志
             flag= false ;
             $( "#close" ).click();
             $( "#submited" ).click();
         });
     });
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*构建原型*/
function huffman(){}
huffman.prototype={
     set: function (value){
         if (flag){
             if (get_Storage( "length" )){
                 var num = parseInt( get_Storage( "length" ))+1;
                 set_Storage( "length" , num);
             } else {
                 set_Storage( "length" ,1);
             }
             set_Storage(get_Storage( "length" ),value);
         }
     },
     get: function (){
         var i = get_Storage( "length" );
         var array = new Array();
         for (p=0; p<i; p++){
             var item=get_Storage(p);
             array.push(item);
         }
         this .show(array);
     },
     show: function (array){
         //这里要显示对话框
     }
}   
 
window.onload=init();
});


数据结构：哈夫曼编码（php版）


联系
我们