数据压缩与LZ系列算法及其改进
LZ77字典压缩算法简介
字典压缩的原理是构建⼀个字典，⽤索引来代替重复出现的字符或字符串。如果字符串相对长，那么对整个字符串构建字典，这个字典将会很⼤，并且随着字典的增⼤，匹配速度也会快速下降。原始的LZ77算法是利⽤了字符串中上下⽂的相关性特点，通过⼀个滑动窗⼝（⼀个查缓冲区）来作为字典，对要压缩的字符串保留⼀个look-aheadbuffer。压缩后的字符串采⽤三元组来表⽰：<；位移，长度，下⼀个字符>，在滑动窗⼝中从后往前，如果在窗⼝中有曾经出现过的相同字符，看最多可以匹配多少字节，完了继续往前查，查完了取窗⼝中最长的匹配串（如果有多个相同长度的串可以匹配，取最后⼀个），将这个匹配串距当前位置的位移，长度，及下⼀个字符构成的三元组写出。如果在滑动窗⼝不到匹配串，那么位移=长度=0，加上不能压缩的字符⼀起输出。滑动窗⼝可以通过循环队列实现。
解压缩是⼀个⽐较简单⽽且快速的过程，在需要解压缩时通过位移和长度拷贝之前出现过的字符串就可以完成。
LZ77字典压缩的改进
LZ77压缩算法的⼤部分时间都会花在字符串匹配上，针对这⼀点有多种改进：
构建查树，该思路也有多种实现⽅法，如LZSS。
构建链表法实现的哈希表，通过对⼀个字符串的头三个字节做哈希，快速到匹配字符串的位置之后再沿链表做顺序搜索，如LZRW。
字符串长度压缩Deflate算法，其在ZIP和GZIP，以及许多软件中使⽤到，是使⽤LZ77的变种和huffman编码结合的⼀种压缩算法。在ZLib的源码中可以到详细的算法说明。
类似的还有⿍⿍有名的7-ZIP所使⽤的LZMA算法，也是LZ77算法和算术编码结合的算法，对LZ77的三元组都根据概率再次进⾏编码，压缩⽐很⾼，但是压缩速度相对较慢。
LZ78/LZW系列算法
LZ77算法针对过去的数据进⾏处理，⽽ LZ78 算法却是针对后来的数据进⾏处理。LZ78通过对输⼊缓存数据进⾏预先扫描与它维护的字典中的数据进⾏匹配来实现这个功能，在到字典中不能匹配的数据之前它扫描进所有的数据，这时它将输出数据在字典中的位置、匹配的长度以及不到匹配的数据，并且将结果数据添加到字典中。
⽐较好的字典数据结构表⽰是字符查树(trie，有多种译法)，即上⼀楼提到的解析树(ParseTree)，在这个数据结构中，前缀相同的字符串共享祖先节点，依此衍⽣。因为要压缩的字符串可能会很长，在LZ78
中新出现的symbol并且在字典中没有匹配时，会加⼊到字典中，字典会不断膨胀，需要限制字典的⼤⼩。这⾥对trie有⼏种处理⽅法：
停⽌继续构造字典，形成⼀个静态的字典，⽤现有的字典对数据进⾏压缩（这个处理⽅法的缺点就是前⾯的字符串构造出来的字典对后来的数据不⼀定有效)
重新开始构造字典。这样会使数据分离为⼀个⼀个的块，每个块都有独⽴的字典。（这个⽅法保留了LZ77的优点，即新数据⽐旧数据更有相关性，类似Oracle的块压缩）
从trie中替换节点。但是需要考虑有效的替换算法。
LZW算法是LZ78的变种，假如字符串S在字典中有匹配，但是Sx在字典中⽆匹配，那么Sx会被加⼊到字典中。因为字典⼀开始就被初始化为256个字符，所以⽆需⽤到LZ77中的三元组表⽰法，每⼀个phrase或char都可以⽤字典中的⼀个索引表⽰（总是能在字典中到），缺点跟LZ78⼀样，字典会快速增⼤。LZW中的字典使⽤了trie结构。
LZMW是LZW的⼀个改进版本（DB2参考的压缩算法），改进如下：
如果trie满了，应该到最近最少使⽤的节点进⾏替换。⼀种⽅法是：出所有没有⼦节点的节点（即没有被当做前缀引⽤的节点），删除其中最⽼的。
加⼊字典的phrase由两个⼦串组成：前匹配项与当前项。LZW中的trie的新增节点表⽰的是后续不能匹配的symbol，但是LZMW中trie 新增节点表⽰的是后续不能匹配的串。这可以使得字典的单元在逻辑上更⾃然，⽣成字典的速度也更快。缺点是：并不是所有在字典中存在的串其前缀都可以在字典中到（注：LZW的trie结构是可以的），那么假如⼀个只部分匹配字典项的串要加⼊字典中会是个问题，《Data compression, the completereference》这本书中提到的可能的替代⽅法是⼀个串加⼊trie中时，其所有的前缀也加⼊到trie中，并且每个节点必须有标志位注明其是否在字典中（因为节点有可能只是上⼀步提到的前缀节点，⽽不是实际的字典项）。
查最长匹配项可能需要回溯。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。