哈夫曼编码及其应用

「这是我参与2022首次更文挑战的第10天，活动详情查看：2022首次更文挑战」

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

这是一种高效的编码方式，在信息存储和传输过程中用于对信息进行压缩。

计算机只认识0（低电平）和1（高电平）。简单来说把人类能看懂的各种信息，转换成计算机能够识别的二进制形式，被称为编码。比如 ASCII 码。

等长编码：每个字符对应的二进制编码长度相等，容易设计，也很方便读写。但计算机的存储空间以及网络传输的宽带是有限的，等长编码最大的缺点就是编码结果太长，会占用过多的资源。

假如一段信息当中，只有A，B，C，D，E，F这6个字符，如果使用等长编码，我们可以把每一个字符都设计成长度为3的二进制编码：

 

给定一段信息 “ABEFCDAED”，就可以编码成二进制的 “000 001 100 101 010 011 000 100 011”，编码总长度是27。

 

 但是，这样的编码方式是最优的设计吗？如果我们让不同的字符对应不同长度的编码，结果会怎样呢？比如：

给定的信息 “ABEFCDAED”，就可以编码成二进制的 “0 00 10 11 01 1 0 10 1”，编码的总长度只有14。

这样的编码设计可一使总长度大大缩短，但是这样设计会带来歧义，如A的编码是0，B的编码是00，那么000既可能代表AB也可能代表AAA，所有这种不定长的代码是不能随意设计的。

哈夫曼编码(Huffman Coding)实现了两个重要目标：

1. 任何一个字符编码，都不是其他字符编码的前缀。

2. 信息编码的总长度最小。

构建哈夫曼树

已知字符集{ a, b, c, d, e, f }，若各字符出现的次数分别为{ 6, 3, 8, 2, 10, 4 }，则对应字符集中各字符的哈夫曼编码可能是：

1.找最小两个数（2和3），放进树中（小左大右），每次组合多一个父节点（2+3=5）

2.再选出2个最小的数（排除已选）—— 4 和 6，因为 4 < 5, 6 > 5，单独拿4来跟5组合（小左大右）

3.继续选取最小两个数 6 和 8，因为 6 < 9 , 8< 9 所以6和8自己组合（小左大右） （组合后先放一边）

4.取出最后10，10 要和这两个子树根节点最小的组合（9<14,所以和9组合）（小左大右）

5.把14的子树组合上去（小左大右）  所以放左边

6.将对应的字符填上去，从根节点开始向下走往左为0，往右1。走到对应的字符的路径就是该字符的哈夫曼编码（左0右1）

字符	哈夫曼编码
A	00
B	1011
C	01
D	1010
E	11
F	100

这样生成的编码没有前缀问题带来的歧义。因为每一个字符对应的都是哈夫曼树的叶子结点，从根结点到这些叶子结点的路径并没有包含关系，最终得到的二进制编码自然也不会是彼此的前缀。

这样生成的编码能保证总长度最小 。哈夫曼树的重要特性，就是所有叶子结点的（权重 X 路径长度）之和最小。放在信息编码的场景下，叶子结点的权重对应字符出现的频次，结点的路径长度对应字符的编码长度。所有字符的（频次 X 编码长度）之和最小，自然就说明总的编码长度最小。

应用

• 数据压缩
• 压缩文件
• 图像编码处理
• 缩短电报文的长度
• 提高查询效率
• ....

使用代码构建哈夫曼编码

class Node {
  constructor(left, right, data) {
    this.left = left;
    this.right = right;
    this.data = data;
  }
}

class Huffman {
  constructor(str) {
    // 需要编码的字符串
    this.str = str;
    // 键和频率映射表
    this.keyCountMap = null;
    // 编码和键的映射表
    this.codeKeyMap = {};
    // 键和编码的映射表
    this.keyCodeMap = {};
    // 哈夫曼树节点列表
    this.nodeList = null;
    // 哈夫曼树根节点
    this.root = null;
    // 哈夫曼编码后的01序列
    this.code = null;
  }
  cal() {
    str = this.str;
    let map = {};
    let i = 0;
    while (str[i]) {
      map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1);
      i++;
    }
    this.keyCountMap = map;
  }
  sort() {
    let map = this.keyCountMap;
    let result = [];
    for (let key in map) {
      if (map.hasOwnProperty(key)) {
        let obj = {
          key: key,
          val: map[key]
        };
        result.push(new Node(null, null, obj));
      }
    }
    this.nodeList = result.sort(function (x, y) { return x.data.val > y.data.val });
  }
  makeTree() {
    let i = 0;
    let parentNode;
    let table = this.nodeList;
    while (table.length > 1) {
      parentNode = new Node(table[i], table[i + 1], { key: null, val: table[i]['data'].val + table[i + 1]['data'].val });
      table.splice(i, 2);
      table.unshift(parentNode);
      table.sort(function (x, y) { return x.data.val > y.data.val });
    }
    this.root = table[0] || new Node();
    return this.root;
  }
  traversal(tree, code) {
    if (tree.left !== null) {
      this.traversal.call(this, tree.left, code + '0');
    } else {
      this.keyCodeMap[tree.data.key] = code;
    }
    if (tree.right !== null) {
      this.traversal.call(this, tree.right, code + '1');
    } else {
      this.keyCodeMap[tree.data.key] = code;
    }
  }
  encode() {
    this.cal();
    this.sort();
    let root = this.makeTree();
    this.traversal(root, '');
    let ret = this.keyCodeMap;
    let i = 0;
    let result = '';
    let str = this.str;
    while (str[i]) {
      result += ret[str[i++]];
    }
    this.code = result;
    console.log('encode:' + result);
    return result
  }
  reverseMap() {
    let ret = this.keyCodeMap;
    let result = {};
    for (let key in ret) {
      if (ret.hasOwnProperty(key)) {
        result[ret[key]] = key;
      }
    }
    this.codeKeyMap = result;
    return result;
  }
  decode() {
    let i = 0;
    let result = '';
    let data = '';
    let map = this.reverseMap();
    let str = this.code;
    while (str) {
      result += str[i++];
      if (result in map) {
        data += map[result];
        str = str.replace(new RegExp("^" + result), '');
        result = '';
        i = 0;
      }
    }
    console.log("decode:" + data)
  }
  encodeBase64() {
    try {
      let base64 = btoa(this.code);
      return base64;
    } catch (e) {
      return '';
    }
  }
}

let str = 'ew qew qd ef 24 gf ewr getElementsByTagName';
let huffman = new Huffman(str)
huffman.encode(str)
huffman.decode();
huffman.encodeBase64()

参考文章：

百度百科

哈夫曼编码

哈夫曼编码详解——图解真能看了秒懂