數(shù)據(jù)結(jié)構(gòu)：哈夫曼編碼（php版）

luodongseu 發(fā)布于2019-06-27 10:32 / 2441人閱讀

摘要：在計(jì)算機(jī)信息處理中，哈夫曼編碼是一種一致性編碼法又稱(chēng)熵編碼法，用于數(shù)據(jù)的無(wú)損耗壓縮。構(gòu)造樹(shù)時(shí)間復(fù)雜度選擇兩個(gè)使用頻率較小字符在字符串中出現(xiàn)的次數(shù)的結(jié)點(diǎn)合并生成出一個(gè)樹(shù)循環(huán)創(chuàng)建哈夫曼樹(shù)數(shù)組函數(shù)刪除數(shù)組中的第一個(gè)元素，并返回被刪除元素的值。

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

演示網(wǎng)址：http://huffman.sinaapp.com/

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

概述下：

????哈夫曼樹(shù)─即最優(yōu)二叉樹(shù)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱(chēng)“熵編碼法”），用于數(shù)據(jù)的無(wú)損耗壓縮。
????簡(jiǎn)單的，就是靠權(quán)值排序，然后，轉(zhuǎn)碼，最優(yōu)保存。

實(shí)現(xiàn)功能：

保存譯碼：在服務(wù)器端保存源字符串，命名為：”Encording.txt”

保存編碼：在服務(wù)器端保存壓縮后壓縮碼，命名為：”Decording.txt”

保存哈夫曼樹(shù)：在服務(wù)器端保存哈夫曼樹(shù)數(shù)組，命名為：”Huffman.txt”

瀏覽器本地保存：在本地緩存輸入歷史。并且實(shí)現(xiàn)自行選擇本地版本。

開(kāi)始實(shí)現(xiàn)

一、先看整個(gè)程序流程圖

二、接下來(lái)是哈夫曼流程圖

三、程序包含文件

前臺(tái)表單提交頁(yè)面，后臺(tái)表單處理頁(yè)面，以及哈夫曼壓縮，解壓縮系統(tǒng)。包含兩個(gè)主文件：huffman.php和index.php（另外還包含style.css控制樣式，huffman.js保存緩存和控制交互。)
　　
|--index.php(處理基本表單，數(shù)據(jù)保存)
|--huffman.php(壓縮，解壓縮)
|--style.css(控制樣式)
|--huffman.js(保存緩存和控制交互)

源碼：

