本文由 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
- 虚拟字符的频率为 3 + 3 = 6。
我们将虚拟字符加入到已排序的字符列表中，得到：
| 字符 | 出现频率 |
| d | 4 |
| e | 5 |
| 6 | 6 |
- 继续合并，得到以下二叉树：
10 / \ 6 d / \ b 3 / \ a c
- 虚拟字符的频率为 4 + 6 = 10。
我们将虚拟字符加入到已排序的字符列表中，得到：
| 字符 | 出现频率 |
| e | 5 |
| 10 | 10 |
- 最后，我们得到了以下二叉树：
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); } } }
