PAYATHON 2026

如何按照 OOP 实践设计 Huffman 压缩器并确定编码表的归属?

技术老齐

树生成编码表,压缩器持有并使用编码表

当前需求下,建议让 HuffmanTreeNaive 提供 makeCodebook() const,在内部遍历树,返回一份独立的编码表。压缩器按值持有这份表,负责查表和写入比特,无须接触树节点。

表示编码的 struct 可以定义在公共头文件或命名空间中。类型定义的位置和运行时对象的所有权是两回事。即使把 struct 嵌套在 HuffmanTreeNaive 中,也不会让树自动拥有所有编码对象。

如果以后需要反复编码、解码,并共享同一套 Huffman 模型,可以让 HuffmanModel 同时持有树和编码表。这样也符合封装要求,不必为了减少类的行数而强行拆分。

如何划分职责

组件 职责
HuffmanTreeNaive 根据频率建树,管理节点生命周期,通过公开接口生成编码表
Codebook 保存符号与比特码之间的映射
Compressor 查询编码表,将编码交给比特输出组件
比特输出组件 将比特打包成字节,处理缓冲与末尾填充

树在内部遍历自己的节点,再返回编码结果,符合封装原则。压缩器只需查询符号对应的编码,不需要了解节点如何连接。

编码表来自树中的路径,由树生成编码表属于合理的职责范围。文件读写、输出格式、缓冲和错误报告等工作,则应避免继续放进同一个类。

如果建树只是为了生成一次编码表,生成后就可以释放树。按值返回的编码表不依赖树的生命周期。

编码类型与编码表怎样定义

压缩时需要按字符查找编码,用映射容器比用同时保存字符和编码的对象数组更直接:

#include <string>
#include <unordered_map>

using Symbol = unsigned char;

struct Code {
    std::string bits;
};

using Codebook = std::unordered_map<Symbol, Code>;

字符已经保存在映射的键中,Code 只保存比特码,无须重复存储字符。如果编码没有额外属性,也可以直接使用:

using Codebook = std::unordered_map<Symbol, std::string>;

示例用 "0101" 这样的字符串表示编码,便于检查。输出时仍需将字符转换成比特并打包;直接写出字符串,无法得到预期的压缩结果。

这里按字节处理输入,用 unsigned char 表示符号。对于 UTF-8 文本,压缩的是编码后的字节。如果要按 Unicode 码点建模,就需要调整符号类型和输入解析方式。

让树通过公开接口返回编码表

可以在已有的 HuffmanTreeNaive 中加入以下成员。代码沿用原来的私有 Node 类型,并假定树已经正确构造:

public:
    Codebook makeCodebook() const
    {
        Codebook result;
        std::string path;
        collectCodes(root, path, result);
        return result;
    }

private:
    static void collectCodes(
        const Node* node,
        std::string& path,
        Codebook& result)
    {
        if (node == nullptr) {
            return;
        }

        if (node->left == nullptr && node->right == nullptr) {
            // 只有一个符号时,约定使用 "0"。
            result.emplace(
                static_cast<Symbol>(node->ch),
                Code{path.empty() ? "0" : path});
            return;
        }

        path.push_back('0');
        collectCodes(node->left, path, result);
        path.pop_back();

        path.push_back('1');
        collectCodes(node->right, path, result);
        path.pop_back();
    }

Node 和遍历函数仍是私有成员。返回的 Codebook 保存独立的键和值,没有节点指针或引用,因此树销毁后,编码表仍然有效。

这里约定单一符号使用 "0",编码器和解码器必须遵守同一约定。也可以使用空编码,依靠原始符号数量恢复数据,但这需要专门设计格式和解码逻辑。

压缩器只依赖编码表

以下示例使用 C++17。BitWriter 需要提供 writeBit(bool),并负责字节打包和最终刷新。

#include <string_view>
#include <utility>

