C語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)的壓縮與解壓
一、壓縮與解壓介紹
數(shù)據(jù)壓縮是通過(guò)一系列的算法和技術(shù)將原始數(shù)據(jù)轉(zhuǎn)換為更緊湊的表示形式，以減少數(shù)據(jù)占用的存儲(chǔ)空間。數(shù)據(jù)解壓縮則是將壓縮后的數(shù)據(jù)恢復(fù)到原始的表示形式。
數(shù)據(jù)可以被壓縮打包并減少空間占用的原因有以下幾個(gè)方面：
（1）無(wú)效數(shù)據(jù)的消除：在數(shù)據(jù)中可能存在大量冗余、重復(fù)或無(wú)效的信息。壓縮算法可以通過(guò)識(shí)別和移除這些無(wú)效數(shù)據(jù)，從而減小數(shù)據(jù)的大小。
（2）統(tǒng)計(jì)特性的利用：數(shù)據(jù)通常具有某種統(tǒng)計(jì)特性，例如頻繁出現(xiàn)的模式、重復(fù)的字節(jié)序列等。壓縮算法可以利用這些統(tǒng)計(jì)特性來(lái)編碼數(shù)據(jù)，從而達(dá)到更高的壓縮比率。
（3）信息編碼：壓縮算法使用不同的編碼方式來(lái)表示源數(shù)據(jù)，在保證數(shù)據(jù)可還原的前提下，使用更少的位數(shù)來(lái)表示信息。例如，Huffman編碼、LZW編碼等。
常見(jiàn)的應(yīng)用場(chǎng)景中會(huì)使用到數(shù)據(jù)壓縮和解壓功能，例如：
（1）存儲(chǔ)媒體：在硬盤(pán)、閃存等存儲(chǔ)介質(zhì)上，壓縮可以節(jié)省存儲(chǔ)空間，并提高存儲(chǔ)效率。尤其在大規(guī)模的數(shù)據(jù)中心、云存儲(chǔ)環(huán)境中，數(shù)據(jù)壓縮可以顯著減少存儲(chǔ)成本。
（2）網(wǎng)絡(luò)傳輸：在網(wǎng)絡(luò)通信中，壓縮可以減少數(shù)據(jù)傳輸?shù)膸捪?，提高傳輸速度。尤其在低帶寬、高延遲的網(wǎng)絡(luò)環(huán)境中，壓縮可以顯著改善傳輸性能。
（3）文件壓縮：壓縮工具如ZIP、RAR等常用于對(duì)文件進(jìn)行打包和壓縮，以減小文件的大小，便于存儲(chǔ)和傳輸。這在文件傳輸、備份和歸檔中非常常見(jiàn)。
（4）多媒體編碼：音頻、圖像、視頻等多媒體數(shù)據(jù)往往具有較高的冗余性，壓縮算法可以大幅減小文件大小，例如MP3、JPEG、H.264等壓縮算法。
二、ZIP格式介紹
ZIP是一種常見(jiàn)的文件壓縮格式，它使用DEFLATE算法來(lái)進(jìn)行數(shù)據(jù)壓縮。
下面是ZIP壓縮的基本原理：
（1）文件分塊：ZIP壓縮將要壓縮的文件按照一定大小的塊進(jìn)行劃分。每個(gè)塊通常包含多個(gè)字節(jié)，并且可以獨(dú)立地進(jìn)行壓縮處理。
（2）壓縮算法：對(duì)于每個(gè)塊，ZIP使用DEFLATE算法進(jìn)行壓縮。DEFLATE是一種無(wú)損的壓縮算法，它結(jié)合了LZ77算法和霍夫曼編碼，可以有效地消除冗余并提高壓縮比率。
- LZ77算法：遍歷輸入數(shù)據(jù)，尋找重復(fù)的模式（前綴）并使用指針來(lái)表示。通過(guò)將重復(fù)的模式替換為指針，可以達(dá)到數(shù)據(jù)壓縮的效果。
- 霍夫曼編碼：利用字符出現(xiàn)的頻率來(lái)設(shè)計(jì)一種更緊湊的編碼方式。頻率較高的字符使用較短的編碼，頻率較低的字符使用較長(zhǎng)的編碼。
（3）數(shù)據(jù)存儲(chǔ)：壓縮后的數(shù)據(jù)以塊為單位存儲(chǔ)在ZIP文件中。每個(gè)塊都包含壓縮后的數(shù)據(jù)、塊的元數(shù)據(jù)和校驗(yàn)和等信息。
（4）全局文件目錄：ZIP文件包含一個(gè)全局文件目錄，記錄了文件的結(jié)構(gòu)以及每個(gè)文件的元數(shù)據(jù)。這使得ZIP文件能夠存儲(chǔ)多個(gè)文件，并確保可以正確地還原被壓縮的文件。
- 文件結(jié)構(gòu)：全局文件目錄記錄了每個(gè)文件的名稱(chēng)、壓縮前后的大小、壓縮方法等信息。
- 文件索引：全局文件目錄還包含一個(gè)索引表，指明每個(gè)文件的起始位置和塊的偏移量。通過(guò)索引表，可以快速定位并解壓指定的文件塊。
（5）壓縮率：ZIP壓縮的效果取決于輸入文件的特性和DEFLATE算法的實(shí)現(xiàn)。通常情況下，文本文件和重復(fù)性較高的內(nèi)容可以獲得更高的壓縮比率，而二進(jìn)制文件和已經(jīng)過(guò)壓縮的文件（如JPEG圖像）則可能無(wú)法再次獲得顯著的壓縮。
ZIP壓縮的好處是它廣泛支持，并且可在各種操作系統(tǒng)和平臺(tái)上使用。ZIP格式支持密碼保護(hù)、文件夾結(jié)構(gòu)、注釋等功能，使其成為一種常用的壓縮格式。
三、C語(yǔ)言實(shí)現(xiàn)壓縮和解壓算法
3.1 代碼框架
下面是使用C語(yǔ)言實(shí)現(xiàn)壓縮和解壓的代碼框架（下一章再實(shí)現(xiàn)完整的算法）：
#include <stdio.h>
#include <stdlib.h>
?
void compressFile(const char* inputFile, const char* outputFile) {
? ?FILE* input = fopen(inputFile, "rb");
? ?FILE* output = fopen(outputFile, "wb");
? ?if (input == NULL || output == NULL) {
? ? ? ?printf("Failed to open files\n");
? ? ? ?return;
? }
?
? ?// 在這里執(zhí)行壓縮算法，將input文件的內(nèi)容壓縮，并寫(xiě)入output文件
?
? ?fclose(input);
? ?fclose(output);
}
?
void decompressFile(const char* compressedFile, const char* outputFile) {
? ?FILE* input = fopen(compressedFile, "rb");
? ?FILE* output = fopen(outputFile, "wb");
? ?if (input == NULL || output == NULL) {
? ? ? ?printf("Failed to open files\n");
? ? ? ?return;
? }
?
? ?// 在這里執(zhí)行解壓算法，將compressedFile文件的內(nèi)容解壓，并寫(xiě)入output文件
?
? ?fclose(input);
? ?fclose(output);
}
?
int main() {
? ?const char* inputFile = "input.txt";
? ?const char* compressedFile = "compressed.bin";
? ?const char* decompressedFile = "decompressed.txt";
?
? ?// 壓縮文件
? ?compressFile(inputFile, compressedFile);
? ?printf("File compressed successfully.\n");
?
? ?// 解壓文件
? ?decompressFile(compressedFile, decompressedFile);
? ?printf("File decompressed successfully.\n");
?
? ?return 0;
}上述代碼只是用于說(shuō)明基本思路，并未實(shí)現(xiàn)具體的壓縮算法。需要在compressFile和decompressFile函數(shù)中實(shí)現(xiàn)實(shí)際的壓縮和解壓算法邏輯。
在compressFile函數(shù)中，打開(kāi)輸入文件（例如input.txt），讀取文件內(nèi)容并進(jìn)行壓縮處理，最后將壓縮后的數(shù)據(jù)寫(xiě)入到輸出文件（例如compressed.bin）中。
在decompressFile函數(shù)中，打開(kāi)壓縮文件（例如compressed.bin），讀取壓縮數(shù)據(jù)并進(jìn)行解壓處理，最后將解壓后的數(shù)據(jù)寫(xiě)入到輸出文件（例如decompressed.txt）中。
可以選擇使用現(xiàn)成的壓縮算法庫(kù)，如zlib、gzip等，或者自行實(shí)現(xiàn)一種簡(jiǎn)單的壓縮算法（例如LZ77）。
下面章節(jié)介紹使用LZ77算法實(shí)現(xiàn)壓縮解壓。
3.2 完整的實(shí)現(xiàn)
LZ77（Lempel-Ziv-Welch 1977）是一種基于字典的無(wú)損數(shù)據(jù)壓縮算法，常用于文件壓縮和網(wǎng)絡(luò)傳輸中。通過(guò)利用數(shù)據(jù)中的重復(fù)片段來(lái)實(shí)現(xiàn)壓縮，并且可以實(shí)現(xiàn)逐步的解壓縮。
LZ77算法的核心思想是使用一個(gè)滑動(dòng)窗口和一個(gè)向前看緩沖區(qū)來(lái)尋找重復(fù)出現(xiàn)的字符串。算法從輸入數(shù)據(jù)的開(kāi)頭開(kāi)始，逐步讀取數(shù)據(jù)并嘗試匹配滑動(dòng)窗口中已經(jīng)出現(xiàn)過(guò)的字符串，如果找到匹配的字符串，就將其表示為（偏移，長(zhǎng)度）的形式，并且在輸出中只保留沒(méi)有匹配的字符，然后向前滑動(dòng)窗口和向前看緩沖區(qū)，繼續(xù)下一輪匹配。如果沒(méi)有找到匹配的字符串，則將當(dāng)前字符作為新的字符串添加到滑動(dòng)窗口，并輸出它。
下面是LZ77算法的詳細(xì)步驟：
（1）初始化滑動(dòng)窗口和向前看緩沖區(qū)。
（2）從輸入數(shù)據(jù)中讀取一個(gè)字符作為當(dāng)前字符。
（3）在滑動(dòng)窗口中查找最長(zhǎng)的匹配字符串，該字符串與向前看緩沖區(qū)中的部分或全部字符匹配。如果有多個(gè)匹配字符串具有相同的長(zhǎng)度，選擇最靠近滑動(dòng)窗口末尾的字符串。
（4）如果找到匹配字符串：
- 記錄該匹配字符串的偏移（滑動(dòng)窗口中的位置）和長(zhǎng)度。
- 將未匹配的字符添加到輸出，并將滑動(dòng)窗口和向前看緩沖區(qū)更新為匹配之后的位置。
（5）如果未找到匹配字符串：
- 將當(dāng)前字符作為新的字符串添加到滑動(dòng)窗口。
- 將當(dāng)前字符添加到輸出。
- 將滑動(dòng)窗口和向前看緩沖區(qū)更新為下一個(gè)位置。
（6）重復(fù)步驟2至步驟5，直到遍歷完整個(gè)輸入數(shù)據(jù)。
（7）輸出壓縮結(jié)果。
LZ77算法的優(yōu)點(diǎn)是簡(jiǎn)單易懂，實(shí)現(xiàn)相對(duì)容易，并且可以提供不錯(cuò)的壓縮率。它也有一些限制，例如在處理長(zhǎng)重復(fù)字符串時(shí)效率較低，并且可能會(huì)導(dǎo)致壓縮結(jié)果略微變大。為了克服這些限制，通常會(huì)結(jié)合其他壓縮算法（如Huffman編碼）來(lái)進(jìn)一步壓縮LZ77的輸出結(jié)果，以獲得更好的壓縮效果。
下面使用C語(yǔ)言自行實(shí)現(xiàn)的LZ77壓縮和解壓算法完成壓縮和解壓：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
?
#define MAX_WINDOW_SIZE 4096 ? // 窗口大小
#define MAX_LOOKAHEAD_SIZE 16 ?// 向前看緩沖區(qū)大小
?
typedef struct {
? ?int offset; ?// 指向匹配字符串在滑動(dòng)窗口中的偏移量
? ?int length; ?// 匹配字符串的長(zhǎng)度
? ?char nextChar; ?// 下一個(gè)字符
} Match;
?
void compressFile(const char* inputFile, const char* outputFile) {
? ?FILE* input = fopen(inputFile, "rb");
? ?FILE* output = fopen(outputFile, "wb");
? ?if (input == NULL || output == NULL) {
? ? ? ?printf("Failed to open files\n");
? ? ? ?return;
? }
?
? ?unsigned char window[MAX_WINDOW_SIZE];
? ?unsigned char lookahead[MAX_LOOKAHEAD_SIZE];
?
? ?int windowPos = 0;
? ?int lookaheadPos = 0;
?
? ?// 初始化窗口和向前看緩沖區(qū)
? ?memset(window, 0, sizeof(window));
? ?fread(lookahead, 1, MAX_LOOKAHEAD_SIZE, input);
? ?int bytesRead = ftell(input);
?
? ?while (bytesRead > 0) {
? ? ? ?Match longestMatch = {0, 0, lookahead[0]};
?
? ? ? ?// 在窗口中查找最長(zhǎng)匹配
? ? ? ?for (int i = windowPos - 1; i >= 0 && i >= windowPos - MAX_WINDOW_SIZE; --i) {
? ? ? ? ? ?int len = 0;
? ? ? ? ? ?while (len < MAX_LOOKAHEAD_SIZE && lookahead[len] == window[(i + len) % MAX_WINDOW_SIZE]) {
? ? ? ? ? ? ? ?++len;
? ? ? ? ? }
? ? ? ? ? ?if (len > longestMatch.length) {
? ? ? ? ? ? ? ?longestMatch.offset = windowPos - i - 1;
? ? ? ? ? ? ? ?longestMatch.length = len;
? ? ? ? ? ? ? ?longestMatch.nextChar = lookahead[len];
? ? ? ? ? }
? ? ? }
?
? ? ? ?// 寫(xiě)入最長(zhǎng)匹配的偏移和長(zhǎng)度
? ? ? ?fwrite(&longestMatch, sizeof(Match), 1, output);
?
? ? ? ?// 更新窗口和向前看緩沖區(qū)
? ? ? ?for (int i = 0; i < longestMatch.length + 1; ++i) {
? ? ? ? ? ?window[windowPos] = lookahead[i];
? ? ? ? ? ?windowPos = (windowPos + 1) % MAX_WINDOW_SIZE;
? ? ? ? ? ?if (bytesRead > 0) {
? ? ? ? ? ? ? ?if (fread(lookahead, 1, 1, input) == 1) {
? ? ? ? ? ? ? ? ? ?bytesRead = ftell(input);
? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ?bytesRead = 0;
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? }
? }
?
? ?fclose(input);
? ?fclose(output);
}
?
void decompressFile(const char* compressedFile, const char* outputFile) {
? ?FILE* input = fopen(compressedFile, "rb");
? ?FILE* output = fopen(outputFile, "wb");
? ?if (input == NULL || output == NULL) {
? ? ? ?printf("Failed to open files\n");
? ? ? ?return;
? }
?
? ?unsigned char window[MAX_WINDOW_SIZE];
? ?unsigned char lookahead[MAX_LOOKAHEAD_SIZE];
?
? ?int windowPos = 0;
? ?int lookaheadPos = 0;
?
? ?// 初始化窗口和向前看緩沖區(qū)
? ?memset(window, 0, sizeof(window));
? ?fread(lookahead, 1, MAX_LOOKAHEAD_SIZE, input);
? ?int bytesRead = ftell(input);
?
? ?while (!feof(input)) {
? ? ? ?Match match;
?
? ? ? ?// 從壓縮文件讀取匹配信息
? ? ? ?fread(&match, sizeof(Match), 1, input);
?
? ? ? ?// 從窗口中復(fù)制匹配字符串到輸出文件
? ? ? ?for (int i = 0; i < match.length; ++i) {
? ? ? ? ? ?unsigned char ch = window[(windowPos - match.offset + i) % MAX_WINDOW_SIZE];
? ? ? ? ? ?fwrite(&ch, 1, 1, output);
? ? ? }
?
? ? ? ?// 寫(xiě)入下一個(gè)字符
? ? ? ?fwrite(&match.nextChar, 1, 1, output);
?
? ? ? ?// 更新窗口和向前看緩沖區(qū)
? ? ? ?for (int i = 0; i < match.length + 1; ++i) {
? ? ? ? ? ?window[windowPos] = match.nextChar;
? ? ? ? ? ?windowPos = (windowPos + 1) % MAX_WINDOW_SIZE;
? ? ? ? ? ?if (bytesRead > 0) {
? ? ? ? ? ? ? ?if (fread(lookahead, 1, 1, input) == 1) {
? ? ? ? ? ? ? ? ? ?bytesRead = ftell(input);
? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ?bytesRead = 0;
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? }
? }
?
? ?fclose(input);
? ?fclose(output);
}
?
int main() {
? ?const char* inputFile = "input.txt";
? ?const char* compressedFile = "compressed.bin";
? ?const char* decompressedFile = "decompressed.txt";
?
? ?// 壓縮文件
? ?compressFile(inputFile, compressedFile);
? ?printf("File compressed successfully.\n");
?
? ?// 解壓文件
? ?decompressFile(compressedFile, decompressedFile);
? ?printf("File decompressed successfully.\n");
?
? ?return 0;
}上面代碼里實(shí)現(xiàn)了LZ77壓縮和解壓算法。在壓縮過(guò)程中，通過(guò)讀取輸入文件并根據(jù)滑動(dòng)窗口中的匹配信息，將最長(zhǎng)匹配的偏移和長(zhǎng)度寫(xiě)入到輸出文件。在解壓過(guò)程中，從壓縮文件中讀取匹配信息，并根據(jù)偏移和長(zhǎng)度將匹配的字符串復(fù)制到輸出文件中。
以上就是C語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)的壓縮與解壓的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言數(shù)據(jù)壓縮與解壓的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)俄羅斯方塊，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-01-01
這篇文章主要為大家詳細(xì)介紹了OpenCV計(jì)算圖像的水平和垂直積分投影，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-12-12
這篇文章主要為大家總結(jié)了C++中輸入輸出流及文件流操作,具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-10-10
C語(yǔ)言可變參數(shù)與內(nèi)存管理超詳細(xì)講解
有時(shí)，您可能會(huì)碰到這樣的情況，您希望函數(shù)帶有可變數(shù)量的參數(shù)，而不是預(yù)定義數(shù)量的參數(shù)。C 語(yǔ)言為這種情況提供了一個(gè)解決方案，這篇文章主要介紹了C語(yǔ)言可變參數(shù)與內(nèi)存管理2023-01-01
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易五子棋小游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單五子棋小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-05-05
C++的靜態(tài)聯(lián)編和動(dòng)態(tài)聯(lián)編
本文闡述了靜態(tài)聯(lián)編和動(dòng)態(tài)聯(lián)編的概念和區(qū)別,通過(guò)具體實(shí)例分析了實(shí)現(xiàn)動(dòng)態(tài)聯(lián)編的條件,指出了虛函數(shù)是實(shí)現(xiàn)動(dòng)態(tài)聯(lián)編的基礎(chǔ)。2016-03-03
C語(yǔ)言循環(huán)鏈表實(shí)現(xiàn)貪吃蛇游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言循環(huán)鏈表實(shí)現(xiàn)貪吃蛇，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
C++實(shí)現(xiàn)四叉樹(shù)效果(附源碼下載)
這篇文章主要介紹了C++實(shí)現(xiàn)四叉樹(shù)效果(附源碼下載),非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2017-03-03
C語(yǔ)言每日練習(xí)之進(jìn)制轉(zhuǎn)換
這篇文章主要介紹了C語(yǔ)言進(jìn)制轉(zhuǎn)換，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-11-11
運(yùn)用指針在不用加號(hào)的情況進(jìn)行加法運(yùn)算的講解
今天小編就為大家分享一篇關(guān)于運(yùn)用指針在不用加號(hào)的情況進(jìn)行加法運(yùn)算的講解，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2019-01-01