数据结构—哈夫曼编码

﹏ヽ暗。殇╰゛Y 2022-04-06 07:14 226阅读 0赞

## 数据结构—哈夫曼编码 ##

**1.哈夫曼树简介**  
哈夫曼（Huffman）编码算法是基于二叉树构建编码压缩结构的，它是数据压缩中经典的一种算法。算法根据文本字符出现的频率，重新对字符进行编码。因为为了缩短编码的长度，我们自然希望**频率越高**的词，**编码越短**，这样最终才能最大化压缩存储文本数据的空间。

我们使用二叉树来构建哈夫曼树并生成哈夫曼编码. 实际上,哈夫曼树构造的过程就是最优二叉树的构建过程.例如:如果\{a,b,c,d,e\} 的权值为 \{5,8,2,10,13\},则生成的最优二叉树为:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70]  
生成哈夫曼树之后,各个需要编码的元素的编码也就得到了:  
a:001, b:01, c:000, d:10, e:11  
我们可以发现哈夫曼树有一些特点:

*  每个需要编码的元素在哈夫曼树中都是作为叶子节点(避免出现前缀冲突)
 *  元素的权值越大,编码也就越短(频率越高,编码越短)

**2.java实现哈弗曼编码**  
要实现哈夫曼编码,首先要构造出一颗哈夫曼树,那么应该采取怎么样的方法呢?继续使用之前的链式表示吗?仔细想一想,之前使用链式表示二叉树时,我们是从上向下构造二叉树的,但是现在如果要构造哈夫曼树,要遵循构造最优二叉树的规则,所以是从下向上构造整颗树的,所以,这里我们用双亲孩子表示法,用类型数组来表示整颗哈夫曼树

*  数据结构:

/**
     * 哈夫曼树每个节点的数据结构
     */
    class HfTree {
        char charset;
        int weight;
        int parent;
        int leftChild;
        int rightChild;
    
        public HfTree() {
            this.parent = -1;
            this.leftChild = -1;
            this.rightChild = -1;
        }
    
        @Override
        public String toString() {
            return " " + charset +
                    "," + weight +
                    "," + parent +
                    "," + leftChild +
                    "," + rightChild;
        }
    }

/**
     * 哈夫曼编码的数据结构
     */
    class HfCode {
        char charset;
        int index;
        Deque code;
    
        public HfCode() {
        }
    
        public HfCode(char charset, int index) {
            this.charset = charset;
            this.index = index;
        }
    }

**构造哈夫曼树的过程:**

/**
         * 构造哈夫曼树
         * @param ht
         * @param n
         */
        public static void createHuffmanTree(HfTree[] ht, int n) {
            for (int i = n; i < 2*n-1; i++) {
                ht[i] = new HfTree();
            }
            for (int i = n; i < 2*n-1; i++) {
                MyMin m = select(ht,i-1);
                ht[i].weight = ht[m.min].weight + ht[m.nextMin].weight;
                ht[i].leftChild = m.min;
                ht[i].rightChild = m.nextMin;
                ht[m.min].parent = i;
                ht[m.nextMin].parent = i;
            }
        }

Mymin这个类型里面封装了两个int类型的数据,min与nextMin,分别表示最小值与次小值

将n个元素放入HfTree\[\]中,然后从下标n+1开始,每次选中前面节点中的两个最小的节点,将他们的parent值改为当前的下标,并且将当前元素的左右孩子分别改成刚才得到的两个最小节点的下标. 然后继续循环找没有parent值的最小的两个节点,重复上述过程.

**生成哈夫曼编码:**

利用构造好的哈夫曼树,要得到每个元素对应的哈夫曼编码, 如果我们从根节点出发,那么每次都要判断不同的0 , 1,最后才能知道是哪一个元素.这样很不方便.所以我们从叶子节点开始,向上扫描. 扫描到的0 和1 压入对应的栈中,这样就能的到每一个元素的哈夫曼编码

