C# Huffman 压缩编码实现

Refrain69 收录于类别技术

2025-06-28 2025-06-28 约 1777 字预计阅读 8 分钟

好久没有认真写一点东西了，今天来实现一个 Huffman 编码的算法。

1 原理分析

先来看一下 Huffman 编码和解码的基本原理：

1.1 编码

统计频率
- 遍历待编码的字符串 / 字节数组，统计每个字符 / 字节出现的频率
构建 Huffman 树
- 将每个字符和其频率作为节点
- 使用优先队列 (最小堆) 来构建 Huffman 树。
- 每次取出频率最小的两个节点，合并成一个新节点，直到只剩下一个节点
生成编码
- 从根节点开始，遍历树，左子节点为 0，右子节点为 1，直到叶节点
- 记录每个字符的编码
替换
- 使用生成的编码替换原字符串中的字符

1.2 解码

构建 Huffman 树
- 使用编码时生成的树结构
遍历编码
- 从根节点开始，根据编码的 0 和 1 走左子节点或右子节点
- 到达叶节点时，将对应字符 / 字节添加到结果中，并返回根节点继续遍历
重复直到遍历完整个编码

2 具体实现

先列举我们需要的几个类：

BitStream：用于处理位流的类
HuffmanNode：表示 Huffman 树的节点
PriorityQueue：优先队列

其中，PriorityQueue 在 .NET 6 及以上版本中已经有了，我们可以直接使用。另外两个类需要我们自己实现。

2.1 BitStream

BitStream 的主要功能是处理位流的读写，通过维护一个 underlying Stream，记录当前缓存的字节、当前位的位置和移位实现。

Huffman 需要的是 MSB (Most Significant Bit) 顺序的位流，我们这里把二者 (MSB、LSB) 都实现了。

BitStream.cs

2.2 HuffmanNode

HuffmanNode 包含以下属性：父节点、左右节点、该节点的值 (字符 / 字节)、该节点的频率、对应的编码 (可选)。

对于编码的表示，思来想去还是 bool[] 最合适。

同时注意到，构造节点有两种情况：

通过频率和字符 / 字节构造叶节点
通过左右子节点构造非叶节点

因此需要两个构造函数。而且显然，构造时即可确定该节点是否为叶节点，后续无需变动。

HuffmanNode.cs

2.3 PriorityQueue

在高版本 .NET 中，可以直接使用 System.Collections.Generic.PriorityQueue<TElement, TPriority>。

在低版本 .NET 中，我们可以自行用最小堆实现一个简易的优先队列。

此处实现遵循 .NET Framework 4.8 的语法。

PriorityQueue.cs

构造函数中需要传入一个比较器 IComparer<T>，用于比较节点的优先级：

HuffmanNodeComparer.cs

使用独立的比较器而不是让 HuffmanNode 实现 IComparable<HuffmanNode> ，是为了保证 HuffmanNode 在不同版本间的一致性。

2.4 HuffmanCompression

接下来是 Huffman 编码和解码的核心类 HuffmanCompression。

2.4.1 编码

统计频率

int[] freqs = new int[256];
foreach (byte b in data)
{
    freqs[b]++;
}

freqs 数组的索引是字节值，值是该字节出现的频率。

构建 Huffman 树

使用内置的 PriorityQueue 来构建 Huffman 树：

private HuffmanNode BuildTree(int[] freqs)
{
    PriorityQueue<HuffmanNode, int> queue = new();
    for (int i = 0; i < freqs.Length; i++)
    {
        if (freqs[i] > 0)
        {
            queue.Enqueue(new(freqs[i], (byte)i), freqs[i]);
        }
    }
    while (queue.Count > 1)
    {
        HuffmanNode left = queue.Dequeue();
        HuffmanNode right = queue.Dequeue();
        HuffmanNode parent = new(left, right);
        queue.Enqueue(parent, parent.Frequency);
    }
    return queue.Count > 0 ? queue.Dequeue() : null;
}

for 循环中构造所有叶节点，并将它们加入优先队列。然后通过不断取出频率最小的两个节点，合并成一个新节点，直到只剩下一个节点。频率的加和与叶节点的判断均在 HuffmanNode 的构造函数中完成。

