基于Huffman算法和LZ77算法的文件壓縮（六）

前面基于Huffman算法和LZ77算法的文件壓縮（四）
基于Huffman算法和LZ77算法的文件壓縮（五）
已經(jīng)充分講解LZ77到基本原理和實(shí)現(xiàn)細(xì)節(jié)。

本文開(kāi)始講解文件的壓縮過(guò)程。

一、回顧整個(gè)壓縮過(guò)程

1.打開(kāi)帶壓縮的文件(注意：必須按照二進(jìn)制格式打開(kāi)，因?yàn)橛脩暨M(jìn)行壓縮的文件不確定)
2.獲取文件大小，如果文件大小小于3個(gè)字節(jié)，則不進(jìn)行壓縮
3.讀取一個(gè)窗口的數(shù)據(jù)，即64K，
4.用前兩個(gè)字符計(jì)算第一個(gè)字符與其后兩個(gè)字符構(gòu)成字符串哈希地址的一部分，因?yàn)楣５刂肥峭ㄟ^(guò)三個(gè)字節(jié)算出來(lái)的，先用前兩個(gè)字節(jié)算出一部分，在壓縮時(shí)，再結(jié)合第三個(gè)字節(jié)算出第一個(gè)字符串完整的哈希地址。
5.循環(huán)開(kāi)始?jí)嚎s
a.計(jì)算哈希地址，將該字符串首字符在窗口中的位置插入到哈希桶中，并返回該桶的狀態(tài)matchHead
b.根據(jù)matchHead檢測(cè)是否找到匹配

• 如果matchHead等于0，未找到匹配，表示該三個(gè)字符在前文中沒(méi)有出現(xiàn)過(guò)，將該當(dāng)前字符 作為源字符寫(xiě)到壓縮文件中
• 如果matchHead不等于0，表示找到匹配，matchHead代表匹配鏈的首地址，從哈希桶matchHead位置開(kāi)始找最長(zhǎng)匹配，找到后用該(距離，長(zhǎng)度對(duì))替換該字符串寫(xiě)到壓縮文件中，然后將該替換串三個(gè)字符一組添加到哈希表中。

6 . 如果窗口中的數(shù)據(jù)小于MIN_LOOKAHEAD時(shí)，將右窗口中數(shù)據(jù)搬移到左窗口，從文件中新讀取一個(gè)窗口的數(shù)據(jù)放置到右窗，更新哈希表，繼續(xù)壓縮，直到壓縮結(jié)束。

二、先封裝一個(gè)哈希表

1.先給一個(gè)公共信息的文件common.h

#pragma once #include <iostream> #include <string> #include <assert.h> #include <string.h> #include <stdio.h> #include <stdlib.h>//記錄程序中用到的常量數(shù)據(jù)typedef unsigned char UCH; typedef unsigned short USH; typedef unsigned long long ULL;const USH MIN_MATCH = 3; //最小匹配長(zhǎng)度 const USH MAX_MATCH = 258; //最大匹配長(zhǎng)度 const USH WSIZE = 32 * 1024; //32k

2.哈希表的整體框架：

#pragma once #include "Common.hpp"class HashTable {public:HashTable(USH size);~HashTable();//哈希表插入，//matchHead為出參，帶出整個(gè)匹配鏈的頭，ch為匹配的字符，pos為//在緩沖區(qū)當(dāng)中的下標(biāo)。hashAddr為哈希地址：出入輸出型參數(shù)，//因?yàn)橛?jì)算本次哈希地址需要用到上一個(gè)哈希地址void Insert(USH& matchHead, UCH ch, USH pos, USH& hashAddr);//哈希函數(shù)void HashFunc(USH& hashAddr, UCH ch);//獲取哈希表前一個(gè)匹配頭USH GetNext(USH matchHead);//在處理大于64k的大文件時(shí)，需要把右窗中的文件拷貝到左窗，需要更新哈希表void Update();private://哈希函數(shù)相關(guān)USH H_SHIFT();private:USH* prev_;USH* head_;};

3.哈希表的構(gòu)造：

