霍夫曼编码(Huffman Coding)

霍夫曼编码(Huffman Coding)是一种编码方法,霍夫曼编码是可变字长编码(VLC)的一种。

霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。

霍夫曼编码的具体步骤如下:

1)将信源符号的概率按减小的顺序排队。

2)把两个最小的概率相加,并继续这一步骤,始终将较高的概率分支放在右边,直到最后变成概率1。

3)画出由概率1处到每个信源符号的路径,顺序记下沿路径的0和1,所得就是该符号的霍夫曼码字。

4)将每对组合的左边一个指定为0,右边一个指定为1(或相反)。

例:现有一个由5个不同符号组成的30个符号的字符串:

BABACAC ADADABB CBABEBE DDABEEEBB

1首先计算出每个字符出现的次数(概率):

霍夫曼编码(Huffman Coding)

2把出现次数(概率)最小的两个相加,并作为左右子树,重复此过程,直到概率值为1

霍夫曼编码(Huffman Coding)

第一次:将概率最低值3和4相加,组合成7:

霍夫曼编码(Huffman Coding)
 

第二次:将最低值5和7相加,组合成12:

霍夫曼编码(Huffman Coding)

第三次:将8和10相加,组合成18:

霍夫曼编码(Huffman Coding)

第四次:将最低值12和18相加,结束组合:

霍夫曼编码(Huffman Coding)

3 将每个二叉树的左边指定为0,右边指定为1

霍夫曼编码(Huffman Coding)

4 沿二叉树顶部到每个字符路径,获得每个符号的编码

霍夫曼编码(Huffman Coding)

我们可以看到出现次数(概率)越多的会越在上层,编码也越短,出现频率越少的就越在下层,编码也越长。当我们编码的时候,我们是按“bit”来编码的,解码也是通过bit来完成,如果我们有这样的bitset “10111101100″ 那么其解码后就是 “ABBDE”。所以,我们需要通过这个二叉树建立我们Huffman编码和解码的字典表。

这里需要注意的是,Huffman编码使得每一个字符的编码都与另一个字符编码的前一部分不同,不会出现像’A’:00,  ’B’:001,这样的情况,解码也不会出现冲突。

霍夫曼编码的局限性

利用霍夫曼编码,每个符号的编码长度只能为整数,所以如果源符号集的概率分布不是2负n次方的形式,则无法达到熵极限;输入符号数受限于可实现的码表尺寸;译码复杂;需要实现知道输入符号集的概率分布;没有错误保护功能。

霍夫曼编码实现 (C++实现):

 
  1. int main()
  2. {
  3. int n, w;
  4. char c;
  5. string s;
  6. cout << "input size of char : ";
  7. cin >> n;
  8. BinartNodes bn;
  9. for(int i = 0; i != n; ++i)
  10. {
  11. cout << "input char and weight: ";
  12. cin >> c >> w;
  13. bn.add_Node((Node(c, w)));
  14. cin.clear();
  15. }
  16. while(bn.size() != 1)
  17. {
  18. Node n1 = bn.pop(),     //获取前两个权重最小的结点
  19. n2 = bn.pop();
  20. Node h(' ', n1.get_weight() + n2.get_weight());     //新建结点,权重为前两个结点权重和
  21. if( n1.get_weight() < n2.get_weight())      //权重较小的结点在新结点左边
  22. {
  23. h.set(n1, n2);      //设置新结点左右子结点
  24. }
  25. else
  26. {
  27. h.set(n2, n1);
  28. }
  29. bn.add_Node(h);     //将新结点插入到multiset中
  30. }
  31. encodeing(bn.get_Node(), s);    //编码
  32. cout << "input huffman code: ";
  33. cin >> s;
  34. cout << "decoded chars: ";
  35. decoding(bn.get_Node(), s);     //解码
  36. }

