C語言實(shí)現(xiàn)數(shù)據(jù)的壓縮與解壓
一、壓縮與解壓介紹
數(shù)據(jù)壓縮是通過一系列的算法和技術(shù)將原始數(shù)據(jù)轉(zhuǎn)換為更緊湊的表示形式，以減少數(shù)據(jù)占用的存儲(chǔ)空間。數(shù)據(jù)解壓縮則是將壓縮后的數(shù)據(jù)恢復(fù)到原始的表示形式。
數(shù)據(jù)可以被壓縮打包并減少空間占用的原因有以下幾個(gè)方面：
（1）無效數(shù)據(jù)的消除：在數(shù)據(jù)中可能存在大量冗余、重復(fù)或無效的信息。壓縮算法可以通過識(shí)別和移除這些無效數(shù)據(jù)，從而減小數(shù)據(jù)的大小。
（2）統(tǒng)計(jì)特性的利用：數(shù)據(jù)通常具有某種統(tǒng)計(jì)特性，例如頻繁出現(xiàn)的模式、重復(fù)的字節(jié)序列等。壓縮算法可以利用這些統(tǒng)計(jì)特性來編碼數(shù)據(jù)，從而達(dá)到更高的壓縮比率。
（3）信息編碼：壓縮算法使用不同的編碼方式來表示源數(shù)據(jù)，在保證數(shù)據(jù)可還原的前提下，使用更少的位數(shù)來表示信息。例如，Huffman編碼、LZW編碼等。
常見的應(yīng)用場景中會(huì)使用到數(shù)據(jù)壓縮和解壓功能，例如：
（1）存儲(chǔ)媒體：在硬盤、閃存等存儲(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ǔ)和傳輸。這在文件傳輸、備份和歸檔中非常常見。
（4）多媒體編碼：音頻、圖像、視頻等多媒體數(shù)據(jù)往往具有較高的冗余性，壓縮算法可以大幅減小文件大小，例如MP3、JPEG、H.264等壓縮算法。
二、ZIP格式介紹
ZIP是一種常見的文件壓縮格式，它使用DEFLATE算法來進(jìn)行數(shù)據(jù)壓縮。
下面是ZIP壓縮的基本原理：
（1）文件分塊：ZIP壓縮將要壓縮的文件按照一定大小的塊進(jìn)行劃分。每個(gè)塊通常包含多個(gè)字節(jié)，并且可以獨(dú)立地進(jìn)行壓縮處理。
（2）壓縮算法：對(duì)于每個(gè)塊，ZIP使用DEFLATE算法進(jìn)行壓縮。DEFLATE是一種無損的壓縮算法，它結(jié)合了LZ77算法和霍夫曼編碼，可以有效地消除冗余并提高壓縮比率。
- LZ77算法：遍歷輸入數(shù)據(jù)，尋找重復(fù)的模式（前綴）并使用指針來表示。通過將重復(fù)的模式替換為指針，可以達(dá)到數(shù)據(jù)壓縮的效果。
- 霍夫曼編碼：利用字符出現(xiàn)的頻率來設(shè)計(jì)一種更緊湊的編碼方式。頻率較高的字符使用較短的編碼，頻率較低的字符使用較長的編碼。
（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è)文件的名稱、壓縮前后的大小、壓縮方法等信息。
- 文件索引：全局文件目錄還包含一個(gè)索引表，指明每個(gè)文件的起始位置和塊的偏移量。通過索引表，可以快速定位并解壓指定的文件塊。
（5）壓縮率：ZIP壓縮的效果取決于輸入文件的特性和DEFLATE算法的實(shí)現(xiàn)。通常情況下，文本文件和重復(fù)性較高的內(nèi)容可以獲得更高的壓縮比率，而二進(jìn)制文件和已經(jīng)過壓縮的文件（如JPEG圖像）則可能無法再次獲得顯著的壓縮。
ZIP壓縮的好處是它廣泛支持，并且可在各種操作系統(tǒng)和平臺(tái)上使用。ZIP格式支持密碼保護(hù)、文件夾結(jié)構(gòu)、注釋等功能，使其成為一種常用的壓縮格式。
三、C語言實(shí)現(xiàn)壓縮和解壓算法
3.1 代碼框架
下面是使用C語言實(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)容壓縮，并寫入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)容解壓，并寫入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;
}上述代碼只是用于說明基本思路，并未實(shí)現(xiàn)具體的壓縮算法。需要在compressFile和decompressFile函數(shù)中實(shí)現(xiàn)實(shí)際的壓縮和解壓算法邏輯。
在compressFile函數(shù)中，打開輸入文件（例如input.txt），讀取文件內(nèi)容并進(jìn)行壓縮處理，最后將壓縮后的數(shù)據(jù)寫入到輸出文件（例如compressed.bin）中。
在decompressFile函數(shù)中，打開壓縮文件（例如compressed.bin），讀取壓縮數(shù)據(jù)并進(jìn)行解壓處理，最后將解壓后的數(shù)據(jù)寫入到輸出文件（例如decompressed.txt）中。
可以選擇使用現(xiàn)成的壓縮算法庫，如zlib、gzip等，或者自行實(shí)現(xiàn)一種簡單的壓縮算法（例如LZ77）。
下面章節(jié)介紹使用LZ77算法實(shí)現(xiàn)壓縮解壓。
3.2 完整的實(shí)現(xiàn)
LZ77（Lempel-Ziv-Welch 1977）是一種基于字典的無損數(shù)據(jù)壓縮算法，常用于文件壓縮和網(wǎng)絡(luò)傳輸中。通過利用數(shù)據(jù)中的重復(fù)片段來實(shí)現(xiàn)壓縮，并且可以實(shí)現(xiàn)逐步的解壓縮。
LZ77算法的核心思想是使用一個(gè)滑動(dòng)窗口和一個(gè)向前看緩沖區(qū)來尋找重復(fù)出現(xiàn)的字符串。算法從輸入數(shù)據(jù)的開頭開始，逐步讀取數(shù)據(jù)并嘗試匹配滑動(dòng)窗口中已經(jīng)出現(xiàn)過的字符串，如果找到匹配的字符串，就將其表示為（偏移，長度）的形式，并且在輸出中只保留沒有匹配的字符，然后向前滑動(dòng)窗口和向前看緩沖區(qū)，繼續(xù)下一輪匹配。如果沒有找到匹配的字符串，則將當(dāng)前字符作為新的字符串添加到滑動(dòng)窗口，并輸出它。
下面是LZ77算法的詳細(xì)步驟：
（1）初始化滑動(dòng)窗口和向前看緩沖區(qū)。
（2）從輸入數(shù)據(jù)中讀取一個(gè)字符作為當(dāng)前字符。
（3）在滑動(dòng)窗口中查找最長的匹配字符串，該字符串與向前看緩沖區(qū)中的部分或全部字符匹配。如果有多個(gè)匹配字符串具有相同的長度，選擇最靠近滑動(dòng)窗口末尾的字符串。
（4）如果找到匹配字符串：
- 記錄該匹配字符串的偏移（滑動(dò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)是簡單易懂，實(shí)現(xiàn)相對(duì)容易，并且可以提供不錯(cuò)的壓縮率。它也有一些限制，例如在處理長重復(fù)字符串時(shí)效率較低，并且可能會(huì)導(dǎo)致壓縮結(jié)果略微變大。為了克服這些限制，通常會(huì)結(jié)合其他壓縮算法（如Huffman編碼）來進(jìn)一步壓縮LZ77的輸出結(jié)果，以獲得更好的壓縮效果。
下面使用C語言自行實(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; ?// 匹配字符串的長度
? ?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]};
?
? ? ? ?// 在窗口中查找最長匹配
? ? ? ?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];
? ? ? ? ? }
? ? ? }
?
? ? ? ?// 寫入最長匹配的偏移和長度
? ? ? ?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);
? ? ? }
?
? ? ? ?// 寫入下一個(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壓縮和解壓算法。在壓縮過程中，通過讀取輸入文件并根據(jù)滑動(dòng)窗口中的匹配信息，將最長匹配的偏移和長度寫入到輸出文件。在解壓過程中，從壓縮文件中讀取匹配信息，并根據(jù)偏移和長度將匹配的字符串復(fù)制到輸出文件中。
以上就是C語言實(shí)現(xiàn)數(shù)據(jù)的壓縮與解壓的詳細(xì)內(nèi)容，更多關(guān)于C語言數(shù)據(jù)壓縮與解壓的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C語言中strcpy()函數(shù)的具體實(shí)現(xiàn)及注意事項(xiàng)
C語言庫函數(shù)char *strcpy(char *dest, const char *src)把src所指向的字符串復(fù)制到dest,下面這篇文章主要給大家介紹了關(guān)于C語言中strcpy()函數(shù)的具體實(shí)現(xiàn)及注意事項(xiàng)的相關(guān)資料,需要的朋友可以參考下2022-11-11
C++實(shí)現(xiàn)LeetCode(768.可排序的最大塊數(shù)之二)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(768.可排序的最大塊數(shù)之二),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++ 回調(diào)接口設(shè)計(jì)和二進(jìn)制兼容詳細(xì)
再開發(fā)視頻編輯 SDK，SDK的回調(diào)接口設(shè)計(jì)成 C 風(fēng)格，結(jié)構(gòu)中放著一些函數(shù)指針,既然對(duì)外接口是 C++，為什么不直接使用 C++ 的虛函數(shù)？這篇文章便對(duì)這一問題做個(gè)詳細(xì)介紹,需要的朋友可以參考一下2021-09-09
以下是分別是對(duì)new和malloc的區(qū)別進(jìn)行了詳細(xì)的分析及介紹，需要的朋友可以過來參考下2013-09-09
Qt利用QDrag實(shí)現(xiàn)拖拽拼圖功能詳解
QDrag類為MIME-based拖拽數(shù)據(jù)轉(zhuǎn)換提供支持。本文為大家主要介紹如何利用QDrag類實(shí)現(xiàn)拖拽拼圖功能。左邊是打散的圖，拖動(dòng)到右邊進(jìn)行復(fù)現(xiàn)，此外程序還支持手動(dòng)拖入原圖片，感興趣的可以了解一下2022-07-07
C語言的常量,字符串,轉(zhuǎn)義字符,注釋你都了解嗎
這篇文章主要為大家詳細(xì)介紹了C語言的常量,字符串,轉(zhuǎn)義字符,注釋，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
VC++實(shí)現(xiàn)添加文件關(guān)聯(lián)的方法示例
這篇文章主要介紹了VC++實(shí)現(xiàn)添加文件關(guān)聯(lián)的方法,涉及VC++針對(duì)注冊(cè)表的寫入與VC事件響應(yīng)相關(guān)操作技巧,需要的朋友可以參考下2017-08-08
函數(shù)指針是一個(gè)指針變量,它可以存儲(chǔ)函數(shù)的地址,然后使用函數(shù)指針,下面這篇文章主要給大家介紹了關(guān)于C語言進(jìn)階教程之函數(shù)指針的相關(guān)資料,需要的朋友可以參考下2022-04-04
C語言中交換int型變量的值及轉(zhuǎn)換為字符數(shù)組的方法
這篇文章主要介紹了C語言中交換int型變量的值及轉(zhuǎn)換為字符數(shù)組的方法,講解了以不同進(jìn)制將整型數(shù)字轉(zhuǎn)換成字符數(shù)組,需要的朋友可以參考下2016-04-04
這篇文章主要介紹了C++純虛函數(shù)與抽象類的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)c++，感興趣的朋友可以了解下2020-08-08