Web 技术研究所

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

LZ77在JavaScript上的简易实现

  原本打算一口气把deflate算法搞明白的,但发现心有余而力不足。这个算法太复杂了,一两天时间恐怕搞不定。那就先把LZ77相关的东西给理解透彻吧。虽然上一篇中介绍了LZ77的基本原理,但没有给出具体的算法例子,于是现在就来简单地实现一个。
  下面这个代码只是简单实现,并没有做性能上的优化,无法在实际需求中使用。并且encodeLZ77函数返回的是一个数组,并不是压缩后的字符串。程序中的两个配置参数SB和LB是SearchBuffer和LookaheadBuffer的大小,对不同数据种类的压缩算法,他们的取值应该都是不同的。比如这里对代码做压缩,那么LB就不需要太大的值,因为代码中几乎不会出现大串连续的字符重复的情况。如果最终需要把它生成的结果格式化成字节流,这些取值的范围就很重要,取值范围小时保存所需的空间才小。 <script>
var result=encodeLZ77(document.currentScript.textContent);
console.log(decodeLZ77(result));

function encodeLZ77(s){
  var SB=512,LB=32; //配置SearchBuffer和LookaheadBuffer的大小
  var i,j,k,offset,length,r=[];
  for(i=0;i<s.length;i++){ //滑动Window
    var offset=0,length=0;
    for(j=i-1;j>=i-SB&&j>=0;j--){ //匹配,寻找最长匹配
      for(k=0;i<s.length&&k<LB&&s.charAt(j+k)==s.charAt(i+k);k++);
      if(k>length)offset=i-j,length=k;
    };
    r.push([offset,length,s.charAt(i+=length)]);
  };
  return r;
};

function decodeLZ77(a){
  for(var s=[],o,i=0;o=a[i];i++)
    //如果指向的位置有字符就取出,否则使用当前字符
    s.push(o[1]?(o[1]--,i--,s[s.length-o[0]]):o[2]);
  return s.join("");
};
</script>
网名:
3.80.55.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^