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

摘要：在计算机信息处理中，哈夫曼编码是一种一致性编码法又称熵编码法，用于数据的无损耗压缩。构造树时间复杂度选择两个使用频率较小字符在字符串中出现的次数的结点合并生成出一个树循环创建哈夫曼树数组函数删除数组中的第一个元素，并返回被删除元素的值。

小草主要博客：http://homeway.me/

演示网址：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

    的结点合并生成出一个树
        */
        //循环创建哈夫曼树数组
        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);
    }
    /**
    * 解压缩入口
    * $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);
    }

    /**
    * 将压缩后的二进制表达式再转为字符串
    * $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;
    }

    /**
     * 构造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);
    }


    /**
    * 广度优先遍历树,得到所有原字符对应的二进制表达式<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);
        }
    }
    }
    ?>

下面是huffman.js本地缓存源码

$( 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 = $("#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 +=""+get_Storage(i)+"

";
        }
        //如果有内容就显示，否则，提示用户添加
        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();
        });
    });
}

/*构建原型*/
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






夏日小草           
               
                                           
                       
                 
            
                     

                 

                                                                                                                    
                         GPU云服务器
                                             
                         云服务器
                                                                                                                                                 
                                      
                     
                    
                                                                                               哈夫曼编码
                                                                                                           霍夫曼树编码c语言
                                                                                                           n元霍夫曼编码c语言
                                                                                                           php连数据库编码
                                                         
                 
               
              
             
               

                   
 文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
                 
                   
转载请注明本文地址：https://www.ucloud.cn/yun/20654.html
               
                      
               

                 
                                  
上一篇：PHP编码规范的十则建议
  
                                                
                                       
下一篇：总有一些不经意的时光，需要被镌刻.