JavaScript数据压缩_霍夫曼编码与解码-js教程-PHP中文网

JavaScript数据压缩_霍夫曼编码与解码

紅蓮之龍

发布： 2025-11-19 17:15:05

原创

308人浏览过

霍夫曼编码通过构建带权路径最短的二叉树实现文本压缩，字符频率越高编码越短。首先统计字符频次并建立最小堆，逐步合并节点形成霍夫曼树；然后遍历树生成字符到二进制编码的映射表；编码时将字符替换为对应变长编码，解码时依比特流在树中路径查找对应字符，最终实现无损压缩与还原。该方法适用于高频重复文本的小规模压缩场景，有助于理解数据结构应用。

javascript数据压缩_霍夫曼编码与解码

在前端开发中，处理大量文本数据时，优化存储和传输效率非常重要。霍夫曼编码是一种经典的无损压缩算法，能根据字符出现频率动态生成最优编码，特别适合用于压缩重复性高的文本内容。下面介绍如何用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);
<p>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];
}</p>

登录后复制

生成编码表

从霍夫曼树根开始，向左走记为0，向右走记为1，直到叶子节点，路径即为该字符的二进制编码。

使用递归遍历树结构生成映射表：

初始化空对象用于存储字符到编码的映射
递归遍历树，每层追加'0'或'1'
遇到叶子节点（char不为空）时记录编码

示例代码：

Grammarly

Grammarly是一款在线语法纠正和校对工具，伟大的AI辅助写作工具

253

查看详情

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;
<p>const root = buildHuffmanTree(freqMap);
const codes = generateCodes(root);</p><p>let binaryStr = '';
for (const ch of str) binaryStr += codes[ch];</p><p>return { binaryStr, root }; // 返回编码结果和树结构用于解码
}</p>

登录后复制

解码示例：

function huffmanDecode(binaryStr, root) {
  let current = root;
  let result = '';
<p>for (const bit of binaryStr) {
current = bit === '0' ? current.left : current.right;</p><pre class='brush:php;toolbar:false;'>if (current.char !== null) {
  result += current.char;
  current = root; // 回到根节点继续
}

登录后复制

} return result; }

基本上就这些。霍夫曼编码在JavaScript中可用于小型文本压缩场景，比如配置项、日志缓存等。虽然现代浏览器已有gzip/Brotli等更强压缩方式，但理解其原理有助于提升对数据结构和算法的应用能力。

以上就是JavaScript数据压缩_霍夫曼编码与解码的详细内容，更多请关注php中文网其它相关文章！