public static HfCode[] createHuffmanCode(HfTree[] ht, int n) {
            HfCode[] hfCode = new HfCode[n];
            for (int i = 0; i < n; i++) {
                hfCode[i] = new HfCode(ht[i].charset,i);
                Deque code = new ArrayDeque();
                int set = i;
                int parent = ht[i].parent;
                while (parent != -1) {
                    if (ht[parent].leftChild == set) {
                        code.push("0");
                    } else {
                        code.push("1");
                    }
                    set = parent;
                    parent = ht[parent].parent;
                }
                hfCode[i].code = code;
            }
            return hfCode;
        }

生成了所有元素对应的编码之后,就可以对一些字符进行编码解码了,例如:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70 1]

整体的代码如下:

public class HuffmanTree {
    
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
    //        System.out.print("请输入字符集大小n:");
    //        int n = scan.nextInt();
    //        HfTree[] ht = new HfTree[2*n-1];//存储字符节点及内部节点
    //
    //        for (int i = 0; i < n; i++) {
    //            ht[i] = new HfTree();
    //            System.out.print("请输入第" + (i+1) + "个字符:");
    //            ht[i].charset = scan.next().charAt(0);
    //            System.out.print("请输入第" + (i+1) + "个字符的权值:");
    //            ht[i].weight = scan.nextInt();
    //        }
    
    //        //构造哈夫曼树结构
    //        createHuffmanTree(ht,n);
    //        System.out.println("哈夫曼树结构:");
    //        for (int i = 0; i < 2*n-1; i++) {
    //            System.out.println(ht[i]);
    //        }
    //        System.out.println("各个字符编码");
    //        //生成哈夫曼编码
    //        HfCode[] hfCode = createHuffmanCode(ht,n);
    //        for (int i = 0; i < n; i++) {
    //            System.out.println("" + hfCode[i].charset + hfCode[i].code);
    //        }
            System.out.print("请输入需要编码的数据:");
            String str = scan.next();
            //编码
            HfTree[] ht = null;
            ht = coding(str);
    
