LZW算法压缩字符串数据

本文主要是介绍LZW算法压缩字符串数据，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

有的时候代码里不得不带上一串长的字符数据表，本来就是小功能，将这种不大不小的数据外部存放显得累赘，放源码里又碍眼又占空间。
这时候数据适合的可以通过设计精巧的结构简化存储的占位，没办法简化的可能会手工替换一下重复次数多的字符，但数量一大就没办法手工操作了，这时候应该用压缩算法来帮助我们。

选型

这次遇到数据类似这样，只有三种字符：0、1、2。

00000002000000000000000000000000000000000100000000000000000000001000010000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000010000000000000000100100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000100000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000001000010000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011000000000000000000000000000000000000000000000000000000000000000000010000000000000000001000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100100000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000000000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

总体长度实际上也不算多，大约上上面贴出来部分的十倍。所以选用的压缩算法不用太复杂、也不能太耗时，能简化存储占位就达到目的了。

数据压缩算法有蛮多，比较容易见到的像是Huffman编码、gzip、ZigZag、LZ系列等，有一些适合文本压缩有一些只适合文件。同时找了一些现成可以压缩的工具或者代码简单试了试Huffman编码、LZW、LZ77、LZ-string、Gzip，发现还是LZW在编码后的长度与编码代码长度上最适合的，边了解边尝试其实也花了一些时间，试好了代码也差不多改出来了。

中间有考虑可以分割固定位数转化成对应字符，但由于0太多，会转出来很多非可见字符，所以还是老老实实用压缩算法。

LZW 简介

LZW是Lempel-Ziv-Welch的缩写，最早是由Lempel与Ziv提出的，后来在1984年Terry Welch提出了改进版。在现在常见的GIF文件中就用到这种算法。更详细的介绍可看维基百科。

LZW其基本概念是将重复的数据以短符号替代，所以适合有大量重复字符出现的字符串，重复越多压缩效率越好。缺点是对数据准确性要求很高，如果一个数据出现偏差，直接影响后面的数据解码。
同时，如果压缩的字符有很多独立字符，这样字典会变得越来越大，所以在有的算法中还会增加清除标志，当字典到达预设大小时，会清除字典重新开始。像是GIF所使用的算法就有设置清除标志，设置大小是2^12，超过则清除。

LZW 算法

几个基本概念：
dict，字典，一般是ASCII表做默认字典
cW，当前读取到的字符，每次只读入一位
pW，上一次留存的字符，第一次读取则为空，可能是一位也可能是多位
str，为pW与cW的字符拼接

编码规则：

1、一次只读一个字符
2、每次读取完cW拼接在pW之后，形成一个新的字符串为str。
3、查询dict里是否有这个新字符串str。
3.no、如果没有，则将这个str存入dict中，并以一个新的字符作为代指。并将cW的值存入pW中。
3.yes、如果有则将这个str存入pW中，等待与下一次的cW拼接成新的字符串
4、这样循环直到结束，然后输出全部代指的字符作为编码后的字符。

解码规则：

1、一次只读取一个字符。
2、因为第一次编码的pW为空，所以解码的第一个cW字符肯定是默认dict里存在的字符，我们可以直接解码输出。并且将cW的值存入pW中，以此为解码开端。
3、读取第二个cW时，与前一个pW拼接，形成新的字符串为str，判断dict中是否存在，如果不存在则将这个组合存入dict中。再判断将要解码的字符是否存在dict中。
3.yes，如果dict中有，就读取出对应字符。
3.no，如果dict中没有。这时候我们应该想到编码的过程，遇到字典中存在的str时，我们会暂存住与下一次cW拼接成新串，直到dict中没有再存入。
所以遇到未知字符必然是我们将要写入字典的那一位字符，所以字典中肯定已经存了这个字符的一部分字典已存字符+一位cW字符，而且这个字典已存在字符恰是上一次保存的字符串，一位cW字符则是这个字符串的开始字符，这样我们就能还原出这个字符并写入字典中了。
4、不断循环这个解码过程，直到结束

JavaScript实现

解释起来比较繁琐，结合代码看会更容易理解，网上的JavaScript实现代码：

function compress(s){
    var dic = {};
    for(var i = 0; i < 256; i++){
        var c = String.fromCharCode(i);
        dic[c] = c;
    }
    var prefix = "";
    var suffix = "";
    var idleCode = 256;
    var result = [];
    for(var i = 0; i < s.length; i++){
        var c = s.charAt(i);
        suffix = prefix + c;
        if(dic.hasOwnProperty(suffix)){
            prefix = suffix;
        } else {
            dic[suffix] = String.fromCharCode(idleCode);
            idleCode++;
            result.push(dic[prefix]);
            prefix = "" + c;
        }
    }
    if(prefix !== ""){
        result.push(dic[prefix]);
    }
    return result.join("");
}

function uncompress(s){
    var dic = {};
    for(var i = 0; i < 256; i++){
        var c = String.fromCharCode(i);
        dic[c] = c;
    }
    var prefix = "";
    var suffix = "";
    var idleCode = 256;
    var result = [];
    for(var i = 0; i < s.length; i++){
        var c = s.charAt(i);
        if(dic.hasOwnProperty(c)){
            suffix = dic[c];    
        } else if(c.charCodeAt(0) === idleCode){
            suffix = suffix + suffix.charAt(0);
        } else {

        }
        if(prefix !== ""){
            dic[String.fromCharCode(idleCode)] = prefix + suffix.charAt(0);
            idleCode++;
        }
        result.push(suffix);
        prefix = suffix;
    }
    return result.join("");
}

