ChatGPT算法训练营—Huffman编码

简介: Huffman 算法是一种常用于数据压缩的算法,其思想是将频繁出现的字符使用较短的编码,不频繁出现的字符使用较长的编码,以此达到压缩数据的目的。本篇文章我们就来一起学习下 Huffman 算法。

本文由 ChatGpt 生成,作者校验,请称我为校验工程师


Huffman 算法是一种常用于数据压缩的算法,其思想是将频繁出现的字符使用较短的编码,不频繁出现的字符使用较长的编码,以此达到压缩数据的目的。本篇文章我们就来一起学习下 Huffman 算法。

核心思想


Huffman 算法的核心思想是通过构建一棵Huffman 树,将频繁出现的字符使用较短的编码,不频繁出现的字符使用较长的编码,以此达到压缩数据的目的。


构建 Huffman 树的过程如下:

1.统计每个字符在数据中出现的频率。

2.将每个字符视为一棵树,权值为该字符出现的频率。

3.选择两棵权值最小的树合并成一棵新树,新树的权值为两棵树的权值之和,合并后的树的根节点没有字符,只有权值。

4.重复步骤3,直到只剩下一棵树,这棵树就是 Huffman 树。


Huffman 树构建完成后,对于每个字符,其对应的编码就是从根节点到该字符所在节点的路径上,左儿子表示 0,右儿子表示 1 的二进制序列。由于 Huffman  树的构建过程保证了频率高的字符离根节点近,频率低的字符离根节点远,因此编码长度不同,可以达到压缩数据的目的。


我们来举个例子。让我们以字符串 "aabbbcddddeeeee" 为例,一步一步实现 Huffman 编码算法。

1.统计字符出现的频率;

字符 出现频率
a 2
b 3
c 1
d 4
e 5

2.将字符按照频率从小到大排序;

字符 出现频率
c 1
a 2
b 3
d 4
e 5

3.将出现频率最小的两个字符合并为一棵二叉树,其中一个字符作为左子树,另一个字符作为右子树;

    3
   / \
  a   c

4.将新生成的二叉树的根节点作为一个虚拟字符,其出现频率为两个字符的频率之和;虚拟字     符的频率为 1 + 2 = 3。
  我们将虚拟字符加入到已排序的字符列表中,得到:

字符 出现频率
b 3
3 3
d 4
e 5

5.重复步骤 3 到步骤 5,直到字符列表中只剩下一个元素;
  我们再次合并字符列表中频率最小的两个字符 b 和 3,得到以下二叉树:

   6
  / \
 b   3
    / \
   a   c
  1. 虚拟字符的频率为 3 + 3 = 6。
    我们将虚拟字符加入到已排序的字符列表中,得到:
字符 出现频率
d 4
e 5
6 6
  1. 继续合并,得到以下二叉树:
       10
     /   \
    6     d
   / \
  b   3
     / \
    a   c
  1. 虚拟字符的频率为 4 + 6 = 10。
    我们将虚拟字符加入到已排序的字符列表中,得到:
字符 出现频率
e 5
10 10
  1. 最后,我们得到了以下二叉树:
      21
     /   \
    10    e
   / \
  6   d
 / \
b   3
   / \
  a   c

6.根据生成的二叉树,给出每个字符的编码。
  遍历上述二叉树,往左就追加 0, 往右就追加1, 我们可以得到以下字符编码:

字符 编码
a 0010
b 000
c 0011
d 01
e 1

这个时候,我们可以来算一下编码前和编码后的比特数:

原始字符串 "aabbbcddddeeeee" 的长度为 16 个字符 * 8 个比特/字符 = 128 个比特。


而 Huffman 编码后的长度是每个字符的出现频率乘以它的编码长度的总和。根据上述示例,可以计算出 Huffman 编码后的长度为:


4 * 2 + 3 * 3 + 4 * 1 + 2 * 4 + 1 * 5 = 34 个比特


因此,Huffman 编码可以将原始字符串的长度从 128 个比特压缩到 34 个比特,可以看到编码后的长度显著减小。


解码实现也是根据 Huffman 树。通过逐一遍历编码字符串的每个字符,根据字符的 0/1 值,不断沿着 Huffman 树的左右子树进行移动,直到遇到叶子节点,即可解码出原始字符串。注意,解码时需要从根节点开始遍历整棵 Huffman 树。

代码实现


Kotlin 实现


