从0开始实现Huffman编码

更新时间:2020-07-23 10:31:57点击次数:335次
1951年,哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。Huffman在划水划了一学期自认为啥也没学到不敢考试,自然就选择了用论文的方式逃避考试。导师Robert M. Fano给他们的学期报告的题目是,寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的,哈夫曼放弃对已有编码的研究,转向新的探索,最终发现了基于有序频率二叉树编码的想法,并很快证明了这个方法是最有效的。由于这个算法,学生终于青出于蓝,超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树,避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。

我们开始今天的主角终于登场了:Huffman编码

先说说Huffman编码的一般过程,首先我们的输入是一串字符串

对字符串统计每一个字符出现的频率
根据频率排序,弹出频率最小的两个,组成一颗二叉树的两个子节点,他们的父节点表示的值为这两个频率之和
重复2直到最后只剩下一颗二叉树,这个树我们成为Huffman树,也叫最优二叉树
这颗二叉树的每一个非叶节点,对节点的左右两个方向编0或1(左边编0右边编1,或者左边编1右边编0,我们这里采用前者来示范)
然后我们就可以找到每一个字符对应的编码啦

下面就以“interesting”为例使用Huffman编码压缩


首先我们找到了出现次数最少的两个字符:“g”和“r”各出现了一次,我们把它们组成一颗二叉树,“g”和“r”所在的为叶节点,节点对应数据为1和1,他们的父节点表示的值为1+1=21+1=21+1=2。

现在我们相当于还剩6个节点,找出其中值最小的两个,其一是我们上一步得到的2(这里选择代表“n”的2或者代表“i“的2都是可以的,达到的效果是一样的),还一个是代表“s”的1。我们把它们作为两个子节点组成二叉树,新的父节点的值为3。

现在我们发现”n“和”i“都是2,这是最少的两个,把它们重复上述操作得到一个值为4的节点。这时”e“和”t“都是2,这是最少的两个,把它们重复上述操作得到一个值为4的节点。然后上一段得到的3,和”n“和”i“得到的4是最小的两个,得到7,再与”e“和”t“得到的4合并,得到值为11的节点。至此,我们的Huffman树建好了,这个树的每一个叶节点代表一个字符。接下来我们进行第四步—赋值。

这里我们假设左边赋值为0,右边赋值为1,我们就得到了如下编码

字符 出现次数 Huffman编码
i 2 111
n 2 110
t 2 01
e 2 00
r 1 1011
s 1 100
g 1 1010
这种编码所占空间大小为 2×3+2×3+2×2+2×2+1×4+1×3+1×4=31(bit)\ 2\times 3+2\times 3+2\times 2+2\times 2+1\times 4+1\times 3+1\times 4=31(bit) 2×3+2×3+2×2+2×2+1×4+1×3+1×4=31(bit),看,是不是比原来的33少一些了,而且也没有发生上述开头重复的问题。

Java代码实现
首先我们创建一个Huffman树类,由于要第二步我们要进行排序比较大小,所以这个类要实现Comparable接口。本类对象包含六个个属性,count为节点的值,s为节点表示的字符,code为节点对应的编码,注意,后面两个属性只有叶节点才有。另外三个属性则是左子节点、右子节点、父节点(注,一般来说二叉树是只用设计左右节点即可,这里为了下文编写方便也设了父节点)

//定义这个类是为了把字符串转换成一个String数组和一个int数组,其中int数组存放的是对应string在字符串中的出现的次数(其实这里把String数组改成char数组更好,但是我懒得改了嘿嘿)
class TransferString{
    int[] nl;
    String[] sl;
    public TransferString(int[] nl,String[] sl){
        this.nl = nl;
        this.sl = sl;
    }
}

//这个就是Huffman树节点类啦
class HTreeNode implements Comparable<HTreeNode>{
  
    Integer count;
    String s;
    String code = "";

    HTreeNode left;
    HTreeNode right;
    HTreeNode parent;

  //构造方法1
    public HTreeNode(int count){
        this.count = count;
    }
  
