[数据结构与算法]哈夫曼树及其应用

一、实验目的：
掌握哈夫曼树的构造和应用，利用哈夫曼方法及其编/译码技术实现对传输信息编码/译码系统。

二、实验内容：
1、用静态链表存储哈夫曼树，根据结点字符及其权值构造哈夫曼树，并输出哈夫曼树中所有结点数据值和各字符的哈夫曼编码

哈夫曼节点类

package HuffmanTree;

public class HuffmanNode {
    public int weight;
    public int flag;
    public HuffmanNode parent,lchild,rchild;
    public HuffmanNode(){
        this(0);
    }
    public HuffmanNode(int weight){
        this.weight = weight;
        flag = 0;
        parent = lchild = rchild = null;
    }
}

哈夫曼树类

包括哈夫曼树的构造函数、生成某一个字符的哈夫曼编码函数、输出一颗Huffman的结点数组和所有字符的哈夫曼编码

package HuffmanTree;

import java.util.HashMap;

public class HuffmanTree {
    //求哈夫曼编码
    public int[][] huffmanCoding(int[] W){
       int num = W.length;
        int m = 2 * num - 1;                    //哈夫曼节点数是2 * 叶节点数 - 1
        HuffmanNode[] HN = new HuffmanNode[m];
        int i;
        //构造n个有权值的根结点
        for (i = 0; i < num; i++) {
            HN[i] = new HuffmanNode(W[i]);
        }
        //构造哈夫曼树
        for (i = num;i < m; i++){
            HuffmanNode min1 = selectMin(HN,i - 1);
            min1.flag = 1;
            HuffmanNode min2 = selectMin(HN,i - 1);
            min2.flag = 1;
            HN[i] = new HuffmanNode();
            min1.parent = HN[i];
            min2.parent = HN[i];
            HN[i].lchild = min1;
            HN[i].rchild = min2;
            HN[i].weight = min1.weight + min2.weight;
          
        }
        //从叶子结点到根结点逆向求每个字符的哈夫曼编码
        int[][] HuffCode = new int[num][num];
        for (int j = 0; j < num; j++) {
            int start = num - 1;
            for (HuffmanNode c = HN[j],p = c.parent;p != null;c = p,p = p.parent){
                //左子树编码为0
                if (p.lchild.equals(c)){
                    HuffCode[j][start--] = 0;
                }else {
                    HuffCode[j][start--] = 1;
                }
            }
            //以-1作为编码开始的标识
            HuffCode[j][start] = -1;
        }
        return HuffCode;
    }

    private HuffmanNode selectMin(HuffmanNode[] HN,int end){
        HuffmanNode min = HN[end];
        for (int i = 0;i <= end; i++){
            HuffmanNode h = HN[i];
            if (min.weight > h.weight && h.flag == 0)
                min = h;
        }
        return min;
    }
}

测试

package HuffmanTree;

public class Test {
    public static void main(String[] args) {
        //int[] W = {6,30,8,9,15,24,4,12};
        int[] W = {5,29,7,8,14,23,3,11};
        HuffmanTree T = new HuffmanTree();
        int[][] huffmanCoding = T.huffmanCoding(W);
        System.out.println("哈夫曼编码为：");
        for (int i = 0;i<huffmanCoding.length;i++){
            System.out.print(W[i] + " ");
            for (int j = 0;j<huffmanCoding[i].length;j++){
                if (huffmanCoding[i][j] == -1){
                    for (int k = j + 1;k<huffmanCoding[i].length;k++)
                        System.out.print(huffmanCoding[i][k]);
                    break;
                }
            }
            System.out.println();
        }
    }
}

应用

2、[问题描述]（设计性实验）
哈夫曼树很易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20％至90％，其压缩效率取决于被压缩文件的特征。
请自行设计实现一个将文本压缩为Huffman编码序列、再将压缩的Huffman编码序列解压缩成原文本功能的哈夫曼码的编码/译码系统。并实现以下文本的压缩和解压缩：“this program is my favorite”。

[测试数据]
某文本的字符集为26个英文字母及空格字符，其出现频度如下表所示：

对节点类进行改进

package TextZip;

import HuffmanTree.HuffmanNode;

public class HuffmanNode_Zip extends HuffmanNode {
    public Object name;
    public String huffmanCode;
    public HuffmanNode_Zip(){
    }
    public HuffmanNode_Zip(Object name,int weight){
        this.name = name;
        this.weight = weight;
        flag = 0;
        parent = lchild = rchild = null;
    }
}

注：此代码仅为demo，不建议拷贝，运行尚不能满足所有测试
对应应用的哈夫曼树及哈夫曼编码
算法思路：

