数据压缩（七）——LZW压缩编码解码

对程序的具体分析我放在了程序的注释中。

LZW编码原理

    LZW的编码思想是不断地从字符流中提取新的字符串，通俗地理解为新“词条”，然后用“代号”也就是码字表示这个“词条”。这样一来，对字符流的编码就变成了用码字去替换字符流，生成码字流，从而达到压缩数据的目的。LZW编码是围绕称为词典的转换表来完成的。LZW编码器通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流。LZW编码算法的步骤如下：

    步骤1：将词典初始化为包含所有可能的单字符，当前前缀P初始化为空。

    步骤2：当前字符C=字符流中的下一个字符。

    步骤3：判断P＋C是否在词典中


（1）如果“是”，则用C扩展P，即让P=P＋C，返回到步骤2。


（2）如果“否”，则

       输出与当前前缀P相对应的码字W；

       将P＋C添加到词典中；

       令P=C，并返回到步骤2

LZW解码原理

    LZW解码算法开始时，译码词典和编码词典相同，包含所有可能的前缀根。具体解码算法如下：

    步骤1：在开始译码时词典包含所有可能的前缀根。

    步骤2：令CW：=码字流中的第一个码字。

    步骤3：输出当前缀-符串string.CW到码字流。

    步骤4：先前码字PW：=当前码字CW。

    步骤5：当前码字CW：=码字流的下一个码字。

    步骤6：判断当前缀-符串string.CW 是否在词典中。

    （1）如果”是”，则把当前缀-符串string.CW输出到字符流。

                               当前前缀P：=先前缀-符串string.PW。

                               当前字符C：=当前前缀-符串string.CW的第一个字符。

                               把缀-符串P+C添加到词典。

    （2）如果”否”，则当前前缀P：=先前缀-符串string.PW。

                               当前字符C：=当前缀-符串string.CW的第一个字符。

                               输出缀-符串P+C到字符流,然后把它添加到词典中。

    步骤7：判断码字流中是否还有码字要译。

    （1）如果”是”，就返回步骤4。

    （2）如果”否”，结束。

bitio.h

#pragma once
/*
 * Declaration for bitwise IO
 *
 * vim: ts=4 sw=4 cindent
 */
#ifndef __BITIO__
#define __BITIO__
#include <stdio.h>
typedef struct {
    FILE* fp;
    unsigned char mask;
    int rack;
}BITFILE;
BITFILE* OpenBitFileInput(char* filename);
BITFILE* OpenBitFileOutput(char* filename);
void CloseBitFileInput(BITFILE* bf);
void CloseBitFileOutput(BITFILE* bf);
int BitInput(BITFILE* bf);
unsigned long BitsInput(BITFILE* bf, int count);
void BitOutput(BITFILE* bf, int bit);
void BitsOutput(BITFILE* bf, unsigned long code, int count);
#endif // __BITIO__

bitio.cpp

#include <stdlib.h>
#include <stdio.h>
#include "bitio.h"
BITFILE* OpenBitFileInput(char* filename) {
 BITFILE* bf;
 bf = (BITFILE*)malloc(sizeof(BITFILE));
 if (NULL == bf) 
  return NULL;
 if (NULL == filename) 
  bf->fp = stdin;
 else
 {
  errno_t err = 0;
  err = fopen_s(&(bf->fp), filename, "rb");
 }
 if (NULL == bf->fp) return NULL;
 bf->mask = 0x80;
 bf->rack = 0;
 return bf;
}

BITFILE* OpenBitFileOutput(char* filename) 
{
 BITFILE* bf;
 bf = (BITFILE*)malloc(sizeof(BITFILE));
 if (NULL == bf) return NULL;
 if (NULL == filename) bf->fp = stdout;//标准输出
 else
 {
  errno_t err = 0;
  err = fopen_s(&(bf->fp), filename, "wb");
 }
 if (NULL == bf->fp) return NULL;
 bf->mask = 0x80;
 bf->rack = 0;
 return bf;
}

void CloseBitFileInput(BITFILE* bf) 
{
 fclose(bf->fp);
 free(bf);
}

void CloseBitFileOutput(BITFILE* bf) {
 // Output the remaining bits
 if (0x80 != bf->mask) fputc(bf->rack, bf->fp);
 fclose(bf->fp);
 free(bf);
}

int BitInput(BITFILE* bf) 
{
 int value;
 if (0x80 == bf->mask) {
  bf->rack = fgetc(bf->fp);
  if (EOF == bf->rack) {
   fprintf(stderr, "Read after the end of file reached\n");
   exit(-1);
  }
 }
 value = bf->mask & bf->rack;
 bf->mask >>= 1;
 if (0 == bf->mask) bf->mask = 0x80;
 return((0 == value) ? 0 : 1);
}