适应性优化

简化初始字典

我们的数据只有三种字符：0、1、2。所以原始的字典可以不必那么大，直接写死即可

var dic = { 0: 0, 1: 1, 2: 2};

修改输出字符

我们编码出的数据是这样的：

0Āā02ĂąĆćĈā1ĉČĊĂċčđĒēĔēĄĕĘęĚěĜĝĞĝ1ĐğēĢģģĥđĐĨĦĬĭĮįİıęėIJČīĤĵĹĞķĔĥļİĿĺłĀĴŃņŇĽŁňĕŊćķōŋőŒœŔŕŀĀŐĆřŖŜŝŞĒŅşşšŠŢŦŧŨũŪūŬŭČŤIJśŮųŴđ

会发现这段编码如果放在源码中，第一眼感觉会是乱码，而且真正的数据是这十倍，使用的非常见字符更多，看上去更像是乱码，万一真的乱码了也无法一眼辨认出来，所以我们应当再美化一下。

一开始想的是用英文大小写+常见特殊字符，但发现这些完全不够编码后的组合使用，所以干脆直接选汉字作为替代字符。
缺点就是，汉字实际占位会比英文字符大一些，但两害相权取其轻，为了提升一点美观度，这点体积还是可以牺牲的。

源码中使用的String.fromCharCode()刚好就可以将UTF16序列转换成字符，所以无需特别麻烦的处理，只要选好汉字的起始位置即可。汉字区间是0x4E00~0x9FA5转化成十进制是19968~40869区间。只需简单的将索引idleCode由256改成19968即可。

var idleCode = 19968;

输出如下：

0一丁02丂丅丆万丈丁1三丌上丂下不丑丒专且专丄丕丘丙业丛东丝丞丝1丐丟专丢丣丣严丑丐丨並丬中丮丯丰丱丙丗串丌丫两丵丹丞丷且严丼丰丿为乂一临乃乆乇丽乁么丕乊万丷乍之乑乒乓乔乕乀一乐丆乙乖乜九乞丒久也也乡习乢书乧乨乩乪乫乬乭丌乤串乛乮乳乴丑

虽然也不太好看，但放代码里至少比之前顺眼了些。
中文参杂数字也不是很舒服，所以把0、1、2，也替换成汉字的零、一、二。

var dic = { 0: '零', 1: '一', 2: '二'};

这时候要考虑一个问题，在不断递增的情况中很可能遇到零、一、二，这样就与字典中的数据重合了，所以应当选一个比较大的区间。38646是零、19968是一、20108是二，所以在20108之后与38646之后的区间都是满足现有需要编码的数据组合，之后再选一个汉字笔划相对少的区间，简单的尝试了一下，最终选取25165。

var idleCode = 25165;

来看看效果：

零才扎零二扏扒打扔払扎一扖扙扗扏托扚扞扟扠扡扠扑扢扥扦执扨扩扪扫扪一扝扬扠扯扰扰扲扞扝扵扳批扺扻扼扽找扦扤承扙扸扱抂抆扫抄扡扲抉扽抌抇抏才抁抐抓抔把抎投扢抗扔抄抚折択抟抠抡抢抍才抝打抦抣抩抪披扟抒抬抬抮抭抯抳抴抵抶抷抸抹抺扙抱承抨抻拀拁扞

比之前编码的会更舒服一些，在大量数据两种编码效果会更明显一点。

解码也很简单，做相应的替换就行，将字典替换成

var dic = { '零': '0', '一': '1', '二': '2'};

字典的值必须是字符串，因为代码中用到了String下的方法。

idleCode也改成25165为起始值。

var idleCode = 25165;

这样就能顺利解码了。

完整代码

最后我们整理一下代码，完整代码如下：

function LZW_compress(text){
    const dict = { 0: '零', 1: '一', 2: '二' }, result = []
    let temp = "", UTFCode = 25165 // 汉字笔画较少的区间开始
    text.split("").reduce((prev, cur)=>{
        const string = prev + cur
        if(dict[string]) temp = string;
        else{
            dict[string] = String.fromCharCode(UTFCode++);
            result.push(dict[prev]);
            temp = cur.toString();
        }
        return temp
    }, "")
    if(temp) result.push(dict[temp]);
    return result.join("");
}


function LZW_uncompress(text){
    const dict = { "零": "0", "一": "1", "二": "2" }, result = []
    let UTFCode = 25165;
    text.split("").reduce((prev, cur)=>{
        let string = ""
        if(dict[cur]) string = dict[cur]
        else string = prev + prev.charAt(0)
        if(prev) dict[String.fromCharCode(UTFCode++)] = prev + string.charAt(0);
        result.push(string);
        return string
    }, "")
    return result.join("");
}

参考

• 维基百科LZW页面
• LZW算法js实现
• LZW算法
• 超级简单的数据压缩算法—LZW算法
• LZW压缩算法原理解析

这篇关于LZW算法压缩字符串数据的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！