1、窗體頂端窗體底端LZ77 壓縮算法實驗報告一、實驗內容 ：使用 C+編程實現(xiàn) LZ77 壓縮算法的實現(xiàn)。 二、 實驗目的 ：用 LZ77 實現(xiàn)文件的壓縮。 三、 實驗環(huán)境 ： 1、軟件環(huán)境：Visual C+ 6.02、編程語言：C+ 四、 實驗原理 ： LZ77 算法在某種意義上又可以稱為“滑動窗口壓縮”，這是由于該算法將一個虛 擬的，可以跟隨壓縮進程滑動的窗口作為術語字 典，要壓縮的字符串如果在該窗口 中出現(xiàn)，則輸出其出現(xiàn)位置和長 度。使用固定大小窗口進行術語匹配，而不是在所 有已經(jīng)編碼的信 息中匹配，是因為匹配算法的時間消耗往往很多，必須限制字典的大小才能保證算法的效率；隨著壓縮的進程滑

2、動字典窗口，使其中總包含最近編碼過的信息，是因為對大多數(shù)信息而言，要編碼的字符串往 往在最近的上下文中更容易找到匹配串。 五、 LZ77 算法的基本流程 ：1、從當前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動窗 口中找出最長的匹 配字符串，如果找到，則進行步驟2，否則進行步驟 3。2、輸出三元符號組 ( off, len, c )。其中 off 為窗口中匹 配字符串相對窗口邊 界的偏移，len 為可匹配的長度，c 為下一個字符。然后將窗口向后 滑動 len + 1 個字符，繼續(xù)步驟 1。 3、輸出三元符號組 ( 0, 0, c )。其中 c 為下一個字符。 然后將窗口向后滑動 len + 1

3、 個字符，繼續(xù)步驟 1。代碼如下：#include #include #include #include lz77.h / / out file format: / 0;flag2;buffer;0;flag2;buffer;.flag1;flag2;bufferlast / flag1 - 2 bytes, source buffer block length / if block size is 65536, be zero / flag2 - 2 bytes, compressed buffer length / if can not compress, be same with fla

4、g1 / void main(int argc, char* argv) /*if (argc != 4) puts(Usage: ); printf( Compress : %s c sourcefile destfilen, argv0); printf( Decompress : %s d sourcefile destfilen, argv0); return; */ BYTE soubuf65536; BYTE destbuf65536 + 16; FILE* in; FILE* out; /* in = fopen(input.txt, rb); if (in = NULL) pu

5、ts(Cant open source file); return; out = fopen(compress.txt, wb); if (out = NULL) puts(Cant open dest file); fclose(in); return; fseek(in, 0, SEEK_END); long soulen = ftell(in); fseek(in, 0, SEEK_SET); CCompressLZ77 cc; WORD flag1, flag2; */ int temp; printf(compress(0) or decompress(1)?:); scanf(%d

6、,&temp); if (temp = 0) / compress in = fopen(input.txt, rb); if (in = NULL) puts(Cant open source file); return; out = fopen(compress.txt, wb); if (out = NULL) puts(Cant open dest file); fclose(in); return; fseek(in, 0, SEEK_END); long soulen = ftell(in); fseek(in, 0, SEEK_SET); CCompressLZ77 cc; WO

7、RD flag1, flag2; int last = soulen, act; while ( last 0 ) act = min(65536, last); fread(soubuf, act, 1, in); last -= act; if (act = 65536) / out 65536 bytes flag1 = 0; else / out last blocks flag1 = act; fwrite(&flag1, sizeof(WORD), 1, out); int destlen = cc.Compress(BYTE*)soubuf, act, (BYTE*)destbu

8、f); if (destlen = 0) / cant compress the block flag2 = flag1; fwrite(&flag2, sizeof(WORD), 1, out); fwrite(soubuf, act, 1, out); else flag2 = (WORD)destlen; fwrite(&flag2, sizeof(WORD), 1, out); fwrite(destbuf, destlen, 1, out); else if (temp = 1) / decompress in = fopen(compress.txt, rb); if (in =

9、NULL) puts(Cant open source file); return; out = fopen(decompress.txt, wb); if (out = NULL) puts(Cant open dest file); fclose(in); return; fseek(in, 0, SEEK_END); long soulen = ftell(in); fseek(in, 0, SEEK_SET); CCompressLZ77 cc; WORD flag1, flag2; int last = soulen, act; while (last 0) fread(&flag1

10、, sizeof(WORD), 1, in); fread(&flag2, sizeof(WORD), 1, in); last -= 2 * sizeof(WORD); if (flag1 = 0) act = 65536; else act = flag1; last-= flag2 ? (flag2) : act; if (flag2 = flag1) fread(soubuf, act, 1, in); else fread(destbuf, flag2, 1, in); if (!cc.Decompress(BYTE*)soubuf, act, (BYTE*)destbuf) put

