LZW算法压缩字符串数据

更新日期: 2020-04-03阅读量: 1142标签: 算法

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


选型

这次遇到数据类似这样,只有三种字符: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;

这样就能顺利解码了。


完整代码

最后我们整理一下代码,完整代码如下(当然,一般场景比较通用,所以字典还是用默认的,编码出来的数据也别用中文,太浪费空间了):

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(""); }" title="">
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("");
}

来自:https://segmentfault.com/a/1190000022263233


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: https://www.fly63.com/article/detial/8514

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

JS实现链表_单链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域

Js排列组合的实现

犹记得高中数学,组合表示C(m, n),意思为从集合m,选出n个数生成一项,总共有多少个项的可能?组合是无序的,排列是有序的。所以排列的项数量多于组合

影响计算机算法世界的十位大师

算法和程序设计技术的先驱者。Oh,God!一些国外网站这样评价他。一般说来,不知道此人的程序员是不可原谅的。其经典著作《计算机程序设计艺术》更是被誉为算法中“真正”的圣经

indexOf实现引申出来的各种字符串匹配算法

我们在表单验证时,经常遇到字符串的包含问题,比如说邮件必须包含indexOf。我们现在说一下indexOf。这是es3.1引进的API ,与lastIndexOf是一套的。可以用于字符串与数组中。一些面试经常用问数组的indexOf是如何实现的

JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

在开发页面的时候,我们有时候会遇到这种需求:在页面某个dom节点中遍历,找到目标dom节点,我们正常做法是利用选择器document.getElementById(),document.getElementsByName()或者document.getElementsByTagName(),

js实现将一个正整数分解质因数

js 把一个正整数分解成若干个质数因子的过程称为分解质因数,在计算机方面,我们可以用一个哈希表来存储这个结果。首先,你需要一个判断是否为质数的方法,然后,利用短除法来分解。

为什么我认为数据结构与算法对前端开发很重要?

一个具有层级结构的数据,实现这个功能非常容易,因为这个结构和组件的结构是一致的,递归遍历就可以了。但是,由于后端通常采用的是关系型数据库,所以返回的数据通常会是这个样子:前端这边想要将数据转换一下其实也不难,因为要合并重复项

一道有意思的面试算法题

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。这道题第一眼看过去,思路挺简单的,我们只需要维护一个对象来记录每一个元素出现的次数,使用元素的值作为key,元素出现的次数作为value。

js实现生成任意长度的随机字符串

js生成任意长度的随机字符串,包含:数字,字母,特殊字符。实现原理:可以手动指定字符库及随机字符长度,利用Math.round()和Math.random()两个方法实现获取随机字符

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!