久久国产成人av_抖音国产毛片_a片网站免费观看_A片无码播放手机在线观看,色五月在线观看,亚洲精品m在线观看,女人自慰的免费网址,悠悠在线观看精品视频,一级日本片免费的,亚洲精品久,国产精品成人久久久久久久

搜索
分享

哈夫曼編碼問題

 為你放縱一生 2016-11-13

    1,、問題描述

      哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間,。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0,，1串表示各字符的最優(yōu)表示方式。一個包含100,000個字符的文件,，各字符出現(xiàn)頻率不同,，如下表所示。


    有多種方式表示文件中的信息,，若用0,1碼表示字符的方法,，即每個字符用唯一的一個0,1串表示。若采用定長編碼表示,，則需要3位表示一個字符,，整個文件編碼需要300,000位；若采用變長編碼表示,，給頻率高的字符較短的編碼,；頻率低的字符較長的編碼,，達到整體編碼減少的目的,，則整個文件編碼需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可見,，變長碼比定長碼方案好,，總碼長減小約25%。

     前綴碼：對每一個字符規(guī)定一個0,1串作為其代碼,，并要求任一字符的代碼都不是其他字符代碼的前綴,。這種編碼稱為前綴碼。編碼的前綴性質(zhì)可以使譯碼方法非常簡單,；例如001011101可以唯一的分解為0,0,101,1101,，因而其譯碼為aabe。

     譯碼過程需要方便的取出編碼的前綴,，因此需要表示前綴碼的合適的數(shù)據(jù)結(jié)構(gòu),。為此，可以用二叉樹作為前綴碼的數(shù)據(jù)結(jié)構(gòu)：樹葉表示給定字符,；從樹根到樹葉的路徑當(dāng)作該字符的前綴碼,；代碼中每一位的0或1分別作為指示某節(jié)點到左兒子或右兒子的“路標(biāo)”。


     從上圖可以看出,，表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹,，即樹中任意節(jié)點都有2個兒子。圖a表示定長編碼方案不是最優(yōu)的,，其編碼的二叉樹不是一棵完全二叉樹,。在一般情況下，若C是編碼字符集，表示其最優(yōu)前綴碼的二叉樹中恰有|C|個葉子,。每個葉子對應(yīng)于字符集中的一個字符,，該二叉樹有|C|-1個內(nèi)部節(jié)點。

     給定編碼字符集C及頻率分布f,即C中任一字符c以頻率f(c)在數(shù)據(jù)文件中出現(xiàn),。C的一個前綴碼編碼方案對應(yīng)于一棵二叉樹T,。字符c在樹T中的深度記為dT(c)。dT(c)也是字符c的前綴碼長,。則平均碼長定義為：使平均碼長達到最小的前綴碼編碼方案稱為C的最優(yōu)前綴碼,。     

     2、構(gòu)造哈弗曼編碼

     哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法,，由此產(chǎn)生的編碼方案稱為哈夫曼編碼,。其構(gòu)造步驟如下：

     (1)哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。

     (2)算法以|C|個葉結(jié)點開始,，執(zhí)行|C|－1次的“合并”運算后產(chǎn)生最終所要求的樹T,。

     (3)假設(shè)編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊列Q用在貪心選擇時有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹,。一旦2棵具有最小頻率的樹合并后,，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和,，并將新樹插入優(yōu)先隊列Q,。經(jīng)過n－1次的合并后，優(yōu)先隊列中只剩下一棵樹,，即所要求的樹T,。

      構(gòu)造過程如圖所示：


     具體代碼實現(xiàn)如下：

     (1)4d4.cpp，程序主文件

  1. //4d4 貪心算法 哈夫曼算法  
  2. #include "stdafx.h"  
  3. #include "BinaryTree.h"  
  4. #include "MinHeap.h"  
  5. #include <iostream>   
  6. using namespace std;   
  7.   
  8. const int N = 6;  
  9.   
  10. template<class Type> class Huffman;  
  11.   
  12. template<class Type>   
  13. BinaryTree<int> HuffmanTree(Type f[],int n);  
  14.   
  15. template<class Type>   
  16. class Huffman  
  17. {  
  18.     friend BinaryTree<int> HuffmanTree(Type[],int);  
  19.     public:  
  20.         operator Type() const   
  21.         {  
  22.             return weight;  
  23.         }  
  24.     //private:  
  25.         BinaryTree<int> tree;  
  26.         Type weight;  
  27. };  
  28.   
  29. int main()  
  30. {  
  31.     char c[] = {'0','a','b','c','d','e','f'};  
  32.     int f[] = {0,45,13,12,16,9,5};//下標(biāo)從1開始  
  33.     BinaryTree<int> t = HuffmanTree(f,N);  
  34.   
  35.     cout<<"各字符出現(xiàn)的對應(yīng)頻率分別為："<<endl;  
  36.     for(int i=1; i<=N; i++)  
  37.     {  
  38.         cout<<c[i]<<":"<<f[i]<<" ";  
  39.     }  
  40.     cout<<endl;  
  41.   
  42.     cout<<"生成二叉樹的前序遍歷結(jié)果為："<<endl;  
  43.     t.Pre_Order();  
  44.     cout<<endl;  
  45.   
  46.     cout<<"生成二叉樹的中序遍歷結(jié)果為："<<endl;  
  47.     t.In_Order();  
  48.     cout<<endl;  
  49.   
  50.     t.DestroyTree();  
  51.     return 0;  
  52. }  
  53.   
  54. template<class Type>  
  55. BinaryTree<int> HuffmanTree(Type f[],int n)  
  56. {  
  57.     //生成單節(jié)點樹  
  58.     Huffman<Type> *w = new Huffman<Type>[n+1];  
  59.     BinaryTree<int> z,zero;  
  60.   
  61.     for(int i=1; i<=n; i++)  
  62.     {  
  63.         z.MakeTree(i,zero,zero);  
  64.         w[i].weight = f[i];  
  65.         w[i].tree = z;  
  66.     }  
  67.   
  68.     //建優(yōu)先隊列  
  69.     MinHeap<Huffman<Type>> Q(n);  
  70.     for(int i=1; i<=n; i++) Q.Insert(w[i]);  
  71.   
  72.     //反復(fù)合并最小頻率樹  
  73.     Huffman<Type> x,y;  
  74.     for(int i=1; i<n; i++)  
  75.     {  
  76.         x = Q.RemoveMin();  
  77.         y = Q.RemoveMin();  
  78.         z.MakeTree(0,x.tree,y.tree);  
  79.         x.weight += y.weight;  
  80.         x.tree = z;  
  81.         Q.Insert(x);  
  82.     }  
  83.   
  84.     x = Q.RemoveMin();  
  85.   
  86.     delete[] w;  
  87.   
  88.     return x.tree;  
  89. }  
     (2)BinaryTree.h 二叉樹實現(xiàn)

  1. #include<iostream>  
  2. using namespace std;  
  3.   
  4. template<class T>  
  5. struct BTNode  
  6. {  
  7.     T data;  
  8.     BTNode<T> *lChild,*rChild;  
  9.   
  10.     BTNode()  
  11.     {  
  12.         lChild=rChild=NULL;  
  13.     }  
  14.   
  15.     BTNode(const T &val,BTNode<T> *Childl=NULL,BTNode<T> *Childr=NULL)  
  16.     {  
  17.         data=val;  
  18.         lChild=Childl;  
  19.         rChild=Childr;  
  20.     }  
  21.   
  22.     BTNode<T>* CopyTree()  
  23.     {  
  24.         BTNode<T> *nl,*nr,*nn;  
  25.   
  26.         if(&data==NULL)  
  27.         return NULL;  
  28.   
  29.         nl=lChild->CopyTree();  
  30.         nr=rChild->CopyTree();  
  31.   
  32.         nn=new BTNode<T>(data,nl,nr);  
  33.         return nn;  
  34.     }  
  35. };  
  36.   
  37.   
  38. template<class T>  
  39. class BinaryTree  
  40. {  
  41.     public:  
  42.         BTNode<T> *root;  
  43.         BinaryTree();  
  44.         ~BinaryTree();  
  45.   
  46.         void Pre_Order();  
  47.         void In_Order();  
  48.         void Post_Order();  
  49.   
  50.         int TreeHeight()const;  
  51.         int TreeNodeCount()const;  
  52.   
  53.         void DestroyTree();  
  54.         void MakeTree(T pData,BinaryTree<T> leftTree,BinaryTree<T> rightTree);  
  55.         void Change(BTNode<T> *r);  
  56.   
  57.     private:  
  58.         void Destroy(BTNode<T> *&r);  
  59.         void PreOrder(BTNode<T> *r);  
  60.         void InOrder(BTNode<T> *r);  
  61.         void PostOrder(BTNode<T> *r);  
  62.   
  63.         int Height(const BTNode<T> *r)const;  
  64.         int NodeCount(const BTNode<T> *r)const;  
  65. };  
  66.   
  67. template<class T>  
  68. BinaryTree<T>::BinaryTree()  
  69. {  
  70.     root=NULL;  
  71. }  
  72.   
  73. template<class T>  
  74. BinaryTree<T>::~BinaryTree()  
  75. {  
  76.       
  77. }  
  78.   
  79. template<class T>  
  80. void BinaryTree<T>::Pre_Order()  
  81. {  
  82.     PreOrder(root);  
  83. }  
  84.   
  85. template<class T>  
  86. void BinaryTree<T>::In_Order()  
  87. {  
  88.     InOrder(root);  
  89. }  
  90.   
  91. template<class T>  
  92. void BinaryTree<T>::Post_Order()  
  93. {  
  94.     PostOrder(root);  
  95. }  
  96.   
  97. template<class T>  
  98. int BinaryTree<T>::TreeHeight()const  
  99. {  
  100.     return Height(root);  
  101. }  
  102.   
  103. template<class T>  
  104. int BinaryTree<T>::TreeNodeCount()const  
  105. {  
  106.     return NodeCount(root);  
  107. }  
  108.   
  109. template<class T>  
  110. void BinaryTree<T>::DestroyTree()  
  111. {  
  112.     Destroy(root);  
  113. }  
  114.   
  115. template<class T>  
  116. void BinaryTree<T>::PreOrder(BTNode<T> *r)  
  117. {  
  118.     if(r!=NULL)  
  119.     {  
  120.         cout<<r->data<<' ';  
  121.         PreOrder(r->lChild);  
  122.         PreOrder(r->rChild);  
  123.     }  
  124. }  
  125.   
  126. template<class T>  
  127. void BinaryTree<T>::InOrder(BTNode<T> *r)  
  128. {  
  129.     if(r!=NULL)  
  130.     {  
  131.         InOrder(r->lChild);  
  132.         cout<<r->data<<' ';  
  133.         InOrder(r->rChild);  
  134.     }  
  135. }  
  136.   
  137. template<class T>  
  138. void BinaryTree<T>::PostOrder(BTNode<T> *r)  
  139. {  
  140.     if(r!=NULL)  
  141.     {  
  142.         PostOrder(r->lChild);  
  143.         PostOrder(r->rChild);  
  144.         cout<<r->data<<' ';  
  145.     }  
  146. }  
  147.   
  148. template<class T>  
  149. int BinaryTree<T>::NodeCount(const BTNode<T> *r)const  
  150. {  
  151.     if(r==NULL)  
  152.         return 0;  
  153.     else  
  154.         return 1+NodeCount(r->lChild)+NodeCount(r->rChild);  
  155. }  
  156.   
  157. template<class T>  
  158. int BinaryTree<T>::Height(const BTNode<T> *r)const  
  159. {  
  160.     if(r==NULL)  
  161.         return 0;  
  162.     else  
  163.     {  
  164.         int lh,rh;  
  165.         lh=Height(r->lChild);  
  166.         rh=Height(r->rChild);  
  167.         return 1+(lh>rh?lh:rh);  
  168.     }  
  169. }  
  170.   
  171. template<class T>  
  172. void BinaryTree<T>::Destroy(BTNode<T> *&r)  
  173. {  
  174.     if(r!=NULL)  
  175.     {  
  176.         Destroy(r->lChild);  
  177.         Destroy(r->rChild);  
  178.         delete r;  
  179.         r=NULL;  
  180.     }  
  181. }  
  182.   
  183. template<class T>  
  184. void BinaryTree<T>::Change(BTNode<T> *r)//將二叉樹bt所有結(jié)點的左右子樹交換  
  185. {  
  186.     BTNode<T> *p;  
  187.     if(r){   
  188.         p=r->lChild;  
  189.         r->lChild=r->rChild;  
  190.         r->rChild=p; //左右子女交換  
  191.         Change(r->lChild);  //交換左子樹上所有結(jié)點的左右子樹  
  192.         Change(r->rChild);  //交換右子樹上所有結(jié)點的左右子樹  
  193.     }  
  194. }  
  195.   
  196. template<class T>  
  197. void BinaryTree<T>::MakeTree(T pData,BinaryTree<T> leftTree,BinaryTree<T> rightTree)  
  198. {  
  199.     root = new BTNode<T>();  
  200.     root->data = pData;  
  201.     root->lChild = leftTree.root;  
  202.     root->rChild = rightTree.root;  
  203. }  
     (3)MinHeap.h 最小堆實現(xiàn)

  1. #include <iostream>  
  2. using namespace std;  
  3. template<class T>  
  4. class MinHeap  
  5. {  
  6.     private:  
  7.         T *heap; //元素數(shù)組,，0號位置也儲存元素  
  8.         int CurrentSize; //目前元素個數(shù)  
  9.         int MaxSize; //可容納的最多元素個數(shù)  
  10.   
  11.         void FilterDown(const int start,const int end); //自上往下調(diào)整,，使關(guān)鍵字小的節(jié)點在上  
  12.         void FilterUp(int start); //自下往上調(diào)整  
  13.   
  14.     public:  
  15.         MinHeap(int n=1000);  
  16.         ~MinHeap();  
  17.         bool Insert(const T &x); //插入元素  
  18.   
  19.         T RemoveMin(); //刪除最小元素  
  20.         T GetMin(); //取最小元素  
  21.   
  22.         bool IsEmpty() const;  
  23.         bool IsFull() const;  
  24.         void Clear();  
  25. };  
  26.   
  27. template<class T>  
  28. MinHeap<T>::MinHeap(int n)  
  29. {  
  30.     MaxSize=n;  
  31.     heap=new T[MaxSize];  
  32.     CurrentSize=0;  
  33. }  
  34.   
  35. template<class T>  
  36. MinHeap<T>::~MinHeap()  
  37. {  
  38.     delete []heap;  
  39. }  
  40.   
  41. template<class T>  
  42. void MinHeap<T>::FilterUp(int start) //自下往上調(diào)整  
  43. {  
  44.     int j=start,i=(j-1)/2; //i指向j的雙親節(jié)點  
  45.     T temp=heap[j];  
  46.   
  47.     while(j>0)  
  48.     {  
  49.         if(heap[i]<=temp)  
  50.             break;  
  51.         else  
  52.         {  
  53.             heap[j]=heap[i];  
  54.             j=i;  
  55.             i=(i-1)/2;  
  56.         }  
  57.     }  
  58.     heap[j]=temp;  
  59. }  
  60.   
  61. template<class T>  
  62. void MinHeap<T>::FilterDown(const int start,const int end) //自上往下調(diào)整，使關(guān)鍵字小的節(jié)點在上  
  63. {  
  64.     int i=start,j=2*i+1;  
  65.     T temp=heap[i];  
  66.     while(j<=end)  
  67.     {  
  68.         if( (j<end) && (heap[j]>heap[j+1]) )  
  69.             j++;  
  70.         if(temp<=heap[j])  
  71.             break;  
  72.         else  
  73.         {  
  74.             heap[i]=heap[j];  
  75.             i=j;  
  76.             j=2*j+1;  
  77.         }  
  78.     }  
  79.     heap[i]=temp;  
  80. }  
  81.   
  82. template<class T>  
  83. bool MinHeap<T>::Insert(const T &x)  
  84. {  
  85.     if(CurrentSize==MaxSize)  
  86.         return false;  
  87.   
  88.     heap[CurrentSize]=x;  
  89.     FilterUp(CurrentSize);  
  90.   
  91.     CurrentSize++;  
  92.     return true;  
  93. }  
  94.   
  95. template<class T>  
  96. T MinHeap<T>::RemoveMin( )  
  97. {  
  98.     T x=heap[0];  
  99.     heap[0]=heap[CurrentSize-1];  
  100.   
  101.     CurrentSize--;  
  102.     FilterDown(0,CurrentSize-1); //調(diào)整新的根節(jié)點  
  103.   
  104.     return x;  
  105. }  
  106.   
  107. template<class T>  
  108. T MinHeap<T>::GetMin()  
  109. {  
  110.     return heap[0];  
  111. }  
  112.   
  113. template<class T>  
  114. bool MinHeap<T>::IsEmpty() const  
  115. {  
  116.     return CurrentSize==0;  
  117. }  
  118.   
  119. template<class T>  
  120. bool MinHeap<T>::IsFull() const  
  121. {  
  122.     return CurrentSize==MaxSize;  
  123. }  
  124.   
  125. template<class T>  
  126. void MinHeap<T>::Clear()  
  127. {  
  128.     CurrentSize=0;  
  129. }  

     3,、貪心選擇性質(zhì)

     二叉樹T表示字符集C的一個最優(yōu)前綴碼,，證明可以對T作適當(dāng)修改后得到一棵新的二叉樹T”，在T”中x和y是最深葉子且為兄弟,，同時T”表示的前綴碼也是C的最優(yōu)前綴碼,。設(shè)b和c是二叉樹T的最深葉子，且為兄弟,。設(shè)f(b)<=f(c),，f(x)<=f(y)。由于x和y是C中具有最小頻率的兩個字符,，有f(x)<=f(b),，f(y)<=f(c),。首先，在樹T中交換葉子b和x的位置得到T',，然后再樹T'中交換葉子c和y的位置,，得到樹T''。如圖所示：


    由此可知,，樹T和T'的前綴碼的平均碼長之差為：


     因此,，T''表示的前綴碼也是最優(yōu)前綴碼，且x,y具有相同的碼長,，同時,，僅最優(yōu)一位編碼不同。

     4,、最優(yōu)子結(jié)構(gòu)性質(zhì)

     二叉樹T表示字符集C的一個最優(yōu)前綴碼,，x和y是樹T中的兩個葉子且為兄弟，z是它們的父親,。若將z當(dāng)作是具有頻率f(z)=f(x)+f(y)的字符,，則樹T’=T-{x,y}表示字符集C’=C-{x, y} ∪ { z}的一個最優(yōu)前綴碼。因此,，有：


     如果T’不是C’的最優(yōu)前綴碼,，假定T”是C’的最優(yōu)前綴碼，那么有,，顯然T”’是比T更優(yōu)的前綴碼,，跟前提矛盾,！故T'所表示的C'的前綴碼是最優(yōu)的,。

     由貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)可以推出哈夫曼算法是正確的，即HuffmanTree產(chǎn)生的一棵最優(yōu)前綴編碼樹,。

     程序運行結(jié)果如圖：

    本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間,，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點,。請注意甄別內(nèi)容中的聯(lián)系方式,、誘導(dǎo)購買等信息，謹(jǐn)防詐騙,。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,，請點擊一鍵舉報。
    轉(zhuǎn)藏 分享 獻花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多