文件壓縮(基于LZ77的壓縮)

LZ77壓縮原理

初始LZ77

LZ77是基于字節的通用壓縮算法，它的原理就是將源文件中的重復字節(即在前文中出現的重復字節)使用(offset，length，nextchar)的三元組進行替換
這里的
長度–offset，距離—length，先行緩沖匹配串的下一個字符
總共三個字節

初始LZ77的缺陷

只是距離按照一個字節的長度，那么只能在先行緩沖區找256個以內的字符，所以壓縮率不是很高

改進后的LZ77

<長度，距離>，長度是一個字節，距離占2個字節
兩個字節：無符號類型來定義----->范圍為65535
但是真正匹配的時候并不用匹配這么遠，匹配的長度是一個WSIZE：32K-------32768

為什么太遠不匹配

為了提高0.1%的壓縮率，程序壓縮的性能可能會急劇下降

為什么匹配距離越遠性能會下降

因為LZ77是基于重復語句的壓縮，如果為了找重復語句，而擴大匹配的范圍，比較的次數增多，壓縮一個文件的時間變成不劃算

LZ77的原理

滑動窗口的設計

<長度，距離>對總共占三個字節

  • 最小的匹配長度：匹配的字符串最小為多少個字節
    MIN_MATCH:

    1. 1個字節肯定不匹配
    2. 2個字節，<長度，距離>占3個字節，如果進行替換，無疑會使壓縮文件變大
    3. 3個字節及以上開始匹配

  • 最大的匹配長度：字符串出現重復最多匹配多大
    MAX_MATCH:

    1. <長度，距離>對中的長度只是一個字節，一個字節范圍:[0,255]
    2. 因為字符串小于3個不進行匹配，所以范圍為[3,258]

在這里插入圖片描述

  • window：緩沖區，作用：在壓縮時，用來保存從待壓縮文件中讀取文件信息

  • 整個窗口的大小為64K。而整個文件分為一個已壓縮過區域，和未壓縮區域
    WSIZE1 = WSIZE2 = WSIZE = 32K

  • 已壓縮過的區域我們選擇剛剛壓縮過的一部分數據作為查找緩沖區，未壓縮過的稱為先行緩沖區，先行緩沖區第一個字節，也就是壓縮的起始位置定義為start

//為了書寫方便
typedef unsigned char UCH;
typedef unsigned short USH;
typedef unsigned long long ULL; //文件比較大//最小匹配的字符串長度，從3個字符開始匹配
const USH MIN_MATCH = 3;
//最大的匹配，0代表3個字符匹配，255可以代表258個字符匹配
const USH MAX_MATCH = 258;
const USH WSIZE = 32 * 1024;
滑動窗口的移動

不斷壓縮的時候，start肯定在往后移動，假設：待壓縮文件大小超過64K，不能一次性將源文件中的數據全部讀取到窗口中，start如果往后移動到一個位置，什么位置？就是start到窗口末尾中剩余的字符比較少（比如剩余10個字符，還有一部分匹配數據還在源文件中，沒讀到緩沖區中），本次匹配暫時不進行

先行緩沖區中的待壓縮數據剩余到一定數量，則不進行匹配，所以定義一個MIN_LOOKAHEAD來表示最小先行緩沖區MIN_LOOKAHEAD=MAX_NATCH +MIN_MATCH+ 1；即：保證待壓縮區域至少有一個字節以及該字節的一個匹配長度。
MIN_LOOKAHEAD:表示先行緩沖區剩余字符最小的個數:

  • MAX_MATCH可以保證：本次匹配達到最大，
  • MIN_MATCH+1可以保證：還可以進行下一次匹配
移動處理
  1. 將WSIZE2窗口中的數據導入到WSIZE1窗口中 start-=WSIZE
  2. 從待壓縮文件中再重新讀取一個WISIZE的數據到WSIZE2中
  3. 必須更新哈希表

真正的匹配距離并不是WSIZE，而是：MAX_DIST = WSIZE-LOOKAHEAD
也就是查找緩沖區就是WSIZE減去先行緩沖區剩余字符最小的個數，MAX_DIST = 查找緩沖區

LZ77高效的查找最長匹配串

哈希的設計

哈希桶大小

每次拿三個字節在前文中找匹配三個字節組合的可能性情況：224的可能性，哈希表應該要能容納224個哈希地址
用三個字節在查找緩沖區中找匹配

  • 三個字節在哈希表中直接查詢
    • 先計算哈希地址
    • 哈希表個中將來要存儲的是三個字符的下標—哈希表中每個位置給出2個字節，哈希表的空間224*2 = 32M
  • 空間太大
    • 隨著壓縮不斷進行，哈希表要不斷的更新，維護的成本太大了
    • LZ77算法在1977年提出，當時的硬件環境可能受限
    • 本項目哈希桶的個數設置為215