Handle.h句柄类:

  1. /*Handle.h*/
  2. //句柄模型类
  3. template <class Type> class Handle{
  4. public:
  5. Handle(Type *ptr = 0): pn(ptr), use(new size_t(1)) {}
  6. Type& operator*();      //重载操作符*
  7. Type* operator->();     //重载操作符->
  8. const Type& operator*() const;
  9. const Type* operator->() const;
  10. Handle(const Handle &h): pn(h.pn), use(h.use) { ++*use; }   //复制操作
  11. Handle& operator=(const Handle &h);     //重载操作符=,赋值操作
  12. ~Handle() {rem_ref(); }     //析构函数
  13. private:
  14. Type *pn;   //对象指针
  15. size_t *use;    //使用次数
  16. void rem_ref()
  17. {
  18. if (--*use == 0)
  19. {delete pn; delete use; }
  20. }
  21. };
  22. template <class Type> inline Type& Handle<Type>::operator*()
  23. {
  24. if (pn) return *pn;
  25. throw runtime_error("dereference of unbound Handle");
  26. }
  27. template <class Type> inline const Type& Handle<Type>::operator*() const
  28. {
  29. if (pn) return *pn;
  30. throw runtime_error("dereference of unbound Handle");
  31. }
  32. template <class Type> inline Type* Handle<Type>::operator->()
  33. {
  34. if (pn) return pn;
  35. throw runtime_error("access through unbound handle");
  36. }
  37. template <class Type> inline const Type* Handle<Type>::operator->() const
  38. {
  39. if (pn) return pn;
  40. throw runtime_error("access through unbound handle");
  41. }
  42. template <class Type> inline Handle<Type>& Handle<Type>::operator=(const Handle &rhs)
  43. {
  44. ++*rhs.use;
  45. rem_ref();
  46. pn = rhs.pn;
  47. use = rhs.use;
  48. return *this;
  49. }
Node.h结点类:
 
  1. /*Node.h*/
  2. template <class T> class Handle;
  3. class Node{
  4. friend class Handle<Node>;  //句柄模型类
  5. public:
  6. Node():ch(' '),wei(0), bits(), lc(), rc(){}
  7. Node(const char c, const int w):
  8. ch(c), wei(w), bits(), lc(), rc(){}
  9. Node(const Node &n){ch = n.ch; wei = n.wei; bits = n.bits;
  10. lc = n.lc; rc = n.rc; }
  11. virtual Node* clone()const {return new Node( *this);}
  12. int get_weight() const {return wei;}    //获取权重
  13. char get_char() const {return ch; }     //获得字符
  14. Node &get_lchild() {return *lc; }       //获得左结点
  15. Node &get_rchild() {return *rc; }       //获得右结点
  16. void set(const Node &l, const Node &r){     //设置左右结点
  17. lc = Handle<Node>(new Node(l));
  18. rc = Handle<Node>(new Node(r));}
  19. void set_bits(const string &s){bits = s; }      //设置编码
  20. private:
  21. char ch;    //字符
  22. int wei;    //权重
  23. string bits;    //编码
  24. Handle<Node> lc;    //左结点句柄
  25. Handle<Node> rc;    //右结点句柄
  26. };
  27. inline bool compare(const Node &lhs, const Node &rhs);      //multiset比较函数
  28. inline bool compare(const Node &lhs, const Node &rhs)
  29. {
  30. return lhs.get_weight()  < rhs.get_weight();
  31. }
  32. class BinartNodes{
  33. typedef bool (*Comp)(const Node&, const Node&);
  34. public:
  35. BinartNodes():ms(compare) {}    //初始化ms的比较函数
  36. void add_Node(Node &n){ms.insert(n); }      //增加Node结点
  37. Node pop();     //出结点
  38. size_t size(){return ms.size(); }   //获取multiset大小
  39. Node get_Node() {return *ms.begin();}       //获取multiset第一个数据
  40. private:
  41. multiset<Node, Comp> ms;
  42. };
  43. /*Node.cpp*/
  44. #include "Node.h"
  45. Node BinartNodes::pop()
  46. {
  47. Node n = *ms.begin();   //获取multiset第一个数据
  48. ms.erase(ms.find(*ms.begin()));     //从multiset中删除该数据
  49. return n;
  50. }

霍夫曼编码(Huffman Coding)

霍夫曼编码(Huffman Coding)

