霍夫曼编码通过贪心策略构建最优前缀码，统计字符频率并用最小堆合并节点生成霍夫曼树，为高频字符分配短编码、低频字符分配长编码，实现高效数据压缩。
霍夫曼编码是一种经典的贪心算法应用，用于数据压缩。它通过构建带权路径长度最短的二叉树（即霍夫曼树），为出现频率高的字符分配较短的编码，频率低的字符分配较长的编码，从而实现高效压缩。
霍夫曼树构建思路
核心思想是每次选择两个频率最小的节点合并，直到只剩一棵树：
- 统计每个字符的出现频率
- 将每个字符作为叶子节点，按频率构建成优先队列（最小堆）
- 不断取出频率最小的两个节点，创建新内部节点，频率为其和，并重新插入队列
- 重复直到队列只剩一个节点，即为根节点
JavaScript实现代码
// 节点定义 function Node(char, freq, left = null, right = null) { return { char, freq, left, right }; }// 构建霍夫曼树 function buildHuffmanTree(text) { // 统计频率 const freqMap = {}; for (let ch of text) { freqMap[ch] = (freqMap[ch] || 0) + 1; }
// 构建最小堆（用数组模拟） let heap = Object.keys(freqMap).map(ch => Node(ch, freqMap[ch]) );
// 最小堆排序函数（简单实现） const heapify = () => { heap.sort((a, b) => a.freq - b.freq); };
heapify();
// 合并节点 while (heap.length > 1) { const left = heap.shift(); // 最小 const right = heap.shift(); // 次小 const merged = Node(null, left.freq + right.freq, left, right); heap.push(merged); heapify(); }
return heap[0]; // 返回根节点 }
// 生成编码表 function generateCodes(root) { const codes = {}; function traverse(node, code) { if (!node) return; if (node.char !== null) { codes[node.char] = code || "0"; // 单字符情况 } else { traverse(node.left, code + "0"); traverse(node.right, code + "1"); } } traverse(root, ""); return codes; }
// 编码字符串 function huffmanEncode(text) { if (!text) return { encoded: "", codes: {}, tree: null };
const root = buildHuffmanTree(text); const codes = generateCodes(root); const encoded = text.split("").map(ch => codes[ch]).join(""); return { encoded, codes, tree: root }; }
// 解码（可选实现） function huffmanDecode(encoded, root) { if (!encoded || !root) return ""; let result = ""; let current = root; for (let bit of encoded) { current = bit === "0" ? current.left : current.right; if (current.char !== null) { result += current.char; current = root; } } return result; }
使用示例
const text = "abracadabra"; const { encoded, codes } = huffmanEncode(text);console.log("原始文本:", text); console.log("编码表:", codes); console.log("编码结果:", encoded); console.log("原长度:", text.length 8); // 假设ASCII console.log("编码长度:", encoded.length); console.log("压缩率:", ((text.length 8 - encoded.length) / (text.length * 8)).toFixed(2));
基本上就这些。这个实现虽然没有用真正的优先队列类，但用数组加排序模拟了最小堆行为，适合理解原理。实际项目中可以优化堆结构提升性能。霍夫曼编码展示了贪心策略在构造最优前缀码中的有效性。
立即学习“Java免费学习笔记（深入）”；