unsigned long BitsInput(BITFILE* bf, int count) {
 unsigned long mask;
 unsigned long value;
 mask = 1L << (count - 1);
 value = 0L;
 while (0 != mask) {
  if (1 == BitInput(bf))
   value |= mask;
  mask >>= 1;
 }
 return value;
}

void BitOutput(BITFILE* bf, int bit) {
 if (0 != bit) bf->rack |= bf->mask;//rack和mask按位或，再赋值给rack
 bf->mask >>= 1;//bit为0的情况
 if (0 == bf->mask) { // eight bits in rack
  fputc(bf->rack, bf->fp);//把rack写道fp指针指向的位置
  bf->rack = 0;
  bf->mask = 0x80;
 }
}

void BitsOutput(BITFILE* bf, unsigned long code, int count) //code文件长度 count 4*8
{
 unsigned long mask;
 mask = 1L << (count - 1);//L把1强转成long型赋给mask，左移31位：10000000000......(32位)
 while (0 != mask) 
 {
  BitOutput(bf, (int)(0 == (code & mask) ? 0 : 1));//code和mask与运算，如果每位都是0，为0,否则为1
  mask >>= 1;//mask=mask右移1位的值
 }
}
#if 0
int main(int argc, char** argv) {
 BITFILE* bfi, * bfo;
 int bit;
 int count = 0;
 if (1 < argc) {
  if (NULL == OpenBitFileInput(bfi, argv[1])) {
   fprintf(stderr, "fail open the file\n");
   return -1;
  }
 }
 else {
  if (NULL == OpenBitFileInput(bfi, NULL)) {
   fprintf(stderr, "fail open stdin\n");
   return -2;
  }
 }
 if (2 < argc) {
  if (NULL == OpenBitFileOutput(bfo, argv[2])) {
   fprintf(stderr, "fail open file for output\n");
   return -3;
  }
 }
 else {
  if (NULL == OpenBitFileOutput(bfo, NULL)) {
   fprintf(stderr, "fail open stdout\n");
   return -4;
  }
 }
 while (1) {
  bit = BitInput(bfi);
  fprintf(stderr, "%d", bit);
  count++;
  if (0 == (count & 7))fprintf(stderr, " ");
  BitOutput(bfo, bit);
 }
 return 0;
}
#endif

lzw_E.cpp

#include <stdlib.h>
#include<cstdio>
#include <stdio.h>
#include "bitio.h"
#include<iostream>
#define MAX_CODE 65535
using namespace std;
struct {
 int suffix;
 int parent, firstchild, nextsibling;
} dictionary[MAX_CODE + 1];
int next_code;
int d_stack[MAX_CODE]; // stack for decoding a phrase 用于解码 堆栈
#define input(f) ((int)BitsInput( f, 16))
#define output(f, x) BitsOutput( f, (unsigned long)(x), 16)
int DecodeString(int start, int code);
void InitDictionary(void);
void PrintDictionary(void) 
{
 int n;
 int count;
 for (n = 256; n < next_code; n++) 
 {
  count = DecodeString(0, n);
  printf("%4d->", n);
  while (0 < count--) printf("%c", (char)(d_stack[count]));
  printf("\n");
 }
}

int DecodeString(int start, int code) 
{
 int count;
 count = start;
 while (0 <= code) 
 {
  d_stack[count] = dictionary[code].suffix;
  code = dictionary[code].parent;
  count++;
 }
 return count;
}
void InitDictionary(void) 
{
 int i;
 for (i = 0; i < 256; i++) {
  dictionary[i].suffix = i;
  dictionary[i].parent = -1;
  dictionary[i].firstchild = -1;
  dictionary[i].nextsibling = i + 1;
 }
 dictionary[255].nextsibling = -1;
 next_code = 256;
}
/*
 * Input: string represented by string_code in dictionary,
 * Output: the index of character+string in the dictionary
 *   index = -1 if not found
 */
int InDictionary(int character, int string_code) {
 int sibling;
 if (0 > string_code) return character;
 sibling = dictionary[string_code].firstchild;
 while (-1 < sibling) {
  if (character == dictionary[sibling].suffix) return sibling;
  sibling = dictionary[sibling].nextsibling;
 }
 return -1;
}