哈希表結構

在這里插入圖片描述
如果prev和head中某個位置存儲的數據大于WSIZE，就給該位置的數據減去WSIZE

  • prev作用
    • 用來解決哈希沖突
  • head作用
    • 保存本次新插入的字符串中首字符在window中的位置

在這里插入圖片描述

 insert(matchHead,ch,pos,hashAddr){//1.計算字符的哈希地址hashAddr = HashFunc(hashAddr,ch);//2.保存匹配鏈的頭matchHead = head[hashAddr];//3. 鏈接prev[pos&HASH_MASK] = matchHead;head[hashAddr] = pos;}

可以通過該種鏈接方式將相同字符的在window中的位置記錄下來查找最長匹配時，只需要順著鏈的方向依次取出對應字符在window中的位置即可進行匹配

pos有可能大于WSIZE，那么prev插入時會導致越界而引起程序崩潰，解決:pos&MASK：可以保證地址不越界，但有可能導致匹配鏈成環，解決方式：在找最長匹配時，限定匹配次數即可，限定次數為255.

為什么prev和head一樣大
  1. 和窗口對應起來，方便運算
  2. 考慮16位系統
&MASK存在的問題
  1. 可能會將某些鏈破壞
  2. 可能會造成鏈成環
    解決方式：設置一個最大的匹配次數255

哈希函數

三個字符的每個比特位都參與運算

A(4,5) + A(6,7,8) ^ B(1,2,3) + B(4,5) + B(6,7,8) ^ C(1,2,3) + C(4,5,6,7,8)

說明：A 指 3 個字節中的第 1 個字節，B 指第 2 個字節，C 指第 3 個字節，
A(4,5) 指第一個字節的第 4,5 位二進制碼，“^”是二進制位的異或操作，
“+”是“連接”而不是“加”，“^”優先于“+”）
這樣使 3 個字節都盡量“參與”到最后的結果中來，而且每個結果值 h 都等于 ((前1個h << 5) ^ c)取右 15位

// hashAddr: 上一個字符串計算出的哈希地址
// ch：當前字符
// 本次的哈希地址是在前一次哈希地址基礎上，再結合當前字符ch計算出來的
// HASH_MASK為WSIZE-1，&上掩碼主要是為了防止哈希地址越界
void HashTable::HashFunc(USH& hashAddr, UCH ch)
{
hashAddr = (((hashAddr) << H_SHIFT()) ^ (ch)) & HASH_MASK;
}USH HashTable::H_SHIFT()
{
return (HASH_BITS + MIN_MATCH - 1) / MIN_MATCH;
}
USH LZHashTable::GetNext(USH& matchHead)
{return _prev[matchHead&HASH_MASK];
}void  LZHashTable::Update()
{for (USH i = 0; i < WSIZE; ++i){//先更新headif (_head[i] >= WSIZE) //右窗_head[i] -= WSIZE; //下標變到左窗else //左窗_head[i] = 0; //清零//更新previf (_prev[i] >= WSIZE)_prev[i] -= WSIZE;else_prev[i] = 0;}
}

高效的查找匹配串實現

//在找的過程中，需要將每次找到的匹配結果進行比對，保存最長匹配
USH LZ77:: LongetMatch(USH matchHead, USH& MatchDist,USH start)
{USH curMatchLen = 0; //一次匹配的長度USH maxMatchLen = 0; //最大的匹配長度UCH maxMatchCount = 255;//最大的匹配次數，解決環狀鏈USH curMatchStart = 0; //當前匹配在查找緩沖區的起始位置//在先行緩沖區中查找匹配時，不能太遠即不能超過MAX_DISTUSH limit = start > MAX_DIST ? start - MAX_DIST : 0;do{// 匹配范圍// 先行緩沖區的起始位置UCH* pstart = _pWin + start;// 先行緩沖區末尾位置UCH* pend = pstart + MAX_MATCH;//查找緩沖區匹配串的起始位置UCH* pMatchStart = _pWin + matchHead;//當前匹配長度每回都要重置為0，要不然所有匹配長度都加到一塊了curMatchLen = 0;//可以進行匹配//先行緩沖區每到末尾并且字符相等while (pstart < pend && *pstart == *pMatchStart){curMatchLen++;pstart++;pMatchStart++;}//一次匹配結束//匹配長度超過最長匹配長度if (curMatchLen>maxMatchLen){//更新最長匹配長度maxMatchLen = curMatchLen;//更新起始位置curMatchStart = matchHead;}} while ((matchHead = _ht.GetNext(matchHead)) > limit && maxMatchCount--); //每設置一次，最大的匹配次數--//start-當前匹配的起始位置MatchDist = start - curMatchStart;return maxMatchLen;
}

LZ77實現

壓縮實現

1.打開待壓縮文件
    //獲取文件大小FILE* fIn = fopen(strFilePath.c_str(), "rb");if (nullptr == fIn){cout << "打開文件失敗" << endl;return;}
2. 獲取文件大小
1. 用fseek()把文件指針移動到末尾
2. 用ftell()計算文件指針偏移的位置

//獲取文件大小
fseek(fIn, 0, SEEK_END);
ULL fileSize = ftell(fIn);
3.源文件大小小于最小的匹配字符串MIN_MATCH，就不進行匹配
	//1.如果源文件的大小小于MIN_MATCH一個匹配長度,則不進行處理if (fileSize <= MIN_MATCH){cout << "文件太小，不壓縮" << endl;return;}
先把文件指針移動到起始位置，再從壓縮文件中讀取一個緩沖區的數據到窗口中
  1. fseek(fIn,SEEK_SET)
  2. fread(_pWin, 1, 2 * WSIZE, fIn);
	//從壓縮文件中讀取一個緩沖區的數據到窗口中fseek(fIn, 0, SEEK_SET);size_t lookAhead = fread(_pWin, 1, 2 * WSIZE, fIn);	USH hashAddr = 0;
5. 設置起始哈希地址
	//處理前兩個字節...設置hashAddrfor (USH i = 0; i < MIN_MATCH - 1; ++i){_ht.HashFunc(hashAddr, _pWin[i]);}

6. 壓縮

1. 用一個變量lookAhead來表示先行緩沖區剩余的個數
	//查找最長匹配相關的變量USH matchHead = 0;USH curMatchLength = 0; //當前匹配長度USH curMatchDist = 0;//寫標記相關的變量UCH chFlag = 0;USH bitCount = 0;bool IsLen = false;
2. 打開壓縮文件和寫標記的文件，保存壓縮數據
	//壓縮數據的文件	FILE* fOUT = fopen("2.lzp", "wb");assert(fOUT);USH start = 0;//寫標記的文件FILE* fOutF = fopen("3.txt", "wb");assert(fOutF);
3. 獲取匹配頭
//1.將當前三個字符(start,start+1,start+2)插入到哈希表中，獲取匹配頭
_ht.Insert(matchHead, _pWin[start + 2],start,hashAddr);
4.驗證再查找緩沖區中是否匹配，如果匹配找最長匹配
  • 如果matchHead != 0 代表匹配找到了，順著鏈找最長匹配，把<長度,距離>對返回來
if (matchHead)
{//順著匹配鏈找最長匹配,最終帶出<長度，距離>對curMatchLength =LongetMatch(matchHead,curMatchDist,start);
}
5.驗證是否找到最長匹配
  • 如果沒有找到，將start位置的字符寫入到壓縮文件中，并寫對應字符的標記，start往后移動，先行緩沖區個數減1
if (curMatchLength < MIN_MATCH)
{//在查找緩沖區中未找到重復字符串// 將start 位置的字符寫入到壓縮文件中fputc(_pWin[start], fOUT);//寫當前字符原字符對應的標記WriteFlage(fOutF,chFlag,bitCount,false );++start;lookAhead--;
}
  • 如果找到匹配，將<長度,距離>對寫入到壓縮文件中
  • 找到匹配，將匹配字符串插入到哈希表格中
//寫長度
UCH chLen = curMatchLength - 3;
fputc(chLen, fOUT);
//寫距離
fwrite(&curMatchDist, sizeof(curMatchDist), 1, fOUT);//寫當前對應的標記
WriteFlage(fOutF, chFlag, bitCount, true);//更新先行緩沖區中剩余的字節數,curMatchLength已經處理過了，就減去
lookAhead -= curMatchLength;//將已經匹配的字符串按照三個一組將其插入到哈希表中
--curMatchLength;//當前字符串已經插入過了
while (curMatchLength){start++;_ht.Insert(matchHead, _pWin[start+2], start, hashAddr);curMatchLength--;}++start; //循環中start少加了一次
6.如果文件大于64K要更新窗口
  1. 壓縮文件大于64K，將window中字符壓縮到小于等于MIN_LOOKAHEAD 正確
  2. 壓縮文件小于64K||現在已經處理到文件末尾，不需要填充
if (lookAhead <= MIN_LOOKAHEAD)FillWindow(fIn,lookAhead,start);
7. 查找匹配完成后，最后一個不夠8個比特位也要寫入壓縮文件
if (bitCount > 0 && bitCount < 8)
{chFlag <<= (8 - bitCount);fputc(chFlag, fOutF);
}
8.合并壓縮文件
//先將文件關閉，清空緩沖區
fclose(fOutF);
//合并壓縮文件
MergeFile(fOUT, fileSize);
fclose(fIn);
fclose(fOUT);

壓縮完整流程

void  LZ77::CompressFile(const std::string& strFilePath)
{//獲取文件大小FILE* fIn = fopen(strFilePath.c_str(), "rb");if (nullptr == fIn){cout << "打開文件失敗" << endl;return;}//獲取文件大小fseek(fIn, 0, SEEK_END);ULL fileSize = ftell(fIn);//1.如果源文件的大小小于MIN_MATCH一個匹配長度,則不進行處理if (fileSize <= MIN_MATCH){cout << "文件太小，不壓縮" << endl;return;}//從壓縮文件中讀取一個緩沖區的數據到窗口中fseek(fIn, 0, SEEK_SET);size_t lookAhead = fread(_pWin, 1, 2 * WSIZE, fIn);	USH hashAddr = 0;//處理前兩個字節...設置hashAddrfor (USH i = 0; i < MIN_MATCH - 1; ++i){_ht.HashFunc(hashAddr, _pWin[i]);}//壓縮FILE* fOUT = fopen("2.lzp", "wb");assert(fOUT);USH start = 0;//與查找最長匹配相關的變量USH matchHead = 0;USH curMatchLength = 0; //當前匹配長度USH curMatchDist = 0;//與寫標記相關的變量UCH chFlag = 0;USH bitCount = 0;bool IsLen = false;//寫標記的文件FILE* fOutF = fopen("3.txt", "wb");assert(fOutF);//lookAhead表示先行緩沖區中剩余字節的個數while (lookAhead){//1.將當前三個字符(start,start+1,start+2)插入到哈希表中，獲取匹配頭_ht.Insert(matchHead, _pWin[start + 2],start,hashAddr);curMatchLength = 0;curMatchDist = 0;//2. 驗證在查找緩沖區中是否找到匹配，如果有匹配，找最長匹配if (matchHead){//順著匹配鏈找最長匹配,最終帶出<長度，距離>對curMatchLength = LongetMatch(matchHead, curMatchDist,start);}//3.驗證是否找到匹配if (curMatchLength < MIN_MATCH){//在查找緩沖區中未找到重復字符串// 將start 位置的字符寫入到壓縮文件中fputc(_pWin[start], fOUT);//寫當前字符原字符對應的標記WriteFlage(fOutF,chFlag,bitCount,false );++start;lookAhead--;}else{//找到匹配//將<長度,距離>對寫入到壓縮文件中//寫長度UCH chLen = curMatchLength - 3;fputc(chLen, fOUT);//寫距離fwrite(&curMatchDist, sizeof(curMatchDist), 1, fOUT);//寫當前對應的標記WriteFlage(fOutF, chFlag, bitCount, true);//更新先行緩沖區中剩余的字節數,curMatchLength已經處理過了，就減去lookAhead -= curMatchLength;//將已經匹配的字符串按照三個一組將其插入到哈希表中--curMatchLength;//當前字符串已經插入過了while (curMatchLength){start++;_ht.Insert(matchHead, _pWin[start+2], start, hashAddr);curMatchLength--;}++start; //循環中start少加了一次}//檢測先行緩沖區中剩余字符的個數//      1.壓縮文件大于64K，將window中字符壓縮到小于等于MIN_LOOKAHEAD 正確//      2.壓縮文件小于64K||現在已經處理到文件末尾，不需要填充//       情況1. start>=WSIZE//       情況2. start < WSIZEif (lookAhead <= MIN_LOOKAHEAD)FillWindow(fIn,lookAhead,start);}//標記位數如果不夠8個比特位:if (bitCount > 0 && bitCount < 8){chFlag <<= (8 - bitCount);fputc(chFlag, fOutF);}fclose(fOutF);//合并壓縮文件MergeFile(fOUT, fileSize);fclose(fIn);fclose(fOUT);
}

解壓縮時，如何判斷該字節是原字符還是長度距離對？

解決方式
對壓縮文件中的數據進行標記

  • 0比特：標記源字符
  • 1比特：標記長度
    距離不需要標記，因為：如果檢測到某個比特位是1，說明該位置對應字節一定是長度，長度后緊跟著的兩個字節一定是距離
//chFlag:該字節中的每個比特位是用來區分當前字符是原字符還是長度
//0：代表原字符
//1：代表長度//bitCount:該字節中的多少比特位已經被設置
//isLen:代表該字節是原字符還是長度
//問題---- 標  記文件沒內容
//解決---參數要用引用傳參，把修改后的值帶出去
void LZ77::WriteFlage(FILE* fOut, UCH& chFalg, USH& bitCount, bool isLen)
{chFalg <<= 1;if (isLen)chFalg |= 1;bitCount++;//當前這個字節中的8個比特位已經用完了，寫入，重新置為0if (bitCount == 8){//將該標記寫入到壓縮文件中fputc(chFalg, fOut);chFalg = 0;bitCount = 0;}
}

壓縮之后壓縮文件的格式

解碼：

  • 用于解碼的信息
  • 壓縮結果：原字符+長度距離對
    不能直接將壓縮結果保存到壓縮文件中，無法區分原字符與長度距離對中的長度，如果不能區分，則無法進行解壓縮

解決方式，對寫入壓縮文件中的每個字節，用一個比特位來進行標記

  • 0比特：標記原字符
  • 比特：標記長度距離對中的長度，距離不用管，因為距離跟在長度后面
    要將用來標記比特位信息+壓縮結果 全部保存到壓縮文件中
    不能先寫標記信息，在壓縮開始之前，不能知道壓縮信息到底是多少，因為標記信息是隨著壓縮不斷進行而構造出來
如何保存：

文件1：壓縮結果
文件2：標記信息
壓縮完成之后有兩個文件，但是解壓縮時，如果提供給用戶兩個文件太麻煩
最終的壓縮文件格式：

在這里插入圖片描述

void LZ77::MergeFile(FILE* fOut,ULL fileSize)
{//將壓縮數據文件和標記信息合并//1.讀取標記信息文件中內容，然后將結果寫入到壓縮文件中FILE* fInF = fopen("3.txt", "rb");size_t flagSize = 0;UCH* pReadbuff = new UCH[1024];while (true){size_t rdSize = fread(pReadbuff, 1, 1024, fInF);if (0 == rdSize)break;fwrite(pReadbuff, 1, rdSize,fOut);flagSize += rdSize;}//2. 保存標記信息字節數//標記字節數fwrite(&flagSize, sizeof(flagSize), 1, fOut);//文件大小fwrite(&fileSize, sizeof(fileSize), 1, fOut);fclose(fInF);delete[]pReadbuff;
}

解壓縮

1. 先從打開壓縮文件

  1. 打開壓縮文件
  2. 用一個指針讀取，標記信息和標記信息大小
//打開壓縮文件
FILE* fInD = fopen(strFilePath.c_str(), "rb");
if (fInD == nullptr)
{cout << "壓縮文件打開失敗" << endl;return;
}// 操作標記的文件指針
FILE* fInF = fopen(strFilePath.c_str(), "rb");
if (fInF == nullptr)
{cout << "標記打開失敗" << endl;return;
}

2. 從壓縮文件末尾往前偏移文件大小字節數，讀取標記信息總的字節數

//獲取源文件的大小
ULL fileSize = 0;
fseek(fInF, 0 - sizeof(fileSize), SEEK_END);
fread(&fileSize, sizeof(fileSize), 1, fInF);//獲取標記信息大小
size_t flagSize = 0;
fseek(fInF,0-sizeof(fileSize)-sizeof(flagSize), SEEK_END);
fread(&flagSize, sizeof(flagSize), 1, fInF);

3.移動指針到壓縮文件起始位置

//將讀取標記信息的文件指針移動到保存標記數據的起始位置
//上面已經讀取了標記信息的大小，所以得再往前偏移標記信息大小得字節
//然后再偏移標記信息的大小，移動到標記信息的起始位置
fseek(fInF, 0 - sizeof(flagSize)-sizeof(fileSize)-flagSize, SEEK_END);

4. 開始解壓縮

  • 讀取壓縮數據，用該字節對應的標記來還原源文件
    • 如果該字節的比特位標記0，說明該字節是原字符，將其直接輸出到解壓縮文件中
    • 如果該字節的比特位標記1，說明該字節是長度距離對中的長度
      1. 從壓縮文件中讀取長度
      2. 從壓縮文件中讀取距離
      3. 根據長度距離對，從前文已經解壓縮成功的部分還原長度距離對部分
//開始解壓縮
//寫解壓縮的數據
FILE* fOut = fopen("4.txt", "wb");
assert(fOut);//用來匹配前文
FILE* fR = fopen("4.txt", "rb");UCH bitCount = 0;
UCH chFalg = 0;
ULL encodeCount = 0;//已經解壓縮完的字節
while (encodeCount < fileSize) 
{if (0 == bitCount){//先讀取一個字節chFalg =  fgetc(fInF);bitCount = 8;}if (chFalg & 0x80){//是距離長度對//讀取長度USH matchLen = fgetc(fInD) + 3;//讀取距離USH matchDist = 0;fread(&matchDist, sizeof(matchDist), 1, fInD);//清空緩沖區，系統把緩沖區中的數據放到文件中fflush(fOut);//更新已經解碼的長度encodeCount += matchLen;//去前文中找匹配//fR:讀取匹配串中的內容//從末尾往前偏移0-matchDistfseek(fR, 0-matchDist, SEEK_END);UCH ch;while (matchLen){ch = fgetc(fR);fputc(ch,fOut);matchLen--;fflush(fOut);}}else{//是原字符UCH ch = fgetc(fInD);fputc(ch, fOut);encodeCount += 1;		}chFalg <<= 1;bitCount--;
}fclose(fInD);fclose(fInF);fclose(fOut);fclose(fR);
}

注意： 操作系統為了提高IO的效率，并不會直接將數據寫到文件中，一般先是將數據保存在緩沖區中，直到緩沖區滿或者用戶調用fflush函數清空緩沖區或者在關閉文件時，系統會自動清空緩沖區，此時數據才會真正的寫入到文件中
所以在用長度距離對還原該部分字節時，必須先清空緩沖區，讓系統已經解壓縮的部分寫入到解壓縮文件中，否則還原長度距離對時可能會出錯

大于64K的文件的處理

隨著壓縮的不斷進行，查找緩沖區不斷的增大，先行緩沖區不斷的縮小，如果先行緩沖區中剩余數據到達MIN_LOOKAHEAD時，就需要重新從待壓縮文件中讀取待壓縮數據

怎么填充數據
  1. 將右窗口中的數據搬移到左窗口
  2. 必須要更新哈希表
    • 如果head，prev中保存的下標：
      • 大于WSIZE：減去WSIZE。因為window中右窗的數據已經搬移到左窗中，每個字符的下標都減少WSIZE，哈希表中存儲的右窗的下標需要全部更新：減去WSIZE
      • 小于WSIZE：置為0。window中左窗的數據距離當前壓縮位置太遠了，因此不進行匹配，因此需要將哈希表中保存左窗的下標全部清空：將下標置為0
  3. 讀取一個WSIZE個壓縮數據放置到右窗口
void  LZ77::FillWindow(FILE* fIn, size_t& lookAhead, USH& start)
{//壓縮已經進行到右窗，先行緩沖區剩余數據不夠MIN_LOOKAHEADif (start >= WSIZE){//1.將右窗的數據搬移到左窗memcpy(_pWin, _pWin + WSIZE, WSIZE);memset(_pWin + WSIZE, 0, WSIZE);start -= WSIZE;//2.更新哈希表_ht.Update();//3.向右窗中補充一個WSIZE個待壓縮數據if (!feof(fIn)) // 文件指針沒走到末尾lookAhead = fread(_pWin + WSIZE, 1, WSIZE, fIn);}
}

問題

窗口越界

讀取大文件時，窗口越界。
lookAhead類型換成size_t

漢字問題

解壓縮的時候，遇到長度距離對還原，需要清空緩沖區，對于文本文件，文件末尾是FF，所以需要清空緩沖區

abcabcabcdef
  1. 第二個abc沒有參與匹配，因為第一個abc首字符的下標再window中的下標是0，因此再head中保存的就是0，第二個abc再匹配時，從哈希表中拿到的匹配鏈起始就是0，而0將其作為匹配鏈的結尾標記，因此第二個abc沒有參與匹配
  2. 對bca的匹配過程，查找范圍和待壓縮的范圍重疊----解壓縮的時候要及時清空緩沖區

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/383067.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/383067.shtml
英文地址，請注明出處：http://en.pswp.cn/news/383067.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

好中的圖像處理方面的期刊_約會中，注意這四個方面，幫助你把握好自己的真愛...

好中的圖像處理方面的期刊_約會中，注意這四個方面，幫助你把握好自己的真愛...

兩個人想要擁有一段美好的感情&#xff0c;那么男生就要掌握好一些技巧去追求對方&#xff0c;在追求的過程中&#xff0c;兩個人的約會也非常重要&#xff0c;畢竟只有約會過程中&#xff0c;女孩子才能夠看到你光鮮亮麗的一面&#xff0c;才能夠慢慢的接受你&#xff0c;如果…
閱讀更多...
kafka consumer配置拉取速度慢_Kafka消費者的使用和原理

kafka consumer配置拉取速度慢_Kafka消費者的使用和原理

這周我們學習下消費者&#xff0c;仍然還是先從一個消費者的Hello World學起&#xff1a;public class Consumer { public static void main(String[] args) { // 1. 配置參數 Properties properties new Properties(); properties.put("key.des…
閱讀更多...
前綴和

前綴和

前綴和 輸入一個長度為n的整數序列。 接下來再輸入m個詢問&#xff0c;每個詢問輸入一對l, r。 對于每個詢問&#xff0c;輸出原序列中從第l個數到第r個數的和。 輸入格式 第一行包含兩個整數n和m。 第二行包含n個整數&#xff0c;表示整數數列。 接下來m行&#xff0c;…
閱讀更多...
子矩陣的和

子矩陣的和

題目描述 輸入一個n行m列的整數矩陣&#xff0c;再輸入q個詢問&#xff0c;每個詢問包含四個整數x1, y1, x2, y2&#xff0c;表示一個子矩陣的左上角坐標和右下角坐標。 對于每個詢問輸出子矩陣中所有數的和。 輸入格式 第一行包含三個整數n&#xff0c;m&#xff0c;q。 …
閱讀更多...
jmeter 循環取值賦值給form_JMeter系列(三)邏輯控制器詳解

jmeter 循環取值賦值給form_JMeter系列(三)邏輯控制器詳解

循環控制器&#xff1a;指定迭代次數&#xff0c;可以用具體數字&#xff0c;也可以通過變量控制永遠&#xff1a;表示無限循環點擊查看示例&#xff1a;Jmeter實例(四)_圖片爬蟲簡單控制器&#xff1a;這是最基礎的一個控制器&#xff0c;它可以讓腳本分層&#xff0c;變成一個…
閱讀更多...
c 復雜的前置后置面試題_OPPO Reno拆解：優秀工藝由外而內，復雜用料不負旗艦之名...

c 復雜的前置后置面試題_OPPO Reno拆解：優秀工藝由外而內，復雜用料不負旗艦之名...

OPPO的新系列Reno手機最近吸引了不少注意力&#xff0c;不管是消費者還是手機極客都對其優秀的性能和強大的配置抱有極大的興趣。最近&#xff0c;知名數碼博主愛玩客對Reno十倍變焦版進行了拆解&#xff0c;從內部結構向我們揭示了這部手機的強大之處。并且點評道&#xff1a;…
閱讀更多...
差分矩陣

差分矩陣

題目描述 輸入一個n行m列的整數矩陣&#xff0c;再輸入q個操作&#xff0c;每個操作包含五個整數x1, y1, x2, y2, c&#xff0c;其中(x1, y1)和(x2, y2)表示一個子矩陣的左上角坐標和右下角坐標。 每個操作都要將選中的子矩陣中的每個元素的值加上c。 請你將進行完所有操作后…
閱讀更多...
python常用的開發環境包括_Python語言主要包括哪些集成開發環境?_學小易找答案...

python常用的開發環境包括_Python語言主要包括哪些集成開發環境?_學小易找答案...

【填空題】Python的標準隨機數生成器模塊是【簡答題】Why does critical thinking matter?【簡答題】采集瓶子的外形進行創意設計 用點、線、面進行裝飾填充 A4紙手繪,構圖要有新意,要飽滿【簡答題】How can a lack of critical thinking cause a loss of personal freedom?【…
閱讀更多...
最長連續不重復子序列

最長連續不重復子序列

題目描述 給定一個長度為n的整數序列&#xff0c;請找出最長的不包含重復數字的連續區間&#xff0c;輸出它的長度。 輸入格式 第一行包含整數n。 第二行包含n個整數&#xff08;均在0~100000范圍內&#xff09;&#xff0c;表示整數序列。 輸出格式 共一行&#xff0c;包…
閱讀更多...
ocp跟oce的區別 oracle_Oracle視頻10g 11g認證視頻教程 OCA/OCP 從入門到精通 數據庫DBA...

ocp跟oce的區別 oracle_Oracle視頻10g 11g認證視頻教程 OCA/OCP 從入門到精通 數據庫DBA...

一、認證Oracle OCP認證(Database 10g Administrator Certified Professional)為Oracle公司的數據庫專家的認證。擁有OCP認證說明你擁有了大型Oracle數據庫管理的技術能力&#xff0c;具備了成為大型企業核心數據庫系統管理員的資格。OCE 1Z0-051&#xff1a;Oracle Database 1…
閱讀更多...
小愛同學app安卓版_小愛同學app下載-小米小愛同學下載2.9.21安卓版-西西軟件下載...

小愛同學app安卓版_小愛同學app下載-小米小愛同學下載2.9.21安卓版-西西軟件下載...

小米小愛同學是小米AI音箱的配套軟件&#xff0c;小愛同學是AI音箱的擬人虛擬形象&#xff0c;是一個二次元的萌妹子&#xff0c;如果你購買了小米AI音箱可以通過跟小愛同學交流來讓小米智能音箱幫你完成你想要的服務。小愛同學支持海量互聯網內容&#xff0c;包括在線音樂&…
閱讀更多...
python畫太極八卦圖_先天太極八卦圖的唯一正確畫法

python畫太極八卦圖_先天太極八卦圖的唯一正確畫法

我們先百度一下先天太極八卦圖.↑&#xff0c;看看結果百度出來的圖片第一頁上半部分&#xff0c;結果非常驚人&#xff0c;40張圖片&#xff0c;沒有一張是正確的。錯誤原因分為兩大類&#xff1a;1.太極圖旋轉方向或陰陽魚所在位置錯誤 2.八卦中每卦的三爻畫法錯誤1. 先天太極…
閱讀更多...
函數無法識別_PostgreSQL找不到最佳函數問題解析

函數無法識別_PostgreSQL找不到最佳函數問題解析

最近給項目做支持&#xff0c;由于函數類型問題&#xff0c;加了幾條函數定義。用戶使用函數場景是func(string, string)。當時給用戶添加了一條函數定義&#xff1a;func(text, text)。后來由于和其他函數沖突改成了func(varchar, varchar)。varchar和text同樣都是字符串類型&…
閱讀更多...
Xshell鏈接不上云服務器的解決方案

Xshell鏈接不上云服務器的解決方案

1.ssh拒絕請求 先該配置文件 https://blog.csdn.net/u012206617/article/details/83026777?ops_request_misc&request_id&biz_id102&utm_termssh%E6%9C%8D%E5%8A%A1%E5%99%A8%E6%8B%92%E7%BB%9D%E4%BA%86%E5%AF%86%E7%A0%81%20%E8%AF%B7%E5%86%8D%E8%AF%95%E4%B8…
閱讀更多...
框架controller找不到_SpingBoot框架知識詳解

框架controller找不到_SpingBoot框架知識詳解

Spring boot框架1、什么是Spring Boot&#xff1f;? Spring Boot是Spring開源組織下的子項目&#xff0c;是Spring組件一站式解決方案&#xff0c;主要是簡化了使用Spring的難度&#xff0c;簡省了繁重的配置&#xff0c;提供了各種啟動器&#xff0c;開發者能快速上手。Sprin…
閱讀更多...
架構的演變

架構的演變

基本概念 在介紹架構之前&#xff0c;為了避免部分讀者對架構設計中的一些概念不了解&#xff0c;下面對幾個最基礎的概念進行介紹。 1.什么是分布式&#xff1f; 系統中的多個模塊在不同服務器上部署&#xff0c;即可稱為分布式系統&#xff0c;如Tomcat和數據庫分別部署在…
閱讀更多...
axure8.0導出頁面打不開問題_excel怎么轉pdf？excel打不開？轉換成PDF就行了

axure8.0導出頁面打不開問題_excel怎么轉pdf？excel打不開？轉換成PDF就行了

excel轉pdf怎么做&#xff1f;年底最后一天了&#xff0c;我都被一堆的Excel文件搞得頭疼&#xff0c;在這些時間里&#xff0c;要讓我對幾個G的文件進行操作&#xff0c;我已經是忙得不可開交&#xff0c;而在最后的最后&#xff0c;我的主管還說他的電腦無法打開我的Excel 了…
閱讀更多...
質數相關問題

質數相關問題

試除法判定質數 題目描述 給定n個正整數ai&#xff0c;判定每個數是否是質數。 輸入格式 第一行包含整數n。 接下來n行&#xff0c;每行包含一個正整數ai。 輸出格式 共n行&#xff0c;其中第 i 行輸出第 i 個正整數ai是否為質數&#xff0c;是則輸出“Yes”&#xff0c…
閱讀更多...
python怎么爬蟲理數據_Python神技能 | 使用爬蟲獲取汽車之家全車型數據

python怎么爬蟲理數據_Python神技能 | 使用爬蟲獲取汽車之家全車型數據

最近想在工作相關的項目上做技術改進&#xff0c;需要全而準的車型數據&#xff0c;尋尋覓覓而不得&#xff0c;所以就只能自己動手豐衣足食&#xff0c;到網上獲&#xff08;竊&#xff09;得&#xff08;取&#xff09;數據了。汽車之家是大家公認的數據做的比較好的汽車網站…
閱讀更多...
linux運算_CentOS「linux」學習筆記22:算術運算符、邏輯運算符、關系運算符

linux運算_CentOS「linux」學習筆記22:算術運算符、邏輯運算符、關系運算符

?linux基礎操作&#xff1a;主要介紹啦算術運算符、邏輯運算符、關系運算符1.算術運算符[主要用來計算數值]注意使用expr運算時運算符和數值之間需要有空格&#xff0c;其他方式運算時不能有空格。常用算術運算符號&#xff1a;表示相加&#xff0c;&#xff0d;表示相減&…
閱讀更多...
最新文章

Copyright @ 2022~2023