LZW 壓縮演算法

LZW衍生自LZ77演算法，為一方便實作且受到廣泛運用的壓縮演算法
在較早期因專利保護的關係，另一個現在也常用的演算法GZip被提出來取代LZW的使用
不過現在LZW在世界各國的專利大約都在2003、2004年左右過期

LZW主要運用在文字及影像的壓縮處理上
他的實作方式是建立一個字典來記錄出現過的文字(字元)
例如：[AA: 258, AAA: 270, AAB: 264, AB: 256 ....]
字典在壓縮完後就被拋棄，解壓縮時則會在運算時依相同規則再建立一本字典
所以當重複的文字或字元較多時會有比較好的效率，反之則有可能幾乎沒效果
這個特性同樣適用在影像上，對於具有大範圍相同顏色的影像有較好的效果
這個演算法的特色是實現簡單，但因為不會對內容作分析，所以不見得是壓縮比最好的演算法
以下為JavaScript的LZW演算法實作

// LZW-compress a string
function lzw_encode(s) {
    var dict = {};
    var data = s.split("");
    var out = [];
    var currChar;
    var phrase = data[0];
    var code = 256;
    for (var i = 1; i < data.length; i++) {
        currChar = data[i];
        if (dict[phrase + currChar]) {
            phrase += currChar;
        } else {
            out.push(phrase.length > 1 ? dict[phrase] : phrase.charCodeAt(0));
            dict[phrase + currChar] = code;
            code++;
            phrase = currChar;
        }
    }
    out.push(phrase.length > 1 ? dict[phrase] : phrase.charCodeAt(0));
    for (i = 0; i < out.length; i++) {
        out[i] = String.fromCharCode(out[i]);
    }
    return out.join("");
}

// Decompress an LZW-encoded string
function lzw_decode(s) {
    var dict = {};
    var data = s.split("");
    var currChar = data[0];
    var oldPhrase = currChar;
    var out = [currChar];
    var code = 256;
    var phrase;
    for (var i = 1; i < data.length; i++) {
        var currCode = data[i].charCodeAt(0);
        if (currCode < 256) {
            phrase = data[i];
        } else {
            phrase = dict[currCode] ? dict[currCode] : (oldPhrase + currChar);
        }
        out.push(phrase);
        currChar = phrase.charAt(0);
        dict[code] = oldPhrase + currChar;
        code++;
        oldPhrase = phrase;
    }
    return out.join("");
}

測試：
var comp = lzw_encode("ABAACDBCAABCBAADABAAAABCBAADABAACDBCAABCBAAD");
var decomp = lzw_decode(comp);
console.log(comp + ' ' + decomp);