LZW資料壓縮算法

LZW算法常用于文本壓縮中，尤其是對于重複出現的字元串的文本壓縮效果不錯。其主要思想是掃描文本，對每個出現的字元，檢查其跟前向字元(串)是否能組成一個之前出現過的字元串，如果能那麼繼續向後掃描；如果不能，則将前向字元(串)轉換為一個索引，并将索引寫入輸出檔案中。這樣就将文本都用其對應的索引代替寫入輸出檔案中，如果文本中字元串重複越多，那麼壓縮效果就越好。

先給出代碼：

/********************************************************************
	created:	2014/01/06 12:13
	file base:	main
	file ext:	cpp
	author:	[email protected]
	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;
}
           

測試結果如下：

1.檔案中内容為

執行程式後，

D:\使用者目錄\Documents\Visual Studio 2008\Projects\LZW\Debug>LZW.exe ../LZW/input.txt ../LZW/output
file ../LZW/input.txt, size is 285B
file ../LZW/output, size is 97B
           

2.将檔案中内容再增大一倍

執行程式後，

D:\使用者目錄\Documents\Visual Studio 2008\Projects\LZW\Debug>LZW.exe ../LZW/input.txt ../LZW/output
file ../LZW/input.txt, size is 572B
file ../LZW/output, size is 155B
           

從以上對比看來，當文本中重複的字元串越多時，壓縮比越高

文章參考于點選打開連結