LZW数据压缩算法

LZW算法常用于文本压缩中，尤其是对于重复出现的字符串的文本压缩效果不错。其主要思想是扫描文本，对每个出现的字符，检查其跟前向字符(串)是否能组成一个之前出现过的字符串，如果能那么继续向后扫描；如果不能，则将前向字符(串)转换为一个索引，并将索引写入输出文件中。这样就将文本都用其对应的索引代替写入输出文件中，如果文本中字符串重复越多，那么压缩效果就越好。

先给出代码：

    /********************************************************************           created:    2014/01/06 12:13           file base:  main           file ext:   cpp           author: lming_08@hotmail.com           purpose:    实现LZW算法，并测试其压缩效果       *********************************************************************/        #include <vector>        #include <iostream>        #include <fstream>        using namespace std;                #define READ_COUNT (8*1024)        #define RET_OK 0        #define RET_FAIL -1                typedef unsigned short UInt2;                typedef struct st_tb         {            char used;//标识该项是否被使用            unsigned int prev;//前向的下标            int ch;//当前的字符        }st_tb;        st_tb string_tab[4096] = {0};                int LZW(char *str, int strlen, ofstream *ofile);        int init_string_tab(st_tb *string_tab);        int search_frm_strtab(st_tb *string_tab, unsigned int prev, int ch);                int main(int argc, char *argv[])        {            char str[READ_COUNT] = {0};            int len = 0;            ifstream ifile;            streampos pos;            ofstream ofile;            int ret = 0;                    ifile.open(argv[1], ios_base::in);            ifile.read(str, READ_COUNT);            //计算输入文件的大小            ifile.seekg(0, ios::end);            pos = ifile.tellg();            cout<<"file "<<argv[1]<<", size is "<<pos<<"B"<<endl;            ifile.close();                    ofile.open(argv[2], ios_base::binary|ios_base::in);            len = strlen(str);            ret = LZW(str, len, &ofile);            ofile.seekp(0, ios::end);            pos = ofile.tellp();            cout<<"file "<<argv[2]<<", size is "<<pos<<"B"<<endl;            ofile.close();                    return 0;        }                int init_string_tab(st_tb *string_tab)        {            int i = 0;                    for (i = 0; i < 258; i++)            {                string_tab[i].used = 1;                string_tab[i].prev = -1;                string_tab[i].ch = i;            }            for(i = 258; i < 4096; i++)            {                string_tab[i].used = 0;            }            return 0;        }                int search_frm_strtab(st_tb *string_tab, unsigned int prev, int ch)        {            int i = 0;                    for (i = 258; i < 4096; i++)            {                if (string_tab[i].used)                {                    if (string_tab[i].prev == prev && string_tab[i].ch == ch)                    {                        return i;                    }                }            }            return RET_FAIL;        }                int LZW(char *str, int strlen, ofstream *ofile)        {            init_string_tab(string_tab);                    int i = 0;            int str_index = 258;            int index = 0;            vector<UInt2> uvec;            UInt2 uwPrev = str[0];                    uvec.push_back(256);//256通常用来表示开始新的编码表            for (i = 1; i < strlen; i++)            {                index = search_frm_strtab(string_tab, uwPrev, str[i]);                if (index == RET_FAIL)                {                    uvec.push_back(uwPrev);                            string_tab[str_index].used = 1;                    string_tab[str_index].prev = uwPrev;                    string_tab[str_index].ch = str[i];                            uwPrev = str[i];                    str_index++;                }                else                {                    uwPrev = index;                }            }            uvec.push_back(uwPrev);            uvec.push_back(257);                    //开始将转换后的数据写入文件中            int flag = 0;            char prevcode = 0;            /*            *  这里写入的数据格式举例如下，连续插入2个数分别为0x0ABC, 0x0abc,这样写入文件后的格式为BCAcab，            *每两个数都是以这种方式写入的            */            for (vector<UInt2>::iterator it = uvec.begin(); it != uvec.end(); it++)            {                UInt2 code = *it;                        if (flag == 0){                    char ch = code & 0xFF;                    ofile->write(&ch, 1);                    prevcode = (code >>4) & 0xF0;                    flag = 1;                }                 else{                    char ch = (code &0x0F) | prevcode;                    ofile->write(&ch, 1);                    flag = 0;                }            }            if (flag == 0){                char ch = prevcode & 0xF0;                ofile->write(&ch, 1);            }                    return RET_OK;        }