11、s(Decompress error); fclose(in); fclose(out); return; fwrite(BYTE*)soubuf, act, 1, out); else puts(Usage: ); printf( Compress : %s c sourcefile destfilen, argv0); printf( Decompress : %s d sourcefile destfilen, argv0); fclose(in); fclose(out); / / LZ77.h / / 使用在自己的堆中分配索引節(jié)點，不滑動窗口/ 每次最多壓縮65536 字節(jié)數(shù)據(jù)/ 的

12、優(yōu)化版本 #ifndef _WIX_LZ77_COMPRESS_HEADER_001_ #define _WIX_LZ77_COMPRESS_HEADER_001_ / 滑動窗口的字節(jié)大小#define _MAX_WINDOW_SIZE65536 class CCompress public: CCompress() ; virtual CCompress() ; public: virtual int Compress(BYTE* src, int srclen, BYTE* dest) = 0; virtual BOOL Decompress(BYTE* src, int srclen,

13、BYTE* dest) = 0; protected: / tools / / CopyBitsInAByte : 在一個字節(jié)范圍內復制位流/ 參數(shù)含義同CopyBits 的參數(shù)/ 說明：/此函數(shù)由CopyBits 調用，不做錯誤檢查，即/假定要復制的位都在一個字節(jié)范圍內void CopyBitsInAByte(BYTE* memDest, int nDestPos, BYTE* memSrc, int nSrcPos, int nBits); / / CopyBits : 復制內存中的位流/memDest - 目標數(shù)據(jù)區(qū)/nDestPos - 目標數(shù)據(jù)區(qū)第一個字節(jié)中的起始位/memSrc -

14、 源數(shù)據(jù)區(qū)/nSrcPos - 源數(shù)據(jù)區(qū)第一個字節(jié)的中起始位/nBits - 要復制的位數(shù)/說明：/起始位的表示約定為從字節(jié)的高位至低位（由左至右）/依次為0，. , 7 /要復制的兩塊數(shù)據(jù)區(qū)不能有重合void CopyBits(BYTE* memDest, int nDestPos, BYTE* memSrc, int nSrcPos, int nBits); / / 將DWORD值從高位字節(jié)到低位字節(jié)排列void InvertDWord(DWORD* pDW); / / 設置byte的第iBit位為aBit /iBit順序為高位起從記數(shù)（左起）void SetBit(BYTE* byte,

15、 int iBit, BYTE aBit); / / 得到字節(jié)byte第pos位的值/pos順序為高位起從記數(shù)（左起）BYTE GetBit(BYTE byte, int pos); / / 將位指針*piByte(字節(jié)偏移), *piBit(字節(jié)內位偏移)后移num位void MovePos(int* piByte, int* piBit, int num); / / 取log2(n)的upper_bound int UpperLog2(int n); / / 取log2(n)的lower_bound int LowerLog2(int n); ; class CCompressLZ77 :

16、 public CCompress public: CCompressLZ77(); virtual CCompressLZ77(); public: / / 壓縮一段字節(jié)流/ src - 源數(shù)據(jù)區(qū)/ srclen - 源數(shù)據(jù)區(qū)字節(jié)長度, srclen 0 壓縮數(shù)據(jù)長度/ 返回值= 0 數(shù)據(jù)無法壓縮/ 返回值 0 壓縮中異常錯誤int Compress(BYTE* src, int srclen, BYTE* dest); / / 解壓縮一段字節(jié)流/ src - 接收原始數(shù)據(jù)的內存區(qū), srclen = 65536 / srclen - 源數(shù)據(jù)區(qū)字節(jié)長度/ dest - 壓縮數(shù)據(jù)區(qū)/ 返回值-

17、 成功與否BOOL Decompress(BYTE* src, int srclen, BYTE* dest); protected: BYTE* pWnd; / 窗口大小最大為64k ，并且不做滑動/ 每次最多只壓縮64k 數(shù)據(jù)，這樣可以方便從文件中間開始解壓/ 當前窗口的長度int nWndSize; / 對滑動窗口中每一個字節(jié)串排序/ 排序是為了進行快速術語匹配/ 排序的方法是用一個k大小的指針數(shù)組/ 數(shù)組下標依次對應每一個字節(jié)串：(00 00) (00 01) . (01 00) (01 01) . / 每一個指針指向一個鏈表，鏈表中的節(jié)點為該字節(jié)串的每一個出現(xiàn)位置struct STI

