霍夫曼编码通过构建带权路径最短的二叉树实现文本压缩，字符频率越高编码越短。首先统计字符频次并建立最小堆，逐步合并节点形成霍夫曼树；然后遍历树生成字符到二进制编码的映射表；编码时将字符替换为对应变长编码，解码时依比特流在树中路径查找对应字符，最终实现无损压缩与还原。该方法适用于高频重复文本的小规模压缩场景，有助于理解数据结构应用。
在前端开发中，处理大量文本数据时，优化存储和传输效率非常重要。霍夫曼编码是一种经典的无损压缩算法，能根据字符出现频率动态生成最优编码，特别适合用于压缩重复性高的文本内容。下面介绍如何用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不为空）时记录编码
示例代码：
CodeSquire
AI代码编写助手，把你的想法变成代码
103 查看详情
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等更强压缩方式，但理解其原理有助于提升对数据结构和算法的应用能力。
以上就是JavaScript数据压缩_霍夫曼编码与解码的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/867760.html
微信扫一扫 
支付宝扫一扫 