HashTable::HashTable(USH size):prev_(new USH[size * 2]) //哈希表中存放的是索引字符串的首地址//(距離字符串開(kāi)始的相對(duì)下標(biāo)), head_(prev_ + size) {memset(prev_, 0, size * 2 * sizeof(USH));//初始化為0，0也代表當(dāng)前匹配是//鏈表的末尾（相當(dāng)于用數(shù)組模擬的鏈表） }

4.哈希表的析構(gòu)函數(shù)：

HashTable::~HashTable() {delete[] prev_;prev_ = nullptr; }

5.定義哈希函數(shù)相關(guān)變量：

const USH HASH_BITS = 15; //哈希地址15位 const USH HASH_SIZE = (1 << HASH_BITS); //哈希地址個(gè)數(shù) 32K const USH HASH_MASK = HASH_SIZE - 1; //防止溢出 低15位全1,因?yàn)閜rev的大小就WSIZE，而當(dāng)start到達(dá)右窗 //時(shí)，下標(biāo)明顯大于WSIZE，如果不處理就會(huì)下標(biāo)越界

6.哈希函數(shù)相關(guān)：

//abcdefgh字符串 //hashaddr1:abc //hashaddr2:bcd//hashAddr:前一次計(jì)算出的哈希地址 abc //本次需要計(jì)算bcd哈希地址 //ch:本次匹配三個(gè)字符中的最后一個(gè) //本次哈希地址是在上一次哈希地址的基礎(chǔ)上計(jì)算出來(lái)的 void HashTable::HashFunc(USH& hashAddr, UCH ch) { //hashAddr是輸入，輸出型參數(shù)，ch是所查找字符串中第一個(gè)字符hashAddr = (((hashAddr) << H_SHIFT()) ^ (ch)) & HASH_MASK; }USH HashTable::H_SHIFT() {return (HASH_BITS + MIN_MATCH - 1) / MIN_MATCH; //5 }

7.向哈希表中插入元素：

//matchHead：匹配鏈的頭 //ch：查找字符串的第三個(gè)字符(也就是最后一個(gè)) //pos：查找字符串的頭到字符串開(kāi)始的距離 //hashAddr：輸入時(shí)是上一次的哈希地址,輸出時(shí)是本次哈希地址 void HashTable::Insert(USH& matchHead, UCH ch, USH pos, USH& hashAddr) {HashFunc(hashAddr, ch); //獲取本次插入的哈希地址matchHead = head_[hashAddr];//找當(dāng)前三個(gè)字符在查找緩沖區(qū)中找到的最近的個(gè)，//即匹配鏈的頭，將來(lái)會(huì)用這個(gè)頭來(lái)找匹配//將新的哈希地址插入鏈表//pos & HASH_MASK的目的是防止越界prev_[pos & HASH_MASK] = head_[hashAddr];head_[hashAddr] = pos; }

三、開(kāi)始?jí)嚎s

1.整體框架

#pragma once #include "HashTable.h"class LZ77 {public:LZ77();~LZ77();void CompressFile(const std::string& strFilePath);void UNCompressFile(const std::string& strFilePath);private://找最長(zhǎng)匹配USH LongestMatch(USH matchHead, USH& curMatchDist, USH start); //寫(xiě)標(biāo)記文件void WriteFlag(FILE* fOUT, UCH& chFlag, UCH& bitCount, bool isLen); //合并壓縮數(shù)據(jù)文件和標(biāo)記信息文件void MergeFile(FILE* fOut, ULL fileSize);//在處理大于64k文件時(shí)，需要重新填充緩沖區(qū)的右窗口void FillWindow(FILE* fIn, size_t& lookAhead, USH& start);//獲取文件的后綴std::string GetStr(std::string filename);private://用來(lái)保存待壓縮數(shù)據(jù)的緩沖區(qū)即滑動(dòng)窗口UCH* pWin_; //哈希表 HashTable ht_; };

2.構(gòu)造函數(shù)：

LZ77::LZ77():pWin_(new UCH[WSIZE * 2])//初始化緩沖區(qū)的大小,ht_(WSIZE) //初始化hash表大小 {}

3.析構(gòu)函數(shù)：

LZ77::~LZ77() {delete[] pWin_;pWin_ = nullptr; }

