哈夫曼编码

主要思想：放弃文本文件的普通保存方式：不再使用7位或8位二进制数表示每一个字符，而是用较少的比特表示出现频率最高的字符，用较多的比特表示出现频率低的字符。

使用变长编码来表示字符串，势必会导致编解码时码字的唯一性问题，因此需要一种编解码方式唯一的前缀码，而表示前缀码的一种简单方式就是使用单词查找树，其中最优前缀码即为Huffman首创。

编码实现

/*
 * @Author: Michael 
 * @Date: 2020-02-17 15:24:27 
 * @Last Modified by: Michael
 * @Last Modified time: 2020-02-17 17:43:29
 * 哈夫曼编码
 */

function TreeNode(val, char) {
  this.val = val; // 数量
  this.char = char;
  this.code = "";
  this.left = this.right = null;
}

/**
 * str 需要编码的字符串
 */
function HuffmanCompression(str) {
  const charCountMap = {};
  var heap = [];
  var length = str.length;
  for (var i = 0; i < length; i++) {
    if (charCountMap[str[i]]) {
      charCountMap[str[i]] = charCountMap[str[i]] + 1;
    } else {
      charCountMap[str[i]] = 1;
    }
  }

  var charCountMapKeys = Object.keys(charCountMap);
  var tempCharArray = []
  for (var i = 0; i < charCountMapKeys.length; i++) {
    var currentKey = charCountMapKeys[i];
    tempCharArray.push({ val: charCountMap[currentKey], char: currentKey });
  }
  tempCharArray.sort(function (a, b) { return a.val - b.val });

  for (var i = 0; i < tempCharArray.length; i++) {
    heap.push(new TreeNode(tempCharArray[i].val, tempCharArray[i].char));
  }

  while (heap.length > 1) {
    var first = heap.shift();
    var second = heap.shift();
    var sum = first.val + second.val;
    var char = first.char + second.char;

    var newTreeNode = new TreeNode(sum, char);
    newTreeNode.left = first;
    newTreeNode.right = second;

    heap.push(newTreeNode);
    heap.sort(function (a, b) { return a.val - b.val });
  }

  calculateCode(heap[0]);
  var codeMap = {};
  generateCodeMap(heap[0], codeMap);

  var result = "";
  for (var i = 0; i < str.length; i++) {
    result += codeMap[str[i]];
  }
  return result;
}

function calculateCode(node) {
  if (node.left) {
    node.left.code = node.code + '0';
    calculateCode(node.left);
  }
  if (node.right) {
    node.right.code = node.code + '1';
    calculateCode(node.right);
  }
}

function generateCodeMap(node, codeMap) {
  if (!node.left && !node.right) {
    codeMap[node.char] = node.code;
  }
  if (node.left) {
    generateCodeMap(node.left, codeMap);
  }
  if (node.right) {
    generateCodeMap(node.right, codeMap);
  }
}

console.log(HuffmanCompression("everyday is awesome!"));

louzhedong / blog

哈夫曼编码 #205

哈夫曼编码