散列与LZW压缩分析

 

这两天实验截止过于集中以至于没法连更,因此小破鱼打算一口气全部打通关后出几期专题答案分享

包括数据结构的实验、python与大数据分析实验、众智科学与网络化群体实验、数据科学导论实验。

LZW压缩(LZW compression)是一种由Abraham Lempel、Jacob Ziv和Terry Welch发明的基于表查寻算法把文件压缩成小文件的无损压缩方法。

之前有在网上看到过一些大佬讲述的相关专题:

比如Lempel-Ziv-Welch Compression Algorithm - Tutorial - YouTubeLZW Compression Algorithm Explained | An introduction to data compression - YouTube

然而,问题是:对于使用的课本 《Data Structures, Algorithms, & Applications in C++》的案例并不是能够很好的匹配到,所以便聊一聊吧。

话不多说,直接看算法。

1、LZW压缩规则 :

开始,为该文本文件中所有可能出现的字母,分配一个代码,构成初始字典。LZW压缩器不断地在输入文件的未编码部分 中寻找在字典中出现的最长的前缀p,输出前 缀p相应的代码,若输入文件中的下一个字符 为c,则为pc分配一个代码,并插入字典。

2、LZW压缩实现:

设当前前缀p为空,读取下一个字符c; 循环(当前字符串pc不为空){
    if (当前字符串pc在字典中) 当前前缀p=当前字符串pc;
    else { 
        将当前字符串pc插入到字典中; 输出当前前缀p的编码;
        p=c;
            }
    读取下一个字符c; 
    }
    输出最后一个当前前缀p的编码;                    

例题1(来自课堂惊险提问):aaabbbbbbaabaaba的lzw编码(十进制):

 

分析此题:首先该字符串中只有a和b两个字母,因此字典中a为0,b为1.

循环1:第一位字符为a,a在字典中,前缀为a,

循环2:读取第二位a,aa不在字典中,将aa插入字典中的2,输出当前aa的前缀a的编码0,前缀变为a。(0)

循环3:读取第三位a,aa在字典中,前缀变为aa(0)

循环4:读取第四位b,aab不在字典中,补充aab到字典中的3,输出前缀aa的编码2,前缀变为b(02)

循环5:读取第五位b,bb不在字典中,补充bb到字典中的4,输出前缀b的编码1,前缀变为第五位的b(021)

循环6:读取第六位b,bb在字典中,前缀变为bb(021)

循环7:读取第七位b,bbb不在字典中,补充bbb到字典中的5,输出前缀bb的编码4,前缀变为b(0214)

循环8:读取第八位b,bb在字典中,前缀变为bb(0214)

循环9:读取第九位b,bbb在字典中,前缀变为bbb(0214)

循环10:读取第十位a,bbba不在字典中,补充进字典的6,输出bbb编码5,前缀变为a(02145)

循环11:读取第十一位a,aa在字典中,前缀变为aa(02145)

循环12:读取第十二位b,aab在字典中,前缀变为aab(02145)

循环13:读取第十三位a,aaba,补充aaba到7,输出aab编码3,前缀变为a(021453)

循环14:读取第十四位a:aa,前缀变为aa,(021453)

循环15:读取第十五位b:aab在字典中,前缀为aab(021453)

循环16:读取第十六位a,aaba在字典中,末位按照算法默认输出,对应为7,(0214537)

至此循环结束。

可以不妨得出两个结论:

1、第一位一定是一个字母,如果在字典中有,前缀更新编码不变;字典中没有,先加入字典下一位编号,前缀更新编码输出前缀。

2、和第一条一样(其实可以画一个2*n的表格对应一下)

 

 

有了压缩便会有解压缩(LZW)

输入第一个代码q,输出相应的文本(第一个代码一定对应于一个单一的字母)
输入下一个代码p; 
If (p在字典中){
输出代码p对应的文本串text(p); 
将text(q)fc(p)及代码插入到字典中
}
Else{
此时只会是: text(p)=text(q)fc(q);
即代码串qp对应文本串text(q)text(q)fc(q)】 
输出代码p对应的文本串text(q)fc(q);
将text(q)fc(q)及代码插入到字典中
}
q=p;

也就是说是上一个过程的逆过程。此处的代码指的是刚刚求出的编号,现在是假设只知道a是0,b是1,继续推。

编码在字典,输出对应的字母组,将该编码和它的前缀插入字典;若不在,只能说明编码重复,输出插入和压缩过程类似

例题2

01041627

 

答案:输出abaaabbb

你明白了吗?

 

 

 

 

 

 

 

 

 

 

 

 

上一篇:生成Excel表表头用的数组['A','B',....'AA','AB',.....]


下一篇:Linux系统管理之定时任务