3.根據(jù)MIN_LOCKAHEAD來(lái)過(guò)濾文件，如果文件大小小于MIN_LOCKAHEAD則不進(jìn)行匹配。

• 注意文件的打開(kāi)方式，和Huffman壓縮的原理一樣，為了保證壓縮算法的通用性，既可以壓縮文本文件也可以壓縮二進(jìn)制文件，需要以rb方式打開(kāi)
• 如何獲取文件大小？？結(jié)合fseek函數(shù)和ftell函數(shù)來(lái)獲取文件大小

FILE* fIn = fopen(strFilePath.c_str(), "rb");if (nullptr == fIn) {std::cout << "打開(kāi)文件失敗" << std::endl;return;}//獲取文件大小fseek(fIn, 0, SEEK_END);//把文件指針移動(dòng)到文件的末尾ULL fileSize = ftell(fIn);//獲取當(dāng)前文件指針到文件開(kāi)始位置的偏移量//1. 如果源文件的大小小于最小匹配長(zhǎng)度 MIN_MATCH，則不進(jìn)行處理,文件太小去進(jìn)行壓縮反而達(dá)不到壓縮的目的if (fileSize <= MIN_MATCH) { //此處是小于3個(gè)字符,在common.hpp文件中定義的std::cout << "文件太小，不壓縮" << std::endl;return;}

4.從壓縮文件中讀取一個(gè)緩沖區(qū)的數(shù)據(jù)到窗口中

• 注意在計(jì)算文件大小的時(shí)候已經(jīng)把文件指針移動(dòng)到文件的末尾，所以此處要把文件指針重新定位

//從壓縮文件中讀取一個(gè)緩沖區(qū)的數(shù)據(jù)到窗口中//上面把文件指針移動(dòng)到文件末尾，還得移回來(lái)，//否則讀不到任何數(shù)據(jù)fseek(fIn, 0, SEEK_SET);//表示先行緩沖區(qū)中剩余的字節(jié)數(shù)size_t lookAhead = fread(pWin_, 1, 2 * WSIZE, fIn);

5 .先計(jì)算最開(kāi)始兩個(gè)字符的哈希地址

• 因?yàn)楣５刂肥歉鶕?jù)前面的字符的哈希地址求的，所以要先計(jì)算前兩個(gè)字符的哈希地址。如abcdefg……，那么滿3個(gè)字符才可以進(jìn)行匹配，所以需要先計(jì)算ab的哈希地址才可以計(jì)算c的哈希地址，然后進(jìn)行匹配

USH hashAddr = 0;//記錄哈希地址//設(shè)置起始hashAddr (前兩個(gè)字符的hash地址)for (USH i = 0; i < MIN_MATCH - 1; ++i) {ht_.HashFunc(hashAddr,pWin_[i]);}

6.循環(huán)進(jìn)行壓縮

• 注意匹配鏈頭matchHead的含義。如果為0，代表沒(méi)找到匹配，因?yàn)楣１沓跏蓟臅r(shí)候都為0
• 那么如果找到匹配，就順著匹配鏈往下找最長(zhǎng)匹配
• 封裝一個(gè)LongestMatch函數(shù)來(lái)進(jìn)行查找最長(zhǎng)匹配
• 在找最長(zhǎng)匹配LongestMatch的時(shí)候需要獲得當(dāng)前匹配鏈的下一個(gè)匹配頭

//獲取當(dāng)前匹配頭的下一個(gè)匹配頭（如果為0代表匹配結(jié)束） USH HashTable::GetNext(USH matchHead) {return prev_[matchHead & HASH_MASK]; }

• 找到最長(zhǎng)匹配就需要返回長(zhǎng)度距離信息

