关于LZW算法的改进研究(2)
2014-01-24 01:12
导读：LZWC算法和LZW算法一样采用编码表来组织输入数据，显然LZW的编码表中包含RC和LZW两个编码器编码的编码表。我们分别称其为编码表中的RC项和LZW项。这两项
LZWC算法和LZW算法一样采用编码表来组织输入数据，显然LZW的编码表中包含RC和LZW两个编码器编码的编码表。我们分别称其为编码表中的RC项和LZW项。这两项虽然对两个编码器来说是通用的，但实现时为了提高编码表的搜索速度，可以把两者分开处理。
RC的编码识别很简单，只在缓冲区中进行，对于较长的重复字符，这种编码方式简便易行，效率较高。
LZW编码器编码不连续的字符，当然是有效的，从而获得较高的压缩率。从LZWC编码过程可以看出，如果RC编码器在输入流中找不到满足条件的字符，则LZW编码器将独自编码输入数据。这时LZWC算法退化为LZW算法。
2.2 LZWC算法的解码原理
LZWC压缩算法的解码过程是编码过程的逆过程，以下是LZWC算法的解码过程：
(1）读一个编码（按LZW方式确定的码长）；
(2）如果是结束码，则结束解码过程；
(3）如果是RC标志的编码，则按照RC编码规则解码，输出原始数据；
(4）否则，按LZW方式解码；
(5）译码过程结束。
2.3 LZWC编码的算例
下面，我们用一个例子来说明LZWC编码算的过程。例如：假设信源发出的序列为：00110000111011100011001解：依题意，有：信源序列的数据依次经过前缓冲区，则
(1）RC编码器对进入前缓冲区的数据进行检测，x1=x2，x2≠x3，即：0重复出现2次，符合RC编码的条件，则00的LZWC编码为（1，2，0）。
（转载自科教范文网http://fw.nseac.com）
(2）RC编码器继续对进入前缓冲区的数据进行检测，x3=x4，x4≠x5，1重复出现2次，符合RC编码的条件，则11的LZWC编码为（2，2，1）。
(3）RC编码器继续对进入前缓冲区的数据进行检测，x5=x6，x6=x7，x7=x8，x8≠x9，0重复出现4次，符合RC编码的条件，则0000的LZWC编码为（3，4，0）。
(4）RC编码器继续对进入前缓冲区的数据进行检测，x9=x10，x10=x11，x11≠x12，1重复出现3次，符合RC编码的条件，则111的LZWC编码为（4，3，1）。
(5）RC编码器继续对进入前缓冲区的数据进行检测，x12≠x13，0仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则0的LZWC编码为（5，1，0）。
(6）RC编码器继续对进入前缓冲区的数据进行检测，x13=x14，x14=x15，x15≠x16，1重复出现3次，符合RC编码的条件，则111的LZWC编码为（6，3，1）。
(7）RC编码器继续对进入前缓冲区的数据进行检测，x16=x17，x17=x18，x18≠x19，0重复出现3次，符合RC编码的条件，则000的LZWC编码为（7，3，0）。
(8）RC编码器继续对进入前缓冲区的数据进行检测，x19=x20，x20≠x21，次，符合RC编码的条件，则11的LZWC编码为（8，2，1），1重复出现2次，符合RC编码的条件，则11的LZWC编码为（8，2，1）。
(9）RC编码器继续对进入前缓冲区的数据进行检测，x21=x22，x22≠x23，次，符合RC编码的条件，则00的LZWC编码为（9，2，0）。
(10）RC编码器继续对进入前缓冲区的数据进行检测，x23是最后一个数据，1仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则1的LZWC编码为（10，1，1）。
（科教范文网 fw.nseac.com编辑发布）
(11）前缓冲区没有数据通过了，编码到此结束。
所以，信源序列的LZWC编码为：C′={(1，2，0)，(2，2，1)，(3，4，0)，(4，3，1)，(5，1，0)，(6，3，1)，(7，3，0)，(8，2，1)，(9，2，0)，(10，1，1)}。
3 LZWC算法与LZW算法性能的比较
压缩算法性能的比较一般有两个重要因素，就是平均数据压缩率和压缩时间。我们从下面例子入手，来讨论他们的压缩性能：
例1：设输入流为：ababcbabccc
先建立初始化字典，将信源符号a，b，c预置为字典的前3项，编码位点分别为1，2，3。编码就从这个初始字典开始。
3.1 LZW编码过程
(1） 由于"a"已经在字典中了，而"ab"不在，输出"a"的编码，同时把"ab"添加到字典中，所以字典的第4个条目为"ab"令其编码位点为4，当前位置前移一位，变为1，当前字符变为"b"。它的LZW编码为（4，1，1）。
(2） 从输入流的第1个位置开始，"b"已在字典中了，
而"ba"不在。同理，输出"b"的编码，同时把"ba"添加到字典中，编码位点为5，当前位置变为2，当前字符为"a"它的LZW编码为（5，1，2）。
(3） 从输入流的第2个位置开始，"ab"已在字典中了，而"abc"不在。同理，输出"ab"的编码，同时把"abc"添加到字典中，编码位点为6，当前位置变为3，当前字符为"c"。它的LZW编码为（6，1，4）。 （科教论文网 Lw.nsEAc.com编辑整理）
(4） 从输入流的第3个位置开始，"c"已在字典中了，而"cb"不在。同理，输出"c"的编码，同时把"cb"添加到字典中，编码位点为7，当前位置变为4，当前字符为"c"。它的LZW编码为（7，1，3）。
(5） 从输入流的第4个位置开始，"ba"已在字典中了，而"bab"不在。同理，输出"ba"的编码，同时把"bab"添加到字典中，编码位点为8，当前位置变为5，当前字符为"b"。它的LZW编码为（8，1，5）。
(6） 从输入流的第5个位置开始，"b"已在字典中了，而"bc"不在。同理，输出"b"的编码，同时把"bc"添加到字典中，编码位点为9，当前位置变为6，当前字符为"c"。它的LZW编码为（9，1，2）。
(7） 从输入流的第6个位置开始，"c"已在字典中了，而"cc"不在。同理，输出"c"的编码，同时把"cc"添加到字典中，编码位点为10，当前位置变为7，当前字符为"c"。它的LZW编码为（10，1，3）。
(8） 从输入流的第10个位置开始，"cc"已在字典中了，并且没有别的字符需要编码了。即，编码过程到此结束。
所以，它的LZW编码为：