void AddToDictionary(int character, int string_code) 
{
 int firstsibling, nextsibling;
 if (0 > string_code) return;
 dictionary[next_code].suffix = character;
 dictionary[next_code].parent = string_code;
 dictionary[next_code].nextsibling = -1;
 dictionary[next_code].firstchild = -1;
 firstsibling = dictionary[string_code].firstchild;
 if (-1 < firstsibling) { // the parent has child
  nextsibling = firstsibling;
  while (-1 < dictionary[nextsibling].nextsibling)
   nextsibling = dictionary[nextsibling].nextsibling;
  dictionary[nextsibling].nextsibling = next_code;
 }
 else {// no child before, modify it to be the first
  dictionary[string_code].firstchild = next_code;
 }
 next_code++;
}

void LZWEncode(FILE* fp, BITFILE* bf) 
{
 int character;
 int string_code;
 int index;
 unsigned long file_length;
 fseek(fp, 0, SEEK_END);//指针指向文件尾
 file_length = ftell(fp);//算当前指针到文件头的偏移，即文件长度
 fseek(fp, 0, SEEK_SET);//指针指向文件开头
 BitsOutput(bf, file_length, 4 * 8);//mask rack
 InitDictionary();//初始化词典
 string_code = -1;
 while (EOF != (character = fgetc(fp))) //往后读一个字符
 {
  index = InDictionary(character, string_code);//是否在字典中
  if (0 <= index) { // string+character in dictionary
   string_code = index;
  }
  else { // string+character not in dictionary
   output(bf, string_code);
   if (MAX_CODE > next_code) { // free space in dictionary
    // add string+character to dictionary
    AddToDictionary(character, string_code);
   }
   string_code = character;//string的编码
  }
 }
 output(bf, string_code);
}

void LZWDecode(BITFILE* bf, FILE* fp) 
{
 int character;
 int new_code, last_code;
 int phrase_length;
 unsigned long file_length;
 file_length = BitsInput(bf, 4 * 8);
 if (-1 == file_length) file_length = 0;
 InitDictionary();
 last_code = -1;//同编码
 while (0 < file_length) 
 {
  new_code = input(bf);//BitsInput( f, 16)
  if (new_code >= next_code) //>=256（不在字典里），就需要解码
  { // this is the case CSCSC( not in dict)
   d_stack[0] = character;
   phrase_length = DecodeString(1, last_code);//start=1，
  }
  else 
  {
   phrase_length = DecodeString(0, new_code);
  }
  character = d_stack[phrase_length - 1];
  while (0 < phrase_length) 
  {
   phrase_length--;
   fputc(d_stack[phrase_length], fp);
   file_length--;
  }
  if (MAX_CODE > next_code) 
  { // add the new phrase to dictionary
   AddToDictionary(character, last_code);
  }
  last_code = new_code;
 }
}

int main(int argc, char** argv) 
{
 FILE* fp;
 BITFILE* bf;
 if (4 > argc) {
  fprintf(stdout, "usage: \n%s <o> <ifile> <ofile>\n", argv[0]);
  fprintf(stdout, "\t<o>: E or D reffers encode or decode\n");
  fprintf(stdout, "\t<ifile>: input file name\n");
  fprintf(stdout, "\t<ofile>: output file name\n");
  return -1;
 }
 if ('E' == argv[1][0]) //编码 第一个参数的第一个字符是E
 { 
  errno_t err = 0;
  err = fopen_s(&fp,argv[2], "rb");
  bf = OpenBitFileOutput(argv[3]);//wb形式打开文件argv[3],把这个文件放进bf结构体里的fp中，同时是给mask、rack赋值
  if (NULL != fp && NULL != bf) 
  {
   LZWEncode(fp, bf);//编码函数
   fclose(fp);
   CloseBitFileOutput(bf);
   fprintf(stdout, "encoding done\n");
  }
 }
 else if ('D' == argv[1][0]) { // do decoding
  bf = OpenBitFileInput(argv[2]);
  errno_t err1 = 0;
  err1 = fopen_s(&fp,argv[3], "wb");
  if (NULL != fp && NULL != bf) 
  {
   LZWDecode(bf, fp);//解码
   fclose(fp);
   CloseBitFileInput(bf);
   fprintf(stdout, "decoding done\n");
  }
 }
 else { // otherwise
  fprintf(stderr, "not supported operation\n");
 }
 return 0;
}

命令参数
argv[1][0]是“E”或者“D”。E代表编码，D代表解码，我把argv[2]直接理解为输入文件，argv[3]为输出文件。

用一个简单的txt文件，检验一下编解码程序的有效性

"1.txt"为原文件，“2.txt"为压缩后解压的文件。“2.dat”是压缩后的文件，用二进制打开。

用一张照片测试了一下各个文件格式的压缩程度，这张照片压缩后的文件都比原文件更大，猜想文件中字符的重复概率很低导致的结果。