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

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

统计字符出现频率

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

排序,组装二叉树

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

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

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

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

得到结果

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

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

最后,上代码:

function Huffman(str) {
    // 需要编码的字符串
    this.str = str;
    // 键和频率映射表
    this.keyCountMap = null;
    // 编码和键的映射表
    this.codeKeyMap = {};
    // 键和编码的映射表
    this.keyCodeMap = {};
    // 哈夫曼树节点列表
    this.nodeList = null;
    // 哈夫曼树根节点
    this.root = null;
    // 哈夫曼编码后的01序列
    this.code = null;
}
Huffman.prototype.cal = function cal() {
    str = this.str;
    var map = {};
    var i = 0;
    while (str[i]) {
     map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1);
     i++;
    }
    this.keyCountMap = map;
}
Huffman.prototype.sort = function sort() {
    map = this.keyCountMap;
    var result = [];
    for (key in map) {
     if (map.hasOwnProperty(key)) {
        var 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
    });
    console.log(result);
}
function Node(left, right, data) {
    this.left = left;
    this.right = right;
    this.data = data;
}
Huffman.prototype.makeTree = function makeTree() {
    var i = 0;
    var len = this.nodeList.length;
    var node1;
    var node2;
    var parentNode;
    var 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.push(parentNode);
     table.sort(function(x, y) {
        return x.data.val > y.data.val
     });
    }
    this.root = table[0] || new Node();
    console.log(table);
    return this.root;
}
Huffman.prototype.traversal = function traversal(tree, code) {
    if (tree.left !== null) {
     traversal.call(this, tree.left, code + '0');
    } else {
     this.keyCodeMap[tree.data.key] = code;
    }
    if (tree.right !== null) {
     traversal.call(this, tree.right, code + '1');
    } else {
     this.keyCodeMap[tree.data.key] = code;
    }
}
Huffman.prototype.encode = function encode() {
    this.cal();
    this.sort();
    var root = this.makeTree();
    this.traversal(root, '');
    var ret = this.keyCodeMap;
    var i = 0;
    var result = '';
    var str = this.str;
    while (str[i]) {
     result += ret[str[i++]];
    }
    this.code = result;
    console.log(result);
    return result
}
var str = 'abbcccdddd';
var huffman = new Huffman(str);
huffman.encode(str);


回到顶部
我要评论

所有评论

返回
邮箱:
绑定
取消
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

邮箱:
绑定邮箱后,若有回复,会邮件通知。
提交
还可以输入500个字