            System.out.println();
            System.out.print("请输入需要译码的数据:");
            String str2 = scan.next();
            decoding(str2,ht);
        }
    
        /**
         * 构造哈夫曼树
         * @param ht
         * @param n
         */
        public static void createHuffmanTree(HfTree[] ht, int n) {
            for (int i = n; i < 2*n-1; i++) {
                ht[i] = new HfTree();
            }
            for (int i = n; i < 2*n-1; i++) {
                MyMin m = select(ht,i-1);
                ht[i].weight = ht[m.min].weight + ht[m.nextMin].weight;
                ht[i].leftChild = m.min;
                ht[i].rightChild = m.nextMin;
                ht[m.min].parent = i;
                ht[m.nextMin].parent = i;
            }
        }
    
        /**
         * 生成哈夫曼编码
         * @param ht
         * @param n
         * @return
         */
        public static HfCode[] createHuffmanCode(HfTree[] ht, int n) {
            HfCode[] hfCode = new HfCode[n];
            for (int i = 0; i < n; i++) {
                hfCode[i] = new HfCode(ht[i].charset,i);
                Deque code = new ArrayDeque();
                int set = i;
                int parent = ht[i].parent;
                while (parent != -1) {
                    if (ht[parent].leftChild == set) {
                        code.push("0");
                    } else {
                        code.push("1");
                    }
                    set = parent;
                    parent = ht[parent].parent;
                }
                hfCode[i].code = code;
            }
            return hfCode;
        }
    
        /**
         * 对输入的字符串编码
         * @param str
         * @return
         */
        public static HfTree[] coding(String str) {
            HashMap<Character,Integer> map = new HashMap();
            for (int i = 0; i < str.length(); i++) {
                if (map.containsKey(str.charAt(i))) {
                    map.put(str.charAt(i),map.get(str.charAt(i)) + 1);
                } else {
                    map.put(str.charAt(i),1);
                }
            }
            int n = map.size();
            HfTree[] ht = new HfTree[2*n-1];
            int i = 0;
            Iterator<Map.Entry<Character,Integer>> it = map.entrySet().iterator();
            while (it.hasNext()) {
                Map.Entry<Character,Integer> entry = it.next();
                ht[i] = new HfTree();
                ht[i].charset = entry.getKey();
                ht[i].weight = entry.getValue();
                i++;
            }
    
            createHuffmanTree(ht,n);
            HfCode[] hfCode = createHuffmanCode(ht,n);
            HashMap<Character,String> code = new HashMap<>();
            for (int k = 0; k < hfCode.length; k++) {
                Deque temp = hfCode[k].code;
                StringBuilder sb = new StringBuilder();
                while (!temp.isEmpty()) {
                    sb.append(temp.pop());
                }
                String cod = new String(sb);
                code.put(hfCode[k].charset,cod);
                System.out.println("" + hfCode[k].charset + "  : " + cod);
            }
            System.out.print("编码结果:");
            for (int j = 0; j < str.length(); j++) {
                char charset = str.charAt(j);
                System.out.print(code.get(charset));
            }
            return ht;
        }
    
    
        /**
         * 译码
         * @param str
         * @param ht
         */
        public static void decoding(String str, HfTree[] ht) {
            HfTree root = ht[ht.length-1];
            HfTree temp = root;
            for (int i = 0; i < str.length(); i++) {
                if (temp.leftChild == -1 && temp.rightChild == -1) {
                    System.out.print(temp.charset);
                    temp = root;
                }
                if (str.charAt(i) == '0') {
                    temp = ht[temp.leftChild];
                } else if (str.charAt(i) == '1'){
                    temp = ht[temp.rightChild];
                } else {
                    System.out.println("输入的编码有误！");
                    return;
                }
            }
            if (temp.rightChild != -1 || temp.rightChild != -1) {
                System.out.println("输入的编码有误！");
                return;
            }
            System.out.println(temp.charset);
        }
    
        /**
         * 返回最小值下标及次小值下标
         * @param ht
         * @param range
         * @return
         */
        public static MyMin select(HfTree[] ht, int range) {
            //默认下标为0
            int min = 0;
            //若0下标已被记录
            if (ht[min].parent != -1) {
                for (int i = 0; i <= range; i++) {
                    if (ht[i].parent == -1) {
                        min = i;
                        break;
                    }
                }
            }
            //开始查找
            for (int i = min + 1; i <= range; i++) {
                if (ht[i].weight < ht[min].weight && ht[i].parent == -1) {
                    min = i;
                }
            }
            //次小值默认从0开始
            int nextMin = 0;
                for (int i = 0; i <= range; i++) {
                    //不能是最小值且没有被记录
                    if (ht[i].parent == -1 && min != i) {
                        nextMin = i;
                        break;
                    }
                }
    
            for (int i = nextMin + 1; i <= range; i++) {
                if (ht[i].weight < ht[nextMin].weight && ht[i].parent == -1
                        &&  ht[i].weight >= ht[min].weight && min != i) {
                    nextMin = i;
                }
            }
    
            MyMin m = new MyMin(min,nextMin);
            return m;
        }
    
    }
    
    /**
     * 哈夫曼树每个节点的数据结构
     */
    class HfTree {
        char charset;
        int weight;
        int parent;
        int leftChild;
        int rightChild;
    
        public HfTree() {
            this.parent = -1;
            this.leftChild = -1;
            this.rightChild = -1;
        }
    
        @Override
        public String toString() {
            return " " + charset +
                    "," + weight +
                    "," + parent +
                    "," + leftChild +
                    "," + rightChild;
        }
    }
    
    /**
     * 哈夫曼编码的数据结构
     */
    class HfCode {
        char charset;
        int index;
        Deque code;
    
        public HfCode() {
        }
    
        public HfCode(char charset, int index) {
            this.charset = charset;
            this.index = index;
        }
    }
    
    /**
     * 最小值与次小值的封装类
     */
    class MyMin {
        int min;
        int nextMin;
    
        public MyMin(int min, int nextMin) {
            this.min = min;
            this.nextMin = nextMin;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70]: /images/20220406/8c773cb7c80f4b6794ea5864f6b43938.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70 1]: /images/20220406/6168e963caff45b385e4ed29a7177dca.png