//在找的過(guò)程中，需要將每次找到的匹配結(jié)果進(jìn)行比較，保持最長(zhǎng)匹配 USH LZ77::LongestMatch(USH matchHead, USH& MatchDist, USH start) { //找最長(zhǎng)匹配USH curMatchLen = 0; //一次匹配的長(zhǎng)度USH maxMatchLen = 0;UCH maxMatchCount = 255; //最大的匹配次數(shù)，解決環(huán)狀鏈USH curMatchStart = 0; //當(dāng)前匹配在查找緩沖區(qū)中的起始位置//在先行緩沖區(qū)中查找匹配時(shí)，不能太遠(yuǎn)即不能超過(guò)MAX_DISTUSH limit = start > MAX_DIST ? start - MAX_DIST : 0;do {//字符串在先行緩沖區(qū)匹配范圍UCH* pstart = pWin_ + start;UCH* pend = pstart + MAX_MATCH;//從查找緩沖區(qū)匹配串的起始開(kāi)始進(jìn)行字符比較UCH* pMatchStart = pWin_ + matchHead;curMatchLen = 0;//可以進(jìn)行本次匹配while (pstart < pend && *pstart == *pMatchStart) {//更新變量++curMatchLen;++pstart;++pMatchStart;}//一次匹配結(jié)束if (curMatchLen > maxMatchLen) {maxMatchLen = curMatchLen;//記錄當(dāng)前匹配的開(kāi)始位置，方便后面計(jì)算匹配距離curMatchStart = matchHead;}} while ((matchHead = ht_.GetNext(matchHead)) > limit&& maxMatchCount--);MatchDist = start - curMatchStart;return maxMatchLen; }

• while ((matchHead = ht_.GetNext(matchHead)) > limit && maxMatchCount--)：matchHead代表下一個(gè)匹配頭即在緩沖區(qū)當(dāng)中的下標(biāo)。

• USH limit = start > MAX_DIST ? start - MAX_DIST : 0;代表如果start > MAX_DIST就從start - MAX_DIST找匹配頭，否則就從開(kāi)始找匹配頭

• matchHead = ht_.GetNext(matchHead)) > limit代表在limit的范圍內(nèi)進(jìn)行找匹配，太遠(yuǎn)就不進(jìn)行匹配

• maxMatchCount--是為了解決&WMASK帶來(lái)死循環(huán)的問(wèn)題及太遠(yuǎn)不進(jìn)行匹配

• 執(zhí)行找最長(zhǎng)匹配后，需要驗(yàn)證是否成功找到匹配，因?yàn)閙atchHead可能為0，就沒(méi)有執(zhí)行找最長(zhǎng)匹配函數(shù)

• 前面我們說(shuō)過(guò)最大匹配長(zhǎng)度為[0，258]，如果用一個(gè)字節(jié)來(lái)記錄是有問(wèn)題的，需要用兩個(gè)字節(jié)來(lái)保存，而寫(xiě)入文件的時(shí)候又不能寫(xiě)入兩個(gè)字節(jié)，所以在寫(xiě)入長(zhǎng)度的時(shí)候臨時(shí)定義一個(gè)字節(jié)變量保存原來(lái)用兩個(gè)字節(jié)來(lái)保存長(zhǎng)度的變量-3，最后把一個(gè)字節(jié)的臨時(shí)變量寫(xiě)入當(dāng)壓縮文件當(dāng)中，這樣就解決問(wèn)題了

• 如果沒(méi)找到匹配就需要把當(dāng)前字符寫(xiě)入到壓縮文件當(dāng)中，如果找到最長(zhǎng)匹配，就需要寫(xiě)入長(zhǎng)度距離信息到壓縮文件當(dāng)中（注意寫(xiě)長(zhǎng)度的時(shí)候要把長(zhǎng)度-3），但是壓縮數(shù)據(jù)和長(zhǎng)度距離對(duì)信息無(wú)法區(qū)分

• 所以還要寫(xiě)入標(biāo)記信息：用0標(biāo)記原字符，1標(biāo)記長(zhǎng)度（距離不用標(biāo)記，下兩個(gè)字節(jié)就是，）

• 但是標(biāo)記信息和壓縮數(shù)據(jù)應(yīng)該保存在不同的文件當(dāng)中，無(wú)法一邊寫(xiě)壓縮數(shù)據(jù)一邊寫(xiě)標(biāo)記信息，那樣無(wú)法區(qū)分

