午夜精品美女久久久久av福利,久久永久免费无码

　LZ77 算法的JS實(shí)現(xiàn)

作者：hutia　時(shí)間： 2010-04-09　文檔類型：原創(chuàng)　來(lái)自：藍(lán)色理想

JS操作二進(jìn)制很麻煩，而且一直沒(méi)有一個(gè)好的無(wú)損壓縮工具來(lái)實(shí)現(xiàn)純文本的壓縮。

所以鉆研了一段時(shí)間的gzip，后來(lái)發(fā)現(xiàn)還是僅用 LZ77 比較容易實(shí)現(xiàn)，gzip中的 haffman 壓縮部分對(duì)于JS來(lái)說(shuō)太難搞了。

代碼如下，注釋的非常完整，所以就不多說(shuō)了，有興趣的可以仔細(xì)研究下：

運(yùn)行代碼框
<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壓縮用時(shí)："+tc+"ms\r\n解壓用時(shí)："+td+"ms\r\n校驗(yà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 原理實(shí)現(xiàn)的JS文本壓縮算法 * Author: Hutia * */ /* LZ77基本原理： 1、從當(dāng)前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動(dòng)窗口中找出最長(zhǎng)的匹配字符串，如果找到，則進(jìn)行步驟 2，否則進(jìn)行步驟 3。 2、輸出三元符號(hào)組 ( off, len, c )。其中 off 為窗口中匹配字符串相對(duì)窗口邊界的偏移，len 為可匹配的長(zhǎng)度，c 為下一個(gè)字符。然后將窗口向后滑動(dòng) len + 1 個(gè)字符，繼續(xù)步驟 1。 3、輸出三元符號(hào)組 ( 0, 0, c )。其中 c 為下一個(gè)字符。然后將窗口向后滑動(dòng) len + 1 個(gè)字符，繼續(xù)步驟 1。變種： 1. 將匹配串和不能匹配的單個(gè)字符分別編碼、分別輸出，輸出匹配串時(shí)不同時(shí)輸出后續(xù)字符。本算法變種： 1. 采用出現(xiàn)概率很低的前導(dǎo)字符P來(lái)區(qū)分匹配串輸出和非匹配串。對(duì)于匹配串，輸出 ( P, off, len )，對(duì)于非匹配串，輸出 c。非匹配串中出現(xiàn)字符P時(shí)，輸出PP來(lái)代替，以示和匹配串的區(qū)別。因此匹配串的輸出 ( off, len ) 結(jié)果中，不可以出現(xiàn)字符P，以免產(chǎn)生混淆。本例中，取 (`) 作為前導(dǎo)字符。 2. 對(duì)于匹配串，輸出為：前導(dǎo)字符 (`) + 偏移量 (3位，92進(jìn)制 = 778688) + 匹配長(zhǎng)度 (2位，92進(jìn)制 = 8464) 因此滑動(dòng)窗大小為778688，最小的匹配長(zhǎng)度為 7。 3. 本算法針對(duì)JS文件，為簡(jiǎn)化算法暫不考慮窗口滑動(dòng)情況（JS文件通常不會(huì)大于700K）。對(duì)于文件大于778688字節(jié)的情況使用本算法會(huì)出錯(cuò)。將來(lái)可以實(shí)現(xiàn)滑動(dòng)窗口或分段壓縮。 4. 本例中為簡(jiǎn)化算法，將 off 與 len 轉(zhuǎn)換為 92 進(jìn)制的字符串，并且將低位放在左側(cè)，高位放在右側(cè)。作者：Hutia Email: Hutia2@163.com 轉(zhuǎn)載請(qǐng)注明出處 */ 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; //輸入字符串的長(zhǎng)度 var output = []; //輸出 var index = ""; //索引 var head = []; //索引頭信息 var prev = []; //位置鏈表 var match_off = 0; //匹配位置的偏移量 var match_len = 0; //發(fā)生匹配的長(zhǎng)度 var last_match_off = 0; //上一次匹配位置的偏移量 var last_match_len = 0; //上一次發(fā)生匹配的長(zhǎng)度 var j = 0; //循環(huán)變量 /*循環(huán)掃描*/ for (p=0; p<len; p++) { index = input.substring(p, p+7); //取當(dāng)前字符開始的7個(gè)字符作為索引 /*鏈表維護(hù)*/ prev[p] = head[index]; //當(dāng)前頭位置進(jìn)鏈表 head[index] = p; //保存現(xiàn)在位置進(jìn)頭信息 /*匹配*/ lp = p; //初始化鏈表查詢指針 match_len = 0; //初始化匹配長(zhǎng)度 match_off = 0; //初始化匹配位置 if (prev[lp]) //如果鏈表上存在上一個(gè)匹配 { /*匹配查詢*/ while (prev[lp]) //依次查看鏈表上的每個(gè)位置 { lp = prev[lp]; //取出鏈表上的前一個(gè)位置到鏈表查詢指針 for (j=1; j<8464 && lp+j<p; j++) //尋找此位置的最長(zhǎng)匹配，匹配長(zhǎng)度不能超過(guò)8464 (92進(jìn)制的2個(gè)字節(jié)長(zhǎng)度)，也不能超過(guò)當(dāng)前指針位置 { if (input.substring(lp, lp + j) != input.substring(p, p + j)) break; } j--; //計(jì)算最長(zhǎng)匹配 if (j > 7 && j > match_len) //如果此匹配比已發(fā)現(xiàn)的匹配長(zhǎng) { match_len = j; //記錄匹配長(zhǎng)度 match_off = lp; //記錄匹配位置 } } /*匹配處理*/ if (match_len > 7) //如果找到了符合要求的匹配 { if (last_match_len != 0 && last_match_len < match_len) //如果上次匹配存在，且長(zhǎng)度沒(méi)有這次匹配的長(zhǎng)度大 { /*懶惰模式*/ output_unmatch(input.charAt(p - 1)); //放棄上次匹配，將字符直接輸出 last_match_off = match_off; //記錄此次的匹配位置 last_match_len = match_len; //記錄此次的匹配長(zhǎng)度 } else if (last_match_len != 0) //如果上次匹配存在，且長(zhǎng)度比這次匹配的長(zhǎng)度大 { /*處理上次的懶惰模式*/ output_match(); //輸出上次的匹配 } else //如果上次匹配不存在 { /*懶惰模式*/ last_match_off = match_off; //記錄此次的匹配位置 last_match_len = match_len; //記錄此次的匹配長(zhǎng)度 } } else //如果找不到符合要求的匹配（例如匹配超出當(dāng)前指針） { if (last_match_len != 0) //如果上次匹配存在 { /*處理上次的懶惰模式*/ output_match(); //輸出上次的匹配 } else { output_unmatch(input.charAt(p)); //直接輸出當(dāng)前的字符 } } } else //如果當(dāng)前不存在匹配 { if (last_match_len != 0) //如果之前發(fā)生了匹配 { /*處理上次的懶惰模式*/ output_match(); //輸出匹配 } else { output_unmatch(input.charAt(p)); //直接輸出當(dāng)前的字符 } } } //循環(huán)掃描結(jié)束 /*邊界處理*/ if (last_match_len != 0) //如果之前發(fā)生了匹配 { /*處理上次的懶惰模式*/ output_match(); //輸出匹配 } /*輸出*/ return output.join(""); function output_match() { output.push("`"); //輸出前綴符 output.push(N2C(last_match_off, 3)); //輸出3字節(jié)偏移量 output.push(N2C(last_match_len, 2)); //輸出2字節(jié)匹配長(zhǎng)度 p += last_match_len - 2; //移動(dòng)當(dāng)前指針到匹配串的末尾（因?yàn)閼卸枘Ｊ�，此時(shí) p 指向 last_match_off + 1 的位置，所以應(yīng) -2 ） last_match_off = 0; //清空匹配位置 last_match_len = 0; //清空匹配長(zhǎng)度 } function output_unmatch(c) { output.push(c == "`" ? "``" : c); //輸出未匹配的字符 } } function Lz77Decompress(input) { /*LZ77解壓縮算法 - Hutia - JS版*/ /*變量聲明*/ var p = 0; //掃描指針 var len = input.length; //輸入字符串的長(zhǎng)度 var output = []; //輸出 var match_off = 0; //匹配位置的偏移量 var match_len = 0; //發(fā)生匹配的長(zhǎng)度 /*循環(huán)掃描*/ for (p=0; p<len; p++) { if (input.charAt(p) == "`") //如果發(fā)現(xiàn)前綴標(biāo)記 { if (input.charAt(p + 1) == "`") //如果是轉(zhuǎn)義前綴 { output.push("`"); //直接輸出字符 "`" p++; //指針后移，跳過(guò)下一個(gè)字符 } else //如果是壓縮編碼 { match_off = C2N(input.substring(p+1, p+4)); //取出其 1-3 個(gè)字符，算出偏移量 match_len = C2N(input.substring(p+4, p+6)); //取出其 4-5 字符，算出匹配長(zhǎng)度 output = [].concat(output.join("")); //整理輸出內(nèi)容 output.push(output[0].substring(match_off, match_off + match_len)); //自輸出內(nèi)容的相應(yīng)偏移量位置取出編碼所代表的字符串 p += 5; //指針后移，跳過(guò)下5個(gè)字符 } } else //如果沒(méi)有發(fā)現(xiàn)前綴標(biāo)記 { output.push(input.charAt(p)); //直接輸出相應(yīng)的字符 } } /*輸出*/ 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,"\\\\").replace(/\r/g,"\\r").replace(/\n/g,"\\n").replace(/\"/g,"\\\"")+"\"));"; } function Lz77CompressDefer(input) { /*LZ77壓縮算法 - Hutia - JS / Defer 版*/ /*變量聲明*/ var p = 0; //掃描指針 var lp = 0; //鏈表查詢指針 var len = input.length; //輸入字符串的長(zhǎng)度 var output = []; //輸出 var index = ""; //索引 var head = []; //索引頭信息 var prev = []; //位置鏈表 var match_off = 0; //匹配位置的偏移量 var match_len = 0; //發(fā)生匹配的長(zhǎng)度 var last_match_off = 0; //上一次匹配位置的偏移量 var last_match_len = 0; //上一次發(fā)生匹配的長(zhǎng)度 var j = 0; //循環(huán)變量 var callback; //回調(diào)函數(shù) this.start = function(fn) { this.start = function(){} callback = fn; run(); } this.status = function () { return p / len; } function run() { var inner_i = 0; /*循環(huán)掃描*/ for (; p<len; p++) { if (++inner_i > 400) { return setTimeout(run); } index = input.substring(p, p+7); //取當(dāng)前字符開始的7個(gè)字符作為索引 /*鏈表維護(hù)*/ prev[p] = head[index]; //當(dāng)前頭位置進(jìn)鏈表 head[index] = p; //保存現(xiàn)在位置進(jìn)頭信息 /*匹配*/ lp = p; //初始化鏈表查詢指針 match_len = 0; //初始化匹配長(zhǎng)度 match_off = 0; //初始化匹配位置 if (prev[lp]) //如果鏈表上存在上一個(gè)匹配 { /*匹配查詢*/ while (prev[lp]) //依次查看鏈表上的每個(gè)位置 { lp = prev[lp]; //取出鏈表上的前一個(gè)位置到鏈表查詢指針 for (j=1; j<8464 && lp+j<p; j++) //尋找此位置的最長(zhǎng)匹配，匹配長(zhǎng)度不能超過(guò)8464 (92進(jìn)制的2個(gè)字節(jié)長(zhǎng)度)，也不能超過(guò)當(dāng)前指針位置 { if (input.substring(lp, lp + j) != input.substring(p, p + j)) break; } j--; //計(jì)算最長(zhǎng)匹配 if (j > 7 && j > match_len) //如果此匹配比已發(fā)現(xiàn)的匹配長(zhǎng) { match_len = j; //記錄匹配長(zhǎng)度 match_off = lp; //記錄匹配位置 } } /*匹配處理*/ if (match_len > 7) //如果找到了符合要求的匹配 { if (last_match_len != 0 && last_match_len < match_len) //如果上次匹配存在，且長(zhǎng)度沒(méi)有這次匹配的長(zhǎng)度大 { /*懶惰模式*/ output_unmatch(input.charAt(p - 1)); //放棄上次匹配，將字符直接輸出 last_match_off = match_off; //記錄此次的匹配位置 last_match_len = match_len; //記錄此次的匹配長(zhǎng)度 } else if (last_match_len != 0) //如果上次匹配存在，且長(zhǎng)度比這次匹配的長(zhǎng)度大 { /*處理上次的懶惰模式*/ output_match(); //輸出上次的匹配 } else //如果上次匹配不存在 { /*懶惰模式*/ last_match_off = match_off; //記錄此次的匹配位置 last_match_len = match_len; //記錄此次的匹配長(zhǎng)度 } } else //如果找不到符合要求的匹配（例如匹配超出當(dāng)前指針） { if (last_match_len != 0) //如果上次匹配存在 { /*處理上次的懶惰模式*/ output_match(); //輸出上次的匹配 } else { output_unmatch(input.charAt(p)); //直接輸出當(dāng)前的字符 } } } else //如果當(dāng)前不存在匹配 { if (last_match_len != 0) //如果之前發(fā)生了匹配 { /*處理上次的懶惰模式*/ output_match(); //輸出匹配 } else { output_unmatch(input.charAt(p)); //直接輸出當(dāng)前的字符 } } } //循環(huán)掃描結(jié)束 /*邊界處理*/ if (last_match_len != 0) //如果之前發(fā)生了匹配 { /*處理上次的懶惰模式*/ output_match(); //輸出匹配 } /*回調(diào)輸出*/ callback(output.join("")); } //end of run function output_match() { output.push("`"); //輸出前綴符 output.push(N2C(last_match_off, 3)); //輸出3字節(jié)偏移量 output.push(N2C(last_match_len, 2)); //輸出2字節(jié)匹配長(zhǎng)度 p += last_match_len - 2; //移動(dòng)當(dāng)前指針到匹配串的末尾（因?yàn)閼卸枘Ｊ剑藭r(shí) p 指向 last_match_off + 1 的位置，所以應(yīng) -2 ） last_match_off = 0; //清空匹配位置 last_match_len = 0; //清空匹配長(zhǎng)度 } function output_unmatch(c) { output.push(c == "`" ? "``" : c); //輸出未匹配的字符 } } function C2N(c) //將 92 進(jìn)制字符串（高位在右）轉(zhuǎn)換為 10 進(jìn)制數(shù)字 { 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 進(jìn)制數(shù)字轉(zhuǎn)換為指定長(zhǎng)度的 92 進(jìn)制字符串，高位在右 { 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> <br/> <input type="button" value="Go" id="btn1"> </body> </html>
[Ctrl+A 全部選擇提示：你可先修改部分代碼，再按運(yùn)行]

經(jīng)典論壇交流：
http://bbs.blueidea.com/thread-2979165-1-1.html

本文鏈接：http://www.95time.cn/tech/web/2010/7492.asp　

出處：藍(lán)色理想
責(zé)任編輯：bluehearts

◎進(jìn)入論壇網(wǎng)頁(yè)制作、WEB標(biāo)準(zhǔn)化版塊參加討論，我還想發(fā)表評(píng)論。

作者文章

更多作者文章

扣代碼工具——捕獲者2.0

扣代碼工具——捕獲者

網(wǎng)頁(yè)制作前臺(tái)之javascript

百分百?gòu)棿?/a>

