当前位置：首页 > 文章列表 > 文章 > 前端 > JavaScript实现霍夫曼编码算法

JavaScript实现霍夫曼编码算法

2026-03-01 18:35:53 0浏览收藏

本文深入浅出地讲解了霍夫曼编码这一经典贪心算法在数据压缩中的核心应用，通过JavaScript手写实现完整流程：从字符频率统计、最小堆模拟、霍夫曼树构建，到编码表生成与编解码逻辑，清晰展现“每次合并频率最小的两个节点”这一贪心选择如何自然导出带权路径长度最短的最优前缀码，让高频字符获得短编码、低频字符承担长编码，从而显著提升压缩效率——不仅代码简洁可运行，更兼顾原理透彻性与工程可扩展性，是理解贪心思想与实际算法落地的绝佳范例。

JavaScript贪心算法_霍夫曼编码实现

霍夫曼编码是一种经典的贪心算法应用，用于数据压缩。它通过构建带权路径长度最短的二叉树（即霍夫曼树），为出现频率高的字符分配较短的编码，频率低的字符分配较长的编码，从而实现高效压缩。

霍夫曼树构建思路

核心思想是每次选择两个频率最小的节点合并，直到只剩一棵树：

统计每个字符的出现频率
将每个字符作为叶子节点，按频率构建成优先队列（最小堆）
不断取出频率最小的两个节点，创建新内部节点，频率为其和，并重新插入队列
重复直到队列只剩一个节点，即为根节点

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));

基本上就这些。这个实现虽然没有用真正的优先队列类，但用数组加排序模拟了最小堆行为，适合理解原理。实际项目中可以优化堆结构提升性能。霍夫曼编码展示了贪心策略在构造最优前缀码中的有效性。

理论要掌握，实操不能落！以上关于《JavaScript实现霍夫曼编码算法》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！

霍夫曼编码