Web 技术研究所

我一直坚信着,Web 将会成为未来应用程序的主流

Huffman编码

  很多压缩算法中都会用到Huffman编码,它的作用是根据序列中项的使用频率,用一些二进制位来表示他们。对使用频率高的项使用更少的位,使用频率低的则用更多的位,这样就可以起到压缩作用。Huffman算法传入一个序列,返回的是一个项于二进制位的映射表。
  首先,要对传入的序列统计每项的使用频率。比如传入的序列是字符串的话就统计每一种字符出现的频率。在JavaScript,我们只要遍历字符串,并把字符放入一个对象中作为key,对应的值来存放出现次数即可。这个过程时间复杂度为 O(n),n为序列长度。
  接着,需要对上面统计处理的次数排序,因为我们要知道那些字符出现的频率小,那些字符出现的频率大。JavaScript的对象是没法直接排序的,需要把它转换成数组,然后完成排序。这个过程的时间复杂度是 O(nlogn),n为序列中不计重复的项的个数。这n的值和我们的定义有关,如果序列是UTF-16的,那么这个n最大就可以是65536。通常我们会以字节来作为项,那这个n就为256。
  得到这个有序的频率排列之后,我们需要把它做成一棵Huffman树。因为Huffman编码提供的二进制位是有一定要求的,比如提供的所有二进制位不能互容,比如如果允许存在二进制位“1000”,那么就不可能存在“100”,因为“1000”中包含了“100”。但是可以存在“0100”和“000”,虽然“000”也在“1000”中,但是匹配是从左开始的,所以它不属于被包含的情况。实际上这就是二叉树叶节点路径的性质,这意味着在这棵树中我们所有的数据项都应该在叶节点上。
  二进制位是根据路径来计算了,我们还要保持使用频率高的项的其路径尽可能的短。于是建这棵树应该从使用频率最低的项开始。把使用频率最低的两个项做成一个树节点,而这个树节点也作为一个新的项插入到排序过的序列中,这个节点的使用频率就是它所有叶节点使用频率的总和。这样如果两个使用频率非常低的项被做成一个树节点,它的使用频率总和依然还是整个序列中最小的两项之一,那么它就会又被作为另一个树节点的子节点,这样一来,使用频率低的项在树中的路径就长了,而使用频率高的项路径自然就短了。
  重复这个过程直到只剩下一个项,那么它就是这棵Huffman树的根了。这个过程每次会取出两个使用频率最低的项做成一个新的项,也就是说每次消耗掉一个项。它需要执行的次数就是项的个数减一,而每次执行需要把新项插入到排序过的序列中,这需要一次二分查找。所以时间复杂度也是 O(nlogn),n为序列中不计重复的项的个数。
  最后,只要遍历这棵树的每叶节点,并记录其路径就可以得到用于表示它的二进制位。但要注意有些位是0开头的,所以不能只用一个数值来储存,还需要储存位的长度。下面是JavaScript的实现
<script>
var huffman=function(s){
  function List(){
    var list=[];
    list.insert=function(node){
      if(this.length==0)return this.push(node);
      var l=0,r=this.length-1,v=node.v,x;
      while(r-l>1) //二分查找
        if(this[x=l+(r-l)/2|0].v<v)r=x
        else l=x;
      x=v-this[l].v<this[r].v-v?r+1:l;
      this.splice(x,0,node);
    };
    return list;
  };
  function Node(a,b){
    if(a.v&&b.v)this.a=a,this.b=b,this.v=a.v+b.v;
    else this.v=a,this.c=b;
  };
  return function(s){
    var map={},list=new List,result={},i,c;
    //建立有序频率序列
    for(i=0;c=s.charAt(i);i++)c in map?map[c]++:map[c]=1;
    for(i in map)list.push(new Node(map[i],i));
    list.sort(function(a,b){return b.v-a.v;});
    //建树
    while(list.length>1)
      list.insert(new Node(list.pop(),list.pop()));
    //遍历叶节点,获取结果集
    (function callee(o,v,d){
      if(o.c)return result[o.c]=[v,d];
      callee(o.a,v*2,d+1),callee(o.b,v*2+1,d+1);
    })(list[0],0,0);
    return result;
  };
}();

var r=huffman("啊,哈哈!!!!!");

//输出结果
var i,bin;
for(i in r){
  bin=r[i][0].toString(2);
  console.log(i,Array(r[i][1]-bin.length+1).join(0)+bin);
};
</script>
  
网名:
3.80.32.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^