霍夫曼编码通过构建带权路径最短的二叉树实现文本压缩，字符频率越高编码越短。首先统计字符频次并建立最小堆，逐步合并节点形成霍夫曼树；然后遍历树生成字符到二进制编码的映射表；编码时将字符替换为对应变长编码，解码时依比特流在树中路径查找对应字符，最终实现无损压缩与还原。该方法适用于高频重复文本的小规模压缩场景，有助于理解数据结构应用。
在前端开发中，处理大量文本数据时，优化存储和传输效率非常重要。霍夫曼编码是一种经典的无损压缩算法，能根据字符出现频率动态生成最优编码，特别适合用于压缩重复性高的文本内容。下面介绍如何用JavaScript实现霍夫曼编码与解码。
构建霍夫曼树
霍夫曼编码的核心是构造一棵带权路径最短的二叉树（霍夫曼树）。每个叶子节点代表一个字符，权重为其出现频率。频率越高的字符离根越近，编码越短。
步骤如下：
- 统计字符串中每个字符的出现次数
- 为每个字符创建一个节点，并按频率升序放入优先队列（最小堆）
- 不断取出频率最小的两个节点，合并成新节点，频率为两者之和，再插入队列
- 重复直到只剩一个节点，即为霍夫曼树的根
示例代码片段：
立即学习“Java免费学习笔记（深入）”；
function buildHuffmanTree(freqMap) {
const heap = [];
for (const ch in freqMap) {
heap.push({ char: ch, freq: freqMap[ch], left: null, right: null });
}
// 最小堆排序
heap.sort((a, b) => a.freq - b.freq);
while (heap.length > 1) {
const left = heap.shift();
const right = heap.shift();
const merged = {
char: null,
freq: left.freq + right.freq,
left,
right
};
heap.push(merged);
heap.sort((a, b) => a.freq - b.freq); // 可优化为堆结构
}
return heap[0];
}
生成编码表
从霍夫曼树根开始，向左走记为0，向右走记为1，直到叶子节点，路径即为该字符的二进制编码。
使用递归遍历树结构生成映射表：
- 初始化空对象用于存储字符到编码的映射
- 递归遍历树，每层追加'0'或'1'
- 遇到叶子节点（char不为空）时记录编码
示例代码：
function generateCodes(root) {
const codes = {};
function traverse(node, code) {
if (node) {
if (node.char !== null) {
codes[node.char] = code || '0'; // 单字符情况
} else {
traverse(node.left, code + '0');
traverse(node.right, code + '1');
}
}
}
traverse(root, '');
return codes;
}
编码与解码实现
有了编码表，就可以对原始字符串进行压缩和还原。
编码过程：将每个字符替换为对应的霍夫曼编码，拼接成比特串。
解码过程：从根节点开始，按比特流逐位判断方向（0左1右），到达叶子节点后输出字符并重置到根。
编码示例：
function huffmanEncode(str) {
const freqMap = {};
for (const ch of str) freqMap[ch] = (freqMap[ch] || 0) + 1;
const root = buildHuffmanTree(freqMap);
const codes = generateCodes(root);
let binaryStr = '';
for (const ch of str) binaryStr += codes[ch];
return { binaryStr, root }; // 返回编码结果和树结构用于解码
}
解码示例：
function huffmanDecode(binaryStr, root) {
let current = root;
let result = '';
for (const bit of binaryStr) {
current = bit === '0' ? current.left : current.right;
if (current.char !== null) {
result += current.char;
current = root; // 回到根节点继续
}}
return result;
}
基本上就这些。霍夫曼编码在JavaScript中可用于小型文本压缩场景，比如配置项、日志缓存等。虽然现代浏览器已有gzip/Brotli等更强压缩方式，但理解其原理有助于提升对数据结构和算法的应用能力。
