Huffman編碼-創(chuàng)新互聯(lián)

背景
Huffman編碼
代碼部分

成都創(chuàng)新互聯(lián)是一家業(yè)務(wù)范圍包括IDC托管業(yè)務(wù),網(wǎng)頁空間、主機(jī)租用、主機(jī)托管，四川、重慶、廣東電信服務(wù)器租用,服務(wù)器機(jī)柜租賃，成都網(wǎng)通服務(wù)器托管,成都服務(wù)器租用,業(yè)務(wù)范圍遍及中國大陸、港澳臺以及歐美等多個(gè)國家及地區(qū)的互聯(lián)網(wǎng)數(shù)據(jù)服務(wù)公司。
背景

??英文字母大小寫總共就52個(gè)，一本英文書籍幾十上百萬的英文單詞都是由這52個(gè)字符排列組合而成，不難看出這52個(gè)字符肯定是大量重復(fù)了。

??一本中文小說幾百萬字，也都是由常用的幾千個(gè)漢字組合而成。如果是一本玄幻小說，那么在相近的章節(jié)中一定大量的重復(fù)出現(xiàn)人名，地名，功法境界，以及主角在一段時(shí)間內(nèi)修煉的功法。至于主角名字更是貫穿整本小說一定大量重復(fù)。還有作者的寫作風(fēng)格是保持一致的，因此文章有時(shí)候在描寫一些緊張氛圍或者描寫反面人物可能會使用相似的句式和詞語來表達(dá)，這些可能會造成很高的重復(fù)率。

??圖片是由像素點(diǎn)組成的而每個(gè)像素點(diǎn)是由rgb：三元素組成。這些都是由0~255的數(shù)字表示，因此可以將圖片看作一堆數(shù)字。一張小的圖片的像素點(diǎn)至少也有幾千，如果是高清圖片估計(jì)有上百萬個(gè)像素點(diǎn)。每一個(gè)像素點(diǎn)都是三個(gè)0~255的數(shù)字，組成圖片的像素點(diǎn)一定存在大量的重復(fù)數(shù)字；一些圖片有很大范圍的背景色這種情況下，數(shù)字更是會發(fā)生大量的重復(fù)。

??不管是中文，英文還是圖片的像素點(diǎn)，如果數(shù)據(jù)量很大那么肯定存在大量重復(fù)字符。一個(gè)英文字符是8bit，一個(gè)中文字符使用UTF-8編碼會占3個(gè)字節(jié)24bit；如果要壓縮數(shù)據(jù)，從字符編碼角度考慮應(yīng)該怎么去壓縮呢？可以思考三秒(PS:就這幾段句子已經(jīng)重復(fù)出現(xiàn)重復(fù)了很多次了)

Huffman編碼

??現(xiàn)在有一段英文文本AAAAAAAAABBCCCDDCCCBBBAAAAABB,這段文本A出現(xiàn)14次，B出現(xiàn)7次，C出現(xiàn)6次，D出現(xiàn)2次。正常編碼，這個(gè)文本所占bit：（14+7+6+2）* 8 = 232bit。

A的編碼是：0100 0001
B的編碼是：0100 0010
C的編碼是：0100 0011
D的編碼是：0100 0100

??我們可以思考下，A,B,C,D這四個(gè)字符在這段文本中需要用8bit來表示嗎？是不是可以用更少的字符來表示這幾個(gè)字符？重新給這4個(gè)字符編碼：

A->1
B->10
C->11
D->100

??重新編碼之后，這段文本所占bit：14 * 1 + 2 * 7 + 2 * 6 + 2 * 3 = 46bit；重新編碼之后的文本大小只占原文本的20%左右。在這個(gè)例子中，A編碼最短，BC次之，D最長我們是按照字母順序來編碼的嗎？顯然不是的，在給字符編碼時(shí)，是按照字符使用的頻率來決定該如何編碼。如果使用次數(shù)多也就是頻率高的就盡量用短編碼，使用次數(shù)少頻率低就用長編碼。這樣才能盡可能的降低壓縮后的字符長度。Huffman編碼在對字符重新編碼時(shí)的指導(dǎo)思想就是這樣的。

