哈夫曼树与文件压缩笔记

Scroll Down

哈夫曼树

哈夫曼编码

哈夫曼编码是一种变长的编码,数据的编码因其使用频率而长短不一,使用频率高的数据编码较短,使用频率高的数据编码较长。

哈夫曼树的构造算法

哈夫曼树的定义

最优二叉树

  1. 带权路径长度WPL最小的二叉树称为哈夫曼树

构造哈夫曼树

  1. 将有权值的叶节点从大到小排成一个有序的序列
  2. 将权值最小的两个节点作为一个新节点的两个子节点
  3. 将刚刚两个权值最小的两个节点去掉,加进去新合成的两个节点(保持排序)
  4. 重复上述两步

哈夫曼树的设计

我们用一个静态表来标识这棵哈夫曼树,因为我们几乎不会去增加或者删除:

public class TriElement {
    int data;
    int parent;
    int left;
    int right;
}
dataparentleftright

在一开始我们用一个数组来表示这些TriElement

数组的长度

设需要编码的元素集合为n
那么根据二叉树的性质,哈夫曼树是没有一度结点的,所以哈夫曼树的结点个数为2n-1

例子

我们用一个序列来举例

AAAABBBCDDBBAAA

初始化

我们再使用两个映射来分别存放编码元素的统计数据和每个字符对应的索引

int index=0;
this.huftree = new TriElement[2*n-1];   //静态的结点数组
this.charIntegerMap=statistic(text);            //statistic为统计函数,text为文本,charIntegerMap为字符的统计映射
//初始化
for (Map.Entry<Character, Integer> characterIntegerEntry : statisticMap.entrySet()) {
   Integer value = characterIntegerEntry.getValue();
   Character key = characterIntegerEntry.getKey();
   huftree[index] = new TriElement(value);
   charIntegerMap.put(key,index);       //字符索引映射
   index++;
   charset+=key;
}

构造哈夫曼树

先放上代码

for (int i=n;i<2*n-1;i++)
{
   int min1 = Integer.MAX_VALUE;
   int min2 = Integer.MAX_VALUE;
   int x1 = -1;
   int x2 = -1;
   for (int j=0;j<i;j++)
   {
       //选出最小值
       if (this.huftree[j].parent==-1)
       {
           if (this.huftree[j].data<min1)
           {
               min2=min1;          //原来的最小值变为次小值
               x2=x1;
               min1 = this.huftree[j].data;
               x1 = j;
           }else if (this.huftree[j].data<min2)
           {
               min2 = huftree[j].data;
               x2 = j;
           }
       }
   }
   this.huftree[x1].parent = i;
   this.huftree[x2].parent = i;
   this.huftree[i] = new TriElement(min1+min2,-1,x1,x2);
}

我们要做的就是选出最小值和次小值,并合成成新的结点,最小值为新节点的左孩子,次小值为右孩子,然后去除掉用来合成的两个结点

注意点

这个算法如果出现两个点权值相同,会优先考虑子树较少的那一个

编码

private String getCode(int i)
{
  int n = getHeight(huftree.length-1);
  char hufCode[] = new char[n];
  int child = i,parent= huftree[i].parent;
  for (i=n-1;parent!=-1;i--)
  {
      hufCode[i] = (huftree[parent].left==child)?'0':'1';     //左孩子编码为‘0’,右孩子编码为‘1’
      child = parent;
      parent = huftree[child].parent;
  }
  return new String(hufCode,i+1,n-1-i);
}

我们采用一个栈,或者一个数组来反向地进行存储。
在这里我们使用一个数组来存储,我们知道,编码最长为哈夫曼树的高度,所以我们声明一个树的高度那么长的数组就可以。

一棵构造好的哈夫曼树
indexdataparentleftright
058-1-1
1298-1-1
279-1-1
389-1-1
41411-1-1
52312-1-1
638-1-1
71110-1-1
881060
9151123
10191287
11291349
1242141015
135814111
14100-11213

编码是一个向上寻找的过程
我们先找到我们要编码的那个点的索引,然后寻找他的父母,我们约定左子树编码为0,右子树编码为1,直到找到根节点为止

解码过程

public String decode(String compressed){
  String text = "";
  int node = this.huftree.length-1;
  for (int i = 0;i<compressed.length();i++)
  {
      if (compressed.charAt(i)=='0')
          node = huftree[node].left;
      else
          node = huftree[node].right;
      if (huftree[node].isLeaf())
      {
          text+=this.charset.charAt(node);
          node = this.huftree.length-1;
      }
  }
  return text;
}

解码是一个自上而下的过程
从根节点开始,如果为1就走右子树,如果为0,就走左子树,直到走到叶子结点为止