霍夫曼编码实现 (C语言实现):

 
    1. #include <stdio.h>
    2. #include<stdlib.h>
    3. #include<string>
    4. #include <iostream>
    5. #define MAXBIT      100
    6. #define MAXVALUE  10000
    7. #define MAXLEAF     30
    8. #define MAXNODE    MAXLEAF*2 -1
    9. typedef struct
    10. {
    11. int bit[MAXBIT];
    12. int start;
    13. } HCodeType;        /* 编码结构体 */
    14. typedef struct
    15. {
    16. int weight;
    17. int parent;
    18. int lchild;
    19. int rchild;
    20. char value;
    21. } HNodeType;        /* 结点结构体 */
    22. /* 构造一颗哈夫曼树 */
    23. void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n)
    24. {
    25. /* i、j: 循环变量,m1、m2:构造哈夫曼树不同过程中两个最小权值结点的权值,
    26. x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
    27. int i, j, m1, m2, x1, x2;
    28. /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
    29. for (i=0; i<2*n-1; i++)
    30. {
    31. HuffNode[i].weight = 0;//权值
    32. HuffNode[i].parent =-1;
    33. HuffNode[i].lchild =-1;
    34. HuffNode[i].rchild =-1;
    35. HuffNode[i].value=' '; //实际值,可根据情况替换为字母
    36. } /* end for */
    37. /* 输入 n 个叶子结点的权值 */
    38. for (i=0; i<n; i++)
    39. {
    40. printf ("Please input char of leaf node: ", i);
    41. scanf ("%c",&HuffNode[i].value);
    42. getchar();
    43. } /* end for */
    44. for (i=0; i<n; i++)
    45. {
    46. printf ("Please input  weight of leaf node: ", i);
    47. scanf ("%d",&HuffNode[i].weight);
    48. getchar();
    49. } /* end for */
    50. /* 循环构造 Huffman 树 */
    51. for (i=0; i<n-1; i++)
    52. {
    53. m1=m2=MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
    54. x1=x2=0;
    55. /* 找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树 */
    56. for (j=0; j<n+i; j++)
    57. {
    58. if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
    59. {
    60. m2=m1;
    61. x2=x1;
    62. m1=HuffNode[j].weight;
    63. x1=j;
    64. }
    65. else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
    66. {
    67. m2=HuffNode[j].weight;
    68. x2=j;
    69. }
    70. } /* end for */
    71. /* 设置找到的两个子结点 x1、x2 的父结点信息 */
    72. HuffNode[x1].parent  = n+i;
    73. HuffNode[x2].parent  = n+i;
    74. HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
    75. HuffNode[n+i].lchild = x1;
    76. HuffNode[n+i].rchild = x2;
    77. printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */
    78. printf ("\n");
    79. } /* end for */
    80. } /* end HuffmanTree */
    81. //解码
    82. void decodeing(char string[],HNodeType Buf[],int Num)
    83. {
    84. int i,tmp=0,code[1024];
    85. int m=2*Num-1;
    86. char *nump;
    87. char num[1024];
    88. for(i=0;i<strlen(string);i++)
    89. {
    90. if(string[i]=='0')
    91. num[i]=0;
    92. else
    93. num[i]=1;
    94. }
    95. i=0;
    96. nump=&num[0];
    97. while(nump<(&num[strlen(string)]))
    98. {tmp=m-1;
    99. while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
    100. {
    101. if(*nump==0)
    102. {
    103. tmp=Buf[tmp].lchild ;
    104. }
    105. else tmp=Buf[tmp].rchild;
    106. nump++;
    107. }
    108. printf("%c",Buf[tmp].value);
    109. }
    110. }
    111. int main(void)
    112. {
    113. HNodeType HuffNode[MAXNODE];            /* 定义一个结点结构体数组 */
    114. HCodeType HuffCode[MAXLEAF],  cd;       /* 定义一个编码结构体数组, 同时定义一个临时变量来存放求解编码时的信息 */
    115. int i, j, c, p, n;
    116. char pp[100];
    117. printf ("Please input n:\n");
    118. scanf ("%d", &n);
    119. HuffmanTree (HuffNode, n);
    120. for (i=0; i < n; i++)
    121. {
    122. cd.start = n-1;
    123. c = i;
    124. p = HuffNode[c].parent;
    125. while (p != -1)   /* 父结点存在 */
    126. {
    127. if (HuffNode[p].lchild == c)
    128. cd.bit[cd.start] = 0;
    129. else
    130. cd.bit[cd.start] = 1;
    131. cd.start--;        /* 求编码的低一位 */
    132. c=p;
    133. p=HuffNode[c].parent;    /* 设置下一循环条件 */
    134. } /* end while */
    135. /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
    136. for (j=cd.start+1; j<n; j++)
    137. { HuffCode[i].bit[j] = cd.bit[j];}
    138. HuffCode[i].start = cd.start;
    139. } /* end for */
    140. /* 输出已保存好的所有存在编码的哈夫曼编码 */
    141. for (i=0; i<n; i++)
    142. {
    143. printf ("%d 's Huffman code is: ", i);
    144. for (j=HuffCode[i].start+1; j < n; j++)
    145. {
    146. printf ("%d", HuffCode[i].bit[j]);
    147. }
    148. printf(" start:%d",HuffCode[i].start);
    149. printf ("\n");
    150. }
    151. printf("Decoding?Please Enter code:\n");
    152. scanf("%s",&pp);
    153. decodeing(pp,HuffNode,n);
    154. getchar();
    155. return 0;
    156. }
上一篇:OC跟Swift混编


下一篇:oc工程中oc、swift混编代码打包成静态framework踩坑笔记