GZIP压缩文件实现
做此项目需要掌握的知识
C：文件操作相关，例如：文件指针、打开文件、写入文件等
C++：模板、类、vector、string、C++11仿函数
数据结构：Huffman树、priority_queue(优先级队列)、堆
项目进行环境
vs2019 + Windows10
为什么要进行文件压缩？
目的是让文件变小，在传输和存储时都可以减少占用。
原理
此项目是基于LZ77和Huffman编码的文件压缩，LZ77算法(下面详细讲)是将重复的字段替换成<长度、距离>对，从而达到减少字符所占的空间，LZ77算法的最大问题时编码和字符不好区分，而且小于等于2字节的字符不值得用<长度、距离>对替换，此时利用Huffman树得到的编码，可以解决LZ77的缺陷，项目中的实现方式是：统计所有字符的出现次数，将出现次数越多的放在树靠上的位置，编码也就越短，反之放在树靠下的位置，编码越长。这样的编码在压缩时大多数情况会比等长编码更优，占用空间会更少。
压缩的时候首要根据每个字符出现的次数构造N个节点的二叉树森林，根据Huffman树的特点(下面详细讲)将森林构建成Huffman树，此时也就能得到Huffman编码，我们要存储这个编码，方便解压，同时还要保存源文件的格式、编码所占用的行数、编码后的数据。
LZ77原型(**<长度、距离>**对)
将重复出现的内容 替换成更短的<长度，距离>对
对重复出现的文字压缩
mnoabczxyuvwabc123456abczxydefgh
用**<长度、距离>**对的方式来替换
长度：重复文件所占的字节
距离：后文中重复出现词语首字节 与 前文中的重复词语的 字节差
压缩：monabczxyuvw==(3,9)123456(6,18)==defgh （真实存储时没有括号和逗号，这里是方便观看）
解压：用长度距离 去替换回来
缺点：
无法区分字符是替换后的编码还是原有的字符
字符<= 2字节 时 不值得去替换，因为替换完还是占用2字节
编码替换
根据LZ77的缺陷，我们想到了编码替换
等长编码
一个字节是8比特位
给每个字节找一个小于8比特位的编码，来替换文件中的字节。
文件：DDAB DDBC DBCD CDCC （16字节）
编码：A：00 B：01 C：10 D：11
压缩：11110001 11110110 11011011 10111010 （4字节）
解压：DDAB DDBC DBCD CDCC (查表解压)
优化：让出现次数少的编码长一点，让出现次数多的编码少一些
动态不等长编码
文件：DDAB DDBC DBCD CDCC DDD (19字节)
编码：A：100 B：101 C：11 D：0
解压：00100101 00101110 10111011 01111000 （4字节）
编码：此时编码从何而来？ —— Huffman树
Huffman树
特点
带权路径长度：二叉树的根节点到二叉树所有叶子节点的路径长度与相应权值乘积之和，
而huffman树的带权路径是最小的。
发现：权值大的靠近根，带权路径就越小。
如何创建Huffman树
先创建N个数的森林 例如：10 5 3 1
先在森林中获取两个权值最小的两个树 3、1 新节点的权值是这两个权值之和
将新的二叉树放回二叉树森林中 10 5 4
4 、5 = 9
9 、10 = 19
此时森林创建完成
Huffman编码如何获得
编码：从根节点到叶子经过的边。
假设：左边为0，右边为1，那么遍历边到叶子，也就得到了这个字符的编码
权值：字符对应节点内的数字是该节点的权值，也是该字符在文件中出现的次数
代码实现：压缩
文件
Common.h ：放头文件的 头文件
FileComperssHuffman.h：定义Huffman压缩文件的 头文件
HuffmanTree.hpp：定义和实现Huffman树
FileComperssHuffman.cpp：实现Huffman压缩
UaenaZioTest.cpp：main函数执行文件
1.实现Huffman树
a.定义树的每一个节点
首先要定义树的每个节点，节点中要记录（左孩子、右孩子、双亲、权值(出现的次数)）
HuffmanTree.hpp
#pragma once
#include <iostream>
#include <vector>
#include <queue>
template<class W>
struct HuffmanTreeNode
{
HuffmanTreeNode<W>* _left;
HuffmanTreeNode<W>* _right;
HuffmanTreeNode<W>* _parent;
W _weight;
HuffmanTreeNode(const W& weight = W())
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_weight(weight)
{}
};
构造函数 weight 给匿名对象W()，是为了在创建节点的时候可以使用无参构造，无参构造会调用初始化列表，来初始化无参构造的对象。
举例：
template<class W>
struct HuffmanTreeNode
{
HuffmanTreeNode<W>* _left;//左子树指针
HuffmanTreeNode<W>* _right;//右子树指针 指向的是ByetInfo的节点
HuffmanTreeNode<W>* _parent;//父节点，为了后面的逆向查找编码
W _weight;
①：HuffmanTreeNode(const W& weight)
②：HuffmanTreeNode(const W& weight = W())
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _weight(weight)
{}
};
int main()
{
HuffmanTreeNode<int>* p = new HuffmanTreeNode<int>();
//①：如果上面weight没有默认参数W()，则会报错，必须传入值才能构造。
//②：给了默认的匿名对象，则会调用初始化列表，初始化p指向的节点。
return 0;
}
template<class W>是类模板，W是模板参数，这样定义，在构造时，可以随意指定类型，而不用创建多个类型的 struct(结构体)。
b.定义树
HuffmanTree.hpp
template<class W>
class HuffmanTree
{
typedef HuffmanTreeNode<W> Node;
//仿函数——用来比较两个节点的权值，作为优先级队列的比较方法
//仿函数是C++11中出现的新规，大概意思是重载operator() 来实现这个类能像函数一样调用 。
class Compare
{
public:
bool operator()(const Node* x, const Node* y)
{
//大于号需要重载 下面会讲
return x->_weight > y->_weight;
}
};
public:
HuffmanTree()
: _root(nullptr)
{}
//vw是每个字符的权值,valid是无效值，为了比较vw出现次数为0 的无效字符
HuffmanTree(const std::vector<W>& vw,const W& valid)
{
//1.用所有的权值构造只有根节点的二叉树森林
//森林中二叉树应该使用堆(优先级队列)来保存
//小堆——优先级队列默认是大堆
//q是优先级队列，存储的是每一个字符组成的(struct)节点
//三个参数<函数指针、存储方式、比较方式>
//vector存储的是节点的地址，而比较的方法是Compare 是要用权值weight比较
std::priority_queue < Node*, std::vector<Node*>, Compare > q;
//遍历是为了拿到 每个权值，来构造Huffman数的每个节点，插入优先级队列，组成N个节点的二叉树森林
for (auto& e : vw)
{
//如果e和无效的权值比较，不想的的话 说明有效
//此时！=号需要重载
if (valid != e)
{
q.push(new Node(e));
}
}
//如果q里只剩下一个节点，那么说明树构建完成，因为q里是个森林
while (q.size() > 1)
{
//优先级队列通过刚才的比较，堆顶是最小的。
//取两个最小的节点 ，取完弹出，再取下一个
Node* left = q.top();
q.pop();
Node* right = q.top();
q.pop();
//新节点的权值是，刚才两个树的权值之和
//此时left和right的_weight是自定义类型，想要相加需要重载
//在谁里重载呢？
// left是node类型 node是 HuffmanTreeNode类型
//HuffmanTreeNode<W>* _left W是ByteInfo类型
//所以在ByteInfo中重载
Node* parent = new Node(left->_weight + right->_weight);
//新节点的左右子树是 刚才的两个节点
parent->_left = left;
left->_parent = parent;//记录父节点，方便后面逆向查找
parent->_right = right;
right->_parent = parent;
//最后将parent放入到二叉树森林中
q.push(parent);
}
//当队列中只剩下最后一个节点，那么这个节点就是Huffman树的根节点
_root = q.top();
}
//析构Huffman树
~HuffmanTree()
{
Destroy(_root);
}
//获取Huffman树的根节点
Node* GetRoot()
{
return _root;
}
private:
void Destroy(Node*& root)
{
//析构 root
if (root)
{
//递归析构左右子树
Destroy(root->_left);
Destroy(root->_right);
//然后delete根节点root，并且置空
delete root;
root = nullptr;
}
}
private:
Node* _root;//二叉树的根节点
};
此时Huffman树构造完成
测试Huffman树是否正确
void TestHuffmanTree()
{
std::vector<int> v{ 7,5,3,1 };
HuffmanTree<int> ht(v);
}
2.Huffman编码压缩过程
1.统计源文件中每个字节出现的次数
2.字节频次 来创建Huffman树
3.获取每个字节的Huffman编码
4.用得到的编码，对源文件的每一个字节来改写。
a. 定义节点声明
节点包括 字符、字符频次信息、字符编码
FileComperssHuffman.h
#pragma once
#include "HuffmanTree.hpp"
#include "Common.h"
#include <string>
#include <iostream>
using std::string;
//记录字符频次信息，通过字符频次构造 树，频次也就是每个树节点的权值
struct ByteInfo
{
uch _ch;//字节
size_t _appearCount;//字节的次数
std::string _chCode;//字符的编码
ByteInfo(size_t appearCount = 0)
:_appearCount(appearCount)
{}
//重载+号
//因为Node* parent = new Node(left->_weight + right->_weight);
ByteInfo operator+(const ByteInfo& other)const
{
return ByteInfo(_appearCount + other._appearCount);
}
//重载>号
//因为return x->_weight > y->_weight;
bool operator>(const ByteInfo& other)const
{
//只需要比较权值就可以了
return _appearCount > other._appearCount;
}
//重载！=号
//因为 if (invalid != e)
bool operator!=(const ByteInfo& other)const
{
return _appearCount != other._appearCount;
}
bool operator==(const ByteInfo& other)const
{
return _appearCount == other._appearCount;
}
}
b. 定义压缩类声明
FileComperssHuffman.h
//声明 ，定义在cpp中
class FileComperssHM
{
public:
//构造函数
FileComperssHM();
//压缩(文件路径)
void CompressFile(const string& filePath);
//解压缩(文件路径)
void UNCompressFile(const string& filePath);
//获取文件后缀
string GetFilePostFix(const string& filePath);
//读取一行
void GetLine(FILE* fIn, string& strInfo);
private:
//获取Huffman编码
void GenerateHuffmanCode(HuffmanTreeNode<ByteInfo>* root);
//填写头部文件信息
void WriteHeadInfo(const string& filePath,FILE* fOut);
//ByteInfo类型的数组 存储字节信息
std::vector<ByteInfo> _fileInfo;
};
c.构造函数实现
FileComperssHuffman.cpp
#include "FileComperssHuffman.h"
FileComperssHM::FileComperssHM()
{
//因为ByteInfo字节频次信息中的ch有
//_fileInfo是FCHM中定义的 ByteInfo类型的数组
//resize 扩容+初始化 扩容比已有数据少则会删除，不会改变空间大小
//reserve 扩容 只开空间
_fileInfo.resize(256);
for (int i = 0; i < 256; ++i)
{
//256个字符对应的ch赋值成对应的ASCII码
//根据ASCII码找到对应的字符，然后增加_appearCount（字符出现的次数）
_fileInfo[i]._ch = i;
}
}
d.压缩实现
1.统计字符出现次数
用数组记录一个char的大小，比并且将下标赋值成对应的ASCII码
再用读取到的字节 将 FileInfo[256] 中对应的字符(ASCII)的次数增加
因为fileinfo的类型是ByteInfo ，ByteInfo中存储的有字符、字符出现的次数、字符的编码
FileComperssHuffman.cpp
void FileComperssHM::CompressFile(const string& filePath)
{
//1.统计源文件中每个字符出现的次数
//fopen（文件路径，读取方式）
//c_str()将字符串以C的形式返回一个指向数组的指针，数组包含\0
//r是只读，文件必须存在， b是二进制读取
FILE* fIn = fopen(filePath.c_str(), "rb");
if (nullptr == fIn)
{
cout << "待压缩文件不存在" << endl;
return;
}
//一次读取1024字节
uch rdBuff[1024];
while (true)
{
//实际读取的大小size = 存储位置ptr，每个元素的大小size，一次读取1024大小count，从输入流的FILE中读取
size_t rdSize = fread(rdBuff, 1, 1024, fIn);
//循环读取，如果rdSize读取的是0，那说明文件读完了。
if (0 == rdSize)
break;
//统计次数
for (size_t i = 0; i < rdSize; ++i)
{
//rdBuff读取的第i个字符 的ASCII码 作为下标
//将刚才256个字符的数组对相应的 字符 的 字符出现次数进行++
_fileInfo[rdBuff[i]]._appearCount++;
}
}
2.用统计的结构创建Huffman树
FileComperssHuffman.cpp
void FileComperssHM::CompressFile(const string& filePath)
{
//2.用统计的结果创建Huffman树
//树的类型是 ByteInfo 类型节点 参数是（_fileInfo(ByteInfo类型数组) ，匿名对象 用作无效的对比）
HuffmanTree<ByteInfo> ht(_fileInfo, ByteInfo());
}
3.获取Huffman编码
a.重写一个函数定义获取编码
FileComperssHuffman.cpp
//获取节点编码
void FileComperssHM::GenerateHuffmanCode(HuffmanTreeNode<ByteInfo>* root)
{
if (nullptr == root)
return;
//递归的方法可以调用到所有的叶子节点
GenerateHuffmanCode(root->_left);
GenerateHuffmanCode(root->_right);
//root是叶子节点
if (nullptr == root->_left && nullptr == root->_right)
{
// root指针 指向类型是ByteInfo的_weight，_ch是ByteInfo节点中的字符，把_fileInfo[字符的ASCII码]中的chCode 保存到chCode，引用保存，也就是修改chCode就会修改_fileInfo对应字符的 编码
string& chCode = _fileInfo[root->_weight._ch]._chCode;
//定义两个指针cur指向叶子节点，parent记录cur的父亲，向上查找
HuffmanTreeNode<ByteInfo>* cur = root;
HuffmanTreeNode<ByteInfo>* parent= cur->_parent;
while (parent)
{
//如果cur是父亲的左孩子 则+0 否则是右孩子+1 编码遍历到根节点则得到编码
if (cur == parent->_left)
chCode += '0';
else
chCode += '1';
//cur等于父亲，父亲再向上走，
cur = parent;
parent = cur->_parent;
}
//编码是逆向得到 则需要逆置
reverse(chCode.begin(), chCode.end());
}
}
b.继续在压缩文件中 添加调用
FileComperssHuffman.cpp
void FileComperssHM::CompressFile(const string& filePath)
{
//3.获取Huffman编码
//Getroot() 获取Huffman树的根节点
GenerateHuffmanCode(ht.GetRoot());
}
4.写用来解压缩的数据
存储解压缩需要的 文件后缀、编码行数、编码
FileComperssHuffman.cpp
void FileComperssHM::CompressFile(const string& filePath)
{
//4.写用来解压缩的数据
//因为压缩后 会产生新的文件，所以再打开一个文件
FILE* fOut = fopen("file.hz", "wb");//w不会打开失败，没有则创建，有则清空
WriteHeadInfo(filePath, fOut);
}
存储 文件后缀、字符和字符出现的次数
void FileComperssHM::WriteHeadInfo(const string& filePath, FILE* fOut)
{
//1.获取源文件后缀 后换行
string headInfo;
headInfo += GetFilePostFix(filePath);
headInfo += '\n';
//2.构造频次信息
size_t appearLineCount = 0;//行数
string chInfo;//字符：字符频次信息
//遍历_fileInfo（存储字符的数组）
for (auto& e : _fileInfo)
{
//字节的出现频次 等于0 则不用计入
if (0 == e._appearCount)
continue;
//字符出现
chInfo += e._ch;//字符
chInfo += ':';//分隔符
chInfo += std::to_string(e._appearCount);//频次 int转string
chInfo += '\n';//换行 记录下一个频次信息
appearLineCount++;//字符频次信息行数++
}
headInfo += std::to_string(appearLineCount);//在文件后缀的基础上，写入频次信息总行数
headInfo += '\n';//换行
//C格式的源文件地址，每次1字节，总共个数，写入的文件指针
fwrite(headInfo.c_str(),1,headInfo.size(),fOut);//后缀和频次信息行数写入文件
fwrite(chInfo.c_str(), 1, chInfo.size(), fOut);//写入频次信息
}
获取源文件后缀 函数
string FileComperssHM::GetFilePostFix(const string& filePath)
{
//获取文件名filePath的后缀 substr返回pos位置向后len个字符 之后的字符串
//pos位置，len长度
return filePath.substr(filePath.find_last_of('.') + 1);
}
5.用获取到的编码对源文件改写
FileComperssHuffman.cpp
void FileComperssHM::CompressFile(const string& filePath)
{
//5.用获取到的编码对源文件进行改写
// (文件指针、偏移量、偏移量的基点) SEEK_SET是起始位置往后偏移0个位置
fseek(fIn, 0, SEEK_SET);//重置文件指针位置
//uch是unsigned char
uch bits = 0;//记录8bt，进行填充数据，满了则写入文件 然后重置
int bitCount = 0;//记录8比特是否存满
while (true)
{
//实际读取的大小size = 存储位置ptr，每个元素的大小size，一次读取1024大小count，从输入流的FILE中读取
size_t rdSize = fread(rdBuff, 1, 1024, fIn);
if (0 == rdSize)
break;
for (size_t i = 0; i < rdSize; ++i) //拿到每个字节(字符)
{
//拿到字符对应的编码
string& strCode = _fileInfo[rdBuff[i]]._chCode;
//遍历 编码 strCode.size()是编码的长度
for (size_t j = 0; j < strCode.size(); ++j)
{
bits <<= 1;//左移后 在后面写编码
//是1则 填充1 是0不用填充 左移相当于已经添加了0
if ('1' == strCode[j])
bits |= 1;
bitCount++;
if(8 == bitCount)
{
//fOut是压缩后的文件 的指针
fputc(bits, fOut);//写入文件
bits = 0;//置0
bitCount = 0;
}
}
}
}
//注意：最后一次bits中的8bt可能没有满，则没写进文件
if (bitCount > 0 && bitCount < 8)
{
//如果有5个有效位(在低位)，那么bitCount是5 ，则左移3次就移动到了高位
bits <<= (8 - bitCount);
fputc(bits, fOut);//写入文件
//最后一个字符是8比特 ，解压时会不会多解压？ 不会 我们判断解压出的字符是否和树根节点的权值相同 下面会讲
}
fclose(fIn);
fclose(fOut);
}
代码实现：解压缩
1.读取解压缩需要用到的信息
FileComperssHuffman.cpp
void FileComperssHM::UNCompressFile(const string& filePath)
{ //传进来的文件名
//检查文件格式 获取后缀
if (GetFilePostFix(filePath) != "hz")
{
cout << "压缩文件格式不对" <<endl;
return;
}
//1.读取解压缩需要用到的信息
//fIn是压缩后的文件指针 读取解压缩的信息
FILE* fIn = fopen(filePath.c_str(), "rb");
if (nullptr == fIn)
{
cout << "解压缩文件路径不对" << endl;
return;
}
//a.读取源文件后缀
string unCompressFile("UNfile.");//定义解压后的文件名
string strInfo;//定义接收后缀的对象
//函数在下面实现
GetLine(fIn, strInfo);//从fIn(解压后的文件指针)中获取后缀存到 strInfo中
unCompressFile += strInfo; //拼接到文件名后面
//b.读取频次信息总行数
strInfo = "";//清空
GetLine(fIn, strInfo);//继续读 存到strInfo
size_t lineCount = atoi(strInfo.c_str()); //字符串转数字拿到 频次
for (size_t i = 0; i < lineCount; ++i)
{
//注意：换行需要特殊处理
strInfo = "";//清空
GetLine(fIn, strInfo);//读取 “：”
//如果源文件有换行 读到的是空 ，那么读到的就是换行
if ("" == strInfo)
{
//把换行加进去，然后再读一次
//因为换行的信息存储样式是
//
//：8 也就是再读一次才能读到换行的频次信息
strInfo += '\n';
GetLine(fIn, strInfo);
}
//A:1 -->_fileInfo
uch ch = strInfo[0];//0的位置是A
_fileInfo[ch]._ch = ch; //放到字符数组的映射位置
//出现的次数 放在对应字符的 频次信息中，+2是 数字起始位置 A一个：一个
_fileInfo[ch]._appearCount = atoi(strInfo.c_str() + 2);
}
//读一行数据
void FileComperssHM::GetLine(FILE* fIn, string& strInfo)
{
while (!feof(fIn)) //feof检查fIn是否结束 ，如果没结束则继续
{
char ch = fgetc(fIn); //fgetc读取 解压缩信息
if (ch == '\n') //读到换行截止 也就是读一行
break;
strInfo += ch;
}
}
2.还原huffman树
FileComperssHuffman.cpp
void FileComperssHM::UNCompressFile(const string& filePath)
{ //传进来的文件名
//2.还原huffman树 刚才实现了
HuffmanTree<ByteInfo> ht(_fileInfo, ByteInfo());
}
3.解压缩
FileComperssHuffman.cpp
1.读取字节
2.遍历比特位的高位，根据比特位是1或0 遍历树向左或向右走，直到走到叶子
3.遍历到根则输出字符
void FileComperssHM::UNCompressFile(const string& filePath)
{ //传进来的文件名
//3.解压缩
//解压缩文件的指针，存储解压后的文件信息
FILE* fOut = fopen(unCompressFile.c_str(), "wb");
uch rdBuff[1024]; //存储解压缩信息
//遍历树 root节点的指针
HuffmanTreeNode<ByteInfo>* cur = ht.GetRoot();
size_t fileSize = 0;//记录字符的个数，判断是否解压完成
while (true)
{
//存储读到的信息，每次1字节，共1024字节，从fIn中读取 (fIn是解压缩信息)
size_t rdSize = fread(rdBuff, 1, 1024, fIn);
if (0 == rdSize)//等于0 说明读完了
break;
for (size_t i = 0; i < rdSize; ++i)
{
char ch = rdBuff[i];//读一个字节的字符
for (int j = 0; j < 8; ++j)//遍历8比特位
{
//80 是1000 0000 或完如果是1 则往右走遍历树
if (ch & 0x80)//检测最高位是0或1
cur = cur->_right;
else
cur = cur->_left;//是0往左走
//检测完一个比特位后左移 当 = 8的时候就会结束 然后继续i++读取下一个字节
ch <<= 1;
//走到叶子节点后 往文件中写，不是则不进去继续往后走
if(nullptr == cur->_left && nullptr == cur->_right)
{
//将weight节点里的字符ch 写到文件中
fputc(cur->_weight._ch, fOut);
cur = ht.GetRoot();//重置cur的位置
fileSize += 1;//每次解压一个字符则++
//当解压次数与 root根节点的权值相等时，则解压完成，因为根节点存的权值与字符的个数相等
if (fileSize == cur->_weight._appearCount)
break;
}
}
}
}
//关闭文件
fclose(fIn);
fclose(fOut);
}
遇到的问题
1.换行
换行特殊处理就好了
2.文字
文字的ASCII码是负数，不能作为下标 将char改为 unsigned char解决
3.读到FF结束了，没解压完成
用二进制方式读取文件 在r 或w后面加上d 则以二进制(内存)读取存储
r是文本方式
rb是二进制格式
main函数执行
#define _CRT_SECURE_NO_WARNINGS 1
#include "FileComperssHuffman.h"
void menu()//菜单
{
cout << "***********************" << endl;
cout << "*** 0.exit ***" << endl;
cout << "*** 1.huffman压缩 ***" << endl;
cout << "*** 2.huffman解压缩 ***" << endl;
cout << "***********************" << endl;
}
int main()
{
FileComperssHM fc;
int input = 0;//接收输入的指令
bool isQust = false;//记录是否结束指令
string fileName;
while (true)
{
menu();
cin >> input;
switch (input)
{
case 0:
isQust = true;
cout << "已经退出\n";
break;
case 1:
cout << "输入压缩文件名称>";
cin >> fileName;
fc.CompressFile(fileName);
cout << "(*^▽^*)压缩完成\n";
break;
case 2:
cout << "输入解压缩文件名称>";
cin >> fileName;
fc.UNCompressFile(fileName);
cout << "(*^▽^*)解压缩完成\n";
break;
}
if (isQust)
break;
}
//fc.CompressFile("file.txt");
//fc.UNCompressFile("file.hz");
return 0;
}