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;  
    }