[XJTUSE]数据结构学习——3.3 Huffman树

[XJTUSE]数据结构学习——3.3 Huffman树

文章目录

3.3 Huffman树

基本概念构造算法Huffman编码

前缀码字符编码图解代码实现（java） 非等概率随机数

3.3 Huffman树 基本概念

路径长度：两个结点之间路径上的分支数

树的外部路径长度：各叶结点到根结点的路径长度之和

树的内部路径长度：各非叶结点到根结点的路径长度之和

树的带权路径长度：树中所有叶子结点的带权路径长度之和

Huffman树定义:是一类带权（外部）路径（Weighted PathLength）长度最短的树

举例：求下面二叉树的带权路径长度

☑️ "权"大的叶结点深度小，它相对于总路径长度的花费最小，因此，其他叶结点如果"权"小，就会被推到树的较深处

构造算法

❓ 如何构造Huffman树?

1️⃣ 根据给定的n个权值 { w 1 , w 2 . . . , w n } {w_1, w_2 ..., w_n} {w1​,w2​...,wn​}，构造n棵二叉树的集合 F = { T 1 , T 2 , . . . , T n } F={T_1,T_2,...,T_n} F={T1​,T2​,...,Tn​}，其中每棵二叉树中均只含一个带权值为 w i w_i wi​的根结点,其左、右子树为空树;

2️⃣ 在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;

3️⃣ 从F中删去这两棵树，同时加入刚生成的新树;

4️⃣ (4)重复(2)和(3)两步，直至F中只含一棵树为止

Huffman编码 前缀码

使用Huffman树编制的代码具有前缀特性prefix：一组代码中的任何一个代码都不是另一个代码的前缀

这种特性保证了代码串被反编码时不会有多种可能

字符编码

利用Huffman树的特性为使用频率不同的字符编写不等长的编码，从而缩短整个文件的长度

This is isinglass

■ t的频度是1 h的频度是1 i的频度是4 s的频度是5
■ n的频度是1 g的频度是1 a的频度是1 I的频度是1

如果采用等长的编码形式，上面的八个字母则需要三位二进制编码
长度=15*3=45

按照上面字母出现的频度创建一个Huffman树

图解

代码实现（java）

class Letter {
    char element;//字母
    double weight;//字母出现的频率

    public Letter(char element, double weight) {
        this.element = element;
        this.weight = weight;
    }

    public char getElement() {
        return element;
    }

    public void setElement(char element) {
        this.element = element;
    }

    public double getWeight() {
        return weight;
    }

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

class HuffTreeNode {
    Letter letter;
    HuffTreeNode left;//左子结点
    HuffTreeNode right;//右子结点

    public Letter getLetter() {
        return letter;
    }

    public void setLetter(Letter letter) {
        this.letter = letter;
    }

    public HuffTreeNode getLeft() {
        return left;
    }

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

    public HuffTreeNode getRight() {
        return right;
    }

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

public class HuffmanTree {
    //简单使用冒泡排序
    private void sort(HuffTreeNode[] nodes) {
        int flags = 0;
        for (int i = 0; i < nodes.length-1; i++) {
            for (int j = 0; j < nodes.length-1-i; j++) {
                if (nodes[j].letter.weight > nodes[j + 1].letter.weight) {
                    HuffTreeNode temp = nodes[j];
                    nodes[j] = nodes[j + 1];
                    nodes[j + 1] = temp;
                    flags = 1;//不是有序的，flags设置为1；

                }
            }
            if (flags == 0)
                return;
        }
    }

    
    public HuffTreeNode generateHuffTree(Letter[] letters) {
        HuffTreeNode[] nodes = new HuffTreeNode[letters.length];
        for (int i = 0; i < letters.length; i++) {
            nodes[i] = new HuffTreeNode();
            nodes[i].letter = letters[i];
        }
        while (nodes.length > 1) {
            sort(nodes);
            HuffTreeNode node1 = nodes[0];
            HuffTreeNode node2 = nodes[1];
            HuffTreeNode newTree = new HuffTreeNode();
            Letter temp = new Letter('0',node1.getLetter().getWeight()+node2.getLetter().getWeight());
            newTree.setLetter(temp);
            newTree.setLeft(node1);
            newTree.setRight(node2);
            HuffTreeNode[] nodes2 = new HuffTreeNode[nodes.length - 1];//新的结点数组，长度减一
            for (int i = 2; i < nodes.length; i++) {
                nodes2[i - 2] = nodes[i];
            }
            nodes2[nodes2.length - 1] = newTree;
            nodes = nodes2;
        }
        return nodes[0];
    }

    
    public void print(HuffTreeNode root,String code){
        if(root != null) {
            print(root.getLeft(),code+"0");
            print(root.getRight(),code+"1");
            if(root.getLeft() == null && root.getRight() == null) {
                String m=root.getLetter().getElement()+"频数:"+root.getLetter().getWeight()+" 哈夫曼编码："+code;
                System.out.println(m);
            }
        }
    }
    public static void main(String[] args) {
        Letter a = new Letter('a', 1);
        Letter g = new Letter('g', 1);
        Letter h = new Letter('h', 1);
        Letter l = new Letter('l', 1);
        Letter n = new Letter('n', 1);
        Letter t = new Letter('t', 1);
        Letter i = new Letter('i', 4);
        Letter s = new Letter('s', 5);
        Letter[] test = {a, g, h, l, n, t, i, s};
        HuffmanTree huffmanTree = new HuffmanTree();
        huffmanTree.print(huffmanTree.generateHuffTree(test),"");
    }
}

n频数:1.0 哈夫曼编码：000
t频数:1.0 哈夫曼编码：001
i频数:4.0 哈夫曼编码：01
a频数:1.0 哈夫曼编码：1000
g频数:1.0 哈夫曼编码：1001
h频数:1.0 哈夫曼编码：1010
l频数:1.0 哈夫曼编码：1011
s频数:5.0 哈夫曼编码：11

非等概率随机数

按照给定的概率生成相应的随机数
比如有1、2、3、4、5、6这6个数，编写一个随机发生器，使其能够按照如下概率（0.15、0.20、0.10、0.30、0.12和0.13）生成相应的6个数

1️⃣ 解决方法一：可以使用JavaAPI中的随机数生成函数，生成[0，1）之间的数，按照区间生成数字

2️⃣ 解决方法二：使用Huffman树减少比较次数

    public static int randomGenerate() {
        double temp = Math.random();
        int result=0;
        if (temp < 0.42) {
            if (temp < 0.22) {
                if (temp < 0.10) {
                    result = 3;
                } else {
                    result = 5;
                }
            } else {
                result = 2;
            }
        } else {
            if (temp < 0.72) {
                result = 4;
            } else {
                if (temp < 0.85) {
                    result = 6;
                } else {
                    result = 1;
                }
            }
        }
        return result;
    }