??我們繼續(xù)上面的例子，將A,B,C,D按照上面的方法編碼并創(chuàng)建一個(gè)對照表。

A	B	C	D
1	10	11	100

??根據(jù)重新編碼后的字符，上面英文文本的二進(jìn)制編碼是：111111111101011111110010011110111111101010111111010，根據(jù)這段編碼我們該如何解碼，將壓縮后的二進(jìn)制碼還原成字符？

在這里插入圖片描述
??根據(jù)上面的編碼我們可以看出，在解壓時(shí)沒法恢復(fù)源文本了。最開始的9個(gè)1，可以有多種解析方式：可以4個(gè)C 一個(gè)A，這種情況下A位置變化都有5種。還可以有3C，3A的組合。。。。等等其他組合根本沒有辦法確定這9個(gè)1該如何編碼。

??那該如何編碼呢？既要按照字符使用頻率來編碼，又要在解壓時(shí)能夠復(fù)原文本。這時(shí)候Huffman樹就隆重出場了Huffman樹的構(gòu)建很簡單，但是構(gòu)建過程非常巧妙。Huffman樹的構(gòu)建規(guī)則：

Huffman樹是一個(gè)二叉樹
所有字符節(jié)點(diǎn)都是葉子節(jié)點(diǎn)
每次都用2個(gè)最少使用頻率節(jié)點(diǎn)來構(gòu)建新節(jié)點(diǎn)；

??這是我自己總結(jié)的構(gòu)造Huffman樹的規(guī)則，看不懂太正常，在我第一次接觸Huffman樹估計(jì)也是看不懂。下面會用上面的例子圖解如何構(gòu)建一顆Huffman樹。

??最開始有 A,B,C,D四個(gè)節(jié)點(diǎn)，經(jīng)過排序之后由較小的2個(gè)節(jié)點(diǎn)生成新的節(jié)點(diǎn)。因此選擇C,D來生成新節(jié)點(diǎn)：8；生成新節(jié)點(diǎn)之后C,D節(jié)點(diǎn)不再參與后續(xù)的過程。

??參與第二次構(gòu)建Huffman樹的新節(jié)點(diǎn)：8，B(7)，A(14),這3個(gè)節(jié)點(diǎn)再比較使用次數(shù)： 7< 8< 14 ；因此使用 B（7），8節(jié)點(diǎn)來構(gòu)建新節(jié)點(diǎn)：15；

??第三次參與構(gòu)建新節(jié)點(diǎn)的的節(jié)點(diǎn)： 15，A（14）；直接用這2個(gè)節(jié)點(diǎn)生成root節(jié)點(diǎn)；Huffman樹構(gòu)建結(jié)束。

??可以看出來，使用頻率最高的A，從根節(jié)點(diǎn)到A的路徑是最短的，而使用頻率最小的D，從根節(jié)點(diǎn)到D的距離是最長的。這路勁長短正好對應(yīng)了使用頻率的高低。如果一個(gè)節(jié)點(diǎn)鏈接left節(jié)點(diǎn)用 0 表示；鏈接 right 節(jié)點(diǎn)用 1表示；（反過來也可以）那么從root節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑就可以用01字符串來表示了；

??A,B,C,D構(gòu)建的Huffman樹形成了新的編碼:

A	B	C	D
1	01	001	000

??英文：AAAAAAAAABBCCCDDCCCBBBAAAAABB經(jīng)過構(gòu)建Huffman樹重新編碼之后的壓縮文本是：1111111110101001001001000000001001001010101111110101一共52字符；只有原文的52/232 = 22%左右大??；

??回到關(guān)鍵問題，如何解壓呢？

