🔥无损压缩🔥哈夫曼算法

一、前言

今天了解一下压缩软件底层使用的什么算法，介绍一下常见的两种格式压缩算法，如下表，本文主要介绍DEFLATE中的哈夫曼算法

格式	算法	压缩软件
RAR	Roshal Archive	WinRaar
ZIP	LZ77和哈夫曼算法	7-Zip

二、算法简介

压缩“hello world”，根据整组数据中符号出现的频率高低，决定如何给符号编码。如果符号出现的频率越高，则给符号的码越短，相反符号的号码越长。

1. 首先将这个文本中的字符提取出来，分别统计各个字符出现的频次 (h:1, e:1, l:3, o:2, w:1, r:1, d:1, 空格: 1)
2. 构建哈夫曼树，每一轮都选择权重最小的两个字符相加，直至顶部只有一个节点。

1. 压缩，将“hello world”用编码代替 01100111000001011110001010100110，压缩后占32bit。压缩前按UTF-8编码，1个英文字符占1个字节，11 * 8 = 88bit，压缩率为63.64%。
2. 解压，从01100111000001011110001010100110最左侧开始，先取出”0“去哈夫曼树中查找是否有对应的字符，如果没有就取“01”依次向后进行。

三、算法实现

class Huffman {
  // 构建哈夫曼树
  static buildTree(data) {
      let freq = {};
      // 计算字符频率
      for (let i = 0; i < data.length; i++) {
          if (freq[data[i]] === undefined) {
              freq[data[i]] = 0;
          }
          freq[data[i]]++;
      }

      // 构建节点
      let nodes = [];
      for (let char in freq) {
          nodes.push(new Node(char, freq[char]));
      }

      // 构建哈夫曼树
      while (nodes.length > 1) {
          nodes.sort((a, b) => a.freq - b.freq);
          let left = nodes.shift();
          let right = nodes.shift();
          let parent = new Node(null, left.freq + right.freq);
          parent.left = left;
          parent.right = right;
          nodes.push(parent);
      }

      return nodes[0];
  }

  // 生成哈夫曼编码
  static buildCode(tree) {
      let codes = {};
      function traverse(node, code) {
          if (node.char !== null) {
              codes[node.char] = code;
          } else {
              traverse(node.left, code + '0');
              traverse(node.right, code + '1');
          }
      }
      traverse(tree, '');
      return codes;
  }

  // 压缩
  static compress(data) {
      let tree = Huffman.buildTree(data);
      let codes = Huffman.buildCode(tree);
      let compressed = '';
      for (let i = 0; i < data.length; i++) {
          compressed += codes[data[i]];
      }
      return {
          tree: tree,
          data: compressed
      };
  }

  // 解压
  static decompress(compressed) {
      let decompressed = '';
      let current = compressed.tree;
      for (let i = 0; i < compressed.data.length; i++) {
          if (compressed.data[i] === '0') {
              current = current.left;
          } else {
              current = current.right;
          }
          if (current.char !== null) {
              decompressed += current.char;
              current = compressed.tree;
          }
      }
      return decompressed;
  }
}

class Node {
  constructor(char, freq) {
      this.char = char;
      this.freq = freq;
      this.left = null;
      this.right = null;
  }
}

// 示例
let data = "abbcccddddeeeee";
let compressed = Huffman.compress(data);
console.log("Compressed:", compressed.data);
console.log("Decompressed:", Huffman.decompress(compressed));

四、使用场景

• 做App、游戏时，本地存储数据
• 通信时压缩传输数据