《數(shù)據(jù)結(jié)構(gòu)》 (java版) 課件 9-1哈夫曼樹

最優(yōu)二叉樹樹的帶權(quán)路徑長度定義為：WPL(T)：樹T中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和ABCHIDEFG5249WPL(T)=7×2+5×2+2×3+4×3+9×2=607最優(yōu)二叉樹ABHDGCIFE74952WPL(T)=7×4+9×4+5×3+4×2+2×1=89最優(yōu)二叉樹最優(yōu)二叉樹定義為：帶權(quán)路徑長度WPL最小的二叉樹，又稱為哈夫曼樹。哈夫曼樹例如:已知權(quán)值W={5,6,2,9,7}9562769692571)2)3)2577713哈夫曼樹WPL=2×3+5×3+6×2+7×2+9×2=6562574)5)137162992571696713練習(xí):已知權(quán)值W={5,6,2,9,8}哈夫曼樹95628686521)2)3)529897713哈夫曼樹4)5)WPL=2×3+5×3+6×2+8×2+9×2=672521317771713308965689哈夫曼樹(哈夫曼算法)以二叉樹為例:1.根據(jù)給定的n個(gè)權(quán)值{w＝w1,w2,…,wn}，構(gòu)造n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn),其左、右子樹為空樹;2.在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和;3.從F中刪去這兩棵樹，同時(shí)將剛生成的新樹加入到F中;4.重復(fù)(2)和(3)兩步，直至F中只含一棵樹為止。哈夫曼樹特點(diǎn)：1、有n個(gè)葉子結(jié)點(diǎn)：過程中的第1步2、沒有度為1的結(jié)點(diǎn)：2個(gè)節(jié)點(diǎn)作為左右孩子生成1個(gè)新的節(jié)點(diǎn)3、總的結(jié)點(diǎn)數(shù)為2n-1：需要合并n-1次，每次增加1個(gè)節(jié)點(diǎn)4、深度≤n-15、形態(tài)不唯一編碼編碼：用二進(jìn)制數(shù)表示字符等例如：ASCII碼，擴(kuò)展的ASCII碼特點(diǎn)：等長編碼定長編碼假設(shè)有8個(gè)符號(hào):a0 a1 a2 a3 a4 a5 a6 a7000 001 010 011 100 101 110 111011110000100001???變長編碼有時(shí)候，每個(gè)字符出現(xiàn)的頻率不一樣，采用變長編碼，使得出現(xiàn)頻率高的編碼短，頻率低的編碼長，使得整體的編碼短。假設(shè)A0.4B0.3C0.2D0.1A B C D0 1 00 010001011???任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。利用哈夫曼樹可以構(gòu)造一種不等長的二進(jìn)制編碼，并且構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即:所傳電文的總長度最短。Prefix-freecode(前綴編碼)010100110001100101111、建立哈夫曼樹2、對(duì)邊編號(hào)3、求出葉子結(jié)點(diǎn)的路徑4、得到字符編碼A B C D E6 7 2 5 900 01 100 101 11291367167925Prefix-freecode(前綴編碼)如何譯碼？001011110001？？？ADECB01010011291367167925A B C D E6 7 2 5 900 01 100 101 11Prefix-freecode(前綴編碼)Huffman樹的實(shí)現(xiàn)

private

static

classNode{

char

data;//葉子結(jié)點(diǎn)放待編碼的符號(hào) Nodeleft; Noderight; Node(char

data,Nodeleft,Noderight){ this.data=data; this.left=left;

this.right=right; } }Huffman樹的實(shí)現(xiàn)

privateNoderoot;//根結(jié)點(diǎn)

private

float

weight;//樹中葉子結(jié)點(diǎn)的權(quán)重之和

privateMap<Character,Byte[]>coder;//存放<符號(hào),編碼>，可以考慮使用BitSet替換Byte[]

private

static

byte

LEFT=0;//左子樹

private

static

byte

RIGHT=1;//右子樹

public

intcompareTo(HuffmanTreerhd){//為了使用優(yōu)先隊(duì)列,需要比較大小，值小的獲勝

returnFpare(this.weight,rhd.weight); }合并Huffman樹

static

privateHuffmanTreemerge(HuffmanTreelhd,HuffmanTreerhd){//合并2棵哈夫曼樹 HuffmanTreeresult=newHuffmanTree();

result.root=newNode('\0',lhd.root,rhd.root);//中間結(jié)點(diǎn)，\0可以替換成任意的符號(hào)

result.weight=lhd.weight+rhd.weight;

lhd.root=rhd.root=null;

lhd.weight=rhd.weight=0;

return

result; }

