Java利用哈夫曼编码实现字符串压缩

赫夫曼编码基本介绍

1) 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法

2) 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。

3) 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%~90%之间

4) 赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法,称之为最佳编码

在通信领域中几种信息处理方式的区别(以字符串" i like like like java do you like a java"举例):

第一种-定长编码:

第二种-变长编码:

第三种-赫夫曼编码:

传输的字符串:

1、 i like like like java do you like a java

2、 d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数

3、 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值

构成赫夫曼树的步骤:

1) 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树

2) 取出根节点权值最小的两颗二叉树

3) 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

4) 再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复 1-2-3-4 的步骤,直到数列中,所有的数据都被处理,就得到一颗赫夫曼树

4、 根据赫夫曼树,给各个字符,规定编码 (前缀编码), 向左的路径为 0 向右的路径为 1 ,编码

如下:

o: 1000 u: 10010 d: 100110 y: 100111 i: 101

a : 110 k: 1110 e: 1111 j: 0000 v: 0001  l: 001 : 01

5、 按照上面的赫夫曼编码,我们的"i like like like java do you like a java" 字符串对应的编码为 (注意这里我们使用的无损压缩)1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 通过赫夫曼编码处理 长度为:133

通过以上三种信息处理方式可以对比看出赫夫曼编码的优越性。

以下给出实现哈夫曼编码需要的各个方法:

1、先创建节点对象:

// 为了排序,必须实现Comprable<>接口

public class Node implements Comparable<Node>{
    Byte data;
    int weight;
    Node left;
    Node right;

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

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

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

    //前序遍历
    public void prefixOrder(){
        System.out.println(this);
        if (this.left != null){
            this.left.prefixOrder();
        }
        if (this.right != null){
            this.right.prefixOrder();
        }
    }
}

2、需要先实现统计输入的字符串中各个字符的个数: 

/**
     * //统计字符串中每个字符出现的次数和空格出现次数
     *
     * @param str 字符串
     * @return 返回一个排好序的Node集合
     */
    public static List<Node> totalCharCounts(String str) {

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            Integer count = map.get(ch);
            if (count == null) {
                count = 0;
            }
            map.put(ch, count + 1);
        }
        //遍历map,将map中的数据存入Node节点中
        //先将map转为set集合
        Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
        //观察测试输出
        //System.out.println(mapSet);
        List<Node> nodeList = new ArrayList<>();
        //遍历set
        for (Map.Entry<Character, Integer> set : mapSet) {
            // 将map中的数据存入Node节点中
            Node node = new Node((byte) set.getKey().charValue(), set.getValue());
            // 将node存入集合中
            nodeList.add(node);
            //System.out.println(set.getKey() + " = " + set.getValue());
        }
        //排序
        Collections.sort(nodeList);
        //测试
        //System.out.println(nodeList);
        return nodeList;
    }

3、创建赫夫曼树:

/**
     * 创建huffman树
     *
     * @param nodeList 排好序的集合
     * @return 返回huffman树的根节点
     */
    public static Node createHuffmanTree(List<Node> nodeList) {
        //循环创建huffman树
        while (nodeList.size() > 1) {
            //1、每次取出集合中的前两个节点
            Node left = nodeList.get(0);
            Node right = nodeList.get(1);
            //2、将他们的权值相加构成一个新的节点并作为他们的父节点
            Node parent = new Node(null, left.weight + right.weight);
            parent.left = left;
            parent.right = right;
            //3、删除已经处理过的节点
            nodeList.remove(left);
            nodeList.remove(right);
            //4、将新的节点存入集合中
            nodeList.add(parent);
            //5、重新给集合排序,循环这5步即可,直到集合中只有一个节点,这就是huffman树的根节点
            Collections.sort(nodeList);
            //观察测试输出
            //System.out.println(nodeList);
        }
        //返回huffman树的根节点
        return nodeList.get(0);
    }

4、根据创建的赫夫曼树进行字符串编码压缩:

