如何按照 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 遍历输入,无法保证两端生成完全相同的编码。
格式还应定义解码终止条件,例如记录原始符号数量或有效比特数,避免将最后一个字节中的填充位当作数据。这些信息由压缩格式定义,可以在压缩流程中统一写入。
备注:内容仅供参考。
