js LZ77算法的實現代碼

2019-11-21 00:35:03

字體：大中小

來源：轉載

供稿：網友

所以鉆研了一段時間的gzip，后來發現還是僅用LZ77 比較容易實現，gzip中的 haffman 壓縮部分對于JS來說太難搞了。
代碼如下，注釋的非常完整，所以就不多說了，有興趣的可以仔細研究下：

<html> <head> <title>LZ77</title> <style> * { font-size:12px; } body { overflow:auto; background-color:buttonface; } textarea { width:100%; height:240px; overflow:auto; } #btn1 { width:100px; } </style> <script> window.onload = init; function $(s){ return document.getElementById(s); } function init() {     $("txtS").focus();     $("btn1").onclick = run;     $("txtS").onkeydown = function ()     {         if (event.keyCode == 13 && event.ctrlKey)         {             run();         }     } } function run() {     var str = $("txtS").value;     $("txtS").value = "";     var lzc = new Lz77CompressDefer(str);     var t = new Date();     lzc.start(function (result)     {         $("txtR").value = Lz77SelfExtract(result);         var tc = new Date() - t;         $("txtS").value = eval($("txtR").value.substring(4));         var td = new Date() - t - tc;         alert("壓縮完畢/r/n壓縮比："+($("txtR").value.length/str.length*100).toFixed(2)+"%/r/n壓縮用時："+tc+"ms/r/n解壓用時："+td+"ms/r/n校驗："+(str==$("txtS").value?"OK":"failed"));     });          function showProgress(){         var p = lzc.status();         if (p < 1)         {             $("txtS").value = "壓縮中 ... " + (p*100).toFixed(2) + "%";             setTimeout(showProgress, 300);         }     }          showProgress();          /*     $("txtR").value = Lz77Compress(str);     var tc = new Date() - t;     $("txtS").value = Lz77Decompress($("txtR").value);     var td = new Date() - t - tc;     alert($("txtR").value.length/$("txtS").value.length+":"+tc+":"+td+":"+(str==$("txtS").value));     */ } /* * 以 LZ77 原理實現的JS文本壓縮算法 * Author: Hutia * */ /* LZ77基本原理： 1、從當前壓縮位置開始，考察未編碼的數據，并試圖在滑動窗口中找出最長的匹配字符串，如果找到，則進行步驟 2，否則進行步驟 3。 2、輸出三元符號組 ( off, len, c )。其中 off 為窗口中匹配字符串相對窗口邊界的偏移，len 為可匹配的長度，c 為下一個字符。然后將窗口向后滑動 len + 1 個字符，繼續步驟 1。 3、輸出三元符號組 ( 0, 0, c )。其中 c 為下一個字符。然后將窗口向后滑動 len + 1 個字符，繼續步驟 1。 變種： 1. 將匹配串和不能匹配的單個字符分別編碼、分別輸出，輸出匹配串時不同時輸出后續字符。 本算法變種： 1. 采用出現概率很低的前導字符P來區分匹配串輸出和非匹配串。對于匹配串，輸出 ( P, off, len )，對于非匹配串，輸出 c。 非匹配串中出現字符P時，輸出PP來代替，以示和匹配串的區別。 因此匹配串的輸出 ( off, len ) 結果中，不可以出現字符P，以免產生混淆。 本例中，取 (`) 作為前導字符。 2. 對于匹配串，輸出為： 前導字符 (`) + 偏移量 (3位，92進制 = 778688) + 匹配長度 (2位，92進制 = 8464) 因此滑動窗大小為778688，最小的匹配長度為 7。 3. 本算法針對JS文件，為簡化算法暫不考慮窗口滑動情況（JS文件通常不會大于700K）。對于文件大于778688字節的情況使用本算法會出錯。將來可以實現滑動窗口或分段壓縮。 4. 本例中為簡化算法，將 off 與 len 轉換為 92 進制的字符串，并且將低位放在左側，高位放在右側。 作者：Hutia Email: Hutia2@163.com 轉載請注明出處 */ var NC = [], CN = []; NC = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789~!@#$%^&*()-=[]/;',./_+{}|:/"<>?".split(""); for (var i=0; i<NC.length; i++) CN[NC[i]] = i; function Lz77Compress(input) {     /*LZ77壓縮算法 - Hutia - JS版*/          /*變量聲明*/     var p = 0; //掃描指針     var lp = 0; //鏈表查詢指針     var len = input.length; //輸入字符串的長度     var output = []; //輸出     var index = ""; //索引     var head = []; //索引頭信息     var prev = []; //位置鏈表     var match_off = 0; //匹配位置的偏移量     var match_len = 0; //發生匹配的長度     var last_match_off = 0; //上一次匹配位置的偏移量     var last_match_len = 0; //上一次發生匹配的長度     var j = 0; //循環變量          /*循環掃描*/     for (p=0; p<len; p++)     {         index = input.substring(p, p+7); //取當前字符開始的7個字符作為索引                  /*鏈表維護*/         prev[p] = head[index]; //當前頭位置進鏈表         head[index] = p; //保存現在位置進頭信息         /*匹配*/         lp = p; //初始化鏈表查詢指針         match_len = 0; //初始化匹配長度         match_off = 0; //初始化匹配位置         if (prev[lp]) //如果鏈表上存在上一個匹配         {             /*匹配查詢*/             while (prev[lp]) //依次查看鏈表上的每個位置             {                 lp = prev[lp]; //取出鏈表上的前一個位置到鏈表查詢指針                 for (j=1; j<8464 && lp+j<p; j++) //尋找此位置的最長匹配，匹配長度不能超過8464 (92進制的2個字節長度)，也不能超過當前指針位置                 {                     if (input.substring(lp, lp + j) != input.substring(p, p + j)) break;                 }                 j--; //計算最長匹配                 if (j > 7 && j > match_len) //如果此匹配比已發現的匹配長                 {                     match_len = j; //記錄匹配長度                     match_off = lp; //記錄匹配位置                 }             }                          /*匹配處理*/             if (match_len > 7) //如果找到了符合要求的匹配             {                 if (last_match_len != 0 && last_match_len < match_len) //如果上次匹配存在，且長度沒有這次匹配的長度大                 {                     /*懶惰模式*/                     output_unmatch(input.charAt(p - 1)); //放棄上次匹配，將字符直接輸出                     last_match_off = match_off; //記錄此次的匹配位置                     last_match_len = match_len; //記錄此次的匹配長度                 }                 else if (last_match_len != 0) //如果上次匹配存在，且長度比這次匹配的長度大                 {                     /*處理上次的懶惰模式*/                     output_match(); //輸出上次的匹配                 }                 else //如果上次匹配不存在                 {                     /*懶惰模式*/                     last_match_off = match_off; //記錄此次的匹配位置                     last_match_len = match_len; //記錄此次的匹配長度                 }             }             else //如果找不到符合要求的匹配（例如匹配超出當前指針）             {                 if (last_match_len != 0) //如果上次匹配存在                 {                     /*處理上次的懶惰模式*/                     output_match(); //輸出上次的匹配                                      }                 else                 {                     output_unmatch(input.charAt(p)); //直接輸出當前的字符                 }             }         }         else //如果當前不存在匹配         {             if (last_match_len != 0) //如果之前發生了匹配             {                 /*處理上次的懶惰模式*/                 output_match(); //輸出匹配             }             else             {                 output_unmatch(input.charAt(p)); //直接輸出當前的字符             }         }     } //循環掃描結束          /*邊界處理*/     if (last_match_len != 0) //如果之前發生了匹配     {         /*處理上次的懶惰模式*/         output_match(); //輸出匹配     }          /*輸出*/     return output.join("");          function output_match()     {         output.push("`"); //輸出前綴符         output.push(N2C(last_match_off, 3)); //輸出3字節偏移量         output.push(N2C(last_match_len, 2)); //輸出2字節匹配長度         p += last_match_len - 2; //移動當前指針到匹配串的末尾（因為懶惰模式，此時 p 指向 last_match_off + 1 的位置，所以應 -2 ）         last_match_off = 0; //清空匹配位置         last_match_len = 0; //清空匹配長度     }          function output_unmatch(c)     {         output.push(c == "`" ? "``" : c); //輸出未匹配的字符     } } function Lz77Decompress(input) {     /*LZ77解壓縮算法 - Hutia - JS版*/          /*變量聲明*/     var p = 0; //掃描指針     var len = input.length; //輸入字符串的長度     var output = []; //輸出     var match_off = 0; //匹配位置的偏移量     var match_len = 0; //發生匹配的長度          /*循環掃描*/     for (p=0; p<len; p++)     {         if (input.charAt(p) == "`") //如果發現前綴標記         {             if (input.charAt(p + 1) == "`") //如果是轉義前綴             {                 output.push("`"); //直接輸出字符 "`"                 p++; //指針后移，跳過下一個字符             }             else //如果是壓縮編碼             {                 match_off = C2N(input.substring(p+1, p+4)); //取出其 1-3 個字符，算出偏移量                 match_len = C2N(input.substring(p+4, p+6)); //取出其 4-5 字符，算出匹配長度                 output = [].concat(output.join("")); //整理輸出內容                 output.push(output[0].substring(match_off, match_off + match_len)); //自輸出內容的相應偏移量位置取出編碼所代表的字符串                 p += 5; //指針后移，跳過下5個字符             }         }         else //如果沒有發現前綴標記         {             output.push(input.charAt(p)); //直接輸出相應的字符         }     }          /*輸出*/     return output.join(""); } /*LZ77解壓縮算法 - Hutia - JS / mini 版*/ hutia = function(s){var A="charAt",p=-1,l=s.length,o=[],m,a="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789~!@#$%^&*()-=[]/;',./_+{}|:/"<>?".split(""),_=[];while(++p<92)_[a[p]]=p;function $(c){var l=c.length,r=0,i=-1;while(++i<l)r+=_[c[A](i)]*Math.pow(92,i);return r;}p=-1;while(++p<l){if(s[A](p)=="`"){if(s[A](p+1)=="`")p++,o.push("`");else{m=$(s.substring(p+1,p+4));o=[].concat(o.join(""));o.push(o[0].substring(m,m+$(s.substring(p+4,p+6))));p+=5;}}else o.push(s.charAt(p));}return o.join("");} function Lz77SelfExtract(s) {     return "eval(("+String(hutia)+")(/""+s.replace(////g,"http:////").replace(//r/g,"http://r").replace(//n/g,"http://n").replace(//"/g,"http:///"")+"/"));"; } function Lz77CompressDefer(input) {     /*LZ77壓縮算法 - Hutia - JS / Defer 版*/          /*變量聲明*/     var p = 0; //掃描指針     var lp = 0; //鏈表查詢指針     var len = input.length; //輸入字符串的長度     var output = []; //輸出     var index = ""; //索引     var head = []; //索引頭信息     var prev = []; //位置鏈表     var match_off = 0; //匹配位置的偏移量     var match_len = 0; //發生匹配的長度     var last_match_off = 0; //上一次匹配位置的偏移量     var last_match_len = 0; //上一次發生匹配的長度     var j = 0; //循環變量     var callback; //回調函數          this.start = function(fn)     {         this.start = function(){}         callback = fn;         run();     }          this.status = function ()     {         return p / len;     }          function run()     {         var inner_i = 0;         /*循環掃描*/         for (; p<len; p++)         {             if (++inner_i > 400)             {                 return setTimeout(run);             }                          index = input.substring(p, p+7); //取當前字符開始的7個字符作為索引                          /*鏈表維護*/             prev[p] = head[index]; //當前頭位置進鏈表             head[index] = p; //保存現在位置進頭信息             /*匹配*/             lp = p; //初始化鏈表查詢指針             match_len = 0; //初始化匹配長度             match_off = 0; //初始化匹配位置                          if (prev[lp]) //如果鏈表上存在上一個匹配             {                 /*匹配查詢*/                 while (prev[lp]) //依次查看鏈表上的每個位置                 {                     lp = prev[lp]; //取出鏈表上的前一個位置到鏈表查詢指針                     for (j=1; j<8464 && lp+j<p; j++) //尋找此位置的最長匹配，匹配長度不能超過8464 (92進制的2個字節長度)，也不能超過當前指針位置                     {                         if (input.substring(lp, lp + j) != input.substring(p, p + j)) break;                     }                     j--; //計算最長匹配                     if (j > 7 && j > match_len) //如果此匹配比已發現的匹配長                     {                         match_len = j; //記錄匹配長度                         match_off = lp; //記錄匹配位置                     }                 }                                  /*匹配處理*/                 if (match_len > 7) //如果找到了符合要求的匹配                 {                     if (last_match_len != 0 && last_match_len < match_len) //如果上次匹配存在，且長度沒有這次匹配的長度大                     {                         /*懶惰模式*/                         output_unmatch(input.charAt(p - 1)); //放棄上次匹配，將字符直接輸出                         last_match_off = match_off; //記錄此次的匹配位置                         last_match_len = match_len; //記錄此次的匹配長度                     }                     else if (last_match_len != 0) //如果上次匹配存在，且長度比這次匹配的長度大                     {                         /*處理上次的懶惰模式*/                         output_match(); //輸出上次的匹配                     }                     else //如果上次匹配不存在                     {                         /*懶惰模式*/                         last_match_off = match_off; //記錄此次的匹配位置                         last_match_len = match_len; //記錄此次的匹配長度                     }                 }                 else //如果找不到符合要求的匹配（例如匹配超出當前指針）                 {                     if (last_match_len != 0) //如果上次匹配存在                     {                         /*處理上次的懶惰模式*/                         output_match(); //輸出上次的匹配                                              }                     else                     {                         output_unmatch(input.charAt(p)); //直接輸出當前的字符                     }                 }             }             else //如果當前不存在匹配             {                 if (last_match_len != 0) //如果之前發生了匹配                 {                     /*處理上次的懶惰模式*/                     output_match(); //輸出匹配                 }                 else                 {                     output_unmatch(input.charAt(p)); //直接輸出當前的字符                 }             }         } //循環掃描結束                  /*邊界處理*/         if (last_match_len != 0) //如果之前發生了匹配         {             /*處理上次的懶惰模式*/             output_match(); //輸出匹配         }                  /*回調輸出*/         callback(output.join(""));     } //end of run          function output_match()     {         output.push("`"); //輸出前綴符         output.push(N2C(last_match_off, 3)); //輸出3字節偏移量         output.push(N2C(last_match_len, 2)); //輸出2字節匹配長度         p += last_match_len - 2; //移動當前指針到匹配串的末尾（因為懶惰模式，此時 p 指向 last_match_off + 1 的位置，所以應 -2 ）         last_match_off = 0; //清空匹配位置         last_match_len = 0; //清空匹配長度     }          function output_unmatch(c)     {         output.push(c == "`" ? "``" : c); //輸出未匹配的字符     } } function C2N(c) //將 92 進制字符串（高位在右）轉換為 10 進制數字 {     var len = c.length;     var re = 0;     for (var i=0; i<len; i++)     {         re += CN[c.charAt(i)] * Math.pow(92, i);     }     return re; } function N2C(n, len) //將 10 進制數字轉換為指定長度的 92 進制字符串，高位在右 {     var re = [];     for (var i=0; i<len; i++)     {         re[i] = NC[n % 92];         n = n / 92 | 0;     }     return re.join(""); } </script> </head> <body> <textarea id="txtS"></textarea> <textarea id="txtR"></textarea>  <input type="button" value="Go" id="btn1"> </body> </html>

[Ctrl+A 全選注:如需引入外部Js需刷新才能執行]

上一篇：javascript cookies操作集合

下一篇：js 獲取當前select元素值的代碼