使用自定义的 PriorityQueue 大同小异：

private HuffmanNode BuildTree(int[] freqs)
{
    PriorityQueue<HuffmanNode> queue = new PriorityQueue<HuffmanNode>(new HuffmanNodeComparer());
    for (int i = 0; i < freqs.Length; i++)
    {
        if (freqs[i] > 0)
        {
            queue.Enqueue(new HuffmanNode(freqs[i], (byte)i));
        }
    }
    while (queue.Count > 1)
    {
        HuffmanNode left = queue.Dequeue();
        HuffmanNode right = queue.Dequeue();
        HuffmanNode parent = new HuffmanNode(left, right);
        queue.Enqueue(parent);
    }
    return queue.Count > 0 ? queue.Dequeue() : null;
}

生成编码

用一个字典存储字节值和对应的编码。

如果当前节点是叶节点，则从该节点开始向上遍历，记录路径上的 0 和 1，直到到达根节点。将路径反转即为该字节的编码。

private void GenerateCodes(HuffmanNode node, Dictionary<byte, bool[]> codeTable)
{
    if (node == null)
    {
        return;
    }

    HuffmanNode current;
    if (node.IsLeaf)
    {
        List<bool> code = [];
        current = node;
        while (!current.IsRoot)
        {
            code.Add(current.Bit);
            current = current.Parent;
        }
        code.Reverse();
        codeTable[node.Value] = [.. code];
    }
    else
    {
        if (node.LeftChild != null)
        {
            GenerateCodes(node.LeftChild, codeTable);
        }
        if (node.RightChild != null)
        {
            GenerateCodes(node.RightChild, codeTable);
        }
    }
}

写入树

为了在解码时能够重建 Huffman 树，我们需要将树结构序列化到输出流中。可以使用前序遍历的方式来写入树。

private void WriteTree(HuffmanNode node)
{
    if (node.IsLeaf)
    {
        input.WriteBit(0);
        input.WriteBits(node.Value);
    }
    else
    {
        input.WriteBit(1);
        WriteTree(node.LeftChild);
        WriteTree(node.RightChild);
    }
}

替换

这一步就简单了，遍历原数据，将每个字节替换为对应的编码。

foreach (byte b in data)
{
    if (codeTable.TryGetValue(b, out bool[] code))
    {
        input.WriteBits(code);
    }
    else
    {
        throw new InvalidDataException($"No code found for byte {b}.");
    }
}

2.4.2 解码

有一个很巧的思路：字节的取值是 0~255，因此我们可以直接拿一个二维数组 ushort[512, 2]：

第一位表示字节值 (<256) 或父节点的索引 (>=256)，第二位表示左右子节点。

读取树

private const ushort MAX = 512;
private ushort index = 256;
private readonly ushort[,] children = new ushort[MAX, 2];

private ushort RebuildTree()
{
    switch (input.ReadBit())
    {
        case 0:
            return (ushort)input.ReadBits(8);
        case 1:
            ushort parent = index++;
            if (parent >= MAX)
            {
                throw new InvalidDataException("Exceeded huffman tree.");
            }
            children[parent, 0] = RebuildTree();
            children[parent, 1] = RebuildTree();
            return parent;
        default:
            throw new InvalidDataException("Invalid bit.");
    }
}

解码

这种表示的好处在于判断是否为叶节点非常简单：如果索引小于 256，则是叶节点，且该值即为字节值；如果索引大于等于 256，则是非叶节点，且可以通过 children 数组获取左右子节点。

public MemoryStream Decompress()
{
    if (mode != CompressionMode.Decompress)
    {
        throw new InvalidOperationException("Not in decompression mode.");
    }

    ushort root = RebuildTree();
    while (output.Length != decompressedLength)
    {
        ushort node = root;
        while (node >= 256)                 // Keep reading bits until we reach a leaf node
        {
            int bit = input.ReadBit();
            if (bit != -1)
            {
                node = children[node, bit]; // Traverse the tree based on the bit read
            }
        }
        output.WriteByte((byte)node);
    }
    return output;
}

3 完整代码

见 https://github.com/detached64/Huffman。

目录

目录