数据归档中的缩减技术:数据压缩和重复数据删除(1)

随着信息化技术的发展和深入，企业对数据的依赖不断增强。与此同时，急速增长的数据量也给管理和使用都带来了全新的挑战。IDC最新报告显示，2007年新增数据量（281 ExaByte）已经超过所有可用存储介质总容量（264 ExaByte）约6%，并预计2011年数据总量将达到2006年的10倍。面对数据的爆炸性增长，仅仅提高系统运算能力和增加存储介质容量已经不能满足高速发展的各种数据应用，对高效数据缩减技术的需求已经逐步显现出来，并且越来越迫切。

目前能够实现数据缩减的技术主要有两种：数据压缩（Data Compression）和重复数据删除（Data De-duplication）。简单来说，数据压缩技术通过对数据重新编码来降低其冗余度（redundancy）；而重复数据删除技术则着眼于删除重复出现的数据块。

数据压缩

数据压缩的起源可以追溯到信息论之父香农（Shannon）在1947年提出的香农编码。1952年霍夫曼(Huffman)提出了第一种实用性的编码算法实现了数据压缩，该算法至今仍在广泛使用。1977年以色列数学家Jacob Ziv 和Abraham Lempel提出了一种全新的数据压缩编码方式，Lempel-Ziv系列算法（LZ77和LZ78，以及若干变种）凭借其简单高效等优越特性，最终成为目前主要数据压缩算法的基础。

Lempel-Ziv系列算法的基本思路是用位置信息替代原始数据从而实现压缩，解压缩时则根据位置信息实现数据的还原，因此又被称作“字典式”编码。目前存储应用中压缩算法的工业标准（ANSI、QIC、IETF、FRF、TIA/EIA）是LZS（Lempel-Ziv-Stac），由Stac公司提出并获得专利，当前该专利权的所有者是Hifn, Inc.

LZS算法基于LZ77（如图一）实现，主要由两部分构成，滑窗（Sliding Window）和自适应编码（Adaptive Coding）。压缩处理时，在滑窗中查找与待处理数据相同的块，并用该块在滑窗中的偏移值及块长度替代待处理数据，从而实现压缩编码。如果滑窗中没有与待处理数据块相同的字段，或偏移值及长度数据超过被替代数据块的长度，则不进行替代处理。LZS算法的实现非常简洁，处理比较简单，能够适应各种高速应用。

 

图一  LZ77算法示意图

数据压缩的应用可以显著降低待处理和存储的数据量，一般情况下可实现2:1 ~ 3:1的压缩比。