哈夫曼演算法最優前綴碼

Ⅰ 如何證明哈夫曼編碼一定是不重復的最優編碼

哈夫曼編碼完全依據字元出現概率來構造異字頭的平均長度最短的碼字，所以頻率相同的編碼可以互換，兩種編碼之後的字元串的平均期望長度是相同的。這里你和你同學做出的結果不同是因為哈夫曼樹是二叉樹，編碼頻率相同，但插入到二叉樹的順序不同，所以出現了不同的結果。

Ⅱ 求數據結構（JAVA版）實驗樹和二叉樹題目答案

/**
* @param args
之前在大學的時候寫的一個二叉樹演算法，運行應該沒有問題，就看適不適合你的項目了 */
public static void main(String[] args) {

BiTree e = new BiTree(5);
BiTree g = new BiTree(7);
BiTree h = new BiTree(8);
BiTree l = new BiTree(12);
BiTree m = new BiTree(13);
BiTree n = new BiTree(14);
BiTree k = new BiTree(11, n, null);
BiTree j = new BiTree(10, l, m);
BiTree i = new BiTree(9, j, k);
BiTree d = new BiTree(4, null, g);
BiTree f = new BiTree(6, h, i);
BiTree b = new BiTree(2, d, e);
BiTree c = new BiTree(3, f, null);
BiTree tree = new BiTree(1, b, c);
System.out.println("遞歸前序遍歷二叉樹結果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("非遞歸前序遍歷二叉樹結果: ");
tree.iterativePreOrder(tree);
System.out.println();
System.out.println("遞歸中序遍歷二叉樹的結果為:");
tree.inOrder(tree);
System.out.println();
System.out.println("非遞歸中序遍歷二叉樹的結果為:");
tree.iterativeInOrder(tree);
System.out.println();
System.out.println("遞歸後序遍歷二叉樹的結果為:");
tree.postOrder(tree);
System.out.println();
System.out.println("非遞歸後序遍歷二叉樹的結果為:");
tree.iterativePostOrder(tree);
System.out.println();
System.out.println("層次遍歷二叉樹結果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("遞歸求二叉樹中所有結點的和為:"+getSumByRecursion(tree));
System.out.println("非遞歸求二叉樹中所有結點的和為:"+getSumByNoRecursion(tree));

System.out.println("二叉樹中,每個節點所在的層數為:");
for (int p = 1; p <= 14; p++)
System.out.println(p + "所在的層為:" + tree.level(p));
System.out.println("二叉樹的高度為:" + height(tree));
System.out.println("二叉樹中節點總數為:" + nodes(tree));
System.out.println("二叉樹中葉子節點總數為:" + leaf(tree));
System.out.println("二叉樹中父節點總數為:" + fatherNodes(tree));
System.out.println("二叉樹中只擁有一個孩子的父節點數:" + oneChildFather(tree));
System.out.println("二叉樹中只擁有左孩子的父節點總數:" + leftChildFather(tree));
System.out.println("二叉樹中只擁有右孩子的父節點總數:" + rightChildFather(tree));
System.out.println("二叉樹中同時擁有兩個孩子的父節點個數為:" + doubleChildFather(tree));
System.out.println("--------------------------------------");
tree.exChange();
System.out.println("交換每個節點的左右孩子節點後......");
System.out.println("遞歸前序遍歷二叉樹結果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("非遞歸前序遍歷二叉樹結果: ");
tree.iterativePreOrder(tree);
System.out.println();
System.out.println("遞歸中序遍歷二叉樹的結果為:");
tree.inOrder(tree);
System.out.println();
System.out.println("非遞歸中序遍歷二叉樹的結果為:");
tree.iterativeInOrder(tree);
System.out.println();
System.out.println("遞歸後序遍歷二叉樹的結果為:");
tree.postOrder(tree);
System.out.println();
System.out.println("非遞歸後序遍歷二叉樹的結果為:");
tree.iterativePostOrder(tree);
System.out.println();
System.out.println("層次遍歷二叉樹結果: ");
tree.LayerOrder(tree);
System.out.println();

System.out.println("遞歸求二叉樹中所有結點的和為:"+getSumByRecursion(tree));
System.out.println("非遞歸求二叉樹中所有結點的和為:"+getSumByNoRecursion(tree));

System.out.println("二叉樹中,每個節點所在的層數為:");
for (int p = 1; p <= 14; p++)
System.out.println(p + "所在的層為:" + tree.level(p));
System.out.println("二叉樹的高度為:" + height(tree));
System.out.println("二叉樹中節點總數為:" + nodes(tree));
System.out.println("二叉樹中葉子節點總數為:" + leaf(tree));
System.out.println("二叉樹中父節點總數為:" + fatherNodes(tree));
System.out.println("二叉樹中只擁有一個孩子的父節點數:" + oneChildFather(tree));
System.out.println("二叉樹中只擁有左孩子的父節點總數:" + leftChildFather(tree));
System.out.println("二叉樹中只擁有右孩子的父節點總數:" + rightChildFather(tree));
System.out.println("二叉樹中同時擁有兩個孩子的父節點個數為:" + doubleChildFather(tree));
}
}

Ⅲ 在什麼情況下，等長編碼是最優前的編碼

在（平均碼長為2.24）情況下，等長編碼是最優前的編碼.常見的等長編碼就是前綴碼。所謂最優前綴碼是指，平均碼長或文件總長最小的前綴編碼稱為最優的前綴碼（這里的平均碼長相當於碼長的期望值）。
變長編碼可能使解碼產生二義性，而前綴碼的出現很好地解決了這個問題。而平均碼長相當於二叉樹的加權路徑長度，從這個意義上說，由哈夫曼樹生成的編碼一定是最優前綴碼，故通常不加區分的將哈夫曼編碼也稱作最優前綴碼。
需要注意的是，由於哈夫曼樹建立過程的不唯一性可知，生成的哈夫曼編碼也是不唯一的.

Ⅳ 哈夫曼編碼碼長怎麼算

設某信源產生有五種符號u1、u2、u3、u4和u5，對應概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。

霍夫曼編碼是變長編碼，思路：對概率大的編的碼字短，概率小的編的碼字長，這樣一來所編的總碼長就小，這樣編碼效率就高。上面那樣求是不對的，除非你這6個碼字是等概率的，各佔1/6。應該用對應的概率*其對應得碼長，再求和。

實際應用中

除採用定時清洗以消除誤差擴散和採用緩沖存儲以解決速率匹配以外，主要問題是解決小符號集合的統計匹配，例如黑（1）、白（0）傳真信源的統計匹配，採用0和1不同長度遊程組成擴大的符號集合信源。遊程，指相同碼元的長度（如二進碼中連續的一串0或一串1的長度或個數）。

按照CCITT標准，需要統計2×1728種遊程（長度），這樣，實現時的存儲量太大。事實上長遊程的概率很小，故CCITT還規定：若l表示遊程長度，則l=64q+r。

Ⅳ 前綴編碼的哈夫曼編碼

用構造哈夫曼樹的過程生成的二進制前綴編碼。哈夫曼樹是一類帶權路徑長度最短的樹。
特點：長度最短

Ⅵ 離散數學如何判斷前編碼

即上述編碼是二進制的前綴碼。前綴碼：對每一個字元規定一個0,1串作為其代碼，並要求任一字元的代碼都不是其他字元代碼的前綴。

利用哈夫曼樹很容易求出給定字元集及其概率(或頻度)分布的最優前綴碼。該編碼即為最優前綴碼（也稱哈夫曼編碼）。2． 哈夫曼編碼為最優前綴碼。這個比較復雜，一般記牢好商品條形碼中的前綴碼（用來標識國家或地區的），加上對批號的認識就差不多了。

歐萊雅在在法國的前綴碼是30-37，表示是 。離散數學前綴碼，utf-8 是一種針對unicode的可變長度字元編碼，也是一種前綴碼。其中第09-20項用於設置需要進行ip路由的市話前綴碼(1位或2位)。

在系統中設置經濟線路接入號碼，見系統編程項目03(經濟線路接入號)，市話經濟線路的指定前綴碼見系統編程16項（限制代碼b)的09~20項輸入，是否設置定時參數，見系統編程項目08(定時參數調整)的參數2。

c的一個前綴碼編碼方案對應於一棵二叉樹t。則平均碼長定義為：使平均碼長達到最的前綴碼編碼方案稱為c的最優前綴碼。離散數學前綴碼，二叉樹t表示字元集c的一個最優前綴碼，證明可以對t作適當修改後得到一棵新的二叉樹t」，在t」中x和y是最深葉子且為兄弟，同時t」表示的前綴碼也是c的最優前綴碼。

二叉樹t表示字元集c的一個最優前綴碼，x和y是樹t中的兩個葉子且為兄弟，z是它們的父親。f(y)的字元，則樹t』=t-{x,y}表示字元集c』=c-{x, y} ∪ { z}的一個最優前綴碼。

Ⅶ 請描述哈夫曼演算法，並用圖描述構造哈夫曼樹的過程。

這個講的相當清楚。
首先介紹什麼是哈夫曼樹。哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。
哈夫曼在上世紀五十年代初就提出這種編碼時，根據字元出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列，則編碼的平均長度是最小的。（註：碼字即為符號經哈夫曼編碼後得到的編碼，其長度是因符號出現的概率而不同，所以說哈夫曼編碼是變長的編碼。）
然而怎樣構造一棵哈夫曼樹呢？最具有一般規律的構造方法就是哈夫曼演算法。一般的數據結構的書中都可以找到其描述：
一、對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現演算法，一般還要求以Ti的權值Wi的升序排列。）
二、在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
三、從F中刪除這兩棵樹，並把這棵新的二叉樹同樣以升序排列加入到集合F中。
四、重復二和三兩步，直到集合F中只有一棵二叉樹為止。
用C語言實現上述演算法，可用靜態的二叉樹或動態的二叉樹。若用動態的二叉樹可用以下數據結構： struct tree{
float weight; /*權值*/
union{
char leaf; /*葉結點信息字元*/
struct tree *left; /*樹的左結點*/
};
struct tree *right; /*樹的右結點*/
};
struct forest{ /*F集合，以鏈表形式表示*/
struct tree *ti; /* F中的樹*/
struct forest *next; /* 下一個結點*/
};
例：若字母A，B，Z，C出現的概率為：0.75,0.54,0.28,0.43；則相應的權值為：75，54，28，43。
構造好哈夫曼樹後，就可根據哈夫曼樹進行編碼。例如：上面的字元根據其出現的概率作為權值構造一棵哈夫曼樹後，經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字元。顯然哈夫曼編碼是前綴編碼，即任一個字元的編碼都不是另一個字元的編碼的前綴，否則，編碼就不能進行翻譯。例如：a,b,c,d的編碼為：0，10，101，11，對於編碼串：1010就可翻譯為bb或ca，因為b的編碼是c的編碼的前綴。剛才進行哈夫曼編碼的規則是從根結點到葉結點（包含原信息）的路徑，向左孩子前進編碼為0，向右孩子前進編碼為1，當然你也可以反過來規定。
這種編碼方法是靜態的哈夫曼編碼，它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為0--2^32-1，這已足夠表示大文件中字元出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。 靜態哈夫曼編碼方法有一些缺點：一、對於過短的文件進行編碼的意義不大，因為光以4BYTES的長度存儲哈夫曼樹的信息就需1024Bytes的存儲空間；二、進行哈夫曼編碼，存儲編碼信息時，若用與通訊網路，就會引起較大的延時；三、對較大的文件進行編碼時，頻繁的磁碟讀寫訪問會降低數據編碼的速度。
因此，後來有人提出了一種動態的哈夫曼編碼方法。動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。動態哈夫曼編碼比靜態哈夫曼編碼復雜的多，有興趣的讀者可參考有關數據結構與演算法的書籍。
前面提到的JPEG中用到了哈夫曼編碼，並不是說JPEG就只用哈夫曼編碼就可以了，而是一幅圖片經過多個步驟後得到它的一列數值，對這些數值進行哈夫曼編碼，以便存儲或傳輸。哈夫曼編碼方法比較易懂，大家可以根據它的編碼方法，自己編寫哈夫曼編碼和解碼的程序。

Ⅷ 敘述哈夫曼演算法的思想

運行過了沒有任何問題,有什麼問題可以交流下.
#include
#include
#define N 6
typedef struct
{

int W,P,R,L;
}HTNode;
typedef struct
{
char ch;
char code[10];
}HTCode;
HTCode HC[27];
void select(HTNode HT[],int *min1,int *min2,int *a,int *b)
{

int i;int mina=100,minb=100;
int m,n;

for(i=1;i

Ⅸ 求助有關哈夫曼樹的問題！急！滿意的答案再加!

哈夫曼樹
一、 基本術語
1. 路徑與路徑長度
若在一棵樹中存在一個結點序列 k1, k2, …., kj ，使得kj是kj+1的雙親（1<=i<j），則稱結點序列是從k1到kj 的路徑（如樹中的某個結點到它的某個祖先，或者到它的某個後代的的包括它本身的一系列按順序的結點序列稱為路徑），因樹中的每個結點只有一個雙親結點，所以這是兩個結點間的唯一路徑，從k1到kj 所經過的分支數稱為這兩點之間的路徑長度。它等於結點數-1。
如： 從結點A到結點J的結點序
列為A，B，E，J。
路徑長度為3。

8 10

4 5 3
2. 結點的權和帶權路徑長度
如果根據需要給樹中的結點賦予一個有某中意義的實數，則稱此實數為該結點的權，結點帶權路徑長度規定為從樹根結點到該結點之間的路徑長度乘上該結點的權值所得到的乘積。
3. 樹的帶權路徑長度
樹的帶權路徑長度定義為樹中所有葉結點的帶權路徑長度之和，通常記為：
n
WPL=∑ wili wi和li 分別代表葉結點ki的權值和ki到
i=1 根結點的路徑長度
例如：上圖的WPL=（4+5+3）*3+（8+10）*2=72
4. 哈夫曼樹
哈夫曼樹又稱為最優二叉樹，它是由n個帶權葉結點構成的所有二叉樹中帶權路徑長度WPL最小的二叉樹。
例如：有四個葉結點a，b，c，d，分別帶權為9，4，5，2，可以構成三棵不同的二叉樹（當然可以構成更多的二叉樹）見下圖：

9 4 5 2 WPL=（9+4+5+2）*2=40

4

2

5 9
WPL=（9+5）*3+2*2+4*1=50

4

2

5 9
WPL=（9+5）*3+2*2+4*1=50

9

5

4 2
WPL=9*1+5*2+（2+4）*3=37
可以證明最後一棵二叉樹是哈夫曼樹。
二、 構造哈夫曼樹
1. 將n個葉結點構成獨立的n棵二叉樹，每棵二叉樹只有一個根結點。
2. 選擇兩棵權值最小的二叉樹合並成一棵二叉樹，並以這兩棵二叉樹的權值之和作為這棵二叉樹的權值，取消原來的兩棵二叉樹。
3. 重復2，知道只剩一棵二叉樹為止。
例如：有6個帶權葉結點的權值分別為：3，6，8，5，2，2，構造一棵哈夫曼樹，並計算WPL的結果。
1.構造6棵二叉樹

3 6 8 5 2 2
2選出兩個權值最小的二叉樹的組成一棵二叉樹

2 2 合並權值為4

3 6 8 5
3 6 8 5 4
2 2
選出兩個權值最小的二叉樹的組成一棵二叉樹

7 6 8 5

3

2 2
選出兩個權值最小的二叉樹的組成一棵二叉樹

7 11 8

3
5 6
2 2
選出兩個權值最小的二叉樹的組成一棵二叉樹

15 11

8
5 6
3

2 2

選出兩個權值最小的二叉樹的組成一棵二叉樹（最終的哈夫曼樹）

8
5 6
3

2 2
WPL=（2+2）*4+3*3+（5+6+8）*2=16+9+38=63
作業：P221/9