bl双性强迫侵犯h_国产在线观看人成激情视频_蜜芽188_被诱拐的少孩全彩啪啪漫画

Huffman編碼-創新互聯

目錄
  • 背景
  • Huffman編碼
  • 代碼部分

成都創新互聯是一家業務范圍包括IDC托管業務,網頁空間、主機租用、主機托管，四川、重慶、廣東電信服務器租用,服務器機柜租賃，成都網通服務器托管,成都服務器租用,業務范圍遍及中國大陸、港澳臺以及歐美等多個國家及地區的互聯網數據服務公司。
背景

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

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

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

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


Huffman編碼

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

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

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

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

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

??我們繼續上面的例子，將A,B,C,D按照上面的方法編碼并創建一個對照表。

ABCD
11011100

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

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

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

  • Huffman樹是一個二叉樹
  • 所有字符節點都是葉子節點
  • 每次都用2個最少使用頻率節點來構建新節點；

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


??最開始有 A,B,C,D四個節點，經過排序之后由較小的2個節點生成新的節點。因此選擇C,D來生成新節點：8；生成新節點之后C,D節點不再參與后續的過程。

??參與第二次構建Huffman樹的新節點：8，B(7)，A(14),這3個節點再比較使用次數： 7< 8< 14 ；因此使用 B（7），8節點來構建新節點：15；

??第三次參與構建新節點的的節點： 15，A（14）；直接用這2個節點生成root節點；Huffman樹構建結束。

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


??A,B,C,D構建的Huffman樹形成了新的編碼:

ABCD
101001000

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

??回到關鍵問題，如何解壓呢？

??也很簡單，在解壓時只需要對照Huffman樹來解壓就行。從root節點往下找，找到葉子節點就找到了對應的字符。用這種方式順序讀取二進制碼對照Huffman樹就可以解析文本了。

代碼部分
  • Huffman樹的構建：
//Huffman樹節點
    class HMNode{int val;
        HMNode left;
        HMNode right;
        boolean leaf;//是否葉子節點
        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);
        }
    }


//統計文本各個字符使用頻率
    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;
    }

//構建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=================================================
//結果:char=_	===>表示新生成的節點
												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樹轉化成編碼
//左分支 + 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

后續：Huffman 二進制碼以及文本壓縮與解壓

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站標題：Huffman編碼-創新互聯
文章位置：http://vcdvsql.cn/article10/giego.html

成都網站建設公司_創新互聯，為您提供網站收錄、移動網站建設、營銷型網站建設、App設計、網站內鏈、網站設計公司

廣告

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

微信小程序開發