/**
     * 根据huffman树来进行数据编码压缩
     * 思路:
     * 1、只要向左子树走就代表0,向右子树走就代表1
     * 2、从头节点走到对于字符在的节点位置的路径对于的0和1组成的二进制编码就是压缩后该字符对于的编码
     * 3、需要定义一个StringBuffer来存储某个节点的路径对于的编码
     * 4、将赫夫曼编码表存放在Map<Byte,String>中
     *
     * @param node         huffman树的根节点
     * @param stringBuffer 用于拼接路径
     * @param code         路径:左子节点是0,右子节点是1
     * @return
     */
    private static void getHuffmanCompressionCode(Node node, String code, StringBuffer stringBuffer) {
        StringBuffer stringBuffer1 = new StringBuffer(stringBuffer);
        stringBuffer1.append(code);
        //如果为空,不进行处理
        if (node != null) {
            //判断node是叶子节点还是非叶子节点
            if (node.data == null) {
                //非叶子节点
                //向左递归
                getHuffmanCompressionCode(node.left, "0", stringBuffer1);
                //向右递归
                getHuffmanCompressionCode(node.right, "1", stringBuffer1);
            } else {
                //叶子节点
                //说明这条路走到尾了,将路径编码存入map中
                huffmanCodes.put(node.data, stringBuffer1.toString());
            }
        }
    }

5、得到压缩后的赫夫曼编码长度(二进制位数):

/**
     * @return 得到压缩后的赫夫曼编码大小
     */
    public static int getStrCodeSize() {
        int size = 0;
        //将两个map集合都转为set集合
        Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
        Set<Map.Entry<Byte, String>> huffmanMapSet = huffmanCodes.entrySet();
        //循环两个set集合
        for (Map.Entry<Character, Integer> set1 : mapSet) {
            for (Map.Entry<Byte, String> set2 : huffmanMapSet) {
                //如果两个set的key相同就将他们的value相乘,只是需要注意存储huffman编码中的是字符串,需要乘字符串的长度
                if ((byte) set1.getKey().charValue() == set2.getKey()) {
                    size = size + set1.getValue() * (set2.getValue().length());
                    //节约时间,之间退出内循环。因为不可能有一对多的关系。
                    break;
                }
            }
        }
        return size;
    }

6、编写一个方法,将字符串对应的byte[]数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码压缩后的byte[]

/**
     * 编写一个方法,将字符串对应的 byte[] 数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码 压缩后的byte[]
     *
     * @param bytes        这时原始的字符串对应的 byte[]
     * @param huffmanCodes 生成的赫夫曼编码 map
     * @return 返回赫夫曼编码处理后的 byte[]
     * 举例: String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
     * 返 回 的 是 字 符 串:
     * "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000
     * 101111111100110001001010011011100"
     * => 对应的 byte[] huffmanCodeBytes ,即 8 位对应一个 byte,放入到 huffmanCodeBytes
     * huffmanCodeBytes[0] = 10101000(补码) => byte [推导 10101000=> 10101000 - 1 => 10100111(反
     * 码)=> 11011000(源码) = -88 ]
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //1、先利用赫夫曼编码表将传进来的bytes数组转为压缩后的编码
        StringBuffer stringBuffer1 = new StringBuffer();
        for (byte b : bytes) {
            stringBuffer1.append(huffmanCodes.get(b));
        }
        //输出字符串压缩成赫夫曼编码后对应的二进制编码
        //System.out.println("输出字符串压缩成赫夫曼编码后对应的二进制编码:" + stringBuffer1 + "长度为:" + stringBuffer1.length());

        //获取byte数组的长度,Math.ceil()表示向上取整
        int len = (int) Math.ceil(stringBuffer1.length()*1.0 / 8);
        //也可以用下面的方法获取长度
        /*if(stringBuffer1.length() % 8 == 0) {
            len = stringBuffer1.length() / 8;
        } else {
            len = stringBuffer1.length() / 8 + 1;
        }*/
        //测试
        //System.out.println(stringBuffer1.length());
        //System.out.println(len);
        byte[] huffmanBytes = new byte[len];
        int index = 0;
        for (int i = 0; i < stringBuffer1.length(); i = i + 8) {
            String strByte;
            if (i + 8 > stringBuffer1.length()) {
                //从i取到字符串最后一个字符
                strByte = stringBuffer1.substring(i);
            } else {
                //一次截取8个
                strByte = stringBuffer1.substring(i, i + 8);
            }
            //将 strByte 转成一个 byte,放入到 huffmanBytes中
            //该方法是将strByte对应的01字符串传换为十进制
            //第二个参数表示基数(radix),表示转换为radix进制
            huffmanBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanBytes;
    }

