哈夫曼树

维库，知识与思想的自由文库

哈夫曼编码(Huffman Coding)是一種編碼方式，以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。

在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。

例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

在计算机科学中，“哈夫曼编码”是一种用于无损数据压缩的熵编码（权编码）算法。它使用变长编码表对源符号（如文件中的一个字符）进行编码，其中变长编码表是通过一种基于评估源符号出现几率的方法得到的。该算法是David A. Huffman1952年在麻省理工读博士的时候发明的，并发表于《一种构建极小冗余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。

从树中一个结点到另一个结点之间的构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一结点的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记作 $\sum_{k=1}^n\omega_kl_k$ 。假设有n个权值{ $ω 1,ω 2,$ •••, $ω n$ }，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为ωi，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。赫夫曼树构造的算法（圆圈表示叶结点，方块表示非终端结点）。

/* 赫夫曼树和赫夫曼编码的存储表示 */
typedef struct
{
  unsigned int weight;
  unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */
typedef char **HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */

/* 求赫夫曼编码 */
#include"c1.h"
#include"c6-7.h"
#include"func6-1.c"
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) /* 算法6.12 */
{ /* w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC */
  int m,i,s1,s2,start;
  unsigned c,f;
  HuffmanTree p;
  char *cd;
  if(n<=1)
    return;
  m=2*n-1;
  *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
  for(p=*HT+1,i=1;i<=n;++i,++p,++w)
  {
    (*p).weight=*w;
    (*p).parent=0;
    (*p).lchild=0;
    (*p).rchild=0;
  }
  for(;i<=m;++i,++p)
    (*p).parent=0;
  for(i=n+1;i<=m;++i) /* 建赫夫曼树 */
  { /* 在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 */
    select(*HT,i-1,&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;
  }
  /* 从叶子到根逆向求每个字符的赫夫曼编码 */
  *HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
  /* 分配n个字符编码的头指针向量([0]不用) */
  cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
  cd[n-1]='\0'; /* 编码结束符 */
  for(i=1;i<=n;i++)
  { /* 逐个字符求赫夫曼编码 */
    start=n-1; /* 编码结束符位置 */
    for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)
    /* 从叶子到根逆向求编码 */
      if((*HT)[f].lchild==c)
        cd[--start]='0';
      else
        cd[--start]='1';
    (*HC)[i]=(char*)malloc((n-start)*sizeof(char));
    /* 为第i个字符编码分配空间 */
    strcpy((*HC)[i],&cd[start]); /* 从cd复制编码(串)到HC */
  }
  free(cd); /* 释放工作空间 */
}
void main()
{
  HuffmanTree HT;
  HuffmanCode HC;
  int *w,n,i;
  printf("请输入权值的个数(>1): ");
  scanf("%d",&n);
  w=(int*)malloc(n*sizeof(int));
  printf("请依次输入%d个权值(整型):\n",n);
  for(i=0;i<=n-1;i++)
    scanf("%d",w+i);
  HuffmanCoding(&HT,&HC,w,n);
  for(i=1;i<=n;i++)
    puts(HC[i]);
}

/*无栈非递归遍历赫夫曼树，求赫夫曼编码*/
#include"c1.h"
#include"c6-7.h"
#include"func6-1.c"
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) */
{ /* w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC */
  int m,i,s1,s2; /* 此句与algo6-1.c不同 */
  unsigned c,cdlen; /* 此句与algo6-1.c不同 */
  HuffmanTree p;
  char *cd;
  if(n<=1)
    return;
  m=2*n-1;
  *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
  for(p=*HT+1,i=1;i<=n;++i,++p,++w)
  {
    (*p).weight=*w;
    (*p).parent=0;
    (*p).lchild=0;
    (*p).rchild=0;
  }
  for(;i<=m;++i,++p)
    (*p).parent=0;
  for(i=n+1;i<=m;++i) /* 建赫夫曼树 */
  { /* 在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 */
    select(*HT,i-1,&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;
  }
  /* 以下为算法6.13，无栈非递归遍历赫夫曼树，求赫夫曼编码，以上同算法6.12 */
  *HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
  /* 分配n个字符编码的头指针向量([0]不用) */
  cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
  c=m;
  cdlen=0;
  for(i=1;i<=m;++i)
    (*HT)[i].weight=0; /* 遍历赫夫曼树时用作结点状态标志 */
  while(c)
  {
    if((*HT)[c].weight==0)
    { /* 向左 */
      (*HT)[c].weight=1;
      if((*HT)[c].lchild!=0)
      {
        c=(*HT)[c].lchild;
        cd[cdlen++]='0';
      }
      else if((*HT)[c].rchild==0)
      { /* 登记叶子结点的字符的编码 */
        (*HC)[c]=(char *)malloc((cdlen+1)*sizeof(char));
        cd[cdlen]='\0';
        strcpy((*HC)[c],cd); /* 复制编码(串) */
      }
    }
    else if((*HT)[c].weight==1)
    { /* 向右 */
      (*HT)[c].weight=2;
      if((*HT)[c].rchild!=0)
      {
        c=(*HT)[c].rchild;
        cd[cdlen++]='1';
      }
    }
    else
    { /* HT[c].weight==2，退回 */
      (*HT)[c].weight=0;
      c=(*HT)[c].parent;
      --cdlen; /* 退到父结点，编码长度减1 */
    }
  }
  free(cd);
}
void main()
{ /* 主程序同algo6-1.c */
  HuffmanTree HT;
  HuffmanCode HC;
  int *w,n,i;
  printf("请输入权值的个数(>1): ");
  scanf("%d",&n);
  w=(int *)malloc(n*sizeof(int));
  printf("请依次输入%d个权值(整型):\n",n);
  for(i=0;i<=n-1;i++)
    scanf("%d",w+i);
  HuffmanCoding(&HT,&HC,w,n);
  for(i=1;i<=n;i++)
    puts(HC[i]);
}