关于java:赫夫曼编码数据压缩算法

赫夫曼算法类 Huffman.java
/**

• @Author: ltx
• @Description: 赫夫曼编码
  */

public class Huffman {

Map<Character, String> codeMap = new HashMap<>();
/**
 * 中序遍历(前序或后序也行)
 * 失去huffman编码
 *
 * @param node 节点
 * @param sb   StringBuilder
 */
public void getCodeByMidOrder(Node node, StringBuilder sb) {
    if (node.left != null) {
        //往左走+'0'
        sb.append("0");
        getCodeByMidOrder(node.left, sb);
    }
    //叶子节点
    if (node.left == null && node.right == null) {

// System.out.print(node + “:” + sb + “, “);

        codeMap.put(node.value, sb.toString());
    }
    if (node.right != null) {
        //往右走+'1'
        sb.append("1");
        getCodeByMidOrder(node.right, sb);
    }
    //回溯向上走缩小一个字符
    if (sb.length() > 0) {
        sb.deleteCharAt(sb.length() - 1);
    }
}
public Node getHuffmanTree(List<Node> nodes) {
    Collections.sort(nodes);

// System.out.println(nodes);

    while (nodes.size() > 1) {
        //左叶子-数组最小值
        Node leafLeft = nodes.remove(0);
        //右叶子-数组次小值
        Node leafRight = nodes.remove(0);
        //父节点=数组最小值+数组次小值
        Node parentNode = new Node(null, leafLeft.weight + leafRight.weight);
        parentNode.left = leafLeft;
        parentNode.right = leafRight;
        //新的节点增加到list外面
        nodes.add(parentNode);
        Collections.sort(nodes);
    }
    return nodes.get(0);
} 
/**
 * 获取各个字符权重(字符个数)
 *
 * @param str
 * @return
 */
public List<Node> getCharWight(String str) {
    Map<Character, Integer> charNumMap = new HashMap<>();
    char[] chs = str.toCharArray();
    for (char c : chs) {
        //数量
        Integer count = charNumMap.get(c);
        if (count == null) {
            charNumMap.put(c, 1);
        } else {
            charNumMap.put(c, count + 1);
        }
    }

// System.out.println(charNumMap);

    List<Node> nodes = new ArrayList<>();
    //创立节点List
    for (char c : charNumMap.keySet()) {
        nodes.add(new Node(c, charNumMap.get(c)));
    }
    return nodes;
} 
/**
 * 编码
 * 依据赫夫曼编码表，对原始数据做转换
 *
 * @param str 原始字符串
 * @return
 */
public String encoding(String str) {
    StringBuilder sb = new StringBuilder();
    char[] chs = str.toCharArray();
    for (char c : chs) {
        sb.append(codeMap.get(c));
    }
    return sb.toString();
} 
/**
 * 解码
 *
 * @return
 */
public String decode(String encodStr) {
    //翻转codeMap
    Map<String, Character> encodeMap = new HashMap<>();
    for (char c : codeMap.keySet()) {
        encodeMap.put(codeMap.get(c), c);
    }
    char[] chs = encodStr.toCharArray();
    int j = 0;
    StringBuilder res = new StringBuilder();
    while (j < encodStr.length() - 1) {
        StringBuilder sb = new StringBuilder();
        Character cr;
        //匹配出字符串
        while ((cr = encodeMap.get(sb.toString())) == null) {
            sb.append(chs[j]);
            j++;
        }
        res.append(cr);
    }
    return res.toString();
}
public static void main(String[] args) {
    Huffman huffman = new Huffman();
    System.out.println("原始数据:");
    //须要压缩的串
    String str = "i like like like java do you like a java";
    System.out.println(str);
    //1.取得字符权重List
    List<Node> nodes = huffman.getCharWight(str);
    //[ :9, a:5, d:1, e:4, u:1, v:2, i:5, y:1, j:2, k:4, l:4, o:2]
    System.out.println("节点权重列表:");
    System.out.println(nodes);
    //2.[PerfectMoney下载](https://www.gendan5.com/wallet/PerfectMoney.html)结构赫夫曼树
    Node root = huffman.getHuffmanTree(nodes);
    //3.取得赫夫曼编码表
    huffman.getCodeByMidOrder(root, new StringBuilder(""));
    System.out.println("赫夫曼编码表:");
    //失去赫夫曼编码表
    //{ =01, a=100, d=11000, u=11001, e=1110, v=11011, i=101, y=11010, j=0010, k=1111, l=000, o=0011}
    System.out.println(huffman.codeMap);
    //4.压缩编码
    String encodStr = huffman.encoding(str);
    System.out.println("压缩后数据:");

//1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100

    System.out.println(encodStr);
    //5.解压
    String res = huffman.decode(encodStr);
    System.out.println("解压后数据:");
    //打印最终后果
    //i like like like java do you like a java
    System.out.println(res);
}

}