其实也可以不用写5中的方法,可以直接在6中输出stringBuffer1.length()就可以得到压缩后的二进制位数。不过也可以把5当作一种解决的算法。

以下给出完整的代码:

import java.util.*;

/**
 * 实现huffman编码
 */

public class HuffmanCode {

    //将赫夫曼编码表存放在Map<Byte,String>中
    public static Map<Byte, String> huffmanCodes = new HashMap<>();

    //需要定义一个StringBuffer来存储某个节点的路径对于的编码
    public static StringBuffer stringBuffer = new StringBuffer();

    //创建一个map,来保存每个字符以及他对应出现的次数
    public static Map<Character, Integer> map = new HashMap<>();

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.println("输入字符串:");
        //scanner.next()方法不能输入空格,例如输入: aaa bbb实际上只能接收到aaa,空格后面的字符串都接收不到
        //所以需要用scanner,nextLine()方法来接收字符串

        String str = scanner.nextLine();

        // 把输入的字符串转为byte数组,在byte数组中存储的是字符对应的ASCII码值
        byte[] strBytes = str.getBytes();
        System.out.println(str + ",压缩成赫夫曼编码前对应的byte数组:" + Arrays.toString(strBytes));

        //计算压缩前的字符串有多少位二进制数
        int compressionBeforeCodeSize = str.length() * 8 + str.length() - 1;
        System.out.println(str + ",压缩前的字符串大小:" + compressionBeforeCodeSize);

        //统计字符串中每个字符出现的次数和空格出现次数并存入Node节点中
        List<Node> nodeList = totalCharCounts(str);

        //创建huffman树
        Node root = createHuffmanTree(nodeList);

        //得到压缩后的编码
        getHuffmanCompressionCode(root, "", stringBuffer);

        //输出赫夫曼编码表
        System.out.println(str + ",对应的赫夫曼编码表:");
        System.out.println(huffmanCodes);

        //得到压缩后的字符串大小
        int compressionAfterCodeSize = getStrCodeSize();
        System.out.println(str + ",压缩后的字符串大小:" + compressionAfterCodeSize);

        //可以算出压缩率是多少
        double compressionRadio = (compressionBeforeCodeSize - compressionAfterCodeSize) * 1.0 / compressionBeforeCodeSize;
        System.out.println(str + ",压缩成赫夫曼编码的压缩率为:" + compressionRadio);