huffman.php


    的結(jié)點(diǎn)合并生成出一個(gè)樹(shù)
        */
        //循環(huán)創(chuàng)建哈夫曼樹(shù)數(shù)組
        while ($item1 = each($array))
        {       
            $item2 = each($array);
            $this->creat_tree($item1,$item2,$array,$HuffmanArray);
            asort($array);
        }
        //array_shift() 函數(shù)刪除數(shù)組中的第一個(gè)元素，并返回被刪除元素的值。
        $HuffmanArray=array_shift($HuffmanArray);
        $tab=null;
        $code_tab=$this->creat_tab($HuffmanArray,$tab);
        //壓縮&轉(zhuǎn)換整個(gè)字符串為二進(jìn)制表達(dá)式
        $binary=null;
        for($i=0; $i<$len; $i++)  $binary.=$tab[ord($str{$i})];        
        //轉(zhuǎn)化為壓縮后的字符串
        $code=$this->encode_bin($binary);
        //靜態(tài)huffman編碼算法壓縮后需保留huffman樹(shù)
        return array("tree"=>$HuffmanArray,"len"=>strlen($binary),"code"=>$code);
    }
    /**
    * 解壓縮入口
    * $huffman:解壓所使用的huffman樹(shù)
    * $str:被壓縮的字符
    * $blen:壓縮前的位長(zhǎng)度
    */
    public function decode($huffman,$str,$blen)
    {
        $len=strlen($str);
        $binary=null;
        //將編碼解為二進(jìn)制表達(dá)式
        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);
    }

    /**
    * 將壓縮后的二進(jìn)制表達(dá)式再轉(zhuǎn)為字符串
    * $binary:二進(jìn)制表達(dá)式字串
    */
    private function encode_bin($binary)
    {
        $len=strlen($binary);
        //二進(jìn)制轉(zhuǎn)字符需要整8位,不足8位補(bǔ)0
        $blen=$len+8-$len%8;
        $binary=str_pad($binary,$blen,"0");
        $encode=null;
        //每8位轉(zhuǎn)為一個(gè)字符
        for($i=7;$i<$blen;$i+=8)
        {
            $frag=substr($binary,$i-7,8);
            //base_convert() 函數(shù)在任意進(jìn)制之間轉(zhuǎn)換數(shù)字
            $encode.=chr(base_convert($frag,2,10));
        }
        return $encode;
    }

    /**
     * 構(gòu)造huffman樹(shù),使用貪婪算法選擇最小的兩個(gè)元素作為樹(shù)的子節(jié)點(diǎn)
     * $item1:權(quán)重最小的元素1
     * $item2:權(quán)重次小的元素2
     * $array:所有字符出現(xiàn)次數(shù)表<權(quán)重表>
     *$HuffmanArray:保存生成的huffman樹(shù)結(jié)構(gòu)
    */
    private function creat_tree($item1,$item2,&$array,&$HuffmanArray)
    {      
        list($key,$weight)=$item1;
        list($key2,$weight2)=$item2;
        //假設(shè)當(dāng)前樹(shù)的左右節(jié)點(diǎn)為空節(jié)點(diǎn)
        $c1=$key;
        $c2=$key2;
        //判斷兩個(gè)元素若為樹(shù)則直接作為節(jié)點(diǎn)并入主樹(shù)
        if(isset($HuffmanArray[$key2]))
        {
            $c2=$HuffmanArray[$key2];        
            unset($HuffmanArray[$key2]);
        }
        if(isset($HuffmanArray[$key]))
        {
            $c1=$HuffmanArray[$key];
            unset($HuffmanArray[$key]);
        }
        //設(shè)置樹(shù)結(jié)點(diǎn)權(quán)值
        $array[$key2]=$weight+$weight2;                                                        
        //合并節(jié)點(diǎn)后刪除元素
        unset($array[$key]);
        //合并到huffman樹(shù)中
        $HuffmanArray[$key2]=array(0=>$c1,1=>$c2);
    }


    /**
    * 廣度優(yōu)先遍歷樹(shù),得到所有原字符對(duì)應(yīng)的二進(jìn)制表達(dá)式<01010...>
    * $tree:已經(jīng)構(gòu)建好的huffman樹(shù)
    * $tab:編碼表,保存所有字符對(duì)應(yīng)的編碼
    * $a0:左遍歷樹(shù)的路徑<11010...>
    * $a1:右遍歷樹(shù)的路徑
    */
    private function creat_tab($tree,&$tab,$a0=null,$a1=null)
    {       

        if($tree==null) return;
        //遍歷左右子樹(shù)

        foreach($tree as $node=>$ctree)
        {     
            if(is_array($ctree))
            {
                //判斷未到達(dá)葉子節(jié)點(diǎn)時(shí)再向下遍歷
                $this->creat_tab($ctree,$tab,$a0.$node,$a1.$node);
            }else{
                //遍歷到葉子節(jié)點(diǎn)<原字符ascii碼>時(shí)的所有路徑,既二進(jìn)制表達(dá)式,下同
                $tab[$ctree]=${"a".$node}.$node;
            }
        }
    }

    /**
    * 使用進(jìn)制表達(dá)式深度優(yōu)先遍歷樹(shù),0為左子樹(shù),1為右子樹(shù),而到根節(jié)點(diǎn),即為二進(jìn)制表達(dá)式所指向的原字符
    * $binary:二進(jìn)制表達(dá)式字串
    * $huffman:huffman樹(shù)
    * $tree:當(dāng)前所遍歷的子樹(shù)
    * $i:指向二進(jìn)制表達(dá)式字串的<指針>
    * $code:解碼后的字符串
    */
    private function decode_tree($binary,$huffman,$tree,$i=0,$code=null)
    {       
        $lr=$binary{$i};
        //遍歷完成
        if($lr==null) return $code;
        //判斷是否到根節(jié)點(diǎn),根節(jié)點(diǎn)既為二進(jìn)制表達(dá)式對(duì)應(yīng)的原字符ascii碼
        if(is_array($tree[$lr]))
        {
            //繼續(xù)向下遍歷子樹(shù)
            return $this->decode_tree($binary,$huffman,$tree[$lr],$i+1,$code);
        }else{
            //將二進(jìn)制表達(dá)式解碼為原字符
            $code.=chr($tree[$lr]);
            return $this->decode_tree($binary,$huffman,$huffman,$i+1,$code);
        }
    }
    }
    ?>