//chFlag:該字節(jié)中的每個(gè)比特位是用來(lái)區(qū)分當(dāng)前字節(jié)是原字符還是長(zhǎng)度? //0:原字符 //1:長(zhǎng)度 //bitCount:該字節(jié)中的多少個(gè)比特位已經(jīng)被設(shè)置 //isCharOrLen:代表該字節(jié)是源字符還是長(zhǎng)度，判斷壓縮數(shù)據(jù)還是長(zhǎng)度信息 void LZ77::WriteFlag(FILE* fOUT, UCH& chFlag, UCH& bitCount, bool isLen) {chFlag <<= 1;if (isLen)//如果是長(zhǎng)度，就給當(dāng)前的比特位置為1chFlag |= 1;bitCount++;if (bitCount == 8) {//代表chFlag8位已經(jīng)設(shè)置完，將該標(biāo)記寫(xiě)入到壓縮文件中fputc(chFlag, fOUT);//重新開(kāi)始chFlag = 0;bitCount = 0;} }

• 注意如果找到匹配，在執(zhí)行寫(xiě)入長(zhǎng)度距離信息后，還需要把匹配的字符寫(xiě)入到哈希表當(dāng)中，否則無(wú)法進(jìn)行下一次匹配（匹配的長(zhǎng)度那么多的字符是不進(jìn)行下一次匹配的，因?yàn)橐呀?jīng)被替換掉），如abcdefg，如果abc找到匹配，把長(zhǎng)度距離信息寫(xiě)完后還要把bcd、cde寫(xiě)入到哈希表當(dāng)中，下一次直接從d開(kāi)始找匹配，而又因?yàn)閍bc在之前插入的時(shí)候已經(jīng)寫(xiě)過(guò)了，此處就不用寫(xiě)。

7.壓縮文件完整代碼