        byte[] bytes = zip(strBytes, huffmanCodes);
        System.out.println(str + ",压缩成赫夫曼编码后对应的byte数组:" + Arrays.toString(bytes));

    }

    /**
     * @return 得到压缩后的赫夫曼编码大小
     */
    public static int getStrCodeSize() {
        int size = 0;
        //将两个map集合都转为set集合
        Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
        Set<Map.Entry<Byte, String>> huffmanMapSet = huffmanCodes.entrySet();
        //循环两个set集合
        for (Map.Entry<Character, Integer> set1 : mapSet) {
            for (Map.Entry<Byte, String> set2 : huffmanMapSet) {
                //如果两个set的key相同就将他们的value相乘,只是需要注意存储huffman编码中的是字符串,需要乘字符串的长度
                if ((byte) set1.getKey().charValue() == set2.getKey()) {
                    size = size + set1.getValue() * (set2.getValue().length());
                    //节约时间,之间退出内循环。因为不可能有一对多的关系。
                    break;
                }
            }
        }
        return size;
    }

    /**
     * 根据huffman树来进行数据编码压缩
     * 思路:
     * 1、只要向左子树走就代表0,向右子树走就代表1
     * 2、从头节点走到对于字符在的节点位置的路径对于的0和1组成的二进制编码就是压缩后该字符对于的编码
     * 3、需要定义一个StringBuffer来存储某个节点的路径对于的编码
     * 4、将赫夫曼编码表存放在Map<Byte,String>中
     *
     * @param node         huffman树的根节点
     * @param stringBuffer 用于拼接路径
     * @param code         路径:左子节点是0,右子节点是1
     * @return
     */
    private static void getHuffmanCompressionCode(Node node, String code, StringBuffer stringBuffer) {
        StringBuffer stringBuffer1 = new StringBuffer(stringBuffer);
        stringBuffer1.append(code);
        //如果为空,不进行处理
        if (node != null) {
            //判断node是叶子节点还是非叶子节点
            if (node.data == null) {
                //非叶子节点
                //向左递归
                getHuffmanCompressionCode(node.left, "0", stringBuffer1);
                //向右递归
                getHuffmanCompressionCode(node.right, "1", stringBuffer1);
            } else {
                //叶子节点
                //说明这条路走到尾了,将路径编码存入map中
                huffmanCodes.put(node.data, stringBuffer1.toString());
            }
        }
    }

    /**
     * //统计字符串中每个字符出现的次数和空格出现次数
     *
     * @param str 字符串
     * @return 返回一个排好序的Node集合
     */
    public static List<Node> totalCharCounts(String str) {

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            Integer count = map.get(ch);
            if (count == null) {
                count = 0;
            }
            map.put(ch, count + 1);
        }
        //遍历map,将map中的数据存入Node节点中
        //先将map转为set集合
        Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
        //观察测试输出
        //System.out.println(mapSet);
        List<Node> nodeList = new ArrayList<>();
        //遍历set
        for (Map.Entry<Character, Integer> set : mapSet) {
            // 将map中的数据存入Node节点中
            Node node = new Node((byte) set.getKey().charValue(), set.getValue());
            // 将node存入集合中
            nodeList.add(node);
            //System.out.println(set.getKey() + " = " + set.getValue());
        }
        //排序
        Collections.sort(nodeList);
        //测试
        //System.out.println(nodeList);
        return nodeList;
    }

    /**
     * 创建huffman树
     *
     * @param nodeList 排好序的集合
     * @return 返回huffman树的根节点
     */
    public static Node createHuffmanTree(List<Node> nodeList) {
        //循环创建huffman树
        while (nodeList.size() > 1) {
            //1、每次取出集合中的前两个节点
            Node left = nodeList.get(0);
            Node right = nodeList.get(1);
            //2、将他们的权值相加构成一个新的节点并作为他们的父节点
            Node parent = new Node(null, left.weight + right.weight);
            parent.left = left;
            parent.right = right;
            //3、删除已经处理过的节点
            nodeList.remove(left);
            nodeList.remove(right);
            //4、将新的节点存入集合中
            nodeList.add(parent);
            //5、重新给集合排序,循环这5步即可,直到集合中只有一个节点,这就是huffman树的根节点
            Collections.sort(nodeList);
            //观察测试输出
            //System.out.println(nodeList);
        }
        //返回huffman树的根节点
        return nodeList.get(0);
    }

    /**
     * 编写一个方法,将字符串对应的byte[]数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码压缩后的byte[]
     *
     * @param bytes        这时原始的字符串对应的 byte[]
     * @param huffmanCodes 生成的赫夫曼编码 map
     * @return 返回赫夫曼编码处理后的 byte[]
     * 举例: String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
     * 返 回 的 是 字 符 串:
     * "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000
     * 101111111100110001001010011011100"
     * => 对应的 byte[] huffmanCodeBytes ,即 8 位对应一个 byte,放入到 huffmanCodeBytes
     * huffmanCodeBytes[0] = 10101000(补码) => byte [推导 10101000=> 10101000 - 1 => 10100111(反
     * 码)=> 11011000(源码) = -88 ]
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //1、先利用赫夫曼编码表将传进来的bytes数组转为压缩后的编码
        StringBuffer stringBuffer1 = new StringBuffer();
        for (byte b : bytes) {
            stringBuffer1.append(huffmanCodes.get(b));
        }
        //输出字符串压缩成赫夫曼编码后对应的二进制编码
        //System.out.println("输出字符串压缩成赫夫曼编码后对应的二进制编码:" + stringBuffer1 + "长度为:" + stringBuffer1.length());

        //获取byte数组的长度,Math.ceil()表示向上取整
        int len = (int) Math.ceil(stringBuffer1.length()*1.0 / 8);
        //也可以用下面的方法获取长度
        /*if(stringBuffer1.length() % 8 == 0) {
            len = stringBuffer1.length() / 8;
        } else {
            len = stringBuffer1.length() / 8 + 1;
        }*/
        //测试
        //System.out.println(stringBuffer1.length());
        //System.out.println(len);
        byte[] huffmanBytes = new byte[len];
        int index = 0;
        for (int i = 0; i < stringBuffer1.length(); i = i + 8) {
            String strByte;
            if (i + 8 > stringBuffer1.length()) {
                //从i取到字符串最后一个字符
                strByte = stringBuffer1.substring(i);
            } else {
                //一次截取8个
                strByte = stringBuffer1.substring(i, i + 8);
            }
            //将 strByte 转成一个 byte,放入到 huffmanBytes中
            //该方法是将strByte对应的01字符串传换为十进制
            //第二个参数表示基数(radix),表示转换为radix进制
            huffmanBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanBytes;
    }

}

