数据结构算法之赫夫曼编码(java实现)

绪论

最近研究二叉树,比较经典的树就是哈夫曼树了,所以研究一下它的构建以及哈夫曼编码,恶补一下数据结构的知识。

有一段密文:aabbccabcacb,解析为电码传输,只能为0、1来表示

abcd
010110

那么aabc….可以表示为00101,但是在解析的时候发现0 01 10可以出现混乱,001可以解析为 ac 或者 aab,这样就会导致数据不唯一。因此可以用哈夫曼树来保证数据唯一。

概念

首先,我来简单说一下哈夫曼编码(Huffman),它主要是数据编码的一种方式,也是数据压缩的一种方法,将某些特定的字符转化为二进制字符,并在转换过程中降低原有字符串的存储量。其具体方法是先按出现的概率大小排队,把两个最小的概率相加,作为新的概率 和剩余的概率重新排队,再把最小的两个概率相加,再重新排队,直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率,读出时由该符号开始一直走到最后的“1”, 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好,就是该符号的哈夫曼编码。

代码

package com.coderman.datastruct.tree;

import java.util.*;

/**
 * 哈夫曼编码
 * @Author zhangyukang
 * @Date 2020/6/4 10:54
 * @Version 1.0
 **/
public class HuffmanCodingTest {

    //模拟要传输的数据
    private static String data="i love you so so so much !";

//    private static String data="i like like like java do you like a java";

    public static void main(String[] args) {
        // 统计各个字符对应的个数(次数作为权值)
        // i->1 ,v->1 ,e->1 ,y->1 ,u->1 , l->1 ,o->2 _->2
//        int[] array={1,1,1,1,1,1,2,2};
        HTree hTree = new HTree(data);
        System.out.println("要传输的字符串");
        System.out.println(data);
//        hTree.preOrder(hTree.getRoot());
        System.out.println("生成编码表");
        System.out.println(hTree.huffmanCodeTable);
        System.out.println("编码后的数据:【反码---> 每8位一个字节】");
        System.out.println(hTree.code());
        System.out.println("编码后的字节数组");
        System.out.println(Arrays.toString(hTree.zip()));
    }
}

class HTree{

    private String value;

    private TNode root;

    //对应的字符编码表
    public   Map<Character,String> huffmanCodeTable=new HashMap<>();

    private StringBuilder stringBuilder=new StringBuilder();

    public TNode getRoot() {
        return root;
    }

    public void setRoot(TNode root) {
        this.root = root;
    }

    public HTree(String value){
        this.value=value;
        this.root=createTree(value);
        createHuffmanTable(this.root);
    }

    public void createHuffmanTable(TNode root){
        createHuffmanTable(root,"",this.stringBuilder);
    }

    /**
     * 赫夫曼编码表
     * @return
     */
    public void createHuffmanTable(TNode current,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder1=new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if(current!=null){
            if(current.getData()==null){
                //非叶子节点,递归
                //向左递归
                createHuffmanTable(current.getLeft(),"0",stringBuilder1);
                //向右递归
                createHuffmanTable(current.getRight(),"1",stringBuilder1);
            }else{
                huffmanCodeTable.put((char)current.getData().byteValue(),stringBuilder1.toString());
            }
        }
    }

    /**
     * 获取编码后要传输的数据
     * @return
     */
    public String code(){
        StringBuilder code= new StringBuilder();
        for (char c : this.value.toCharArray()) {
            String value = this.huffmanCodeTable.get(c);
            code.append(value);
        }
        return code.toString();
    }

    /**
     * 返回编码过后的字节数组
     * 8位一个字节
     * 1011000110011101011100111101111101100001001111101111101
     * 补码: 【0】= 10110001
     * 反码:【0】= 10110000
     * 原码:【0】= 11001111
     * 十进制:-
     * @return
     */
    public byte[] zip(){
        String code = code();
        //构造字节数组的长度
        int len=code.length()%8==0? (code.length()/8): ((code.length()/8)+1);

        byte[] bytes=new byte[len];
        int index=0;
        for(int i=0;i<code.length();i+=8){
            String substring;
            if(i+8>code.length()) {//不够8位
                substring = code.substring(i);
            }else {
                substring = code.substring(i, i + 8);
            }
            bytes[index]=(byte) Integer.parseInt(substring,2);
            index++;
        }
        return bytes;
    }

    /**
     * 创建赫夫曼树
     * @param value
     */
    private TNode createTree(String value) {
        //构建出节点集合
        List<TNode> tNodes=buildNodeList(value);
        //排序集合
        while (tNodes.size()>1){
            Collections.sort(tNodes);
            //取出最小的一个,和次小的一个节点重写构成一颗树
            TNode leftNode = tNodes.get(0);
            TNode rightNode= tNodes.get(1);
            TNode parent = new TNode(null,leftNode.getWeight()+rightNode.getWeight());
            parent.setLeft(leftNode);
            parent.setRight(rightNode);
            //移除
            tNodes.remove(leftNode);
            tNodes.remove(rightNode);
            //添加
            tNodes.add(parent);
        }
        return tNodes.get(0);
    }

    /**
     * 前序遍历
     * @param current
     */
    public void preOrder(TNode current){
        if(current!=null){
            System.out.println(current);
            preOrder(current.getLeft());
            preOrder(current.getRight());
        }
    }

    /**
     * build nodes
     * @param value
     * @return
     */
    private List<TNode> buildNodeList(String value) {
        byte[] bytes = value.getBytes();
        List<TNode> result=new ArrayList<>();
        Map<Byte,Integer> map=new HashMap<>();
        //统计每个字符出现的次数
        for (byte aByte : bytes) {
            map.merge(aByte, 1, Integer::sum);
        }
        //遍历Map,构建节点
        if(map.size()>0){
            for(Map.Entry<Byte,Integer> entry: map.entrySet()){
                TNode tNode = new TNode(entry.getKey(),entry.getValue());
                result.add(tNode);
            }
        }
        return result;
    }

}


class TNode implements Comparable<TNode>{
    private Byte data;//存放数据

    private int weight;//存放权重: 字符出现的次数

    private TNode left;

    private TNode right;

    public TNode(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    public Byte getData() {
        return data;
    }

    public void setData(Byte data) {
        this.data = data;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public TNode getLeft() {
        return left;
    }

    public void setLeft(TNode left) {
        this.left = left;
    }

    public TNode getRight() {
        return right;
    }

    public void setRight(TNode right) {
        this.right = right;
    }

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

    @Override
    public java.lang.String toString() {
        return "TNode{" +
                "data=" + (data==null? "null":(char)data.byteValue()) +
                ", weight=" + weight +
                '}';
    }
}

输出

要传输的字符串
i love you so so so much !
生成编码表
{ =10, !=11000, c=11001, e=11010, h=11100, i=11110, l=11111, m=0110, o=00, s=010, u=0111, v=11011, y=11101}
编码后的数据:【反码---> 每8位一个字节】
1111010111110011011110101011101000111100100010010001001000100110011111001111001011000
编码后的字节数组
[-11, -13, 122, -70, 60, -119, 18, 38, 124, -14, 24]

Process finished with exit code 0
# Java   算法      数据结构  

评论

公众号:mumuser

企鹅群:932154986

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×