下面是huffman.js本地緩存源碼

$( document ).ready(function(){

/*函數(shù)寫(xiě)的比較亂，慢慢改進(jìn)*/

//flag是用來(lái)判斷，是否需要添加緩存計(jì)數(shù)
var flag=true;

function get_Storage(key){
    return window.localStorage.getItem(key);
}

function set_Storage(key, value){
    return window.localStorage.setItem(key, value);
}

/*初始化函數(shù)*/
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 +="

";
        }
        //如果有內(nèi)容就顯示，否則，提示用戶(hù)添加
        if(len){
            $("#modal-body").html(text);
        }
        //選擇本地緩存設(shè)置
        $(".item").click(function (event){
            var id = $(this).attr("data");
            $("#node").val(get_Storage(id));
            //設(shè)置flag標(biāo)志
            flag=false;
            $("#close").click();
            $("#submited").click();
        });
    });
}

/*構(gòu)建原型*/
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






夏日小草           
               
                                           
                       
                 
            
                     
                 
                                                                                                                    
                         云服務(wù)器
                                             
                         GPU云服務(wù)器
                                                                                                                                                 
                                      
                     
                    
                                                                                               哈夫曼編碼
                                                                                                           霍夫曼樹(shù)編碼c語(yǔ)言
                                                                                                           n元霍夫曼編碼c語(yǔ)言
                                                                                                           php連數(shù)據(jù)庫(kù)編碼
                                                         
                 
               
              
             
               
                    文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
                 
                   轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/20654.html
               
                      
               
                 
                                  上一篇：PHP編碼規(guī)范的十則建議  
                                                
                                       下一篇：總有一些不經(jīng)意的時(shí)光，需要被鐫刻.

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

luodongseu

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

Sharktech：美國(guó)服務(wù)器，洛杉磯雙E5-2678v3/64GB/1TB NVME/60Gbps

閱讀 1165·2021-10-15 09:39
【軟件測(cè)試】上線前的bug，這些bug先留著，之后再改吧

閱讀 3069·2021-09-10 10:50
vue+webpack構(gòu)建項(xiàng)目過(guò)程

閱讀 3461·2019-08-30 15:53
【新年快樂(lè)】繽紛多彩的Vue點(diǎn)贊組件

閱讀 1889·2019-08-30 15:52
一個(gè)未知寬高的元素在div中垂直水平居中

閱讀 2574·2019-08-29 15:31
前端培訓(xùn)-初級(jí)階段（13） - 類(lèi)、模塊、繼承

閱讀 1984·2019-08-26 13:43
使用 Nuxt.js 快速搭建服務(wù)端渲染(SSR) 應(yīng)用

閱讀 2605·2019-08-26 13:37
JS基礎(chǔ)——Proxy

閱讀 1448·2019-08-23 18:31

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

數(shù)據(jù)結(jié)構(gòu)：哈夫曼編碼（php版）

一、先看整個(gè)程序流程圖

二、接下來(lái)是哈夫曼流程圖

三、程序包含文件

源碼：

相關(guān)文章

PHP實(shí)現(xiàn)markdown文檔管理工具

**怎么利用Python和C語(yǔ)言實(shí)現(xiàn)哈夫曼編碼（霍夫曼編碼）**

發(fā)表評(píng)論

0條評(píng)論

luodongseu

男|高級(jí)講師

TA的文章

Sharktech：美國(guó)服務(wù)器，洛杉磯雙E5-2678v3/64GB/1TB NVME/60Gbps

【軟件測(cè)試】上線前的bug，這些bug先留著，之后再改吧

vue+webpack構(gòu)建項(xiàng)目過(guò)程

【新年快樂(lè)】繽紛多彩的Vue點(diǎn)贊組件

一個(gè)未知寬高的元素在div中垂直水平居中

前端培訓(xùn)-初級(jí)階段（13） - 類(lèi)、模塊、繼承

使用 Nuxt.js 快速搭建服務(wù)端渲染(SSR) 應(yīng)用

JS基礎(chǔ)——Proxy

最新活動(dòng)

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

數(shù)據(jù)結(jié)構(gòu)：哈夫曼編碼（php版）

一、先看整個(gè)程序流程圖

二、接下來(lái)是哈夫曼流程圖

三、程序包含文件

源碼：

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

一、先看整個(gè)程序流程圖

二、接下來(lái)是哈夫曼流程圖

三、程序包含文件