简单哈弗曼树(Java)

哈夫曼树的实现

---

　　1.编码思想

　　　　哈夫曼编码是一种变长的编码方案,字符的编码根据使用频率的的不同而长短不一, 使用频率高的字符其编码较短,使用频率低的字符编码较长,从而使所有的编码总长度为最短.

1. 统计原始数据中个新号符号的频率,安频率高低的次序排列
2. 将两个频率最小的相加,作为原本两个节点的父节点,次父节点的频率为子节点之和
3. 重复上述两部,直到和为只剩下一个元素,那么这个元素就是根

---

       2.解码思想

           利用Haffman树进行解码,已知一个二进制位串S,

　　　从串S的第一位出发,逐位的去匹配二叉树边上标记的0和1

　　　从haffman树的根节点出发,遇到0时,向左,遇到1时向右,若干连续的0和1确定一条从根节点到某个叶子节点的路径.一旦到达一个叶子节点,便译出一个字符,

　　　接着从S的下一个位开始继续寻找,然后在重新将指针指向根.

---

编码和解码操作

主要有三部分

1.对编码进行计数,然后通过键值对构造haffman树,这里主要使用了优先队列,也就是最小堆,需要内部节点类实现Comparable接口

2.通过树,返回叶节点的编码,这里我利用Map<Character, String>这样将字符和编码绑定到了一起,方便后面操作

3.根据输入的字符串,遍历,返回编码后的字符串,如下:

        //toCode()返回一个Map键值对
        Map<Character, String> codes = haff.toCode() ;

        StringBuilder stringcode = new StringBuilder() ;
        //遍历字符串,求其编码
        for(char ch : text.toCharArray()) {
            stringcode.append(codes.get(ch)) ;
        }

        return stringcode.toString() ;

---

下面是代码演示:

package com.jffx.util;

import java.util.*;

/*
本类负责逻辑处理,
负责串---->码的编码
    吗---->串的解码
 */
public class HaffmanCode {

    private Node root ;


    //---------------------------------------- 下面是内部节点类
    static class Node implements Comparable<Node> {
        Integer weight ;
        String code = "" ;                  //取一个字符串域表示每个节点的编码
        Character data ;

        Node parent ;
        Node left ;
        Node right ;
        public Node(int w, Node left, Node right, Node parent) {
            this.weight = w ;
            this.left = left ;
            this.parent = parent ;
            this.right = right ;
        }

        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight ;
        }

        @Override
        public String toString() {
            return "[" + this.data + ", " + this.weight + "]" ;
        }
    }


    /**
     * 构造haffman树
     * 先将strs这样的键值对转化为节点, 然后加入优先队列
     * @param strs 字符--频率这样的键值对
     */
    public HaffmanCode(Map<Character, Integer> strs) {
        Queue<Node> queue = new PriorityQueue<>() ;

        Set<Character> keys = strs.keySet() ;
        for(Character key : keys) {
            Node newNode = new Node(strs.get(key), null, null, null) ;
            newNode.data = key ;
            newNode.weight = strs.get(key) ;

            //入堆 -- 覆写CompareTo
            queue.add(newNode) ;
        }

        while(queue.size() > 1) {
            Node n1 = queue.poll() ;
            Node n2 = queue.poll() ;

            Node sumNode = new Node(n1.weight + n2.weight , n1, n2, null) ;

            n1.parent = sumNode ;
            n2.parent = sumNode ;

            queue.add(sumNode) ;
        }

        this.root = queue.poll() ;
    }

    /**
     * 将树的叶节点的编码返回, 返回的键值是   字符 -- 编码 这样的形式
     * @return
     */
    public Map<Character, String> toCode() {
        Map<Character, String> map = new HashMap<>() ;

        preTraverse() ;

        //前序遍历.将叶节点的属性保存到map中
        List<Node> stack = new LinkedList<>() ;
        Node p = this.root ;
        while(p != null || !stack.isEmpty()) {
            while(p != null) {
                stack.add(p) ;
                p = p.left ;
            }
            //如果栈不空,去栈顶元素,然后向右
            if(!stack.isEmpty()) {
                p = ((LinkedList<Node>) stack).pop() ;
                if(isLeafNode(p)) {
                    map.put(p.data, p.code) ;
                }
                p = p.right ;
            }
        }
        return map ;
    }

    /**
     * 输入一串编码,然后返回解码后的字符串
     * @return
     */
    public String deCode(String codes) {
        StringBuilder stringBuilder = new StringBuilder() ;

        Node p = this.root ;        //从根出发
        for(int i = 0 ; i < codes.length() ; ++i) {
            if(codes.charAt(i) == '0') {
                p = p.left ;
            } else {
                p = p.right ;
            }
            if(isLeafNode(p)) { //如果是叶子
                stringBuilder.append(p.data) ;
                p = this.root ;
            }
        }
        return stringBuilder.toString() ;
    }

    private void preTraverse() {
        preTraverse(this.root) ;
    }
    private void preTraverse(Node root) {
        if(root != null) {
            if(root != this.root) {     //如果不是根节点
                if(root == root.parent.left) {  //左孩子
                    root.code = root.parent.code + "0" ;
                } else {
                    root.code = root.parent.code + "1" ;
                }
            }
            //System.out.println(root) ;
            preTraverse(root.left) ;
            preTraverse(root.right) ;
        }
    }

    public boolean isLeafNode(Node node) {
        return node.left == null && node.right == null ;
    }









    /**
     * 测试
     * @param args
     */
    public static void main(String[] args) {
        String str = "today is Saturday." ;

        char[] strCh = str.toCharArray() ;
        Map<Character, Integer> map = new HashMap<>() ;

        for(int i = 0 ; i < strCh.length ; ++i) {
            if(map.containsKey(strCh[i])) { //如果存在键
                map.put(strCh[i], map.get(strCh[i]) + 1) ;
            } else {
                map.put(strCh[i], 1) ;
            }
        }

        HaffmanCode haff = new HaffmanCode(map) ;

        String code = getTextCode(haff, str) ;
        String decode = haff.deCode(code) ;
        System.out.println(decode) ;
    }

    /**
     * 获取一个字符串的编码
     * @param text 需要压缩的字符串
     * @return
     */
    public static String getTextCode(HaffmanCode haff, String text) {

        Map<Character, String> codes = haff.toCode() ;
        StringBuilder stringcode = new StringBuilder() ;
        for(char ch : text.toCharArray()) {
            stringcode.append(codes.get(ch)) ;
        }
        return stringcode.toString() ;
    }
}

---

这里你会发现,你压缩后的数据比你没压缩前还大,额--------

---

学无止境