//壓縮文件 void LZ77 :: CompressFile(const std::string& strFilePath) {FILE* fIn = fopen(strFilePath.c_str(), "rb");if (nullptr == fIn) {std::cout << "打開(kāi)文件失敗" << std::endl;return;}//獲取文件大小fseek(fIn, 0, SEEK_END);//把文件指針移動(dòng)到文件的末尾ULL fileSize = ftell(fIn);//獲取當(dāng)前文件指針到文件開(kāi)始位置的偏移量//1. 如果源文件的大小小于最小匹配長(zhǎng)度 MIN_MATCH，則不進(jìn)行處理,文件太小去進(jìn)行壓縮反而達(dá)不到壓縮的目的if (fileSize <= MIN_MATCH) { //此處是小于3個(gè)字符,在common.hpp文件中定義的std::cout << "文件太小，不壓縮" << std::endl;return;}//從壓縮文件中讀取一個(gè)緩沖區(qū)的數(shù)據(jù)到窗口中fseek(fIn, 0, SEEK_SET);//上面把文件指針移動(dòng)到文件末尾，還得移回來(lái)，否則讀不到任何數(shù)據(jù)size_t lookAhead = fread(pWin_, 1, 2 * WSIZE, fIn);//表示先行緩沖區(qū)中剩余的字節(jié)數(shù)USH hashAddr = 0;//記錄哈希地址//設(shè)置起始hashAddr (前兩個(gè)字符的hash地址)for (USH i = 0; i < MIN_MATCH - 1; ++i) {ht_.HashFunc(hashAddr,pWin_[i]);}//開(kāi)始寫(xiě)壓縮數(shù)據(jù)://根據(jù)獲取的文件后綴打開(kāi)一個(gè)同樣文件后綴的壓縮數(shù)據(jù)存儲(chǔ)文件//std::string str = GetStr(strFilePath);//FILE* ffIn = fopen("5.txt","wb");//fwrite(str.c_str(),sizeof(str),1,ffIn);//fclose(ffIn);//壓縮FILE* fOUT = fopen("2.lzp", "wb");assert(fOUT);USH start = 0;//查找字符串在緩沖區(qū)的地址,隨著壓縮的不斷進(jìn)行，start不斷的在先行緩沖區(qū)中增加//與查找最長(zhǎng)匹配相關(guān)的變量USH matchHead = 0; //匹配字符串的頭USH curMatchLength = 0; //一次匹配字符串的長(zhǎng)度USH curMatchDist = 0; //一次匹配字符串的距離//與寫(xiě)標(biāo)記相關(guān)的變量UCH chFlag = 0;//代表當(dāng)前字符是字符還是長(zhǎng)度UCH bitCount = 0;//代表1個(gè)字節(jié)已經(jīng)用了多少字節(jié)//寫(xiě)標(biāo)記的文件FILE* fOutF = fopen("3.txt", "wb");assert(fOutF);//lookAhead表示先行緩沖區(qū)中剩余字節(jié)的個(gè)數(shù)while (lookAhead) {//1.將第三個(gè)字符插入到哈希表中，因?yàn)榍皟蓚€(gè)字符已經(jīng)插入到哈希表當(dāng)中，//(pWin_[start],pWin_[satrt + 1].pWin_[start + 2])并獲取匹配鏈的頭ht_.Insert(matchHead, pWin_[start + 2], start, hashAddr);//因?yàn)椴恢贿M(jìn)行一此匹配，每次匹配前都要置為0，防止影響后面的數(shù)據(jù)curMatchLength = 0;curMatchDist = 0;//2.驗(yàn)證在查找緩沖區(qū)中是否找到匹配，如果有匹配，找最長(zhǎng)匹配//因?yàn)樵诔跏蓟１淼臅r(shí)候都設(shè)置為0，代表沒(méi)有任何匹配，如果不為0，代表有匹配if (matchHead) {//順著匹配鏈找最長(zhǎng)匹配,最終帶出<長(zhǎng)度，距離>對(duì)curMatchLength = LongestMatch(matchHead, curMatchDist, start);}//3.驗(yàn)證是否找到匹配if (curMatchLength < MIN_MATCH) {//在查找緩沖區(qū)中未找到重復(fù)字符串//將start位置的字符寫(xiě)入到壓縮文件中fputc(pWin_[start], fOUT); //寫(xiě)字符//寫(xiě)當(dāng)前原字符對(duì)應(yīng)的標(biāo)記WriteFlag(fOutF, chFlag, bitCount, false);//寫(xiě)標(biāo)記//更新變量++ start;lookAhead--;}else {//找到匹配//將《長(zhǎng)度，距離》對(duì)寫(xiě)入壓縮文件中//寫(xiě)長(zhǎng)度UCH chLen = curMatchLength - 3;//因?yàn)殚L(zhǎng)度是1個(gè)字節(jié)，其范圍本來(lái)是//[0,255],但是因?yàn)槭?個(gè)一組，所以其范圍是[3,258]fputc(chLen, fOUT);//寫(xiě)距離fwrite(&curMatchDist, sizeof(curMatchDist), 1, fOUT);//寫(xiě)當(dāng)前原字符對(duì)應(yīng)的標(biāo)記WriteFlag(fOutF, chFlag, bitCount, true);//更新先行緩沖區(qū)中剩余的字節(jié)數(shù)lookAhead -= curMatchLength;//將已經(jīng)匹配的字符串按照三個(gè)一組將其插入到哈希表中--curMatchLength; //當(dāng)前字符串已經(jīng)插入++start;while (curMatchLength) {ht_.Insert(matchHead, pWin_[start + 2], start, hashAddr);--curMatchLength;++start;}}//檢測(cè)先行緩沖區(qū)中剩余字符個(gè)數(shù),如果小于最短匹配長(zhǎng)度，//需要更新緩沖區(qū)和哈希表，向緩沖區(qū)中重新填充內(nèi)容，if (lookAhead <= MIN_LOOKAHEAD)FillWindow(fIn, lookAhead, start);}//標(biāo)記位數(shù)如果不夠八位，因?yàn)閷?xiě)標(biāo)記是8位寫(xiě)一次，最后可能//不夠8bit，所以要另外判斷if (bitCount > 0 && bitCount < 8) {chFlag <<= (8 - bitCount);fputc(chFlag, fOutF);}fclose(fOutF);//把壓縮數(shù)據(jù)文件和標(biāo)記信息文件合并MergeFile(fOUT, fileSize);//刪除標(biāo)記信息文件remove("./3.txt");fclose(fIn);fclose(fOUT); }

到這里文件壓縮過(guò)程基本結(jié)束了，還有大文件處理方式在后面解決

總結(jié)

以上是生活随笔為你收集整理的基于LZ77算法的文件压缩收尾的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。