Web 技术研究所

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

字典压缩算法(用于数据差异化加载)

  数据差异化加载理论中的核心部分就是字符串的diff算法,实际上diff算法只是数据差异化加载的众多可用算法其中之一,我们之前从版本控制工具说起,所以直接就扯到了diff算法。字典压缩算法同样也可以用,而且它的性能比diff算法还高。
  对于字典压缩算法而言,字典越贴近数据,压缩率就越高。当字典等于数据时,理论上压缩率可以无限接近于0。我们是在数据变化时将旧数据作为字典,对新数据压缩。通常在新数据中大部分内容与旧数据相同,这意味着大部分内容都会被压缩掉,我们真正需要传输的内容大概只有一些位置信息和字典中没有的内容。
  下面是我写的个比较简陋的字典压缩算法 <script>
//测试
onload=function(){
  //把当前页面的HTML作为测试数据
  var a=document.documentElement.outerHTML;
  //把代码中所有“压缩”替换成“\u6B21\u78B3\u9178\u94B4”
  var b=a.replace(/压缩/g,"\u6B21\u78B3\u9178\u94B4");
  //开始压缩
  console.log("旧数据字符数:",a.length);
  console.log("新数据字符数:",b.length);
  console.time("压缩耗时:");
  var e=compress(a,b);
  console.timeEnd("压缩耗时:");
  //输出结果
  console.log(JSON.stringify(e));
  //开始解压
  var r=decompress(a,e);
  //解压结果和源编码是相同的
  console.log(r==b); //true
};

function compress(a,b){
  //如果新数据中的内容旧数据中也存在就引用
  var data=(function(a,b){
    var i,t,o={},a=a.split(/(?:)/),b=b.split(/(?:)/);
    //将a的每个部分作为key,所在索引数组作为value
    for(i=0;i<a.length;i++)t=a[i],o[t]=o[t]||{},o[t][i]=null;
    //b中的每个部分如果在a中的话就直接引用
    for(i=0;i<b.length;i++)if(b[i] in o)b[i]=o[b[i]];
    return b;
  })(a,b);
  //合并邻近匹配项,整理结果
  return (function(){
    var i,j,n,result=[],positions,offset;
    //遍历整个数据
    for(i=0;i<data.length;i++)
      //如果是一个引用则寻找邻近的引用尽可能的合并起来
      if(typeof data[i]=="object"){
        n=true;
        for(j in positions)
          +j+i-offset in data[i]?n=false:delete positions[j];
        if(n)fetch(j);
        if(isNaN(offset))positions=clone(data[offset=i]);
      }else{ //否则不是引用
        fetch(); //处理未结束的引用合并
        //如果结果集的最后一项是字符串就加入到那个字符串中
        //否则插入新字符串项
        j=result.length-1;
        if(typeof result[j]=="string")
          result[j]+=data[i];
        else result.push(data[i]+"");
      };
    fetch(); //处理未结束的引用合并
    return result;
    function fetch(n){
      if(n==null)for(n in positions)break;
      if(n!=null&&i>offset)result.push([n*1,i-offset]);
      positions={},offset=void 0;
    };
    function clone(o){
      var i,m={};
      for(i in o)m[i]=o[i];
      return m;
    }
  })();
};

function decompress(a,s){
  var i,r=[],a=a.split(/(?:)/);
  for(i=0;i<s.length;i++)s[i] instanceof Array
    ?Array.prototype.push.apply(r,a.slice(s[i][0],s[i][0]+s[i][1]))
    :r.push(s[i]);
  return r.join("");
};
</script>

  压缩结果中还有一些重复的字符串,如果有需要可以将结果再进行LZ77之类的压缩处理。其实也没这个必要,可以把它交到HTTP上使用GZIP把这些重复字符压缩掉。
  上面的压缩算法是字符级的,压缩质量比较高,性能比较低。如果用于数据量大的场景应该改成行级的或固定块级的,这样对质量降低,对性能提高。最后,如果发现代码有什么问题请跟帖,其实我也没做过多少测试,毕竟还没投入使用,只是测试代码。
网名:
54.144.24.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^