Huffman编码是一种压缩算法,一种通过字符出现的频率和二叉树来进行的压缩算法,下面通过一个简单的例子看看如何构建它:

    假设现在要压缩的字符串为:abbcccdddd。

    统计字符出现频率

    第一步我们就是要遍历这个字符串,然后统计出每个字符出现的频率,可以得到如下Map:

    排序,组装二叉树

    1.先将数组排序,将数组中前两个元素(出现频率最低的两个)放在一个新建节点的左右两侧,同时删除那两个元素,并将新建的节点放入数组进行下一轮排序。(新建节点的频率等于最低两个元素之和)

    2.重复上面的操作,直到所有的节点都被放入树中。

    3.遍历树,树的左边赋值0,树的右边赋值1,就可以得到所有字符被编码是多少了。上面的文字过程如下图所示:

    Huffman编码的计算过程是不断排序,构建树,因此它的结果不唯一,因为可能有的字符频率一样,那么树的结果就不一定相同。

    得到结果

    经过上面的计算,我们可以得到每个字符的编码,如下:

    因此,原来的abbcccdddd就可以表示成1001011011111110000。

    最后,上代码:

    1. function Huffman(str) {
    2.     // 需要编码的字符串
    3.     this.str = str;
    4.     // 键和频率映射表
    5.     this.keyCountMap = null;
    6.     // 编码和键的映射表
    7.     this.codeKeyMap = {};
    8.     // 键和编码的映射表
    9.     this.keyCodeMap = {};
    10.     // 哈夫曼树节点列表
    11.     this.nodeList = null;
    12.     // 哈夫曼树根节点
    13.     this.root = null;
    14.     // 哈夫曼编码后的01序列
    15.     this.code = null;
    16. }
    17. Huffman.prototype.cal = function cal() {
    18.     str = this.str;
    19.     var map = {};
    20.     var i = 0;
    21.     while (str[i]) {
    22.      map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1);
    23.      i++;
    24.     }
    25.     this.keyCountMap = map;
    26. }
    27. Huffman.prototype.sort = function sort() {
    28.     map = this.keyCountMap;
    29.     var result = [];
    30.     for (key in map) {
    31.      if (map.hasOwnProperty(key)) {
    32.         var obj = {
    33.          key: key,
    34.          val: map[key]
    35.         };
    36.         result.push(new Node(null, null, obj));
    37.      }
    38.     }
    39.     this.nodeList = result.sort(function(x, y) {
    40.      return x.data.val > y.data.val
    41.     });
    42.     console.log(result);
    43. }
    44. function Node(left, right, data) {
    45.     this.left = left;
    46.     this.right = right;
    47.     this.data = data;
    48. }
    49. Huffman.prototype.makeTree = function makeTree() {
    50.     var i = 0;
    51.     var len = this.nodeList.length;
    52.     var node1;
    53.     var node2;
    54.     var parentNode;
    55.     var table = this.nodeList;
    56.     while (table.length > 1) {
    57.      parentNode = new Node(table[i], table[i + 1], {
    58.         key: null,
    59.         val: table[i]['data'].val + table[i + 1]['data'].val
    60.      });
    61.      table.splice(i, 2);
    62.      table.push(parentNode);
    63.      table.sort(function(x, y) {
    64.         return x.data.val > y.data.val
    65.      });
    66.     }
    67.     this.root = table[0] || new Node();
    68.     console.log(table);
    69.     return this.root;
    70. }
    71. Huffman.prototype.traversal = function traversal(tree, code) {
    72.     if (tree.left !== null) {
    73.      traversal.call(this, tree.left, code + '0');
    74.     } else {
    75.      this.keyCodeMap[tree.data.key] = code;
    76.     }
    77.     if (tree.right !== null) {
    78.      traversal.call(this, tree.right, code + '1');
    79.     } else {
    80.      this.keyCodeMap[tree.data.key] = code;
    81.     }
    82. }
    83. Huffman.prototype.encode = function encode() {
    84.     this.cal();
    85.     this.sort();
    86.     var root = this.makeTree();
    87.     this.traversal(root, '');
    88.     var ret = this.keyCodeMap;
    89.     var i = 0;
    90.     var result = '';
    91.     var str = this.str;
    92.     while (str[i]) {
    93.      result += ret[str[i++]];
    94.     }
    95.     this.code = result;
    96.     console.log(result);
    97.     return result
    98. }
    99. var str = 'abbcccdddd';
    100. var huffman = new Huffman(str);
    101. huffman.encode(str);


    回到顶部
    我要评论

    所有评论

      相关文章