[导读] 数据压缩与重复数据删除两种技术有何区别与联系呢？实际中又该如何正确应用呢？笔者之前对数据压缩原理和技术没有研究，因此做了点功课，查阅整理了相关资料，并与重复数据删除技术进行对比分析。
面对数据的急剧膨胀，企业需要不断购置大量的存储设备来应对不断增长的存储需求。然而，单纯地提高存储容量，这似乎并不能从根本解决问题。首先，存储设备的采购预算越来越高，大多数企业难以承受如此巨大的开支。其次，随着数据中心的扩大，存储管理成本、占用空间、制冷能力、能耗等也都变得越来越严重，其中能耗尤为突出。再者，大量的异构物理存储资源大大增加了存储管理的复杂性，容易造成存储资源浪费和利用效率不高。因此，我们需要另辟蹊径来解决信息的急剧增长问题，堵住数据“井喷”。高效存储理念正是为此而提出的，它旨在缓解存储系统的空间增长问题，缩减数据占用空间，简化存储管理，最大程度地利用已有资源，降低成本。目前业界公认的五项高效存储技术分别是数据压缩、重复数据删除、自动精简配置、自动分层存储和存储虚拟化。目前，数据压缩和重复数据删除是实现数据缩减的两种关键技术。简而言之，数据压缩技术通过对数据重新编码来降低冗余度，而重复数据删除技术侧重于删除重复的数据块，从而实现数据容量缩减的目的。
数据压缩[1][2]数据压缩的起源可以追溯到信息论之父香农(Shannon)在1947年提出的香农编码。1952年霍夫曼(Huffman)提出了第一种实用性的编码算法实现了数据压缩，该算法至今仍在广泛使用。1977年以色列数学家Jacob Ziv 和Abraham Lempel提出了一种全新的数据压缩编码方式，Lempel-Ziv系列算法(LZ77和LZ78，以及若干变种)凭借其简单高效等优越特性，最终成为目前主要数据压缩算法的基础。LZ系列算法属于无损数据压缩算法范畴，采用词曲编码技术实现，目前主要包括LZ77、LZSS、LZ78和LZW四种主流算法。可以归纳为两类：第一类词典法的想法是企图查找正在压缩的字符序列是否在前面的输入数据中出现过，如果是，则用指向早期出现过的字符串的“指针”替代重复的字符串。这种编码思想如图1所示。这里的“词典”是隐含的，指用以前处理过的数据。这类编码中的所有算法都是以Abraham Lempel和Jakob Ziv在1977年开发和发表的算法（称为LZ77算法）为基础。此算法的一个改进算法是由Storer和Szymanski在1982年开发的，称为LZSS算法。
图1 第一类词典法编码概念
第二类算法的想法是企图从输入的数据中创建一个“短语词典(dictionary of the phrases)”。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。这个概念如图2所示。A.Lempel和J.Ziv在1978年首次发表了介绍这种编码方法的文章，称为LZ78。在他们的研究基础上，Terry A.Welch在1984年发表对这种编码算法进行了改进的文章，并首先在高速硬盘控制器上应用了这种算法。因此后来把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码。
图2 第二类词典法编码概念
Lempel-Ziv系列算法的基本思路是用位置信息替代原始数据从而实现压缩，解压缩时则根据位置信息实现数据的还原，因此又被称作”字典式”编码。目前存储应用中压缩算法的工业标准(ANSI、QIC、IETF、FRF、TIA/EIA)是LZS(Lempel-Ziv-Stac)，由Stac公司提出并获得专利，当前该专利权的所有者是Hifn, Inc.。数据压缩的应用可以显著降低待处理和存储的数据量，一般情况下可实现2:1 ~ 3:1的压缩比。
LZ77算法[3]1977年，Jacob Ziv和Abraham Lempel描述了一种基于滑动窗口缓存的技术，该缓存用于保存最近刚刚处理的文本（J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data Compression”, IEEE Transaction on Information Theory, May 1977）。这个算法一般称为LZ77。LZ77和它的变体发现，在正文流中词汇和短语(GIF中的图像模式)很可能会出现重复。当出现一个重复时，重复的序列可以用一个短的编码来代替。压缩程序扫描这样的重复，同时生成编码来代替重复序列。随着时间的过去，编码可以重用来捕获新的序列。算法必须设计成解压程序能够在编码和原始数据序列推导出当前的映射。
图3 LZ77算法示意图
LZ77（及其变体）的压缩算法使用了两个缓存。滑动历史缓存包含了前面处理过的N个源字符，前向缓存包含了将要处理的下面L个字符。算法尝试将前向缓存开始的两个或多个字符与滑动历史缓存中的字符串相匹配。如果没有发现匹配，前向缓存的第一个字符作为9 bit的字符输出并且移入滑动窗口，滑动窗口中最久的字符被移出。如果找到匹配，算法继续扫描以找出最长的匹配。然后匹配字符串作为三元组输出（指示标记、指针和长度）。对于K个字符的字符串，滑动窗口中最久的K个字符被移出，并且被编码的K个字符被移入窗口。尽管LZ77是有效的，对于当前的输入情况也是合适的，但是存在一些不足。算法使用了有限的窗口在以前的文本中查找匹配，对于相对于窗口大小来说非常长的文本块，很多可能的匹配就会被丢掉。窗口大小可以增加，但这会带来两个损失：(1)算法的处理时间会增加，因为它必须为滑动窗口的每个位置进行一次与前向缓存的字符串匹配的工作；(2)<指针>字段必须更长，以允许更长的跳转。
LZSS算法[4]LZS算法基于LZ77实现，主要由两部分构成，滑窗(Sliding Window)和自适应编码(Adaptive Coding)。压缩处理时，在滑窗中查找与待处理数据相同的块，并用该块在滑窗中的偏移值及块长度替代待处理数据，从而实现压缩编码。如果滑窗中没有与待处理数据块相同的字段，或偏移值及长度数据超过被替代数据块的长度，则不进行替代处理。LZS算法的实现非常简洁，处理比较简单，能够适应各种高速应用。
值不值得，真是不足为外人道，自己心里有数就行。