class Compressor {
public:
    explicit Compressor(Codebook codes)
        : codes_(std::move(codes))
    {
    }

    template<class BitWriter>
    void encode(std::string_view input, BitWriter& output) const
    {
        for (unsigned char symbol : input) {
            const auto& bits = codes_.at(symbol).bits;

            for (char bit : bits) {
                output.writeBit(bit == '1');
            }
        }
    }

private:
    Codebook codes_;
};

创建压缩器时,传入生成的编码表即可:

Compressor compressor(tree.makeCodebook());

构造函数按值接收编码表,再将它移动到成员中,由压缩器持有。传入临时结果时,压缩器也无须保留对树的引用。

示例使用 at() 查表,遇到表中没有的符号时会抛出 std::out_of_range。实际接口可以保留这一行为,也可以改为返回明确的编码错误。如果要求出错时不留下部分输出,就需要在写入前完成检查,或使用可回滚的输出缓冲。

当前场景按值持有即可。如果多个压缩器需要复用大型编码表,再考虑共享只读所有权。

什么情况下应该同时保存树和编码表

如果同一个对象负责管理编码模型,还要为解码提供树结构,就可以同时持有树和编码表。此时可以将类命名为 HuffmanModel,通过 codeFor(symbol) 等接口提供编码查询。

树和编码表必须始终对应。最简单的做法是在构造期间完成建树和编码表生成,之后保持模型不变。如果允许重新建树,就必须同步更新编码表,或使缓存失效。

如果类仍叫 HuffmanTreeNaive,而调用方只需要获取一次编码表,按值返回更容易管理,也能避免长期缓存的一致性问题。

原实现还需要修正的问题

原代码还有几处错误,与类的职责划分无关,应先修正。

递归释放检查了错误的指针

deleteHelper() 应检查当前参数 node。原代码检查的是 root,递归到空子节点时仍会访问 node->left:

void deleteHelper(Node* node)
{
    if (node == nullptr) {
        return;
    }

    deleteHelper(node->left);
    deleteHelper(node->right);
    delete node;
}

空频率表会导致非法访问

没有正频率符号时,队列为空,但 while (pq.size() != 1) 仍会进入循环,随后调用空队列的 top()。

应将成员初始化为:

Node* root = nullptr;

合并循环改为:

while (pq.size() > 1) {
    // 保留原来的取出两个节点并合并的操作。
}

循环结束后,再设置根节点:

root = pq.empty() ? nullptr : pq.top();

这样就能安全处理空队列,让空输入对应空树和空编码表。

频率类型需要保持一致

输入使用 uint64_t,节点和合并结果却使用 int,可能丢失数值。建议统一使用 std::uint64_t,并在相加前检查溢出。

构造函数参数也可以改为常量引用,避免复制整张频率表:

explicit HuffmanTreeNaive(
    const std::unordered_map<char, std::uint64_t>& freq);

需要包含 <cstdint>。

节点所有权需要明确

当前类通过裸指针拥有节点,并定义了析构函数。默认复制会让两个对象指向同一棵树,最终重复释放。

至少应禁用复制,或实现深拷贝。后续重构时,更适合用 std::unique_ptr 管理节点,让节点自动释放。优先队列可以保存不拥有节点的指针,但在这些指针的使用期间,节点的所有者必须始终存在。

解码端还需要获得相同的编码信息

解码器也需要获得编码信息。压缩格式应保存足以恢复编码关系的数据,例如序列化的树,或规范 Huffman 编码所需的符号与码长。

如果保存频率表,让解码端重新建树,就必须明确相同频率节点的排序规则。原代码只比较频率,又通过 unordered_map 遍历输入,无法保证两端生成完全相同的编码。

格式还应定义解码终止条件,例如记录原始符号数量或有效比特数,避免将最后一个字节中的填充位当作数据。这些信息由压缩格式定义,可以在压缩流程中统一写入。

备注:内容仅供参考。