lzw算法 c语言 lzw压缩算法的c语言实现.doc

lzw算法 c语言 lzw压缩算法的c语言实现 导读：就爱阅读网友为您分享以下“lzw压缩算法的c语言实现”的资讯，希望对您有所帮助，感谢您对92的支持! 标准的LZW压缩原理： ~~~~~~~~~~~~~~~~~~ 先来解释一下几个基本概念： LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译 表(String Table)。在编码时，数据流是输入对象（图象的光栅数据序列），编码流 就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据 流是输出对象；而编译表是在编码和解码时都须要用借助的对象。 字符(Character)：最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就 是一个像素的颜色在指定的颜色列表中的索引值； 字符串(String)：由几个连续的字符组成； 前缀(Prefix)：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0； 根(Root)：单个长度的字符串； 编码(Code)：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值； 图案：一个字符串，按不定长度从数据流中读出,映射到编译表条目. LZW压缩的原理：提取原始图象数据中的不同图案，基于这些图案创建一个编译表， 然后用编译表中的图案索引来替代原始光栅数据中的相应图案，减少原始数据大小。看 起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事 先创建好的，而是根据原始图象数据动态创建的，解码时还要从已编码的数据中还原出 原来的编译表（GIF文件中是不携带编译表信息的），为了更好理解编解码原理，我们 来看看具体的处理过程： 编码器(Compressor) ~~~~~~~~~~~~~~~~ 编码数据，第一步，初始化一个编译表，假设这个编译表的大小是12位的，也就是最 多有4096个单位，另外假设我们有32个不同的字符（也可以认为图象的每个像素最多有32 种颜色），表示为a，b，c，d，e...，初始化编译表：第0项为a，第1项为b，第2项为c... 一直到第31项，我们把这32项就称为根。 开始编译，先定义一个前缀对象Current Prefix，记为[.c.]，现在它是空的，然后 定义一个当前字符串Current String，标记为[.c.]k，[.c.]就为Current Prefix，k就 为当前读取字符。现在来读取数据流的第一个字符，假如为p，那么Current String就等 于[.c.]p（由于[.c.]为空，实际上值就等于p），现在在编译表中查找有没有Current String的值，由于p就是一个根字符，我们已经初始了32个根索引，当然可以找到，把p 设为Current Prefix的值，不做任何事继续读取下一个字符，假设为q，Current String 就等于[.c.]q（也就是pq），看看在编译表中有没有该值，当然。没有，这时我们要做下 面的事情：将Current String的值（也就是pq）添加到编译表的第32项，把Current Prefix 的值（也就是p）在编译表中的索引输出到编码流，修改Current Prefix为当前读取的字符 （也就是q）。继续往下读，如果在编译表中可以查找到Current String的值([.c.]k)， 则把Current String的值([.c.]k)赋予Current Prefix；如果查找不到，则添加Current String的值([.c.]k)到编译表，把Current Prefix的值([.c.])在编译表中所对应的索引 输出到编码流，同时修改Current Prefix为k ，这样一直循环下去直到数据流结束。伪代 码看起来就像下面这样： 编码器伪代码 Initialize String Table; [.c.] = Empty; [.c.]k = First Character in CharStream; while