第三次实验：LZW编码

LZW编码概述

LZW的编码思想是不断地从字符流中提取新的字符串，通俗地理解为新 “ 词条 ” ，然后用 “ 代号 ” 也就是码字表示这个 “ 词条 ” 。这样一来，对字符流的编码就变成了用码字去替 换字符流，生成码字流，从而达到压缩数据的目的。
LZW编码是围绕称为词典的转换表 来完成的， LZW 编码器通过管理这个词典完成输入与输出之间的转换。
LZW编码器的输 入是字符流，字符流可以是用 8 位 ASCII 字符组成的字符串，而输出是用 n 位 ( 例如 12 位 ) 表 示的码字流。
相比于Huffman编码：1）LZW编码只需要一遍扫描，具有自适应的特点；2）采用数字查找树/键树的算法，较为简单，便于快速实现

编码原理

编码步骤

1：初始化字典，将所有可能的单字符放入词典中。当前前缀P初始化为空。
2：当前字符C=字符流中的下一个字符。
3：判断P＋C是否在词典中
（1）如果“是”，则用C扩展P，即让P=P＋C，返回到步骤2。
（2）如果“否”，则输出与当前前缀P相对应的码字W；
将P＋C添加到词典中；
令P=C，并返回到步骤2

代码部分

#include "hashChain.h"
#include 
#include 
#include 
#include 

const int DIVISOR   = 4099,   
          MAX_CODES = 4096,   
          BYTE_SIZE = 8,     
          EXCESS    = 4,      
          ALPHA     = 256,  
          MASK1     = 255,    
          MASK2     = 15;  

//hash表的一个节点
//pair.first = key,pair.second = code
typedef std::pair pairType;


int leftOver;
bool bitsLeftOver = false;//上来表示剩余的4位的，所以我们需要输出8位，然后留下4位，这样bitsLeftOver就为true了，所以这样
//就可以交换的输出和不输出4位了
std::ifstream in;    //表示输入文件流，其实就是读文件的流
std::ofstream out;  //表示用来输出的文件流，其实就是写文件的流

//处理用户输入的数据
//这个是用C风格写的，我注释的是用C++风格写的
void setFiles(int argc,char *argv[]){
   
    char inputFile[54],outputFile[50];
    if(argc >= 2){//先判断下用户输入的参数的个数
        //将文件名copy到inputfile中去
        //extern char *strcpy (char *__restrict __dest, const char *__restrict __src)
        strcpy(inputFile,argv[1]);
    }else{//如果用户没有输入要转换的文件，
        std::cout<<"Enter name of file to compressn";
        std::cin>>inputFile;
    }
    //用二进制文件方式打开
    in.open(inputFile,std::ios::binary);
    if(in.fail()){//如果文件打开失败的话，
        std::cerr<<"Cannot open "<>BYTE_SIZE使第9---12位变成了1--4，也就是变成了低四位了
                    //通过 | 运算，其实就是 高四位 0000 | 0000 低四位，其实就是相加了
        c = int((leftOver << EXCESS)|(pcode>>BYTE_SIZE));
        out.put(c);
        out.put(d);
        bitsLeftOver = false;
    }else{//如果前边没有剩余的4位的话，也就是说我需要留出4位来等着下一次输出
      
        leftOver = pcode & MASK2;//低四位作为了下一次要输出的
        bitsLeftOver = true;
        c = int(pcode >> EXCESS);//输出高八位
        out.put(c);
    }
}

void compress(){

    hashChain h(DIVISOR);//创建一个hash表用来存储关系对
    //这个表示的是录入的初始化的字典
    for(int i = 0; i < ALPHA;++i)
        h.insert(pairType(i,i));
    int codeUsed = ALPHA;//这个表示已经被使用的编码号有多少个，最大有MAX_CODE

    int c = in.get();//这个表示的是当前的字符
    if(c != EOF){//如果没有到达文件尾的
        long pcode = c;//表示当前的前缀
        while((c = in.get()) != EOF){//如果不是空的话
            //pcode左移8位表示的是相当于是高于c的八位了]
            //代码左移8位，让给c字符一个8位的位置
            long theKey = (pcode << BYTE_SIZE) + c;
            //theKey = pcode + c
            //去在字典里查找pcode + c
            pairType  *thePair = h.find(theKey);
            if(thePair == NULL){//如果字典不存在的话，那么就输出pcode，并且插入pcode+c
                output(pcode);
                if(codeUsed < MAX_CODES)//如果编码还没占满的话，那么就插入
                    //书中的是
                    //hash.insert(pairType((pcode << BYTE_SIZE) | c,codeUsed++))
                    h.insert(pairType((pcode << BYTE_SIZE) | c,codeUsed++));
                pcode = c;
            }else//如果已经存在了的话，那么我就用这个thekey的编号来代替它了
                pcode = thePair->second;
        }
        output(pcode);
        if(bitsLeftOver)
            out.put(leftOver << EXCESS);
    }
    out.close();
    in.close();
}
int main(int argc,char *argv[])
{
    setFiles(argc,argv);
    compress();
    return 0;
}

解码步骤

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）如果”否”，结束。

代码部分

#include "sortedChain.h"
#include 
#include 
#include 
#include 

const int MAX_CODES = 4096,     //表示的是12位的代码(也就是P)
          BYTESIZE  = 8,        //一个字节的大小
          EXCESS    = 4,        //表示移动4位的位置
          ALPHA     = 256,      //表示一个8位ASCII码的全部表示的代码
          MASK      = 15;       //表示低4位或者高四位的数据


std::ifstream in;    //表示的是读取的文件
std::ofstream out;   //表示的是输出的文件

typedef std::pair pairType;

pairType ht[MAX_CODES];     //表示要翻译的代码的字典
char s[MAX_CODES];          //用来盛放一个代码对应的字符是什么
int size;                   //表示当前一个代码输出多少个字符，可以用来保留本次代码的第一个字符
int leftOver;               //是不是有要输出的四位
bool bitsLeftOver = false;  //

void setFiles(int argc,char *argv[]){
    char outputFile[50],inputFile[54];
    if(argc == 2)
        //strcpy(des,res)，将第二个数组的内容拷贝到第一个数组中去
        std::strcpy(outputFile,argv[1]);
    else{
        std::cout<<"Enter name of file to decompress"<>outputFile;
    }
    std::strcpy(inputFile,outputFile);
    std::strcat(inputFile,".zzz");
    in.open(inputFile,std::ios::binary);
    if(in.fail()){
        std::cerr<<"Cannot open "<> EXCESS);
        leftOver = d & MASK;
    }
    bitsLeftOver = !bitsLeftOver;//翻转一下
    return true;
}

void output(int code){
    size = -1;
    while(code >= ALPHA){
    //如果，你得到的结果不是单个单词的话，也就是存在于255以外的话
        s[++size] = ht[code].second;
        code = ht[code].first;
    }
    s[++size] = code;
    for(int i = size;i >= 0;--i)
        out.put(s[i]);
}

int main(int argc,char *argv[]){
    setFiles(argc,argv);
    decompress();
}

总结：LZW编码方式简单，但编码效率并不高，因为文件中可能并没有足够多的重复字符，因此无法体现出LZW编码的优势。但.xml文件可以大幅度压缩，在其内编辑时引入大量重复字符，因此压缩率很大。