JS代碼格式化和語(yǔ)法著色


關(guān)鍵字搜索	常規(guī)搜索	推薦文檔
熱門搜索：CSS Fireworks 設(shè)計(jì)比賽網(wǎng)頁(yè)制作 web標(biāo)準(zhǔn) 用戶體驗(yàn) UE photoshop Dreamweaver Studio8 Flash 手繪 CG

站點(diǎn)最新

站點(diǎn)最新列表

周大福“敬•自然”設(shè)計(jì)大賽開啟

國(guó)際體驗(yàn)設(shè)計(jì)大會(huì)7月將在京舉行

中國(guó)國(guó)防科技信息中心標(biāo)志征集

云計(jì)算如何讓安全問(wèn)題可控

云計(jì)算是多數(shù)企業(yè)唯一擁抱互聯(lián)網(wǎng)的機(jī)會(huì)

阿里行云

云手機(jī)年終巨獻(xiàn)，送禮標(biāo)配299起

阿里巴巴CTO王堅(jiān)的"云和互聯(lián)網(wǎng)觀"

1499元買真八核云OS雙蛋大促

首屆COCO桌面手機(jī)主題設(shè)計(jì)大賽

欄目最新

欄目最新列表

淺談JavaScript編程語(yǔ)言的編碼規(guī)范

如何在illustrator中繪制臺(tái)歷

Ps簡(jiǎn)單繪制一個(gè)可愛(ài)的鉛筆圖標(biāo)

數(shù)據(jù)同步算法研究

用ps作簡(jiǎn)單的作品展示頁(yè)面

CSS定位機(jī)制之一:普通流

25個(gè)最佳最閃亮的Eclipse開發(fā)項(xiàng)目

Illustrator中制作針線縫制文字效果

Photoshop制作印刷凹凸字體

VS2010中創(chuàng)建自定義SQL Rule

中文字幕二区_国产精品免费在线观看_黄色网站观看_人人草人人澡_日本真实娇小xxxx