GIF、PDF文件中使用的LZW解压缩算法介绍

最近编程中，需要改写GIF图像和PDF文件中使用的LZW解压缩算法。在网上查了一些资料，讲算法的很多（因为LZW算法已经被很广泛的使用），但是讲LZW在各个领域中实际使用确很少。本人于是就标题所提内容做一些细节的说明，以飨读者。GIF-LZWPDF-LZWWarning数据源BitsPerComp1,2,4,8(bits)8(bits)（文本压缩）PDF文件中的图像如果使用LZW算法，在打印输出时有问题，可能是打印驱动不支持。清除码的使用（FlushCode）有有 结束码的使用（EndStream）有无GIF图的压缩数据使用块结构进行存储，并且使用结束码，这样可以很方便结束结码。相反，PDF文本内容压缩内容则没有结束码。BITS顺序8765432112345678两种压缩数据最大的不同点。这种不同点不像大小endian码那样不同，下面将有更为详细的说明。数据存储结构有结构无结构GIF压缩数据结构为（数据Bits长度，数据块长度，数据内容，----） ?嗦两句：1. LZW压缩码长度最长是12bits。超过这个长度将要重新开始编码解码。2. 在压缩数据中，数据开头和压缩码长度变换后，GIF和PDF都放置有清除码。查一下PDF文件中的LZWDecode压缩数据就可以了。3. 字典初始内容。内容与压缩数据源相关，如果数据源为3bits,则字典只有1<<3 + 1个大小，其中8为FlushCode，9为EndStreamCode。虽然pdf文本压缩内容中不使用EndStreamCode，但是这个编程还是保留没有做其它用处。（具体情况本人也没有做很确切的调查）字节顺序：这里以例子来讲：E1：PDF文本内容压缩（LZW）,E2：GIF(8BITS)数据源内容：(单位bit)E1：10000000,00000110,10000010,10……(简单回车换行)E2：00000000,00000001,…..（简单的一个清0码）其中pdf文件内容可以很自然地进行理解。但是E2内容则要进行如下变换：bits倒换：00000000,10000000,…读出一个压缩码：00000000,1再倒置码：100000000（清0码）不得不提：LZW压缩和解压缩已经极为成熟了，示意方法如下。//////////////////////////压缩//////////////////////////////////////////////////////Dictionary[j] ← all n single-character， j＝1, 2， …，nj ← n+1Prefix ← read first Character in Charstreamwhile((C ← next Character)!=NULL)BeginIf Prefix.C is in DictionaryPrefix ← Prefix.CelseCodestream ← cW for PrefixDictionary[j] ← Prefix.Cj ← n+1Prefix ← CendCodestream ← cW for Prefix////////////////////////解压缩/////////////////////////////////////////////////Dictionary[j] ← all n single-character， j＝1, 2， …，nj ← n+1cW ← first code from CodestreamCharsream ← Dictionary[cW]pW ← cWWhile((cW ← next Code word)!=NULL)BeginIf cW is in DictionaryCharstream ← Dictionary[cW]Prefix ← Dictionary[pW]cW ← first Character of Dictionary[cW]Dictionary[j] ← Prefix.cWj ← n+1pW ← cWelsePrefix ← Dictionary[pW]cW ← first Character of PrefixCharstream ← Prefix.cWDictionary[j] ← Prefix.CpW ← cWj ← n+1end