以下是我的测试结果输出:

输入的字符串: i like like like java do you like a java

输入的字符串: asdjkj ;lkjsadlkj kj ()dasd

到此这篇关于Java利用哈夫曼编码实现字符串压缩的文章就介绍到这了,更多相关Java字符串压缩内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2022-09-18

Java实现赫夫曼树(哈夫曼树)的创建

目录 一.赫夫曼树是什么? 1.路径和路径长度 2.节点的权和带权路径长度 3.树的带权路径长度 二.创建赫夫曼树 1.图文创建过程 2.代码实现 一.赫夫曼树是什么? 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度(WPL)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 图1 一棵赫夫曼树 1.路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径.

java字符串压缩解压示例

我测试的字符串是JQuery源码. 明文长度:78082压缩后:26566加密长度:54746再压缩:41647-----------------------------密文长度:41647解压缩:54746解密后:26566再解压:78082-----------------------------比对成功 Des需要Jar:sun.misc.BASE64Decoder.jar Test 复制代码 代码如下: public static void main(String[] args) thr

Java字符串的压缩与解压缩的两种方法

应用场景 当字符串太长, 需要将字符串值存入数据库时,如果字段长度不够,则会出现插入失败: 或者需要进行Http传输时,由于参数长度过长造成http传输失败等. 字符串压缩与解压方法 方法一:用 Java8中的gzip /** * 使用gzip压缩字符串 * @param str 要压缩的字符串 * @return */ public static String compress(String str) { if (str == null || str.length() == 0) { retu

Java&nbsp;字符串压缩与解压的开发记录

目录 1.场景: 2.CompressUtil类: 3.注意点: 4.单元测试: 1.场景: 由于数据库字段长度有限,并且不能随意的修改数据库字段的配置,数据库的某个字段设置的长度可能在设置初期是满足需求的,后期由于业务变更或业务量增大导致该字段存储的数据增长,落库时可能因为该字段数据长度过长导致落库失败,基于这种场景我们就有必要进行字符串的压缩,然后再进行落库,而落库后取出数据使用时再进行解压即可. 2.CompressUtil类: 使用Java8中的gzip来进行实现 import lomb

java实现压缩字符串和java字符串过滤

题目一:通过键盘输入一串小写字母(a~z)组成的字符串. 请编写一个字符串过滤程序,若字符串中出现多个相同的字符,将非首次出现的字符过滤掉.比如字符串"abacacde"过滤结果为"abcde". 要求实现函数: 复制代码 代码如下: void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr); [输入] pInputStr:输入字符串lInputLen:输入字符串长度[输出]

java哈夫曼树实例代码

本文实例为大家分享了哈夫曼树java代码,供大家参考,具体内容如下 package boom; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Queue; class Node<T> implements Comparable<Node<T>>{ private T

C#求解哈夫曼树,实例代码

复制代码 代码如下: class HuffmanTree    {        private Node[] data;        public int LeafNum { get; set; }        public Node this[int index]        {            get { return data[index]; }            set { data[index] = value; }        }        public Hu

解读赫夫曼树编码的问题

定义: 结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积.树的带权路径长度为树中所有叶子结点的带权路径长度之和.假设有n个权值,试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为wi,则其中带权路径长度最小的二叉树称做最优二叉树或赫夫曼树. 构造赫夫曼树的方法: (1)根据给定的n个权值{w1,w2,w3......}构成n棵二叉树的集合F={T1,T2,T3,T4......},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均空. (2)在F中选取两棵根结点的权值

C++数据结构之文件压缩(哈夫曼树)实例详解

C++数据结构之文件压缩(哈夫曼树)实例详解 概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述:         1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编

图文详解JAVA实现哈夫曼树

前言  我想学过数据结构的小伙伴一定都认识哈夫曼,这位大神发明了大名鼎鼎的"最优二叉树",为了纪念他呢,我们称之为"哈夫曼树".哈夫曼树可以用于哈夫曼编码,编码的话学问可就大了,比如用于压缩,用于密码学等.今天一起来看看哈夫曼树到底是什么东东. 概念 当然,套路之一,首先我们要了解一些基本概念. 1.路径长度:从树中的一个结点到另一个结点之间的分支构成这两个结点的路径,路径上的分支数目称为路径长度. 2.树的路径长度:从树根到每一个结点的路径长度之和,我们所说的完全

C++ 哈夫曼树对文件压缩、加密实现代码

在以前写LZW压缩算法的时候,遇到很多难受的问题,基本上都在哈夫曼编码中解决了,虽然写这代码很费神,但还是把代码完整的码出来了,毕竟哈夫曼这个思想确实很牛逼.哈夫曼树很巧妙的解决了当时我在LZW序列化的时候想解决的问题,就是压缩后文本的分割.比如用lzw编码abc,就是1,2,3.但这个在存为文件的时候必须用分割符把1,2,3分割开,非常浪费空间,否则会和12 23 123 产生二义性.而哈夫曼树,将所有char分布在叶节点上,在还原的时候,比如1101110,假设110是叶节点,那么走到110

C++数据结构与算法之哈夫曼树的实现方法

本文实例讲述了C++数据结构与算法之哈夫曼树的实现方法.分享给大家供大家参考,具体如下: 哈夫曼树又称最优二叉树,是一类带权路径长度最短的树. 对于最优二叉树,权值越大的结点越接近树的根结点,权值越小的结点越远离树的根结点. 前面一篇图文详解JAVA实现哈夫曼树对哈夫曼树的原理与java实现方法做了较为详尽的描述,这里再来看看C++实现方法. 具体代码如下: #include <iostream> using namespace std; #if !defined(_HUFFMANTREE_H

使用C语言详解霍夫曼树数据结构

1.基本概念 a.路径和路径长度 若在一棵树中存在着一个结点序列 k1,k2,--,kj, 使得 ki是ki+1 的双亲(1<=i<j),则称此结点序列是从 k1 到 kj 的路径. 从 k1 到 kj 所经过的分支数称为这两点之间的路径长度,它等于路径上的结点数减1. b.结点的权和带权路径长度 在许多应用中,常常将树中的结点赋予一个有着某种意义的实数,我们称此实数为该结点的权,(如下面一个树中的蓝色数字表示结点的权) 结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘

Python数据结构之哈夫曼树定义与使用方法示例

本文实例讲述了Python数据结构之哈夫曼树定义与使用方法.分享给大家供大家参考,具体如下: HaffMan.py #coding=utf-8 #考虑权值的haff曼树查找效率并非最高,但可以用于编码等使用场景下 class TreeNode: def __init__(self,data): self.data=data self.left=None self.right=None self.parent=None class HaffTree: def __init__(self): sel

C语言实现哈夫曼树

本文实例为大家分享了C语言实现哈夫曼树的具体代码,供大家参考,具体内容如下 //哈夫曼树C语言实现 #include <stdio.h> #include <stdlib.h> typedef struct HuffmanNode { char letter;//存储的字符,叶节点为字母,非叶节点为# struct HuffmanNode *parent;//父亲结点 int code;//如果为父亲结点的左孩子,则为0,右孩子为1 }HuffmanNode; typedef st