1. 先将输入文本的不同字符记录，根据不同字符的数目来创建对应数目的节点，之后构造哈夫曼树及哈夫曼编码。同时因为哈夫曼编码的唯一性，所以通过Hashmap来存储不同字符对应的编码（用于压缩），以及不同编码对应的字符（用于解压缩）

特殊函数展示：

//判断target元素是否在arr数组里面
Arrays.asList(arr).contains(target);

package TextZip;

import HuffmanTree.HuffmanTree;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class HuffmanTree_Zip extends HuffmanTree {
    private String zip_Coding = "";
    private String unzip_Coding = "";
    private HashMap unzip_CodingMap;
    private HashMap zip_CodingMap;

    public int[][] huffmanCoding(String str){

        String[] chars = getChars(str);
        int num = chars.length;
        int m = 2 * num - 1;
        HuffmanNode_Zip[] HN = new HuffmanNode_Zip[m];
        int i;
        //构造n个有名字、有权值的根结点
        for ( i = 0; i < num; i++) {
            switch(chars[i]){
                case " ":
                    HN[i] = new HuffmanNode_Zip(chars[i],186);
                    break;
                case "a":
                    HN[i] = new HuffmanNode_Zip(chars[i],64);
                    break;
                case "b":
                    HN[i] = new HuffmanNode_Zip(chars[i],13);
                    break;
                case "c":
                    HN[i] = new HuffmanNode_Zip(chars[i],22);
                    break;
                case "d":
                    HN[i] = new HuffmanNode_Zip(chars[i],32);
                    break;
                case "e":
                    HN[i] = new HuffmanNode_Zip(chars[i],103);
                    break;
                case "f":
                    HN[i] = new HuffmanNode_Zip(chars[i],21);
                    break;
                case "g":
                    HN[i] = new HuffmanNode_Zip(chars[i],15);
                    break;
                case "h":
                    HN[i] = new HuffmanNode_Zip(chars[i],47);
                    break;
                case "i":
                    HN[i] = new HuffmanNode_Zip(chars[i],57);
                    break;
                case "j":
                    HN[i] = new HuffmanNode_Zip(chars[i],1);
                    break;
                case "k":
                    HN[i] = new HuffmanNode_Zip(chars[i],5);
                    break;
                case "l":
                    HN[i] = new HuffmanNode_Zip(chars[i],32);
                    break;
                case "m":
                    HN[i] = new HuffmanNode_Zip(chars[i],20);
                    break;
                case "n":
                    HN[i] = new HuffmanNode_Zip(chars[i],57);
                    break;
                case "o":
                    HN[i] = new HuffmanNode_Zip(chars[i],63);
                    break;
                case "p":
                    HN[i] = new HuffmanNode_Zip(chars[i],15);
                    break;
                case "q":
                    HN[i] = new HuffmanNode_Zip(chars[i],1);
                    break;
                case "r":
                    HN[i] = new HuffmanNode_Zip(chars[i],48);
                    break;
                case "s":
                    HN[i] = new HuffmanNode_Zip(chars[i],51);
                    break;
                case "t":
                    HN[i] = new HuffmanNode_Zip(chars[i],80);
                    break;
                case "u":
                    HN[i] = new HuffmanNode_Zip(chars[i],23);
                    break;
                case "v":
                    HN[i] = new HuffmanNode_Zip(chars[i],8);
                    break;
                case "w":
                    HN[i] = new HuffmanNode_Zip(chars[i],18);
                    break;
                case "x":
                    HN[i] = new HuffmanNode_Zip(chars[i],1);
                    break;
                case "y":
                    HN[i] = new HuffmanNode_Zip(chars[i],16);
                    break;
                case "z":
                    HN[i] = new HuffmanNode_Zip(chars[i],1);
                    break;
            }
        }
        //构造哈夫曼树
        for (i = num;i<m;i++){
            HuffmanNode_Zip min1 = selectMin(HN,i - 1);
            min1.flag = 1;
            HuffmanNode_Zip min2 = selectMin(HN,i - 1);
            min2.flag = 1;
            HN[i] = new HuffmanNode_Zip();
            min1.parent = HN[i];
            min2.parent = HN[i];
            HN[i].lchild = min1;
            HN[i].rchild = min2;
            HN[i].weight = min1.weight + min2.weight;
        }
        //从叶子结点到根结点逆向求每个字符的哈夫曼编码
        int[][] HuffCode = new int[num][num];
        for (int j = 0; j < num; j++) {
            int start = num - 1;
            for (HuffmanNode_Zip c = HN[j], p = (HuffmanNode_Zip) c.parent; p != null; c = p,p = (HuffmanNode_Zip) p.parent){
                //左子树编码为0
                if (p.lchild.equals(c)){
                    HuffCode[j][start--] = 0;
                }else {
                    HuffCode[j][start--] = 1;
                }
            }
            //以-1作为编码开始的标识
            HuffCode[j][start] = -1;
        }
        return HuffCode;
    }
    private HuffmanNode_Zip selectMin(HuffmanNode_Zip[] HN, int end){
        HuffmanNode_Zip min = HN[end];
        for (int i = 0;i <= end; i++){
            HuffmanNode_Zip h = HN[i];
            if (min.weight > h.weight && h.flag == 0)
                min = h;
        }
        return min;
    }

    public boolean useList(char[] arr,char target){
        return Arrays.asList(arr).contains(target);
    }
    //用集合的元素唯一性，来将所有不重复的字符记录下来
    private String[] getChars(String str){
        int index = 0;
        String[] chars = new String[str.length()];
        for (int i=0;i<str.length();i++){
            if (!Arrays.asList(chars).contains(str.charAt(i)+"")) {
                chars[index] = str.charAt(i)+"";
                index++;
                if (index == 27)
                    break;
            }
        }
        String[] strings = new String[index];
        for (int i=0;i<index;i++){
            strings[i] = chars[i];
        }
        return strings;
    }

    private HashMap zip_CodingMap(String str){
        int[][] hcode = huffmanCoding(str);
        String[] huffmanCoding = new String[hcode.length];
        String[] strings = getChars(str);
        for (int i=0;i<hcode.length;i++)
            huffmanCoding[i] = strings[i];
        for (int i=0;i<hcode.length;i++){
            for (int j=0;j<hcode[i].length;j++){
                if (hcode[i][j] == -1){
                    for (int k = j+1;k<hcode[i].length;k++)
                        huffmanCoding[i] = huffmanCoding[i]+hcode[i][k];
                }
            }
        }
        HashMap<String,String > hashMap = new HashMap<String,String >();
        for (int i=0;i<huffmanCoding.length;i++){
            String key = huffmanCoding[i].substring(0,1);
            String value = huffmanCoding[i].substring(1);
            hashMap.put(key,value);
        }
        zip_CodingMap = hashMap;
        return hashMap;
    }
    private HashMap unzip_CodingMap(String str){
        int[][] hcode = huffmanCoding(str);
        String[] huffmanCoding = new String[hcode.length];
        String[] strings = getChars(str);
        for (int i=0;i<hcode.length;i++)
            huffmanCoding[i] = strings[i];
        for (int i=0;i<hcode.length;i++){
            for (int j=0;j<hcode[i].length;j++){
                if (hcode[i][j] == -1){
                    for (int k = j+1;k<hcode[i].length;k++)
                        huffmanCoding[i] = huffmanCoding[i]+hcode[i][k];
                }
            }
        }
        HashMap<String,String > hashMap = new HashMap<String,String >();
        for (int i=0;i<huffmanCoding.length;i++){
            String key = huffmanCoding[i].substring(1);
            String value = huffmanCoding[i].substring(0,1);
            hashMap.put(key,value);
        }
        unzip_CodingMap = hashMap;
        return hashMap;
    }

    public String zip_Coding(String str){
        HashMap hashMap_zip = zip_CodingMap(str);
        HashMap hashMap_unzip = unzip_CodingMap(str);
        Set<String> keys = hashMap_zip.keySet();
        for (int i=0;i<str.length();i++){
            String key = str.charAt(i)+"";
            zip_Coding = zip_Coding+hashMap_zip.get(key);
        }
        return zip_Coding;
    }

    public String unzip_Coding(String str){
        String string = "";
        if (zip_Coding == "")
            throw new StringIndexOutOfBoundsException("请先进行zip_Coding操作");
        int i;
        int j;
        for (i=0 , j=1;j<str.length();i = j){
            for (;;j++){
                String str2 = str.substring(i,j);
                String coding = (String) unzip_CodingMap.get(str2);
                if (coding != null){
                    string = string+coding;
                    break;
                }
            }
        }
        return string;
    }

    public static void main(String[] args) {
        HuffmanTree_Zip huffmanTree_zip = new HuffmanTree_Zip();
        String str = "abcdefghit   aaabbbccc";

        HashMap hashMap = huffmanTree_zip.zip_CodingMap(str);
        Set<String> keys = hashMap.keySet();
        for (String key : keys){
            System.out.println(key+"="+hashMap.get(key));
        }
        System.out.println("原文本为："+str);
        String zip_coding = huffmanTree_zip.zip_Coding(str);
        String unzip_coding = huffmanTree_zip.unzip_Coding(zip_coding);
        System.out.println("加密为：");
        System.out.print(zip_coding);
        System.out.println();
        System.out.println("解密为：");
        System.out.print(unzip_coding);
    }
}