import java.util.*
// 定义节点类
class Node(
    val frequency: Int,
    val character: Char? = null,
    val left: Node? = null,
    val right: Node? = null
) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return frequency - other.frequency
    }
}
// 构造 Huffman 树
fun buildHuffmanTree(data: String): Node? {
    // 统计字符出现频率
    val frequencyMap = mutableMapOf<Char, Int>()
    for (char in data) {
        frequencyMap[char] = frequencyMap.getOrDefault(char, 0) + 1
    }
    // 构造节点队列,按照频率从小到大排序
    val queue = PriorityQueue<Node>()
    for ((char, frequency) in frequencyMap) {
        queue.offer(Node(frequency, char))
    }
    // 合并节点,构造 Huffman 树
    while (queue.size > 1) {
        val left = queue.poll()
        val right = queue.poll()
        queue.offer(Node(left.frequency + right.frequency, left = left, right = right))
    }
    // 返回根节点
    return queue.poll()
}
fun encode(root: Node, data: String): BitSet {
    // 构建字符与编码之间的映射表
    val codeTable = buildCodeTable(root)
    // 将字符串转换为比特数组
    val bitArray = data.toCharArray().map { codeTable[it]!! }.joinToString("").toCharArray().map { it == '1' }.toBooleanArray()
    // 将比特数组转换为比特集合
    val bitSet = BitSet(bitArray.size)
    for (i in bitArray.indices) {
        bitSet[i] = bitArray[i]
    }
    return bitSet
}
fun decode(root: Node, bitSet: BitSet, length: Int): String {
    // 将比特集合转换为比特数组
    val bitArray = BooleanArray(length)
    for (i in 0 until length) {
        bitArray[i] = bitSet[i]
    }
    // 将比特数组转换为字符串
    val sb = StringBuilder()
    var curr = root
    for (bit in bitArray) {
        if (bit) {
            curr = curr.right!!
        } else {
            curr = curr.left!!
        }
        if (curr.char != null) {
            sb.append(curr.char)
            curr = root
        }
    }
    return sb.toString()
}
// 这里用的是栈实现, rust 版本用的是递归调用,都体验下
private fun buildCodeTable(root: Node): Map<Char, String> {
    val codeTable = mutableMapOf<Char, String>()
    val stack = LinkedList<Node>()
    stack.push(root)
    var code = ""
    while (stack.isNotEmpty()) {
        val node = stack.pop()
        if (node.char != null) {
            codeTable[node.char!!] = code
        } else {
            node.right?.let {
                stack.push(it)
                code += "1"
            }
            node.left?.let {
                stack.push(it)
                code += "0"
            }
        }
        if (code.isNotEmpty() && node.char == null) {
            code = code.dropLast(1)
        }
    }
    return codeTable
}

Rust 实现


use std::collections::BinaryHeap;
use std::collections::HashMap;
use bitvec::prelude::*;
#[derive(Debug, Eq, PartialEq)]
struct Node {
    character: Option<char>,
    frequency: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}
impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.frequency.cmp(&other.frequency).reverse()
    }
}
impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}
impl Node {
    fn new(frequency: i32, character: Option<char>, left: Option<Box<Node>>, right: Option<Box<Node>>) -> Self {
        Node {
            frequency,
            character,
            left,
            right,
        }
    }
}
// 构建树
fn build_tree(s: &str) -> Option<Node> {
    let mut frequency_map: HashMap<char, i32> = HashMap::new();
    for c in s.chars() {
        *frequency_map.entry(c).or_insert(0) += 1;
    }
    // 通过二叉堆实现 Huffman 树的构建,可以很方便地将字符的出现频率按照从小到大的顺序排序,并且在每次取出两个频率最小的节点时,可以快速地找到它们
    // 在 Rust 中,二叉堆是通过 std::collections::BinaryHeap 实现的,它是一个泛型类型,可以存储任何可以比较大小的元素。默认情况下,BinaryHeap 会实现最大堆的功能
    // 我们通过对元素实现 Ord trait 来改变它们的顺序,从而实现最小堆的功能
    let mut heap: BinaryHeap<Node> = BinaryHeap::new();
    for (character, frequency) in frequency_map {
        heap.push(Node::new(frequency, Some(character), None, None));
    }
    while heap.len() > 1 {
        let left = heap.pop().unwrap();
        let right = heap.pop().unwrap();
        heap.push(Node::new(left.frequency + right.frequency, None, Some(Box::new(left)), Some(Box::new(right))));
    }
    heap.pop()
}
// 编码
fn encode(s: &str, root: &Node) -> Option<String> {
    let mut encoding_map: HashMap<char, String> = HashMap::new();
    build_encoding_map(&root, &mut encoding_map, String::new());
    let mut result = String::new();
    for c in s.chars() {
        if let Some(encoding) = encoding_map.get(&c) {
            result.push_str(encoding);
        } else {
            return None;
        }
    }
    Some(result)
}
// Huffman 编码函数
fn encode(root: &Node, input: &str) -> BitVec {
    // 构建编码表
    let mut code_table: HashMap<char, BitVec> = HashMap::new();
    build_code_table(root, &mut code_table, &BitVec::new());
    // 将输入字符串转换为 Huffman 编码
    let mut output = BitVec::new();
    for c in input.chars() {
        let code = code_table.get(&c).unwrap();
        output.extend(code.iter());
    }
    output
}
// Huffman 解码函数
fn decode(root: &Node, input: &BitVec) -> String {
    let mut output = String::new();
    let mut node = root;
    // 遍历输入的比特流
    for bit in input.iter() {
        // 如果当前节点为叶子节点,说明找到了一个字符
        if node.character.is_some() {
            output.push(node.character.unwrap());
            node = root;
        }
        // 根据当前比特值选择左右子节点
        node = if bit { node.right.as_ref() } else { node.left.as_ref() }
            .expect("Invalid input");
    }
    // 处理最后一个字符
    if node.character.is_some() {
        output.push(node.character.unwrap());
    }
    output
}
// 遍历二叉树寻找节点
fn build_code_table(node: &Node, code_table: &mut HashMap<char, BitVec>, code: &BitVec) {
    match &node.character {
        // 如果当前节点为叶子节点,将字符和对应的编码添加到编码表中
        Some(&c) => {
            code_table.insert(c, code.clone());
        }
        // 如果当前节点不是叶子节点,递归处理左右子节点
        None => {
            let mut left_code = code.clone();
            left_code.push(false);
            build_code_table(&node.left.as_ref().unwrap(), code_table, &left_code);
            let mut right_code = code.clone();
            right_code.push(true);
            build_code_table(&node.right.as_ref().unwrap(), code_table, &right_code);
        }
    }
}


目录
相关文章
|
2月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
76 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
1月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
2月前
|
机器学习/深度学习 人工智能 并行计算
DeepSpeed Chat: 一键式RLHF训练,让你的类ChatGPT千亿大模型提速省钱15倍
DeepSpeed Chat 是一款革命性的平台,专为简化和加速类ChatGPT模型的训练而设计。通过一键式脚本,用户可以轻松完成从预训练模型到生成自定义ChatGPT模型的全过程。该系统复刻了InstructGPT的RLHF训练方法,并集成了一系列优化技术,如DeepSpeed Hybrid Engine,大幅提升了训练效率和经济性。使用DeepSpeed Chat,即使是拥有数千亿参数的大模型,也能在短时间内完成训练,且成本显著降低。无论是单GPU还是多GPU集群环境,DeepSpeed Chat都能提供卓越的性能和易用性,让RLHF训练变得更加普及。
DeepSpeed Chat: 一键式RLHF训练,让你的类ChatGPT千亿大模型提速省钱15倍
|
2月前
|
机器学习/深度学习 算法 决策智能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
|
2月前
|
算法 Java C++
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
|
2月前
|
算法 C++
蓝桥 算法训练 共线(C++)
蓝桥 算法训练 共线(C++)
|
4月前
|
机器学习/深度学习 人工智能 自然语言处理
让非算法同学也能了解 ChatGPT 等相关大模型
让非算法同学也能了解 ChatGPT 等相关大模型
让非算法同学也能了解 ChatGPT 等相关大模型
|
4月前
|
人工智能 开发者 芯片
【51单片机】单片机开发者的福音: 让AI看电路图帮你编写程序(使用ChatGPT 中训练好的单片机工程师模型)
使用AI大语言模型编写 单片机程序. 使用的是 OpenAI公司发布的 ChatGPT .在ChatGPT上有别人训练好的 单片机工程师 with Keil uVision 5 - C Code Explainer模型, 可以上传电路图改模型可以通过这个用户所给的电路图进行编程.
308 0
【51单片机】单片机开发者的福音: 让AI看电路图帮你编写程序(使用ChatGPT 中训练好的单片机工程师模型)
|
4月前
|
算法
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()