privateHuffmanTree(){//空樹 }

privateHuffmanTree(char

symbol,float

weight){//只有根結(jié)點(diǎn)的樹

this.weight=weight;

root=newNode(symbol,null,null); }建立Huffman樹

static

publicHuffmanTreemakeTree(char[]symbol,float[]weights){

if(weights.length!=symbol.length||weights.length<2)

throw

newIllegalStateException(); PriorityQueue<HuffmanTree>pq=newPriorityQueue<>(weights.length);

for(int

i=0;i<weights.length;i++)//創(chuàng)建葉子結(jié)點(diǎn)對(duì)應(yīng)的霍夫曼樹，并入隊(duì)

pq.offer(newHuffmanTree(symbol[i],weights[i]));

while(pq.size()!=1){//取2棵最小的樹，合并后得到1棵新樹，再放入隊(duì)列

pq.offer(merge(pq.poll(),pq.poll())); }

return

pq.poll(); }Huffman編碼-譯碼//只能處理1個(gè)符號(hào)使用了1個(gè)char場合public

classHuffmanCoding{

privateHuffmanTreeht;

privateMap<Character,Byte[]>coder;//符號(hào)編碼表，存放<符號(hào),編碼>

private

static

byte

LEFT=0;//左子樹的標(biāo)識(shí)

private

static

byte

RIGHT=1;//右子樹的標(biāo)識(shí)

publicHuffmanCoding(HuffmanTreeht){

this.ht=ht; }獲取編碼表

private

voidmakeCodeList(){//根據(jù)霍夫曼樹建立符號(hào)編碼表

coder=newHashMap<>(); Deque<Byte>stack=newArrayDeque<>(); preCoding(ht.root.left,LEFT,stack); preCoding(ht.root.right,RIGHT,stack); }獲取編碼表

private

voidpreCoding(Nodet,byte

b,Deque<Byte>stack){

//為了toArray的次序和從根到葉子結(jié)點(diǎn)的路徑的次序一致，使用Deque的右端棧

stack.addLast(b);

if(t.left==null&&t.right==null){//葉子結(jié)點(diǎn) Byte[]code=newByte[stack.size()];

stack.toArray(code);

coder.put(t.data,code); }else{ preCoding(t.left,LEFT,stack); preCoding(t.right,RIGHT,stack); }

stack.removeLast();//回溯 }01000100110110010111291367167925編碼

publicByte[]enCoder(Stringstr){

if(coder==null)//第1次使用這棵哈夫曼樹編碼 makeCodeList();

int

len=str.length(); List<Byte[]>list=newArrayList<>(len);//存放各字符的編碼

int

count=0;//編碼的總長度

for(int

i=0;i<len;i++){ Byte[]b=coder.get(str.charAt(i));//查表，獲取字符的編碼

count+=b.length;

list.add(b); } Byte[]result=newByte[count];//str的編碼

int

pos=0;

for(int

i=0;i<list.size();i++){ Byte[]b=list.get(i); System.arraycopy(b,0,result,pos,b.length);

pos+=b.length; }

return

result; }譯碼

publicStringdeCoder(Byte[]code){//沒有處理一些特殊情況 StringBuilderresult=newStringBuilder(); Nodenode=ht.root;

for(int

i=0;i<code.length;i++){

if(code[i].byteValue()==LEFT)

node=node.left;

else

node=node.right;

if(node.left==null&&node.right==null){//葉子結(jié)點(diǎn)

result.append(node.data);//葉子結(jié)點(diǎn)中存的符號(hào)

node=ht.root;//譯出一個(gè)字符后，再從根開始 } }

return

result.toString(); }測試10010111111111010110010101000111011helloworld

public

static

voidmain(String[]args){

float[]weights={9f,7f,5f,4f,2f};

char[]symbol={'A','B','C','D','E'}; HuffmanCodinghc=newHuffmanCoding(HuffmanTree.makeTree(symbol,weights)); Stringstr="ABECD"; Byte[]codes=hc.enCoder(str);

for(int

i=0;i<codes.length;i++) System.out.print(codes[i]); System.out.println(); System.out.println(hc.deCoder(codes)); }總結(jié)1、哈夫曼樹提供了對(duì)符號(hào)集的一種前綴編碼，用于文本壓縮、通訊等。2、哈夫曼樹算法比較簡單，在實(shí)現(xiàn)時(shí)用到了Map、PriorityQueue等數(shù)據(jù)結(jié)構(gòu)。很好的說明了算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系。3、代碼沒有考慮各種特殊情形，而且簡單的用Byte保存編碼，可以考慮用BitSet等替換，或進(jìn)一步處理成其它形式。處理雙char的符號(hào)

public

static

voidmain(String[]args){

float[]weights={0.01f,0.01f,0.01f,0.20f,0.3f,0.2f,0.1f,0.2f}; String[]symbol={"??","??","??","漢","字","1","2","3"}; HuffmanTree1ht=newHuffmanTree1(symbol,weights); Stringstr="??????漢字123"; Byte[]codes=ht.coding(str);

for(int

i=0;i<codes.length;i++) System.out.print(codes[i]); System.out.println(); System.out.println(ht.decoding(codes)); }??這樣的符號(hào)不能用1個(gè)char，而是2個(gè)char，可以使用String處理雙char的符號(hào)

private

static

classNode{

Stringdata; Nodeleft; Noderight; Node(Stringdata,Nodeleft,Noderight){

this.data=data;

this.left=left;

this.right=right; } }處理雙char的符號(hào)

publicByte[]enCoder(Stringstr){//該方法變了

if(coder==null)//第1次編碼 makeCodeList(); List<Byte[]>list=newArrayList<>();

int

count=0;//編碼的總長度

int

i=0;

while(i<str.length()){ Byte[]b;

//1個(gè)符號(hào)需要2個(gè)char，高位的char是HighSurrogate

if(Character.isHighSurrogate(str.charAt(i))){

b=coder.get(str.substring(i,i+2));

i+=2; }else{

b=coder.get(str.substring(i,i+1)); ++i; }

count+=b.length;

list.add(b); }

//各個(gè)字符的總編碼 Byte[]result=newByte[count];

int

pos=0;

for(int

j=0;j<list.size();j++){ Byte[]b=list.get(j); System.arraycopy(b,0,result,pos,b.length);

pos+=b.length; }