18、DXNODE WORD off;/ 在src中的偏移WORD off2;/ 用于對應的字節(jié)串為重復字節(jié)的節(jié)點/ 指從off 到off2 都對應了該字節(jié)串WORD next;/ 在SortHeap中的指針; WORD SortTable65536; / 256 * 256 指向SortHeap中下標的指針 / 因為窗口不滑動，沒有刪除節(jié)點的操作，所以/ 節(jié)點可以在SortHeap 中連續(xù)分配struct STIDXNODE* SortHeap; int HeapPos;/ 當前分配位置 / 當前輸出位置(字節(jié)偏移及位偏移) int CurByte, CurBit; protected: / /

19、輸出壓縮碼/ code - 要輸出的數(shù)/ bits - 要輸出的位數(shù)(對isGamma=TRUE時無效) / isGamma - 是否輸出為編碼void _OutCode(BYTE* dest, DWORD code, int bits, BOOL isGamma); / / 在滑動窗口中查找術語/ nSeekStart - 從何處開始匹配/ offset, len - 用于接收結果，表示在滑動窗口內的偏移和長度/ 返回值- 是否查到長度為或以上的匹配字節(jié)串BOOL _SeekPhase(BYTE* src, int srclen, int nSeekStart, int* offset, i

20、nt* len); / / 得到已經(jīng)匹配了個字節(jié)的窗口位置offset / 共能匹配多少個字節(jié)inline int _GetSameLen(BYTE* src, int srclen, int nSeekStart, int offset); / / 將窗口向右滑動n個字節(jié)inline void _ScrollWindow(int n); / 向索引中添加一個字節(jié)串inline void _InsertIndexItem(int off); / 初始化索引表，釋放上次壓縮用的空間void _InitSortTable(); ; #endif / _WIX_LZW_COMPRESS_HEADER

21、_001_/ / LZ77.CPP / #include #include #include #include #include lz77.h / / 取log2(n)的upper_bound int CCompress:UpperLog2(int n) int i = 0; if (n 0) int m = 1; while(1) if (m = n) return i; m 0) int m = 1; while(1) if (m = n) return i; if (m n) return i - 1; m = 1; i+; else return -1; / LowerLog2 / /

22、 / 將位指針*piByte(字節(jié)偏移), *piBit(字節(jié)內位偏移)后移num位 void CCompress:MovePos(int* piByte, int* piBit, int num) num += (*piBit); (*piByte) += num / 8; (*piBit) = num % 8; / MovePos / / / 得到字節(jié)byte第pos位的值 / pos順序為高位起從記數(shù)（左起） BYTE CCompress:GetBit(BYTE byte, int pos) int j = 1; j = 7 - pos; if (byte & j) return 1;