    //构造方法2
    public HTreeNode(int count,String s){
        this.count = count;
        this.s = s;
    }

    @Override
    public int compareTo(HTreeNode h) {
        return this.count.compareTo(h.count);
    }
}

ps:注意到count的类型是Integer而不是int,读者可自行查找一下两个数据类型的关系,int是不能compareTo的,但是Integer可以

下面是主体

import java.util.PriorityQueue;
import java.util.Queue;

public class Test {

  //输入字符串,返回上述两个数组
    private static TransferString transferString(String s){
        char[] cl = s.toCharArray();
        int[] counts = new int[26];

        //数出每一个字母的频率
        for(int i = 0; i < cl.length; i++) {
            counts[cl[i] - 'a']++; // 'b' - 'a' = 1
        }

        //创建字母标准表
        String[] std = "abcdefghijklmnopqrstuvwxyz".split("");

        //数出不存在字母个数
        int Number_Of_Zero=0;
        for(int i=0;i<counts.length;i++){
            if(counts[i]==0){
                Number_Of_Zero++;
            }
        }

        //定义新数组
        int[] nl = new int[counts.length-Number_Of_Zero];
        String[] sl = new String[counts.length-Number_Of_Zero];
        int j=0; // 新数组的索引
        for(int i=0;i<counts.length;i++){ // 遍历原来旧的数组
            if(counts[i]!=0){ // 假如不等于0
                nl[j]= counts[i];
                sl[j]= std[i];// 赋值给新的数组
                j++;
            }
        }

        return new TransferString(nl,sl);
    }

  //通过两个数组,创建以Huffman树节点为元素的优先队列
    private static Queue<HTreeNode> init(TransferString ts){
        int[]    ca = ts.nl;
        String[] sa = ts.sl;
        Queue<HTreeNode> q = new PriorityQueue<HTreeNode>();
        for(int i=0;i<ca.length;i++){
            HTreeNode h = new HTreeNode(ca[i],sa[i]);
            q.add(h);
        }

        return q;
    }

//更新,对应于第三步
    public static void update(Queue<HTreeNode> q){
        HTreeNode a = q.poll();
        HTreeNode b = q.poll();
        HTreeNode c = new HTreeNode(a.count+b.count);
        c.left  = a;
        c.right = b;
        a.parent = c;
        b.parent = c;
        q.add(c);

    }

  //左边编0右边编1,对树进行编码
    private static void printTreeCode(HTreeNode t){

        if(t.left!=null){
            t.left.code += t.code+"0";
            printTreeCode(t.left);
        }

        if(t.right!=null){
            t.right.code += t.code+"1";
            printTreeCode(t.right);
        }


    }

  
    
  //用来输出树的节点对应的编码
    private static void traversing(HTreeNode t){
      
        if(t.s!=null){
            System.out.println(t.s+" 的Huffman编码为:"+t.code);
        }
       
        if (t.left!=null){
            traversing(t.left);
        }

        if (t.right!=null){
            traversing(t.right);
        }

    }

  //主函数
    public static void main(String[] args){
      
      //输入字符串”interesting”
        TransferString ts = transferString("interesting");
        Queue<HTreeNode> q = init(ts);
        while (q.size()>1){
            update(q);
        }
        HTreeNode t = q.poll();
        printTreeCode(t);
        traversing(t);

    }

}

代码执行效果

e 的Huffman编码为:00
t 的Huffman编码为:01
s 的Huffman编码为:100
g 的Huffman编码为:1010
r 的Huffman编码为:1011
n 的Huffman编码为:110
i 的Huffman编码为:111

本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责,本站只提供参考并不构成任何投资及应用建议。本站是一个个人学习交流的平台,网站上部分文章为转载,并不用于任何商业目的,我们已经尽可能的对作者和来源进行了通告,但是能力有限或疏忽,造成漏登,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

  • 项目经理 点击这里给我发消息
  • 项目经理 点击这里给我发消息
  • 项目经理 点击这里给我发消息
  • 项目经理 点击这里给我发消息