首页 > 文章 > 前端

JavaScript实现霍夫曼编码算法

时间：2025-11-29 15:13:18 109浏览收藏

对于一个文章开发者来说，牢固扎实的基础是十分重要的，golang学习网就来带大家一点点的掌握基础知识点。今天本篇文章带大家了解《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学习网公众号，给大家分享更多文章知识！

JavaScript 数据压缩贪心算法霍夫曼编码霍夫曼树