構造哈夫曼演算法

㈠ 哈夫曼樹的構造演算法

/*-------------------------------------------------------------------------
*Name:哈夫曼編碼源代碼。
*Date:2011.04.16
*Author:JeffreyHill+Jezze(解碼部分)
*在Win-TC下測試通過
*實現過程：著先通過HuffmanTree()函數構造哈夫曼樹，然後在主函數main()中
*自底向上開始(也就是從數組序號為零的結點開始)向上層層判斷，若在
*父結點左側，則置碼為0,若在右側,則置碼為1。最後輸出生成的編碼。
*------------------------------------------------------------------------*/
#include<stdio.h>
#include<stdlib.h>

#defineMAXBIT100
#defineMAXVALUE10000
#defineMAXLEAF30
#defineMAXNODEMAXLEAF*2-1

typedefstruct
{
intbit[MAXBIT];
intstart;
}HCodeType;/*編碼結構體*/
typedefstruct
{
intweight;
intparent;
intlchild;
intrchild;
intvalue;
}HNodeType;/*結點結構體*/

/*構造一顆哈夫曼樹*/
voidHuffmanTree(HNodeTypeHuffNode[MAXNODE],intn)
{
/*i、j：循環變數，m1、m2：構造哈夫曼樹不同過程中兩個最小權值結點的權值，
x1、x2：構造哈夫曼樹不同過程中兩個最小權值結點在數組中的序號。*/
inti,j,m1,m2,x1,x2;
/*初始化存放哈夫曼樹數組HuffNode[]中的結點*/
for(i=0;i<2*n-1;i++)
{
HuffNode[i].weight=0;//權值
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
HuffNode[i].value=i;//實際值，可根據情況替換為字母
}/*endfor*/

/*輸入n個葉子結點的權值*/
for(i=0;i<n;i++)
{
printf("Pleaseinputweightofleafnode%d:
",i);
scanf("%d",&HuffNode[i].weight);
}/*endfor*/

/*循環構造Huffman樹*/
for(i=0;i<n-1;i++)
{
m1=m2=MAXVALUE;/*m1、m2中存放兩個無父結點且結點權值最小的兩個結點*/
x1=x2=0;
/*找出所有結點中權值最小、無父結點的兩個結點，並合並之為一顆二叉樹*/
for(j=0;j<n+i;j++)
{
if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}/*endfor*/
/*設置找到的兩個子結點x1、x2的父結點信息*/
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;

printf("x1.weightandx2.weightinround%d:%d,%d
",i+1,HuffNode[x1].weight,HuffNode[x2].weight);/*用於測試*/
printf("
");
}/*endfor*/
/*for(i=0;i<n+2;i++)
{
printf("Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d
",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///測試
}/*endHuffmanTree*/

//解碼
voiddecodeing(charstring[],HNodeTypeBuf[],intNum)
{
inti,tmp=0,code[1024];
intm=2*Num-1;
char*nump;
charnum[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];

while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{

if(*nump==0)
{
tmp=Buf[tmp].lchild;
}
elsetmp=Buf[tmp].rchild;
nump++;

}

printf("%d",Buf[tmp].value);
}


}


intmain(void)
{

HNodeTypeHuffNode[MAXNODE];/*定義一個結點結構體數組*/
HCodeTypeHuffCode[MAXLEAF],cd;/*定義一個編碼結構體數組，同時定義一個臨時變數來存放求解編碼時的信息*/
inti,j,c,p,n;
charpp[100];
printf("Pleaseinputn:
");
scanf("%d",&n);
HuffmanTree(HuffNode,n);


for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1)/*父結點存在*/
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;/*求編碼的低一位*/
c=p;
p=HuffNode[c].parent;/*設置下一循環條件*/
}/*endwhile*/

/*保存求出的每個葉結點的哈夫曼編碼和編碼的起始位*/
for(j=cd.start+1;j<n;j++)
{HuffCode[i].bit[j]=cd.bit[j];}
HuffCode[i].start=cd.start;
}/*endfor*/

/*輸出已保存好的所有存在編碼的哈夫曼編碼*/
for(i=0;i<n;i++)
{
printf("%d'sHuffmancodeis:",i);
for(j=HuffCode[i].start+1;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf("start:%d",HuffCode[i].start);

printf("
");

}
/*for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf("
");
}*/
printf("Decoding?PleaseEntercode:
");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return0;
}

http://www.cnblogs.com/Jezze/archive/2011/12/23/2299884.html

㈡ 哈夫曼演算法簡介

看官們建議在看我的這篇文章之前，先看一下RlE演算法  這個是計算機壓縮演算法的入門級，如果連這個演算法的思想都不清楚的，請私聊我，單獨講解

簡單說一下rle=字元乘以重復數量

舉個例子，aaaaaabbbbbb的rlu就是a6b6

說回哈夫曼演算法

第一  統計每個字元出現的次數

第二  將出現次數最少的字元連線並求數量和

第三  重復第二步完成哈夫曼樹

第四  將哈夫曼樹的左邊的邊寫上0，右邊的邊也寫上  1 

第五  從根節點開始沿著邊去將數字寫在對應的字元下面

這樣一個哈夫曼編碼就完成了

#include <iostream>

#include <iomanip>

using namespace std;

//哈夫曼樹的存儲表示

typedef struct

{

    int weight;    // 權值

    int parent, lChild, rChild;    // 雙親及左右孩子的下標

}HTNode, *HuffmanTree;

// 選擇權值最小的兩顆樹

void SelectMin(HuffmanTree hT, int n, int &s1, int &s2)

{

    s1 = s2 = 0;

    int i;

    for(i = 1; i < n; ++ i){

        if(0 == hT[i].parent){

            if(0 == s1){

                s1 = i;

            }

            else{

                s2 = i;

                break;

            }

        }

    }

    if(hT[s1].weight > hT[s2].weight){

        int t = s1;

        s1 = s2;

        s2 = t;

    }

    for(i += 1; i < n; ++ i){

        if(0 == hT[i].parent){

            if(hT[i].weight < hT[s1].weight){

                s2 = s1;

                s1 = i;

            }else if(hT[i].weight < hT[s2].weight){

                s2 = i;

            }

        }

    }

}

// 構造有n個權值（葉子節點）的哈夫曼樹

void CreateHufmanTree(HuffmanTree &hT)

{

    int n, m;

    cin >> n;

    m = 2*n - 1;

    hT = new HTNode[m + 1];    // 0號節點不使用

    for(int i = 1; i <= m; ++ i){

        hT[i].parent = hT[i].lChild = hT[i].rChild = 0;

    }

    for(int i = 1; i <= n; ++ i){

        cin >> hT[i].weight;    // 輸入權值

    }

    hT[0].weight = m;    // 用0號節點保存節點數量

    /****** 初始化完畢, 創建哈夫曼樹 ******/

    for(int i = n + 1; i <= m; ++ i){

        int s1, s2;

        SelectMin(hT, i, s1, s2);

        hT[s1].parent = hT[s2].parent = i;

        hT[i].lChild = s1; hT[i].rChild = s2;    // 作為新節點的孩子

        hT[i].weight = hT[s1].weight + hT[s2].weight;    // 新節點為左右孩子節點權值之和

    }

}

int HuffmanTreeWPL_(HuffmanTree hT, int i, int deepth)

{

    if(hT[i].lChild == 0 && hT[i].rChild == 0){

        return hT[i].weight * deepth;

    }

    else{

        return HuffmanTreeWPL_(hT, hT[i].lChild, deepth + 1) + HuffmanTreeWPL_(hT, hT[i].rChild, deepth + 1);

    }

}

// 計算WPL（帶權路徑長度）

int HuffmanTreeWPL(HuffmanTree hT)

{

    return HuffmanTreeWPL_(hT, hT[0].weight, 0);

}

// 輸出哈夫曼樹各節點的狀態

void Print(HuffmanTree hT)

{

    cout << "index weight parent lChild rChild" << endl;

    cout << left;    // 左對齊輸出

    for(int i = 1, m = hT[0].weight; i <= m; ++ i){

        cout << setw(5) << i << " ";

        cout << setw(6) << hT[i].weight << " ";

        cout << setw(6) << hT[i].parent << " ";

        cout << setw(6) << hT[i].lChild << " ";

        cout << setw(6) << hT[i].rChild << endl;

    }

}

// 銷毀哈夫曼樹

void DestoryHuffmanTree(HuffmanTree &hT)

{

    delete[] hT;

    hT = NULL;

}

int main()

{

    HuffmanTree hT;

    CreateHufmanTree(hT);

    Print(hT);

    cout << "WPL = " << HuffmanTreeWPL(hT) << endl;

    DestoryHuffmanTree(hT);

    return 0;

}

㈢ 哈夫曼樹構造演算法中j<n+i是什麼意思

先看一下哈夫曼樹的構造規則是：
假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：
(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
(2) 在森林中選出兩個根結點的權值最小的樹合並，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
(3)從森林中刪除選取的兩棵樹，並將新樹加入森林；
(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

用數據表示哈夫曼樹的話，首先有n個權值點，其初始化就是從 0 到 n -1，先從這裡面查找兩個權值最小的結點，就是遍歷一遍，把最小的值取出來。X1 和X2 要記錄著兩個權值在哪個位置。
然後把這兩個權值加起來的和放回到數組n的位置，然後繼續遍歷這個數據，現在是從0 到n了，當然原來X1 和X2位置的兩個點不用管，已經有父節點了。繼續上述過程直到只有一個節點位置。

如 1 2 3 4 5 6構造哈夫曼樹，先初始化parent 為 -1
1 2 3 4 5 6
parent -1 -1 -1 -1 -1 -1
先從上述中選取兩個權值最小的節點 1 和 2，構造樹變為3，放到數組6的位置，原權值序列變為：
1 2 3 4 5 6 3
parent 6 6 -1 -1 -1 -1 -1
繼續選取 兩個最小權值且parent為-1的點。找到3 和 3，放到數組7的位置，權值序列變為：
1 2 3 4 5 6 3 6
parent 6 6 7 -1 -1 -1 7 -1
繼續選取 兩個最小權值且parent為-1的點。找到4 和5，到數組8的位置，權值序列變為：
1 2 3 4 5 6 3 6 9
parent 6 6 7 8 8 -1 7 -1 -1
繼續選取 兩個最小權值且parent為-1的點。找到6 和6，到數組9的位置，權值序列變為：
1 2 3 4 5 6 3 6 9 12
parent 6 6 7 8 8 9 7 9 -1 -1
繼續選取 兩個最小權值且parent為-1的點。找到9 和12，到數組10的位置，權值序列變為：
1 2 3 4 5 6 3 6 9 12 21
parent 6 6 7 8 8 9 7 9 10 10 -1
結束
所以你說的j < n + i，由於每次選取兩個權值的點權值和做為新的節點放在數組後面，當然下一次循環的時候要多一次循環。
X1 和X2要記錄下選擇兩個權值，將其父節點的位置設置為新的權值點位置。

㈣ 哈夫曼樹的構造是什麼

哈夫曼樹構造：結構化的Huffman演算法生成的Huffman樹子樹都是有序的，所以一般生成Huffman樹時都為節點排序，即使這樣結果也不唯一。

哈夫曼靜態編碼：它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。

歷史

1951年，哈夫曼在麻省理工學院（MIT）攻讀博士學位，他和修讀資訊理論課程的同學得選擇是完成學期報告還是期末考試。

導師羅伯特·法諾（Robert Fano）出的學期報告題目是：查找最有效的二進制編碼。由於無法證明哪個已有編碼是最有效的，哈夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二叉樹編碼的想法，並很快證明了這個方法是最有效的。

哈夫曼使用自底向上的方法構建二叉樹，避免了次優演算法香農-范諾編碼（Shannon–Fano coding）的最大弊端──自頂向下構建樹。

1952年，於論文《一種構建極小多餘編碼的方法》（A Method for the Construction of Minimum-Rendancy Codes）中發表了這個編碼方法。

㈤ 哈夫曼的如何構造

然而怎樣構造一棵哈夫曼樹呢？最具有一般規律的構造方法就是哈夫曼演算法。一般的數據結構的書中都可以找到其描述： 重復二和三兩步，直到集合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，C，D出現的概率為：0.75,0.54,0.28,0.43；則相應的權值為：75，54，28，43。
構造好哈夫曼樹後，就可根據哈夫曼樹進行編碼。例如：上面的字元根據其出現的概率作為權值構造一棵哈夫曼樹後，經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字元。顯然哈夫曼編碼是前綴編碼，即任一個字元的編碼都不是另一個字元的編碼的前綴，否則，編碼就不能進行翻譯。例如：a,b,c,d的編碼為：0，10，110，111，對於編碼串：1010就翻譯為bb。剛才進行哈夫曼編碼的規則是從根結點到葉結點（包含原信息）的路徑，向左孩子前進編碼為0，向右孩子前進編碼為1，當然你也可以反過來規定。

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

1. 根據給定的n個權值{w1,w2,…wn}構成n棵二叉樹的集合F={T1,T2,..,Tn}，其中每棵二叉樹Ti中只有一個帶權wi的根結點，左右子樹均空。
2. 在F中選擇兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和。
3. 在F中刪除這兩棵樹，並將新的二叉樹加入F中。
4. 重復前兩步（2和3），直到F中只含有一棵樹為止。該樹即為哈夫曼樹
幫你貼過來了，網路
這東西實際用法是可以減少樹的訪問次數，因為他把頻率高的點放在比較靠近根節點的地方，頻率低的在下面，這樣訪問速度快。舉個例子，比如四個點，他們的使用頻率分別是1,2,3,4，然後構成的樹就是
4
0 3
0 2
0 1
補：打不出樹形結構...