??也很簡單，在解壓時(shí)只需要對照Huffman樹來解壓就行。從root節(jié)點(diǎn)往下找，找到葉子節(jié)點(diǎn)就找到了對應(yīng)的字符。用這種方式順序讀取二進(jìn)制碼對照Huffman樹就可以解析文本了。

代碼部分

Huffman樹的構(gòu)建：

//Huffman樹節(jié)點(diǎn)
    class HMNode{int val;
        HMNode left;
        HMNode right;
        boolean leaf;//是否葉子節(jié)點(diǎn)
        char str;

        public HMNode(int val){this.val = val;
        }
        public HMNode(int val,char str){this.val = val;
            leaf = true;
            this.str = str;
        }

        @Override
        public String toString() {return "val="+val+";char="+(str=='\0' ? '_':str);
        }
    }


//統(tǒng)計(jì)文本各個(gè)字符使用頻率
    public Mapcount(String text){Mapmap = new HashMap<>();
        for (int i = 0; ichar t = text.charAt(i);
            if(map.containsKey(t)){map.compute(t,(key,val)->val+1);
            }else{map.computeIfAbsent(t,key->1);
            }
        }
        return map;
    }

//構(gòu)建Huffman樹
    public HMNode buildHuffManTree(String text){Mapmap = count(text);
        Listnodes = new ArrayList<>(map.size()<<1);
        map.forEach((key,val)->nodes.add(new HMNode(val,key)));
        nodes.sort((n1, n2)->n1.val-n2.val);
        int start = 0;
        while(nodes.size()-2>=start){HMNode root  = new HMNode(nodes.get(start).val+nodes.get(start+1).val);
            root.left = nodes.get(start);
            root.right = nodes.get(start+1);
            nodes.add(root);
            nodes.sort((n1, n2)->n1.val-n2.val);
            start+=2;
        }
        return nodes.get(start);
    }

測試

@Test
    public void test(){String text = "aaabbbbbccccccddddee";
        HMNode root =buildHuffManTree(text);
        List nodes =  new ArrayList();
        nodes.add(root);
        print(nodes);

    }


    public void print(Listnodes){Listc = new ArrayList<>();
        System.out.println("\n");
        for (HMNode hmNode : nodes){if(hmNode.left != null)c.add(hmNode.left);
            if(hmNode.right != null)c.add(hmNode.right);
            System.out.print(hmNode+ "\t");
        }
        System.out.println("\n");
        if(!c.isEmpty())print(c);
    }
=========================================res=================================================
//結(jié)果:char=_	===>表示新生成的節(jié)點(diǎn)
												val=20;char=_	
	


						val=9;char=_									val=11;char=_	



		val=4;char=d				val=5;char=b	 		val=5;char=_	   val=6;char=c	



													val=2;char=e	val=3;char=a

將Huffman樹轉(zhuǎn)化成編碼

//左分支 + 0  ； 右分支 + 1

    public void huffmanCode(HMNode root,MaphuffmanCode,String code){if(root.leaf){huffmanCode.put(code,root.str);
            return;
        }
        if(root.left != null){huffmanCode(root.left,huffmanCode,code+"0");
        }
        if(root.right != null){huffmanCode(root.right,huffmanCode,code+"1");
        }
     }

    @Test
    public void test(){String text = "aaabbbbbccccccddddee";
        Mapcount = count(text);
        HMNode root =buildHuffManTree(text);
        Mapcode = new HashMap<>();
        huffmanCode(root,code,"");
        code.forEach((key,val)->System.out.println(val+" ->"+key));

    }

=========================================res=================================================

d ->00
c ->11
b ->01
e ->100
a ->101

后續(xù)：Huffman 二進(jìn)制碼以及文本壓縮與解壓

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站標(biāo)題：Huffman編碼-創(chuàng)新互聯(lián)
文章位置：http://bm7419.com/article10/giego.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、移動網(wǎng)站建設(shè)、營銷型網(wǎng)站建設(shè)、App設(shè)計(jì)、網(wǎng)站內(nèi)鏈、網(wǎng)站設(shè)計(jì)公司

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容