23、else return 0; / GetBit / / / 設置byte的第iBit位為aBit / iBit順序為高位起從記數(shù)（左起） void CCompress:SetBit(BYTE* byte, int iBit, BYTE aBit) if (aBit) (*byte) |= (1 (7 - iBit); else (*byte) &= (1 b0; pUDW-b0 = pUDW-b3; pUDW-b3 = b; b = pUDW-b1; pUDW-b1 = pUDW-b2; pUDW-b2 = b; / InvertDWord / / / CopyBits : 復制內存中的位流

24、/ memDest - 目標數(shù)據(jù)區(qū) / nDestPos - 目標數(shù)據(jù)區(qū)第一個字節(jié)中的起始位 / memSrc - 源數(shù)據(jù)區(qū) / nSrcPos - 源數(shù)據(jù)區(qū)第一個字節(jié)的中起始位 / nBits - 要復制的位數(shù) / 說明： / 起始位的表示約定為從字節(jié)的高位至低位（由左至右） / 依次為0，. , 7 / 要復制的兩塊數(shù)據(jù)區(qū)不能有重合 void CCompress:CopyBits(BYTE* memDest, int nDestPos, BYTE* memSrc, int nSrcPos, int nBits) int iByteDest = 0, iBitDest; int iByteS

25、rc = 0, iBitSrc = nSrcPos; int nBitsToFill, nBitsCanFill; while (nBits 0) / 計算要在目標區(qū)當前字節(jié)填充的位數(shù) nBitsToFill = min(nBits, iByteDest ? 8 : 8 - nDestPos); / 目標區(qū)當前字節(jié)要填充的起始位 iBitDest = iByteDest ? 0 : nDestPos; / 計算可以一次從源數(shù)據(jù)區(qū)中復制的位數(shù) nBitsCanFill = min(nBitsToFill, 8 - iBitSrc); / 字節(jié)內復制 CopyBitsInAByte(memDest

26、 + iByteDest, iBitDest, memSrc + iByteSrc, iBitSrc, nBitsCanFill); / 如果還沒有復制完nBitsToFill 個 if (nBitsToFill nBitsCanFill) iByteSrc+; iBitSrc = 0; iBitDest += nBitsCanFill; CopyBitsInAByte(memDest + iByteDest, iBitDest, memSrc + iByteSrc, iBitSrc, nBitsToFill - nBitsCanFill); iBitSrc += nBitsToFill -

27、nBitsCanFill; else iBitSrc += nBitsCanFill; if (iBitSrc = 8) iByteSrc+; iBitSrc = 0; nBits -= nBitsToFill; / 已經(jīng)填充了nBitsToFill位 iByteDest+; / CopyBits / / / CopyBitsInAByte : 在一個字節(jié)范圍內復制位流 / 參數(shù)含義同CopyBits 的參數(shù) / 說明： / 此函數(shù)由CopyBits 調用，不做錯誤檢查，即 / 假定要復制的位都在一個字節(jié)范圍內 void CCompress:CopyBitsInAByte(BYTE* memD

28、est, int nDestPos, BYTE* memSrc, int nSrcPos, int nBits) BYTE b1, b2; b1 = *memSrc; b1 = 8 - nBits; / 將不用復制的位清 b1 = 8 - nBits - nDestPos; / 將源和目的字節(jié)對齊 *memDest |= b1; / 復制值為的位 b2 = 0xff; b2 = nDestPos + nBits; b1 |= b2; *memDest &= b1; / 復制值為的位 / CopyBitsInAByte / /- CCompressLZ77:CCompressLZ77() Sor

29、tHeap = new struct STIDXNODE_MAX_WINDOW_SIZE; CCompressLZ77:CCompressLZ77() delete SortHeap; / 初始化索引表，釋放上次壓縮用的空間 void CCompressLZ77:_InitSortTable() memset(SortTable, 0, sizeof(WORD) * 65536); nWndSize = 0; HeapPos = 1; / 向索引中添加一個字節(jié)串 void CCompressLZ77:_InsertIndexItem(int off) WORD q; BYTE ch1, ch2

30、; ch1 = pWndoff; ch2 = pWndoff + 1; if (ch1 != ch2) / 新建節(jié)點 q = HeapPos; HeapPos+; SortHeapq.off = off; SortHeapq.next = SortTablech1 * 256 + ch2; SortTablech1 * 256 + ch2 = q; else / 對重復字節(jié)串 / 因為沒有虛擬偏移也沒有刪除操作，只要比較第一個節(jié)點 / 是否和off 相連接即可 q = SortTablech1 * 256 + ch2; if (q != 0 & off = SortHeapq.off2 + 1

31、) / 節(jié)點合并 SortHeapq.off2 = off; else / 新建節(jié)點 q = HeapPos; HeapPos+; SortHeapq.off = off; SortHeapq.off2 = off; SortHeapq.next = SortTablech1 * 256 + ch2; SortTablech1 * 256 + ch2 = q; / / 將窗口向右滑動n個字節(jié) void CCompressLZ77:_ScrollWindow(int n) for (int i = 0; i 1) _InsertIndexItem(nWndSize - 2); / / 得到已經(jīng)匹

32、配了個字節(jié)的窗口位置offset / 共能匹配多少個字節(jié) int CCompressLZ77:_GetSameLen(BYTE* src, int srclen, int nSeekStart, int offset) int i = 2; / 已經(jīng)匹配了個字節(jié) int maxsame = min(srclen - nSeekStart, nWndSize - offset); while (i maxsame & srcnSeekStart + i = pWndoffset + i) i+; _ASSERT(nSeekStart + i = srclen & offset + i = nWndSize); return i; / / 在滑動窗口中查找術語 / nSeekStart - 從何處開始匹配 / offset, len - 用于接收結果，表示在滑動窗口內的偏移和長度 / 返回值- 是否查到長度為或