數據結構：哈夫曼編碼（php版）

luodongseu 發布于2019-06-27 10:32 / 2432人閱讀

摘要：在計算機信息處理中，哈夫曼編碼是一種一致性編碼法又稱熵編碼法，用于數據的無損耗壓縮。構造樹時間復雜度選擇兩個使用頻率較小字符在字符串中出現的次數的結點合并生成出一個樹循環創建哈夫曼樹數組函數刪除數組中的第一個元素，并返回被刪除元素的值。

小草主要博客：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 +="

";
        }
        //如果有內容就顯示，否則，提示用戶添加
        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連數據庫編碼
                                                         
                 
               
              
             
               
                    文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
                 
                   轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/20654.html
               
                      
               
                 
                                  上一篇：PHP編碼規范的十則建議  
                                                
                                       下一篇：總有一些不經意的時光，需要被鐫刻.

PHP實現markdown文檔管理工具

摘要：工作后一直在從事開發從以前的大包大攬到現在的退居服務端寫接口當中接觸過幾個的接口文檔管理工具或系統簡單描述下功能全面而且簡潔有用戶權限管理功能支持支持導出有多種文檔模板目錄支持兩級折疊功能強大權限管理郵件提醒全文搜索插件管理等重收費的一個文工作后一直在從事PHP開發, 從以前的大包大攬到現在的退居服務端寫接口, 當中接觸過幾個的接口文檔管理工具或系統, 簡單描述下: showdoc...

wpw 2019-06-28 18:22 評論0 收藏0
怎么利用Python和C語言實現哈夫曼編碼（霍夫曼編碼）

　　小編寫這篇文章的主要目的是，教給大家怎么使用哈夫曼編碼，也就是霍夫曼編碼，并把具體的一些代碼實例給大家貼了出來，希望可以為大家帶來幫助。　　一、用C語言實現哈夫曼編碼　　1、代碼解釋　　（1）建立一個互相連接的表　　我們在創建哈夫曼樹的過程之中，要對互相之間的連接點進行增刪查改，所以使用雙向鏈路表格會更加的容易。'''C #include<stdlib.h>...

89542767 2022-09-09 09:53 評論0 收藏0