用 JavaScript 操作二進位資料向來麻煩,而純文字又一直缺乏好用的無失真壓縮工具。研究 gzip 一陣子之後,我發現單獨實作 LZ77 相對可行——gzip 裡的 Huffman 編碼部分對 JS 來說實在太難處理。
LZ77 的核心想法是用「滑動視窗」找出重複片段,再用參照取代重複內容:
原始定義會在每次輸出匹配串時額外帶一個字元,顯得有點浪費。實作上常見的改良是把「匹配串」與「無法匹配的單一字元」分開編碼、分開輸出,匹配串不再附帶後續字元。
本例的做法是:取一個出現機率極低的前導字元(這裡用反引號 ` )作為區隔符號。
( 前導字元, off, len )。c。`` 以示區別。因此 ( off, len ) 的編碼結果中不可出現前導字元,否則會產生混淆。
接著是位寬的取捨:匹配串的輸出格式為「前導字元 + 偏移量(3 位,92 進位,可表示 778688)+ 匹配長度(2 位,92 進位,可表示 8464)」。由此推得滑動視窗大小為 778688,最短的有效匹配長度為 7。
由於目標是 JS 檔,為簡化實作暫不處理視窗滑動(JS 檔通常不會超過 700K);若檔案大於 778688 位元組,本演算法會出錯,未來可再補上滑動視窗或分段壓縮。另外,為了簡化,off 與 len 轉成 92 進位字串時,低位放左、高位放右。
整份範例是一個可直接開啟的 HTML 頁面:左上是輸入框,貼上待壓縮的文字後按鈕或 Ctrl+Enter 觸發,下方顯示壓縮結果,並自動跑一次還原與校驗。
window.onload = init;
function $(s){ return document.getElementById(s); }
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();
}
這裡有兩個值得注意的設計。第一,壓縮器寫成 Lz77CompressDefer(延遲式),並透過 status() 回報進度,讓 UI 在壓縮過程中不會完全凍住——這對 JS 這類單執行緒環境尤其重要。第二,範例用 eval 還原資料,只是為了示範方便;實務上應該改成真正的字串解析,避免執行不可信的內容。