目录
2.两者都从实际对于二进制文件的压缩来看两者都对于二进制文件的压缩效果较差。
2.1首先我们面临一个问题那么就是GZIP是否就是先进行LZ77压缩然后再用Huffman压缩进一步对于LZ77的结果来进行压缩呢？
2.2将原字符和长度放在同一颗Huffman树中压缩如何区别两者？
1.Huffman压缩和LZ77压缩的对比
1.Huffman压缩和LZ77压缩的本质：
- Huffman压缩就是对字符出现的次数进行统计，对于出现次数多的字符重新编码为较短的编码，对于出现出次数较少的字符编码为较长的编码。然后对文件中的每个字符进行改写，替换为我们对应的编码信息。
- LZ77就是将文本中在前文出现的字符串在后文中替换为更短的长度距离对来表示，用长度距离对来表示重复出现的字符串，然后再解压缩的时候遇到长度距离对通过长度距离对来在前文中查找字符串。这里会额外开销：有记录当前压缩文件中的字符是否是长度距离对的标志位。
2.两者都从实际对于二进制文件的压缩来看两者都对于二进制文件的压缩效果较差。
- 1.对于Huffman压缩二进制文件来说：字符种类越多那么字符编码位数越接近，字符种类越多那么huffman的树越大，树越大那么编码位数越多，二进制格式的文件中，字符种类比较多，而且平均所以字符的编码位数接近而且Huffman树较大。因为Huffman压缩本质上就是将出现次数多的字符编码为更少的bit位，用少量bit位来表示。而出现次数多的字符用较多bit位来表示，以对文件达到压缩目的，那么这里当每个字符的出现次数接近那么导致Huffman树较大就会导致编码效果较差。
- 2.而对于LZ77来说：一般文本文件中字符串出现的重复较多那么用长度距离对来表示就会起到很好的压缩效果，但是二进制文件中都是不规律的二进制组成的字符，那么字符种类的分布和字符重复出现的次数就较少，而LZ77还有额外的标志位开销，这些标志位信息就差不多占了原文件大小的1/8。
2.GZIP就是对于LZ77和Huffman的结合
2.1首先我们面临一个问题那么就是GZIP是否就是先进行LZ77压缩然后再用Huffman压缩进一步对于LZ77的结果来进行压缩呢？
可以这样做，但是不合理，通过LZ77的压缩之后有1/8的字符是标记位，然后加上LZ77的压缩结果本身就大，那么两个结果加起来再采用Huffman压缩的时候就会导致Huffman树非常大，那么导致每个字符的编码位数过长然后导致结果越压越大。那么这里GZIP是如何解决的呢？GZIP这里通过将长度放在一棵树中压缩，将距离和原字符放在另一棵树中压缩，早在我们研究LZ77表示长度的时候我们就说明了为什么LZ77表示的长度的字节是1个字节除了局部原理性之外就是当前的原因，GZIP中长度要和原字符放到同一颗Huffman树种压缩，因为这里的原字节和长度都是一个字节。而距离是两个字节所以我们要放在另一颗树中压缩。
2.2将原字符和长度放在同一颗Huffman树中压缩如何区别两者？
这里我们又遇到了这个问题，我们在LZ77当中是采用标志位的方式来区别到底是原字符还是标志位，但是在GZIP中肯定不是用这么lou的方式，高低整点不一样的，这里在GZIP在压缩的时候统一将LZ77中求出来的长度偏移257个字节，那么这里我们就用0-255来表示原字符（这里突然想到ASII码表中一共就0-127那么128-255用来代表什么呢？这里其实用来表示汉字，因为汉字占两个字符来长度而且汉字用一个字符来表示的时候都是负数，那么在无符号char类型中这些负数的范围就是在128-255范围内所以这里的128-255用来表示汉字），用257-512来表示长度因为长度的范围为0-255，如果了解LZ77的都知道LZ77的长度表示范围是3-258那么这里为啥只用257-512来表示，这是因为Huffman压缩只处理LZ77中处理后的结果，这里在LZ77中就已经将长度都减去3了，那么这里只需要压缩即可，在解压的时候再将数据都+3。这样我们就不用处理标志位了。那么这里如果读取到数字范围是0-127那么就直接写入压缩文件中。如果是长度那么就读取相应的距离。
2.3Huffman树过于大的问题
对于上面我们将距离放在一棵树中压缩，将长度和原字符放在另一棵树中压缩，那么我们假设所有长度和字符都出现而且所有的距离也都出现，那么对于保存长度字符的Huffman树来说最大就有513个叶子节点那么对于距离Huffman树就最大又32767个叶子节点这无疑是一个大的数据，对于创作LZ77的作者所处的年代来说计算机内存可能无法创建这么大的树。
解决方式：
解决距离压缩的分组编码：这里对于距离在Huffman树中的编码于是大佬就想到一种方式那就是将距离段分组将其分为30个组。每个距离段有一个编码code那么我们只需要先找到当前的距离的分组在Huffman中的编码，然后将当前的编码写入到压缩文件中去，然后将当前的距离在编码对应的范围内的偏移量也（表格当中的bits）也写入到文件当中。那么我们在解压缩读取的时候就可以先读取分组编码然后读取相应的偏移量然后再分组当中找到具体的距离。这样我们构建的距离Huffman树就只有30个叶子节点大小。（分组中距离个数为2的幂次方个数）
注意：这里上面的偏移量（bits）是代表偏移量位数，也就是一共用多少个bit位来表示偏移量例如：
解决长度压缩的分组编码：上面既然已经对于距离进行了分组那么下面我们也可以对于距离进行分组，这里GZIP对于距离分为了29个分组，同样和上面的分组计算方式相同，这里将范围内的长度进行Huffman树编码压缩写入压缩文件，然后将偏移量也写入文件当中，这里对于原字符是不进行压缩的，所以这里Huffman树中叶子节点的个数一共只有255+1+29=285个。
2.4对于Huffman树的优化--范式Huffman树
这里我们在GZIP压缩中其实并不是采用的是传统Huffman而是采用范式Huffman树来进行压缩，我们在压缩文件的时候就不是保存的字符频次信息了而是的保存各个字节对应的码字长度(huffffman压缩中保存的是符号及符号出现的频率。）我们来介绍一下范式Huffman树。
对于范式Huffman树的编码规则：
范式Huffman树是从Huffman树演变而来的，通过统计每个字符在Huffman树中的编码位长我们就可以得到范式Huffman树的编码，范式Huffman树通过每个符号的编码码位长来分层，将编码位长相同的字符分在同一层，每一层的字符再按照字典顺序排序，后面的字符由前面字符+1得到。那么我们就要知道每一层的首位字符的编码，编码位长最短的一层的首字符的编码为全0。然后通过以下公式计算就可以得到每一层的首位编码。
范式Huffman树的好处：
1.编码获取的速度快
原来我们要获取一个字符的编码需要遍历Huffman树但是这里只需要通过上面那个小算法就可以直接获取字符的编码。这里我们在采用范式Huffman树获取编码位长的时候其实只需要每个字符的编码位长信息，那么获取编码位长信息只需要将Huffman树构建出来，然后再遍历Huffman树，获取每个元素的编码位长存储到buf中，那么我们就可以得到每个字符的编码位长然后对他们进行排序得到范式Huffman编码表，那么我们就可以通过算法来获取到每个元素的编码。而不是像传统的Huffman树获取每个字符的编码只能通过遍历Huffman树的方式来获取。
2.压缩结果中
直接保存编码位长，我们在压缩文件的时候就不是保存的字符频次信息了而是的保存各个字节对应的码字长度。
3.解压缩的时候就不需要还原Huffman树了
2.5范式Huffman树的解码
原来我们普通的Huffman树解码的时候需要将Huffman树来进行还原，但是我们的范式Huffman树在解码的时候是不需要还原Huffman树的直接采用一个小算法就可以对Huffman树来进行还原了。这里我们在还原范式Huffman树的时候需要两张表，一张符号位长表，一张解码表。
我们来具体实现一下解码的过程
- 循环进行以下操作，直到所有的比特流解析完成：设i=0
- 1. 从解码表的第i行开始，根据编码位长从压缩数据比特流中获取相应长度的比特位。
- 2. 将读取的数据与首编码相减，假设结果为num
- 3. 如果num>=符号数量，i++，继续1，如果num小于符号数量，进行4
- 4. 将符号索引加上num，用该结果从符号位长表对应位置解析出该符号
- 例如，输入数据“11110”。令i = 0，此时编码位长为2。读取2位的数据“11”与首编码相减等于3。3大于等于符号数量，于是i = i + 1等于1。此时编码位长为3。读取3位的数据“111”与首编码相减等于1。1大于等于符号数量，于是i = i + 1等于2。此时编码位长为5。读取5位的数据“11110”与首编码相减等于2。2小于符号数量，2加符号索引4等于6。从表2.3中可以查到序号为6的符号是“E”。从而解码出符号“E”。跳过当前已经解码的5位数据，可以重新开始解码下一个符号。相信通过这个例子你就已经可以理解范式Huffman树的解码过程了，那么这里我们来解读一下原理。
原理：我们统计解码表的时候解码表的排序是以编码位长为第一字段来编码的就是统计当前编码位长的数据有多少个，那么我们在读取数据的时候先读取解码表第一行的编码位长个数据进来，那么此时我们可以将读取进来的数据和当前编码位长的首位编码相减，那么我们就可以得到当前编码长度的元素个数如果次数元素个数大于或等于当前编码长度的元素的个数那么我们就再读取下一个编码长度的与当前编码长度相减的长度，这里这样做是因为当前的编码都是由上一个编码长度的首位编码左移编码长度差而来那么当前编码长度的编码一定是大于前一个编码长度的编码的。那么我们接下来再读取当前编码长度和下一个编码长度差的bit位来进行循环如下步骤就最后就可以得到解码。这里的符号索引是由上一个编码位长的符号数量和符号索引相加而来，到时候通过符号索引去符号长度表中偏移相应的数量就可以得到相应的解码字符。这里偏移其实也用到了上面分组然后偏移的思想。通过符号索引找到当前编码位长的首位编码，然后再通过当前编码减去当前编码长度的首位编码从而得到当前编码的在当前符号表中的偏移量从而计算得出符号。
2.6分块压缩
再GZIP中采用Huffman压缩并不是采取的直接将LZ77压缩后的数据直接进行压缩的，而是分块进行压缩的，当将LZ77压缩好的数据分为多个小块来进行压缩，用我们上面的原字符和长度中间的第256位来表示当前块是否为最后一个块如果当前块结束标志位为1的话那么就代表当前压缩的块不是LZ77的最后一个块，如果为0的话那么代表当前压缩的块是LZ77压缩文件的最后一个块。
3.GZIP的模拟实现
GZIP的压缩的本质其实就是将LZ77对文件的压缩结果再经过Huffman进行压缩从而使得文件减小，但是却不可以直接将LZ77的压缩结果进行Huffman压缩，因为直接进行Huffman压缩的话LZ77压缩文件的内容较多那么会导致Huffman树过大，那么就会使得每个字符的编码位数变长，而Huffman压缩最根本的就是要通过较少的编码来表示一个字符从而达到压缩文件的效果。
这里我们给出压缩和解压缩的思维导图只要按照步骤就可以实现ZIP压缩。
如下是GZIP的模拟实现代码（这里看着多其实有多个文件是原来实现LZ77和Huffman文件压缩的代码，重点关注<wbxzip.cpp>和<wbxzip.h>文件）：
<common.h>//文件
#pragma once
#include<iostream>
#include<string>
#include<vector>
#include<assert.h>
#include<map>
//用来重命名要在工程中用到的类型和定义常量
using std::cout;
using std::endl;
using std::cin;
using std::string;
using std::vector;
using std::map;
typedef unsigned char uch;
typedef unsigned short ush;
typedef unsigned long long ull;
typedef unsigned int uint;
//加上static防止多个文件同时包含而导致变量重复定义
static const int MAX_ATHCH = 258;//最大匹配长度
static const int MIN_MATCH = 3;//最小匹配长度
static const ush WSIZE = 32 * 1024;//窗口大小
static const ush MIN_LOOKAHEAD = MIN_MATCH + MAX_ATHCH + 1;//先行缓冲区至少要预留长度
static const ush MAX_DIST = WSIZE - MIN_LOOKAHEAD;//查找缓冲区最大距离：向左侧查找的最远距离。
//读取文件中一行的字符：
void get_line(string& buf, FILE* fpread);
<file_compress_huffman.h>//文件
#pragma once
#include<string>
#include<vector>
#include"common.h"
//当前的头文件用来放置huffman文件编码类的头文件
using namespace std;
//用一个结构体来保存每个字符的信息：
struct byteinfo
{
uch _ch;//代表字符
size_t _appear_count;
string _ch_code;//当前字符的所用的编码
byteinfo(size_t appear_count = 0)
:_appear_count(appear_count)
{}
//因为在构造哈夫曼树要建堆那么我们就需要比较，那么就要提供我们自定义结构体的比较符号重载：
bool operator>(const byteinfo& b)const
{
return _appear_count > b._appear_count;
}
bool operator<(const byteinfo& b)const
{
return _appear_count < b._appear_count;
}
bool operator==(const byteinfo& b)const
{
return _appear_count == b._appear_count;
}
bool operator!=(const byteinfo& b)const
{
return _appear_count != b._appear_count;
}
//在构造huffman树时候中途要构造新树那么新树的根节点的权值是两个子树根节点的权值的和，那么就要将两个
//节点相加那么就要重载+号：
byteinfo operator+(const byteinfo& b)
{
//这里我们重载+只需要关注它的出现次数即可不需要关心其他因为我们构造huffman树的时候是用频次来构造
//而且最终我们用的只是叶子节点。所以我们这里只需要返回相加之后正确的出现频次即可
return byteinfo(_appear_count + b._appear_count);
}
};
class file_compress_huffman
{
public:
file_compress_huffman();
void compress_file(const string& file_name);//压缩
void un_compress_file(const string& file_name);//解压缩
string get_file_name(const string& file_name);//获取文件名
string get_postfix(const string& file_name);//获取文件后缀
private:
void write_head_info(const string& file_path, FILE* fout); //用来向压缩文件中写入头部信息：
vector<byteinfo> _fileinfo;//用来存放文件中的每个字符的信息
};<HashTable.h>//文件
#pragma once
#include "common.h"
//哈希表：底层维护的两个空间一个是存储当前字符下标的head指向的空间，另一个是存储哈希冲突的空间
//prev指向的空间。
class HashTable
{
public:
HashTable();
~HashTable();
//插入：
void InsertString(ush& hashAddr, uch ch, ush pos, ush& macthHead);
//获取前一个匹配串
ush GetPrevMatch(ush &MathcHead);
//更新哈希表：
void updatahash();
private:
//哈希函数：
void HashFunc(ush& hashAddr, uch ch);
ush H_SHIFT();
ush* _prev;
ush* _head;
// 哈希桶的个数为2^15=32*1024:就是head或者prev空间的大小
const ush HASH_BITS = 15;
// 哈希表的大小=32K
const ush HASH_SIZE = (1 << HASH_BITS);
// 哈希掩码：主要作用是将右窗数据往左窗搬移时，用来更新哈希表中数据
//当文件超过32k才会用到
const ush HASH_MASK = HASH_SIZE - 1;
};<huffman_tree.hpp>//文件
#pragma once
#if 1
#include<iostream>
#include<vector>
#include<queue>
#include<initializer_list>
using namespace std;
//实现哈夫曼树：
//1.首先用优先级队列来存储只有根节点的二叉树森林每颗二叉树只有一个带权的根节点左右孩子都为空。
//2.在优先级队列队列中把根节点权值最小的两颗二叉树作为左右子树来构造一颗新的二叉树，新的二叉树根节点的
//权值为两棵树根节点权值之和。然后将新的二叉树的根节点再放回到优先级队列中。
//3.重复上面的步骤就可以得到哈夫曼树了。
template<class T>
struct huffman_tree_node
{
huffman_tree_node(T weight)
:_right(nullptr)
, _left(nullptr)
, _weight(weight)
{}
huffman_tree_node(huffman_tree_node<T>* left = nullptr, huffman_tree_node<T>* right = nullptr, T weight = T())
:_left(left)
, _right(right)
, _weight(weight)
{}
huffman_tree_node<T>* _left;
huffman_tree_node<T>* _right;
T _weight;
};
template<class T>
class huffman_tree
{
public:
typedef huffman_tree_node<T> node;
class compare
{//创建小堆要提供大于的比较方式：
public:
bool operator()(const node* a, const node* b)
{
return a->_weight > b->_weight;
}
};
public:
//用invalid来代表无效元素，在我们的文件压缩中就代表没有出现的元素那么也就是_appear_count=0的
//元素不需要在huffman树中存在因为他们在文件中没有出现，我们不需要他们的编码。
huffman_tree(const vector<T>& ln,const T invalid=T())
{
priority_queue<node*,vector<node*>,compare> q;
for (auto e : ln)
{
if(e!=invalid)
q.push(new node(e));
}
while (q.size() > 1)
{//这里我们将较大的元素放到新构造的树的右边，小的放到左边
node* temp1 = q.top();//最小的元素
q.pop();
node* temp2 = q.top();
q.pop();
node* temp_root= new node(temp1, temp2, (temp1->_weight + temp2->_weight));
q.push(temp_root);
}
if (!q.empty())
{
_root = q.top();
}
}
//列表构造huffman树
huffman_tree(const initializer_list<T> ln)
{
priority_queue<node*, vector<node*>, compare> q;
for (auto e : ln)
{
q.push(new node(e));
}
while (q.size() > 1)
{//这里我们将较大的元素放到新构造的树的右边，小的放到左边
node* temp1 = q.top();//最小的元素
q.pop();
node* temp2 = q.top();
q.pop();
node* temp_root = new node(temp1, temp2,(temp1->_weight + temp2->_weight));
q.push(temp_root);
}
_root = q.top();
}
~huffman_tree()
{
destroy(_root);
}
//哈夫曼编码：获取每个叶子节点的编码
void huffman_code(vector<T>& fileinfo)
{
string path;
front(path, _root, fileinfo);
}
node* get_root()
{
return _root;
}
private:
void front(string& path, node* root,vector<T>& fileinfo)
{
if (root == nullptr)
{
return;
}
if (root->_left == nullptr&&root->_right == nullptr)
{
fileinfo[root->_weight._ch]._ch_code = path;
return;
}
path.push_back('0');
front(path, root->_left, fileinfo);
path.pop_back();
path.push_back('1');
front(path, root->_right, fileinfo);
path.pop_back();
}
void destroy(node* root)
{
if (root)
{
destroy(root->_left);
destroy(root->_right);
delete root;
root = nullptr;
}
}
node* _root;
};
#endif<LZ77.h>//文件
#pragma once
#include "HashTable.h"
#include "common.h"
class LZ77
{
public:
LZ77();
~LZ77();
void CompressFile(const string& filename);
void UNCompressFile(const string& filename);
string Getfilename(const string& filename);
string Getfilepostfix(const string& file_name);
ush maxlenth(ush start, ush match_head, ush& matchdis);
void WriteFlaginfo(FILE* fp, ush match_head, uch& bitinfo, uch& bitcount);
void Filldata(ush &start, FILE* fin, size_t &looksize);
private:
uch* _pWin;//用来读取文件的窗口大小
HashTable _ht;
};<wbxzip.h>//文件
#pragma once
#include "HashTable.h"
#include "common.h"
#include "huffman_tree.hpp"
// 区间码结构体
struct IntervalSolution
{
ush code; // 区间编号
uch extraBit; // 扩展码长度
ush interval[2]; // 改区间中包含多少个数字
};
/*************************************************************/
// 距离区间码所有区间码都是左闭右闭的
static IntervalSolution distInterval[] = {
{ 0, 0, { 1, 1 } },
{ 1, 0, { 2, 2 } },
{ 2, 0, { 3, 3 } },
{ 3, 0, { 4, 4 } },
{ 4, 1, { 5, 6 } },
{ 5, 1, { 7, 8 } },
{ 6, 2, { 9, 12 } },
{ 7, 2, { 13, 16 } },
{ 8, 3, { 17, 24 } },
{ 9, 3, { 25, 32 } },
{ 10, 4, { 33, 48 } },
{ 11, 4, { 49, 64 } },
{ 12, 5, { 65, 96 } },
{ 13, 5, { 97, 128 } },
{ 14, 6, { 129, 192 } },
{ 15, 6, { 193, 256 } },
{ 16, 7, { 257, 384 } },
{ 17, 7, { 385, 512 } },
{ 18, 8, { 513, 768 } },
{ 19, 8, { 769, 1024 } },
{ 20, 9, { 1025, 1536 } },
{ 21, 9, { 1537, 2048 } },
{ 22, 10, { 2049, 3072 } },
{ 23, 10, { 3073, 4096 } },
{ 24, 11, { 4097, 6144 } },
{ 25, 11, { 6145, 8192 } },
{ 26, 12, { 8193, 12288 } },
{ 27, 12, { 12289, 16384 } },
{ 28, 13, { 16385, 24576 } },
{ 29, 13, { 24577, 32768 } }
};
// 长度区间码
static IntervalSolution lengthInterval[] = {
{ 257, 0, { 3, 3 } },
{ 258, 0, { 4, 4 } },
{ 259, 0, { 5, 5 } },
{ 260, 0, { 6, 6 } },
{ 261, 0, { 7, 7 } },
{ 262, 0, { 8, 8 } },
{ 263, 0, { 9, 9 } },
{ 264, 0, { 10, 10 } },
{ 265, 1, { 11, 12 } },
{ 266, 1, { 13, 14 } },
{ 267, 1, { 15, 16 } },
{ 268, 1, { 17, 18 } },
{ 269, 2, { 19, 22 } },
{ 270, 2, { 23, 26 } },
{ 271, 2, { 27, 30 } },
{ 272, 2, { 31, 34 } },
{ 273, 3, { 35, 42 } },
{ 274, 3, { 43, 50 } },
{ 275, 3, { 51, 58 } },
{ 276, 3, { 59, 66 } },
{ 277, 4, { 67, 82 } },
{ 278, 4, { 83, 98 } },
{ 279, 4, { 99, 114 } },
{ 280, 4, { 115, 130 } },
{ 281, 5, { 131, 162 } },
{ 282, 5, { 163, 194 } },
{ 283, 5, { 195, 226 } },
{ 284, 5, { 227, 257 } },
{ 285, 0, { 258, 258 } } };
/******************************************************************/
class wbxzip
{
public:
//解码表结构体
struct DecodeTable
{
uch _decodelen;//编码位长
uint _code;//首字符编码
ush _lencount;//相同编码长度个数
ush _charindex;//符号索引
};
struct bytelenthinfo
{//用来保存每个长度距离和字符的信息，从而构建Huffman树
bytelenthinfo(ush appearcount=0)
:_appearcount(appearcount)
{}
ush _elem;//用来表示长度或距离或字符
uch _codelength;//编码位长
ush _appearcount;//出现次数:这里的出现次数之所以用ush来表示是因为我们每达到32K的数据就进行压缩所以每个字符出现的最大的频次不会超过ush的范围
uint _code;//编码
//因为在构造哈夫曼树要建堆那么我们就需要比较，那么就要提供我们自定义结构体的比较符号重载：
bool operator>(const bytelenthinfo& b)const
{
return _appearcount > b._appearcount;
}
bool operator<(const bytelenthinfo& b)const
{
if (_codelength < b._codelength ||
((_codelength == b._codelength) && (_elem < b._elem)))
{
return true;
}
else
{
return false;
}
}
bool operator==(const bytelenthinfo& b)const
{
return _appearcount == b._appearcount;
}
bool operator!=(const bytelenthinfo& b)const
{
return _appearcount != b._appearcount;
}
//在构造huffman树时候中途要构造新树那么新树的根节点的权值是两个子树根节点的权值的和，那么就要将两个
//节点相加那么就要重载+号：
bytelenthinfo operator+(const bytelenthinfo& b)
{
//这里我们重载+只需要关注它的出现次数即可不需要关心其他因为我们构造huffman树的时候是用频次来构造
//而且最终我们用的只是叶子节点。所以我们这里只需要返回相加之后正确的出现频次即可
return bytelenthinfo(_appearcount + b._appearcount);
}
};
wbxzip();
~wbxzip();
void CompressFile(const string& filename);
void UNCompressFile(const string& filename);
string Getfilename(const string& filename);
string Getfilepostfix(const string& file_name);
ush maxlenth(ush start, ush match_head, ush& matchdis);
void WriteFlaginfo(FILE* fp, ush match_head, uch& bitinfo, uch& bitcount);
void Filldata(ush &start, FILE* fin, size_t &looksize);
void SaveLz77Result( ush matchlenth,const ush& matchdist, uch &bitinfo, uch& bitcount, size_t looksize);
//获取编码位长
void Getcodelenth(huffman_tree_node<bytelenthinfo>* root, vector<bytelenthinfo>& eleminfo);
void HelpGetcodelenth(huffman_tree_node<bytelenthinfo>* root, vector<bytelenthinfo>& eleminfo,uch len);
//生成Huffman编码：
void Generatehuffmancode(vector<bytelenthinfo>& eleminfo);
//压缩长度和距离
void CompressLenthDist(ush lenth, ush dist, uch& compressbitinfo, uch& compressbitcount);
//写比特位信息
void WriteByte(uint code, uch codelenth, uch& compressbitinfo, uch& compressbitcount);
//统计每个字符出现次数
void StatisticsAppearcount();
ush GetLenthcode(ush lenth, uch& index);
ush GetDistcode(ush dist);
// 写编码位长信息：字符长度编码和距离编码位长
void Writeinfo();
void Clear();//清空统计信息
///
//解码相关
void Getcodelenthinfo(FILE* fin);//获取压缩文件当中的字符长度信息
void GenerateDecode(vector<DecodeTable>& table, vector<bytelenthinfo>& eleminfo);//生成解码信息
ush UNCopressSymbol(FILE* fin, vector<bytelenthinfo>& codeinfo, vector<DecodeTable>& decTable, uch& ch, uch& bitcount);
void GetNextBit(FILE* fin, ush& code, uch& ch, uch& bitcount);//读取下一个bit位
private:
void CompressBlock();
uch* _pWin;//用来读取文件的窗口大小
HashTable _ht;
/ZIP
//下面这些信息都要交给Huffman来进行压缩
vector<ush> _ByteLenthLZ77; //用来保存字符长度信息和文件中的字符信息，到时候交给Huffman来压缩
vector<ush> _DistIfoLZ77; //用来保存距离长度信息
vector<uch> _FlagInfoLZ77; //用来保存标志位信息
const ush BUFF_SIZE = 0x8000; //这里是LZ77每个块的大小，ZIP压缩并不是等LZ77整体压缩完成之后
//然后对压缩结果进行压缩而是当压缩结果达到一定大小之后就对其进行Huffman压缩
vector<bytelenthinfo> _ByteLenthInfo;//用来保存Huffman压缩中要用到的字符长度信息
vector<bytelenthinfo> _DistInfo;//用来保存Huffman压缩中要用到的距离长度信息
ush UNCopressSymbol(FILE* fin, vector<bytelenthinfo>& codeinfo, vector<DecodeTable>& decTable);
bool _islast = false;//用来标记当前块信息是否为最后一块这里在LZ77压缩中最后来标记
FILE* fout;
};<file_compress_huffman.cpp>//文件
#define _CRT_SECURE_NO_WARNINGS
#include "file_compress_huffman.h"
#include "huffman_tree.hpp"
//在构造函数中要初始化类中的字符信息数组表：
file_compress_huffman::file_compress_huffman()
{
_fileinfo.resize(256);
//因为byteinfo中的ch表示字符，而ch是char类型的，那么就有256种状态，我们初始化存放
//哈夫曼压缩中的数组那么我们就可以得到文件中所有出现的字符的状态,用字符的ASII码来
//定位字符在数组中的位置
for (int i = 0; i < 256; i++)
{
_fileinfo[i]._ch = i;
}
}
//获取文件后缀名
string file_compress_huffman::get_postfix(const string& file_name)
{
return file_name.substr(file_name.find_first_of('.')+1);
}
//获取文件名
string file_compress_huffman::get_file_name(const string& file_name)
{
return file_name.substr(0, file_name.find_first_of('.'));
}
//写入解压缩要用的头部信息：
void file_compress_huffman::write_head_info(const string& file_name, FILE* fpout)
{
//首先写入文件后缀名，因为要在解压缩的时候还原文件名所以要保存信息
string file_postfix = get_postfix(file_name);
file_postfix += "\n";
//然后写入在文件中出现字符种类的个数,以及每个字符出现的次数字符和出现次数之间用：隔开
string numappear_count;
size_t type_count = 0;
for (auto e:_fileinfo)
{
if (e._appear_count == 0)
{
continue;
}
numappear_count += e._ch;
numappear_count += ':';
numappear_count += to_string(e._appear_count);
numappear_count += '\n';
type_count++;
}
file_postfix += to_string(type_count);
file_postfix += "\n";
fwrite(file_postfix.c_str(), 1, file_postfix.size(), fpout);//先写入文件后缀和字符出现种类个数
fwrite(numappear_count.c_str(), 1, numappear_count.size(), fpout);
}
//压缩函数：
void file_compress_huffman::compress_file(const string& file_name)
{
//1.首先要统计源文件中字符的出现次数：
//(1).首先要打开文件：
FILE* fpin = fopen(file_name.c_str(), "rb");
if (fpin == nullptr)
{
cout << "文件打开失败" << endl;
return ;
}
//(2).读取文件到内存中
uch buf[1024] = {0};
while (true)
{
size_t read_size = fread(buf, 1, 1024, fpin);
if (read_size == 0)
{
//if (feof(fpin))
//{
// break;
//}
//else
//{
// buf[0] = (uch)0xFF;
// fseek(fpin, 1, SEEK_CUR);
// read_size = 1;
//}
break;
}
//统计文件中的出现的字符的次数
for (size_t i = 0; i < read_size; i++)
{
_fileinfo[buf[i]]._appear_count++;
}
}
//2.用字节频次来创建huffman树：
//(1).先构造一个huffman树对象
huffman_tree<byteinfo> tree(_fileinfo,byteinfo());
//3.获取每个huffman编码：
tree.huffman_code(_fileinfo);
//tree.getree(_fileinfo);
//要打开的压缩文件名
string compressed_filename = get_file_name(file_name);
compressed_filename += ".hz";这里压缩后的后缀应该要修改一下，但是我不知修改为什么
FILE* fpout = fopen(compressed_filename.c_str(), "wb");
//4.向压缩文件中写入头部信息：
write_head_info(file_name, fpout);
//5.用获取的到的编码对源文件进行改写,然后写入到文件当中：
//(1).先将文件指针指到文件头部
fseek(fpin, 0, SEEK_SET);
uch bit = 0;//对文件中编码临时要用的bit位
int bitcount = 0;//计算上面bit用了多少位
//string text;
while (true)
{
size_t read_size = fread(buf, 1, 1024, fpin);
if (read_size == 0)
{
break;
}
//将文件中的每个字符读到内存中，然后将每一位替换为相应的编码然后写到压缩文件中
for (size_t i = 0; i < read_size; i++)
{
string& temp_code = _fileinfo[buf[i]]._ch_code;
for (size_t j = 0; j < temp_code.size(); j++)
{
bit <<= 1;
if (temp_code[j] == '1')
{
bit |= 1;
}
bitcount++;
if (bitcount == 8)
{
//text.push_back(uch(bit));
fputc(bit, fpout);
//if (text.size() > 0x40000000)
//{//这里如果每次凑够一个bit位就向文件中写入太浪费时间所以这里我们先将bit位存储起来然后一次性写入到文件中
但是如果一次存储过多那么可能会导致写入失败，我在网上看32位linux系统下一次性最多写2G的数据那么我们这里保险起见
达到1G的数据就进行写入
// fwrite(text.c_str(), 1, text.size(), fpout);
// text.clear();
//}
bit = 0;
bitcount = 0;
}
}
}
//fwrite(text.c_str(), 1, text.size(), fpout);
//防止最后一位bit位没有写入
/*if (bitcount > 0 && bitcount < 8)
{
bit <<= (8 - bitcount);
fputc(bit, fpout);
}*/
}
if (bitcount > 0 && bitcount < 8)
{
bit <<= (8 - bitcount);
fputc(bit, fpout);
}
fclose(fpin);
fclose(fpout);
}
//解压缩
void file_compress_huffman::un_compress_file(const string& file_name)
{
//打开压缩文件：
//(1)这里可以判断一下文件的后缀名是否是我们我们的设置的后缀，因为我们当前的函数的功能只能解压huffman编码的压缩文件：
//但是由于我测试没有打开二进制文件的软件所以我就将压缩文件的后缀名也写为了txt方便测试所以这里就不判断了
//(2)打开文件：
FILE* fpread = fopen(file_name.c_str(), "rb");
if (fpread == nullptr)
{
cout << "要解压缩打开文件不存在" << endl;
}
//1.首先要读取文件后缀信息,还原后的文件我们要以压缩文件中保存的后缀信息作为文件的类型
string file_post_fix;
get_line(file_post_fix, fpread);
//2.读取总行数
string fileinfo;
get_line(fileinfo, fpread);
int count = atoi(fileinfo.c_str());//读取的频次信息总行数
//3.读取频次信息
while (count--)
{
fileinfo = "";//重复利用fileinfo字符串
get_line(fileinfo, fpread);
if (fileinfo == "")
{
fileinfo = "\n";
get_line(fileinfo, fpread);
}
uch ch = fileinfo[0];
//用读到的字符来构造_fileinfo数组因为要用_fileinfo来还原huffman树从而来解压文件
//_fileinfo[ch]._ch = ch;//这一步可有可无因为我们在构造对象的时候就已经初始化过_fileinfo了
_fileinfo[ch]._appear_count = atoi(fileinfo.c_str() + 2);
}
//4.还原Huffman树
huffman_tree<byteinfo> tree(_fileinfo);
//5.解压缩
//从huffman树的根开始按照文件中的存放的bit位来还原huffman树
//(1)打开要保存解压缩之后的还原文件
string refilename = get_file_name(file_name);
refilename += "huffun";
refilename += ".";
refilename += file_post_fix;
//FILE* fpwrite = fopen("121up.txt", "wb");
FILE* fpwrite = fopen(refilename.c_str(), "wb");
uch buf[1024];
string text;
uch bit = 0;
count = 0;//解压缩字符个数
huffman_tree_node<byteinfo>* cur = tree.get_root();
while (true)
{
size_t read_size=fread(buf, 1, 1024, fpread);
if (read_size == 0)
{
break;
}
for (size_t i = 0; i < read_size; i++)
{
bit = buf[i];
for (size_t j = 0; j < 8;j++)
{
if (bit & 0x80)
{
cur = cur->_right;
}
else
{
cur = cur->_left;
}
bit <<= 1;
if (cur&&cur->_left == nullptr&&cur->_right == nullptr)
{
uch ch = cur->_weight._ch;
fputc(ch, fpwrite);
//text.push_back(cur->_weight._ch);
cur = tree.get_root();
count++;
//if (text.size() > 0x40000000)
//{
// fwrite(text.c_str(), 1, text.size(), fpwrite);
// text.clear();
//}
if (count == cur->_weight._appear_count)
{
break;
}
}
}
}
}
//fwrite(text.c_str(), 1, text.size(), fpwrite);
fclose(fpwrite);
fclose(fpread);
}
<HashTable.cpp>//文件
#include "HashTable.h"
//构造函数
//哈希表：底层维护的两个空间一个是存储当前字符下标的head指向的空间，另一个是存储哈希冲突的空间
//prev指向的空间。
HashTable::HashTable()
:_prev(new ush[2 * WSIZE])
,_head(_prev+WSIZE)
{
memset(_prev, 0,sizeof(ush)* 2 * WSIZE);
}
//析构函数
HashTable::~HashTable()
{
delete[] _prev;
_prev = _head = nullptr;
}
// 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;
}
//插入：
// hashAddr：上一次哈希地址
//ch：当前要插入的三个字符的第三个字符，因为我们将上一个哈希地址传入，那么上一个哈希地址的计算是通过当前三个
//字符的前两个字符和上一个三个字符的第一个字符计算得出，那么这里我们只需要将当前的三个字符的最后一个字符传入
//然后计算出当前三个字符的哈希地址即可。//那假如要插入的字符串是第一个字符串那么第一个哈希地址从哪里来？？？？？
// pos：当前三个字符的首字符的地址。
//matchHead：如果匹配，保存上一个在存储在当前哈希地址的三个元素的首地址。例如当前三号位置保存的是19当前要插入3号位置的
//三个字符串首地址是24那么macthhead保存的就是19。//这里为啥要保存？？？？？？？？？？？因为这里要在后面文件压缩的时候
//获取macthHead通过判断macthHead是否为0判断当前字符串是否有匹配串。
void HashTable::InsertString(ush& hashAddr, uch ch, ush pos, ush& macthHead)
{
//1.计算当前要插入的三个字符串的哈希地址：
HashFunc(hashAddr, ch);
//2.将hashaddr位置存储的前文中的匹配字符串的位置搬移到prev的pos的位置
_prev[pos & HASH_MASK] = _head[hashAddr];
//3.保存当前将前文中找到的最近一个匹配串通过macthhead带出去
macthHead = _head[hashAddr];///这里取hashaddr中的macthhead的时候要不要给macthead与上掩码？？？？？？？？？？？？这里其实不用与因为我们在获取上一个match的时候就对macthhead与掩码处理过。
//4.将当前哈希地址存入当前字符串的首地址
_head[hashAddr] = pos;
}
ush HashTable::GetPrevMatch(ush &MathcHead)
{
MathcHead = _prev[MathcHead & HASH_MASK];
return MathcHead;
}
//将数据搬移之后我们需要将哈希表更新：因为右窗的数据都搬移到了左窗那么此时哈希表中存放的地址都改变了
//所以我们需要将哈希表中的每个地址都减去WSIZE，对于哈希表中小于WSIZE的数据就相当于被覆盖了属于无效地址
//那么我们就将其置为0
void HashTable::updatahash()
{
//更新head
for (ush i = 0; i < HASH_SIZE; i++)
{
if (_head[i] < WSIZE)
{
_head[i] = 0;
}
else
{
_head[i] -= WSIZE;
}
}
//更新prev
for (ush i = 0; i < HASH_SIZE; i++)
{
if (_prev[i] < WSIZE)
{
_prev[i] = 0;
}
else
{
_prev[i] -= WSIZE;
}
}
}
void get_line(string& buf, FILE* fpread)
{
if (fpread == nullptr)
{
return;
}
while (!feof(fpread))//这里的feof当文件结束的时候会返回一个非0的值
{
uch ch = fgetc(fpread);
if (ch == '\n')
{
return;
}
buf += ch;
}
}
<LZ77.cpp>//文件
#define _CRT_SECURE_NO_WARNINGS
#include "LZ77.h"
LZ77::LZ77()
:_pWin(new uch[2*WSIZE])
,_ht()
{}
LZ77::~LZ77()
{
if (_pWin)
{
delete[] _pWin;
}
}
//压缩文件
void LZ77::CompressFile(const string& filename)
{
//首先要打开一个文件：
FILE* fin = fopen(filename.c_str(), "rb");
if (fin == nullptr)
{
cout << "待压缩文件打开失败" << endl;
return;
}
//当文件大小为3个字节的时候那么就没有必要对文件进行压缩了
//获取文件大小：
fseek(fin, 0, SEEK_END);
ull filesize = ftell(fin);//对于二进制文件返回从开始到当前文件流指针的字节数对于文本流，数值可能没有意义，但仍然可以用于在以后使用fseek将位置恢复到相同的位置（如果使用ungetc放回的字符仍在等待读取，则行为未定义）。
fseek(fin, 0, SEEK_SET);
//如果文件大小小于等于MIN_MATCH则不进行压缩
if (filesize <= MIN_MATCH)
{
cout << "文件大小小于等于3个字节，不进行压缩" << endl;
fclose(fin);
return;
}
//文件压缩：
//1.首先打开文件：
string compressfilename = Getfilename(filename);
compressfilename += ".lz";
FILE* fout = fopen(compressfilename.c_str(),"wb");
//2.先读取一个窗口的数据：
size_t looksize = fread(_pWin, 1, 2 * WSIZE, fin);
//3.在处理窗口数据循环插入之前我们要先获取前两个bit位的编码也就是前两个哈希编码
ush hash_addr = 0;
ush match_head = 0;
for (int i = 0; i < MIN_MATCH-1; i++)
{
_ht.InsertString(hash_addr, _pWin[i], i, match_head);
}
//这里我们不将标志位文件和压缩文件放在一起，而是分开，将标志位放到另一个文件当中
compressfilename = Getfilename(filename);
compressfilename += ".flag";
FILE* flag = fopen(compressfilename.c_str(), "wb");
//将文件后缀名称也写入到标志位文件：
string filepostfix = Getfilepostfix(filename);
fwrite(filepostfix.c_str(), 1, filepostfix.size(), flag);
fputc('\n', flag);
uch bitinfo = 0;//要写入标志位文件的比特位
uch bitcount = 0;//写入比特位计数计数够8位就向文件中写入一次
ush start = 0;//当前字符插入的地方
ush matchdis = 0;//最长匹配距离//防止越界
ush matchlenth = 0;//最长匹配长度
while (looksize)//这里looksize是窗口的数据个数，这里我们将窗口中的数据全部处理完成那么我们的压缩也就结束了。
{
match_head = 0;
matchlenth = 0;
//1.首先将每个字符插入哈希表：
_ht.InsertString(hash_addr, _pWin[start + 2], start, match_head);
if (match_head)
{//这里如果match_head不为0的话那么就代表在前面找到了匹配串：
matchlenth = maxlenth(start,match_head,matchdis);
}
if (matchlenth < MIN_MATCH)
{//没有找到最长匹配:那么此时就将字符原封不动的写入到压缩文件
fputc(_pWin[start], fout);
WriteFlaginfo(flag, 0, bitinfo, bitcount);
start++;
looksize--;
}
else
{//找到了最长匹配：那么此时就将字符替换为长度距离对写入到压缩文件中
matchlenth -= 3;//因为这里matchlenth要表示3-258范围的匹配字节
fputc(matchlenth, fout);//长度写入
//fwrite(&matchlenth, 1, sizeof(matchlenth), fout);
fwrite(&matchdis, sizeof(matchdis), 1, fout);//距离写入
WriteFlaginfo(flag, 1, bitinfo, bitcount);//将标志位写入
matchlenth += 3;
looksize -= matchlenth;
matchlenth--;//因为当前的字符已经插入到了哈希表中后面只需要将匹配的字符全部插入到哈希表中即可
start++;
while (matchlenth--)
{//将匹配区间内的元素都插入哈希表中因为匹配区间内的元素有可能是后文中的匹配串
_ht.InsertString(hash_addr, _pWin[start + 2], start, match_head);
start++;
}
}
//处理大文件：在处理大文件的时候当先行缓冲区中的数据少于最佳匹配元素个数的时候那么我们就要进行数据填充
if (start >= WSIZE + MAX_DIST)
{
Filldata(start,fin,looksize);
}
}
if (bitcount > 0)//将最后一位没有写入到标志位文件当中的bit位信息写入
{
bitinfo <<= (8 - bitcount);
fputc(bitinfo, flag);
}
//将文件大小信息写入到文件的最后：
fwrite(&filesize, 1, sizeof(filesize), flag);
fclose(fin);
fclose(fout);
fclose(flag);
}
//数据填充：
void LZ77::Filldata(ush &start, FILE* fin, size_t &looksize)
{
//1.将右窗中的数据都搬移到左窗
start -= WSIZE;
memcpy(_pWin, _pWin + WSIZE, WSIZE);
//2.那么向右窗中写入数据
if (!feof(fin))//如果文件走到末尾那么feof返回一个非0值
{
looksize += fread(_pWin + WSIZE, 1, WSIZE, fin);
}
//3.更新哈希表：
_ht.updatahash();
}
//写标志位函数：
void LZ77::WriteFlaginfo(FILE* fp, ush match_head, uch& bitinfo, uch& bitcount)
{
bitinfo <<= 1;
if (match_head)
{
bitinfo |= 1;
}
bitcount++;
if (bitcount == 8)
{
fputc(bitinfo,fp);
bitcount = 0;
bitinfo = 0;
}
}
//求前后文最长匹配长度：
//在这个函数中我们要求出从match_head开始和从start开始两者最长匹配长度和距离：
ush LZ77::maxlenth(ush start,ush match_head,ush& matchdis)
{
//这里因为大文件加入了哈希掩码可能会导致哈希表成链状，所以这里我们要控制匹配次数最多匹配255次就够了
ush MaxMachthcount = 255;
//这里因为匹配距离也就是查询距离还不可以超过MAX_DIST所以这里我们也要有所限制：
ush limit = start >= MAX_DIST ? start - MAX_DIST : 0;
ush max_lenth = 0;//这里最长匹配如果到了255之后如果再++那么就会加到0，1，2所以用ush来定义max_lenth
do
{
ush pstart = start;
ush pend = start + MAX_ATHCH;//最大匹配长度//这里因为最大匹配长度为255所以有可能会超出长度范围所以用ush来表示
ush curmatch_head = match_head;//当前的match_head
uch cur_lenth = 0;//当前的匹配长度
while (pstart < pend &&_pWin[pstart] == _pWin[curmatch_head])
{
pstart++;
curmatch_head++;
cur_lenth++;
}
if (cur_lenth>max_lenth)
{
matchdis = start - match_head;
max_lenth = cur_lenth;
}
} while ((_ht.GetPrevMatch(match_head)>limit)&&(MaxMachthcount--));
//这里如果最大匹配距离大于MAX_DIST那么我们就舍弃本次匹配：
if (matchdis > MAX_DIST)
{
max_lenth = 0;
}
return max_lenth;
}
void LZ77::UNCompressFile(const string& filename)
{
//打开待解压缩压缩文件：
FILE* fin1 = fopen(filename.c_str(), "rb");
//打开标志位文件：
string file_name = Getfilename(filename);//获取当前文件的文件名
file_name += ".flag";
FILE* fin2 = fopen(file_name.c_str(), "rb");//这里将标志位文件写死了？？？？？？？？？？？
//读取要还原的文件后缀：
string filenamepostfix;
while (true)
{
char ch = fgetc(fin2);
if (ch == '\n')
{
break;
}
filenamepostfix.push_back(ch);
}
//打开要还原的文件：
string recoverfilename = Getfilename(filename) + "lzun." + filenamepostfix;
FILE* fout1 = fopen(recoverfilename.c_str(), "wb");
//FILE* fout1 = fopen("222.txt", "wb");
if (fout1==nullptr)
{
perror("fopen");
cout << "解压缩文件打开失败" << endl;
return;
}
//用另一个文件指针打开压缩文件当我们要用长度距离对来进行还原压缩文件的时候那么我们就可以用当前文件指针偏移相应的距离来读取
FILE* fout2 = fopen(recoverfilename.c_str(), "rb");
//FILE* fout2 = fopen("222.txt", "rb");
if (fout2 == nullptr)
{
perror("fopen");
cout << "解压缩文件打开失败" << endl;
return;
}
//向文件中写：读一个标志位写一个
//1.首先读取文件的大小：因为在文件的最后八个字节所以我们将文件指针移动到倒数第八个字节处
fseek(fin2, -8, SEEK_END);
ull filesize = 0;
fread(&filesize, 1, sizeof(filesize), fin2);
fseek(fin2, 0, SEEK_SET);
while (true)
{
char ch = fgetc(fin2);
if (ch == '\n')
{
break;
}
}
uch bit=0;
uch bitcount=0;
while (filesize)
{
if (bitcount == 0)
{//当bitcount为0时候代表当前字节的八个bit标志位都读取完成，那么再从文件中读取一个字节：
bit = fgetc(fin2);
bitcount = 8;
}
if (bit & 0x80)
{
fflush(fout1);//在用匹配还原前先将文件缓冲区中的数据刷新出去。
//如果当前位置为1那么就利用长度距离对来读取数据：
ush matchlenth = fgetc(fin1) + 3;//长度
filesize -= matchlenth;
ush matchdis = 0;//距离,读取两个字节
fread(&matchdis, sizeof(matchdis), 1, fin1);
fseek(fout2, 0 - matchdis, SEEK_END);//将文件指针偏移到匹配字符串的位置
while (matchlenth--)
{//这里我们在前文中读取一个匹配字符就向后文中写一个匹配字符
char ch=fgetc(fout2);//从解压缩文件中读取
fputc(ch, fout1);
fflush(fout1);//这里注意要及时刷新缓冲区，因为如果前文匹配字符串与后文匹配字符串又重叠那么就会造成
//还原不完整例如abc abc abc这里当前文匹配读取到第二个abc的时候后文写入的abc还在文件缓冲区中那么后文还原
//的字符就不完整。
}
}
else
{//将压缩文件中的字符原封不动的写入到还原文件当中
char ch=fgetc(fin1);
fputc(ch,fout1);
filesize--;
}
bit <<= 1;
bitcount--;
}
fclose(fin1);
fclose(fin2);
fclose(fout1);
fclose(fout2);
}
//获取文件名
string LZ77::Getfilename(const string& filename)
{
return filename.substr(0, filename.find('.'));
}
//获取文件后缀名
string LZ77::Getfilepostfix(const string& file_name)
{
return file_name.substr(file_name.find_first_of('.') + 1);
}<wbxzip.cpp>//文件
#define _CRT_SECURE_NO_WARNINGS
#include "wbxzip.h"
#include "huffman_tree.hpp"
wbxzip::wbxzip()
:_pWin(new uch[2*WSIZE])
,_ht()
{
_ByteLenthLZ77.reserve(BUFF_SIZE);
_DistIfoLZ77.reserve(BUFF_SIZE);
_FlagInfoLZ77.reserve(BUFF_SIZE / 8);
//给保存字符长度信息和距离长度的数组初始化
//字符长度信息的数组一共有256+1+29=286个元素
_ByteLenthInfo.resize(286);
for (size_t i = 0; i < _ByteLenthInfo.size(); i++)
{
_ByteLenthInfo[i]._elem = i;
_ByteLenthInfo[i]._appearcount = 0;
_ByteLenthInfo[i]._code = 0;
_ByteLenthInfo[i]._codelength = 0;
}
_DistInfo.resize(30);
for (size_t i = 0; i < _DistInfo.size(); i++)
{
_DistInfo[i]._elem = i;
_DistInfo[i]._appearcount = 0;
_DistInfo[i]._code = 0;
_DistInfo[i]._codelength = 0;
}
}
wbxzip::~wbxzip()
{
if (_pWin)
{
delete[] _pWin;
}
}
//压缩文件
void wbxzip::CompressFile(const string& filename)
{
//首先要打开一个文件：
FILE* fin = fopen(filename.c_str(), "rb");
if (fin == nullptr)
{
cout << "待压缩文件打开失败" << endl;
return;
}
//当文件大小为3个字节的时候那么就没有必要对文件进行压缩了
//获取文件大小：
fseek(fin, 0, SEEK_END);
ull filesize = ftell(fin);//对于二进制文件返回从开始到当前文件流指针的字节数对于文本流，数值可能没有意义，但仍然可以用于在以后使用fseek将位置恢复到相同的位置（如果使用ungetc放回的字符仍在等待读取，则行为未定义）。
fseek(fin, 0, SEEK_SET);
//如果文件大小小于等于MIN_MATCH则不进行压缩
if (filesize <= MIN_MATCH)
{
cout << "文件大小小于等于3个字节，不进行压缩" << endl;
fclose(fin);
return;
}
//文件压缩：
//1.首先打开文件：
string compressfilename = Getfilename(filename);
compressfilename += ".wbxzip";
fout = fopen(compressfilename.c_str(),"wb");
//2.先读取一个窗口的数据：
size_t looksize = fread(_pWin, 1, 2 * WSIZE, fin);
//3.在处理窗口数据循环插入之前我们要先获取前两个bit位的编码也就是前两个哈希编码
ush hash_addr = 0;
ush match_head = 0;
for (int i = 0; i < MIN_MATCH-1; i++)
{
_ht.InsertString(hash_addr, _pWin[i], i, match_head);
}
//将文件后缀名称写入到压缩文件中：
string filepostfix = Getfilepostfix(filename);
fwrite(filepostfix.c_str(), 1, filepostfix.size(), fout);
fputc('\n', fout);
uch bitinfo = 0;//要写入标志位文件的比特位
uch bitcount = 0;//写入比特位计数计数够8位就向文件中写入一次
ush start = 0;//当前字符插入的地方
ush matchdis = 0;//最长匹配距离//防止越界
ush matchlenth = 0;//最长匹配长度
while (looksize)//这里looksize是窗口的数据个数，这里我们将窗口中的数据全部处理完成那么我们的压缩也就结束了。
{
match_head = 0;
matchlenth = 0;
//1.首先将每个字符插入哈希表：
_ht.InsertString(hash_addr, _pWin[start + 2], start, match_head);
if (match_head)
{//这里如果match_head不为0的话那么就代表在前面找到了匹配串：
matchlenth = maxlenth(start,match_head,matchdis);
}
if (matchlenth < MIN_MATCH)
{//没有找到最长匹配:那么此时就将字符原封不动的写入到压缩文件
//fputc(_pWin[start], fout);
// 这里我们就先不将字符写入到文件当中了我们将字符先保存到一个空间中然后用Huffman来进行编码压缩
//WriteFlaginfo(flag, 0, bitinfo, bitcount);
looksize--;
SaveLz77Result( _pWin[start], 0, bitinfo, bitcount, looksize);
start++;
}
else
{//找到了最长匹配：那么此时就将字符替换为长度距离对写入到压缩文件中
looksize -= matchlenth;
//fputc(matchlenth, fout);//长度写入
//fwrite(&matchlenth, 1, sizeof(matchlenth), fout);
//fwrite(&matchdis, sizeof(matchdis), 1, fout);//距离写入
//WriteFlaginfo(flag, 1, bitinfo, bitcount);//将标志位写入
SaveLz77Result( matchlenth, matchdis, bitinfo, bitcount, looksize);//这里存入的长度就是原匹配的距离没有减3
matchlenth--;//因为当前的字符已经插入到了哈希表中后面只需要将匹配的字符全部插入到哈希表中即可
start++;
while (matchlenth--)
{//将匹配区间内的元素都插入哈希表中因为匹配区间内的元素有可能是后文中的匹配串
_ht.InsertString(hash_addr, _pWin[start + 2], start, match_head);
start++;
}
}
//处理大文件：在处理大文件的时候当先行缓冲区中的数据少于最佳匹配元素个数的时候那么我们就要进行数据填充
if (start >= WSIZE + MAX_DIST)
{
Filldata(start,fin,looksize);
}
}
//这里可能最后我们的LZ77压缩结果不够一个BUFF_SIZE那么我们要在这里单独压缩
if (BUFF_SIZE >= _ByteLenthLZ77.size())
{//如果当前的字符长度信息的大小达到了要压缩的一块的大小那么我们就将其交给Huffman来进行压缩
if (bitcount > 0 && bitcount < 8)
{
bitinfo <<= (8 - bitcount);
_FlagInfoLZ77.push_back(bitinfo);
}
_islast = true;//到了这里那么文件一定是最后一块
//将该块的数据交给Huffman来进行压缩：
CompressBlock();
}
//将文件大小信息写入到文件的最后：
//fwrite(&filesize, 1, sizeof(filesize), flag);
fclose(fin);
fclose(fout);
}
//数据填充：
void wbxzip::Filldata(ush &start, FILE* fin, size_t &looksize)
{
//1.将右窗中的数据都搬移到左窗
start -= WSIZE;
memcpy(_pWin, _pWin + WSIZE, WSIZE);
//2.那么向右窗中写入数据
if (!feof(fin))//如果文件走到末尾那么feof返回一个非0值
{
looksize += fread(_pWin + WSIZE, 1, WSIZE, fin);
}
//3.更新哈希表：
_ht.updatahash();
}
//存储LZ77的压缩信息：ZIP
//我们要将当前LZ77压缩的结果保存到buf当中然后用Huffman来压缩buf中的信息
void wbxzip::SaveLz77Result( ush matchlenth, const ush& matchdist,uch &bitinfo ,uch& bitcount,size_t looksize)
{
//这里我们直接用matchlenth来传递字符或者长度信息，直接将其写入buf中那么我们在用Huffman进行压缩的时候只要判断标志位信息
//如果标志位信息为0的话那么当前的matchlenth就代表字符那么直接压缩，如果为1的话那么当前的matchlenth就代表长度，那么
//就要压缩其编码范围。
_ByteLenthLZ77.push_back(matchlenth);
bitinfo <<= 1;
if (matchdist>0)
{
bitinfo |= 1;
_DistIfoLZ77.push_back(matchdist);//这里如果匹配的话就将距离存入到buf中
}
bitcount++;
if (bitcount == 8)
{
bitcount = 0;
_FlagInfoLZ77.push_back(bitinfo);
bitinfo = 0;
}
if (BUFF_SIZE == _ByteLenthLZ77.size())
{//如果当前的字符长度信息的大小达到了要压缩的一块的大小那么我们就将其交给Huffman来进行压缩
if (bitcount > 0 && bitcount < 8)
{
bitinfo <<= (8 - bitcount);
_FlagInfoLZ77.push_back(bitinfo);
}
//将该块的数据交给Huffman来进行压缩：
CompressBlock();
}
}
//zip//
void wbxzip::CompressBlock()
{
Clear();//这里要在每次压缩开始的时候就清空数据而不是在最后因为最后的话如果是最后一次压缩那么就没有必要清空数据了
//1.统计每个字节出现的次数：
StatisticsAppearcount();
//2.创建Huffman树
huffman_tree<bytelenthinfo> Lenthhuffmantree(_ByteLenthInfo, bytelenthinfo());//长度字符Huffman树
huffman_tree<bytelenthinfo> disthuffmantree(_DistInfo, bytelenthinfo());//距离Huffman树
//3.获取编码位长
Getcodelenth(Lenthhuffmantree.get_root(), _ByteLenthInfo);//获取长度的编码位长
Getcodelenth(disthuffmantree.get_root(),_DistInfo);//获取距离编码位长
//4.生成Huffman编码
Generatehuffmancode(_ByteLenthInfo);
Generatehuffmancode(_DistInfo);
//5.写解压缩时候用到的信息----写编码位长
Writeinfo();
//6.压缩
//这里就是将LZ77中的压缩结果按照Huffman编码写入到文件中，其中LZ77压缩结果中有长度原字符和距离信息
size_t flagindex=0;//这里其实用ush就行因为flag信息是原字符信息的1/8所以绰绰有余
uch bit = 0;
uch bitcount = 0;
uch compressbitinfo = 0;
uch compressbitcount = 0;
size_t distindex = 0;
for (size_t i = 0; i < _ByteLenthLZ77.size(); i++)
{
if (bitcount == 0)
{
bit =_FlagInfoLZ77[flagindex++];
bitcount = 8;
}
if (bit & 0x80)
{//长度或距离
CompressLenthDist(_ByteLenthLZ77[i], _DistIfoLZ77[distindex++], compressbitinfo, compressbitcount);
}
else
{//原字符
WriteByte(_ByteLenthInfo[_ByteLenthLZ77[i]]._code, _ByteLenthInfo[_ByteLenthLZ77[i]]._codelength, compressbitinfo, compressbitcount);
}
bit <<= 1;
bitcount--;
}
//将256也写入文件当读取到256时那么就代表当前块文件解压缩完毕
WriteByte(_ByteLenthInfo[256]._code, _ByteLenthInfo[256]._codelength, compressbitinfo, compressbitcount);
//防止最后一个字节没有写入文件中：
if (compressbitcount > 0 && compressbitcount < 8)
{
compressbitinfo <<= (8 - compressbitcount);
fputc(compressbitinfo, fout);
}
//清空保存本次LZ77压缩结果的buf
_ByteLenthLZ77.clear();
_FlagInfoLZ77.clear();
_DistIfoLZ77.clear();
}
//清空统计信息：
void wbxzip::Clear()
{
for (size_t i = 0; i < _ByteLenthInfo.size(); i++)
{
_ByteLenthInfo[i]._appearcount = 0;
_ByteLenthInfo[i]._code = 0;
_ByteLenthInfo[i]._codelength = 0;
}
for (size_t i = 0; i < _DistInfo.size(); i++)
{
_DistInfo[i]._appearcount = 0;
_DistInfo[i]._code = 0;
_DistInfo[i]._codelength = 0;
}
}
//将长度距离对写入到文件当中
void wbxzip::CompressLenthDist(ush lenth, ush dist, uch& compressbitinfo, uch& compressbitcount)
{
//将长度信息压缩到文件当中
//1.那么这里就是将长度的编码压缩到文件当中，但是长度是经过范围编码的，所以我们要将长度对于的范围编码号压缩到文件当中而且要将长度的额外编码也压缩到文件当中
uch index = 0;
uint code = _ByteLenthInfo[GetLenthcode(lenth,index)]._code;
uch codelenth = _ByteLenthInfo[GetLenthcode(lenth,index)]._codelength;
WriteByte(code, codelenth, compressbitinfo, compressbitcount);//写入长度编码
//2.压入长度扩展码//这里在写入长度扩展码的时候有的扩展码是0位那么我们在读取扩展码还原文件的时候就需要先获取当前长度扩展码的位长然后在获取长度扩展码
code = lenth - lengthInterval[index].interval[0];
codelenth = lengthInterval[index].extraBit;//长度扩展码长度
WriteByte(code, codelenth, compressbitinfo, compressbitcount);//写入长度扩展码
//3.将距离信息压缩到文件当中：
code = _DistInfo[GetDistcode(dist)]._code;
codelenth = _DistInfo[GetDistcode(dist)]._codelength;
WriteByte(code, codelenth, compressbitinfo, compressbitcount);//写入距离信息
//4.压入距离扩展码：
index = GetDistcode(dist);//这里发生截断没有事因为距离的范围编码为0-29所以发生截断也不会丢失
code = dist-distInterval[index].interval[0];
codelenth = distInterval[index].extraBit;//距离长度扩展码
WriteByte(code, codelenth, compressbitinfo, compressbitcount);//写入距离扩展码
}
//向文件中写入一个原字符：
//一个字符长度或距离的编码为uint型为32位，而编码信息在最后几位，那么我们就要知道编码信息然后将其每一位都先存入一个临时的
//bit位也就是compressbitinfo当其全部的八位都存满的时候我们就将其写入到文件当中。
void wbxzip::WriteByte(uint code, uch codelenth, uch& compressbitinfo, uch& compressbitcount)//后面两个是压缩bit位信息和bit位计数
{
code <<= (32 - codelenth);//将其编码都移到最高位
for (uch i = 0; i < codelenth; i++)
{
compressbitinfo <<= 1;
if (code & 0x80000000)
{
compressbitinfo |= 1;
}
code <<= 1;
compressbitcount++;
if (compressbitcount == 8)
{
fputc(compressbitinfo, fout);
compressbitinfo = 0;
compressbitcount = 0;
}
}
}
void wbxzip::Writeinfo()
{//写字符长度编码：这里我们将数组中所有的编码位长写入，那么我们在读取的时候按照buf顺序读取那么就可以获得所有字符的编码位长
//从而通过编码位长还原信息：
if (_islast)
{//在ZIP压缩文件中首先将当前文件是否为最后一块一块文件的标志信息写入
fputc(0, fout);
}
else
{
fputc(1, fout);
}
//写入字节长度编码位长信息
for (size_t i = 0; i < _ByteLenthInfo.size(); i++)
{
fputc(_ByteLenthInfo[i]._codelength, fout);
}
//写入距离编码长度信息：
for (size_t i = 0; i < _DistInfo.size(); i++)
{
fputc(_DistInfo[i]._codelength, fout);
}
}
//获取编码位长：
//本函数就是获取每个字符的Huffman编码的长度信息：
//遍历Huffman树获取每个字符的长度信息
void wbxzip::Getcodelenth(huffman_tree_node<bytelenthinfo>* root, vector<bytelenthinfo>& eleminfo)
{
uch len = 0;
HelpGetcodelenth(root, eleminfo, len);
}
void wbxzip::HelpGetcodelenth(huffman_tree_node<bytelenthinfo>* root, vector<bytelenthinfo>& eleminfo, uch len)
{
if (root == nullptr)
{
return;
}
if (root->_left == nullptr&&root->_right == nullptr)
{
eleminfo[root->_weight._elem]._codelength = len;
return;
}
len++;
HelpGetcodelenth(root->_left, eleminfo, len);
HelpGetcodelenth(root->_right, eleminfo, len);
}
//生成Huffman编码：
//1.首先将保存元素信息的buf进行排序，用字符长度信息为第一字段进行排序，字符按照字典序进行第二字段的排序也就是同一层的排序
//要在一起而且同一层的要用字典来进行排序
void wbxzip::Generatehuffmancode(vector<bytelenthinfo>& eleminfo)
{
vector<bytelenthinfo> temp(eleminfo);
sort(temp.begin(), temp.end());//这里直接用默认的小于的比较方式我们只将其<运算符重载
size_t index = 0;//标记第一个编码长度不为0的字符
while (true)
{
if (temp[index]._codelength)
{
break;
}
index++;
}
if (index >= temp.size())
{
assert(false);
}
for (size_t i = index+1; i < temp.size(); i++)
{
if (temp[i]._codelength == temp[i - 1]._codelength)
{//如果这里是同一层的字符那么当前字符的编码就由前一个字符的编码+1而来
temp[i]._code = temp[i - 1]._code + 1;//用于调试
eleminfo[temp[i]._elem]._code = temp[i - 1]._code + 1;
}
else
{//如果不相同那么当前编码就由上一层编码的最后一个字符的编码+1然后左移层数差得到：
temp[i]._code = ((temp[i - 1]._code + 1) << (temp[i]._codelength - temp[i - 1]._codelength));//用于调试
eleminfo[temp[i]._elem]._code = ((temp[i - 1]._code + 1) << (temp[i]._codelength - temp[i - 1]._codelength));
}
}
}
//统计LZ77压缩结果中字符出现的频次信息，这里我们在统计的时候通过判断当前标志位否为1来判断当前的字符是否是长度距离对
void wbxzip::StatisticsAppearcount()
{
size_t flagindex = 0;
uch bit = 0;
uch bitcount = 0;
size_t distindex = 0;
for (size_t i = 0; i < _ByteLenthLZ77.size(); i++)
{
if (bitcount ==0)
{
bit = _FlagInfoLZ77[flagindex++];
bitcount = 8;
}
if (bit & 0x80)
{//当前为长度距离信息
//这里不用给获取到的长度距离编码加257，因为我们Huffman压缩的时候最终用这里的区间编码来构造Huffman树??？？？？？？？？？？？？？？？？？？他哪里给加了257
uch index =0;//这里无用只是占位符
_ByteLenthInfo[GetLenthcode(_ByteLenthLZ77[i],index)]._appearcount++;
_DistInfo[GetDistcode(_DistIfoLZ77[distindex++])]._appearcount++;
}
else
{//当前长度字符信息为字符
_ByteLenthInfo[_ByteLenthLZ77[i]]._appearcount++;
}
bit <<= 1;
bitcount--;
}
//让256出现一次因为256是块结束的标志，当解压到256的时候说明块解压缩结束了//？？？？？？？？？？？？？不知道啥意思
//这里256是不会在LZ77压缩结果中出现的，因为0-255个字符中没有256，而就算出现了长度为256那么我们也可以在解压缩的时候区分，
//因为我们在解压缩的时候有标记位信息当标志位为1的时候那么才是距离而255解压的时候对应的标志位肯定不是1？？？？？这在解压缩的时候是否会缺一个
_ByteLenthInfo[256] ._appearcount= 1;
}
//获取当前长度的区间编码：
ush wbxzip::GetLenthcode(ush lenth,uch& index)
{
for (int i = 0; i < 29; i++)
{
if (lenth >= lengthInterval[i].interval[0] && lenth <= lengthInterval[i].interval[1])
{
index = i;
return lengthInterval[i].code;
}
}
assert(false);
return 0;
}
//获取当前距离的区间编码：
ush wbxzip::GetDistcode(ush dist)
{
for (int i = 0; i < 30; i++)
{
if (dist >= distInterval[i].interval[0] && dist <= distInterval[i].interval[1])
{
return distInterval[i].code;
}
}
return 0;
}
//求前后文最长匹配长度：
//在这个函数中我们要求出从match_head开始和从start开始两者最长匹配长度和距离：
ush wbxzip::maxlenth(ush start, ush match_head, ush& matchdis)
{
//这里因为大文件加入了哈希掩码可能会导致哈希表成链状，所以这里我们要控制匹配次数最多匹配255次就够了
ush MaxMachthcount = 255;
//这里因为匹配距离也就是查询距离还不可以超过MAX_DIST所以这里我们也要有所限制：
ush limit = start >= MAX_DIST ? start - MAX_DIST : 0;
ush max_lenth = 0;//这里最长匹配如果到了255之后如果再++那么就会加到0，1，2所以用ush来定义max_lenth
do
{
ush pstart = start;
ush pend = start + MAX_ATHCH;//最大匹配长度//这里因为最大匹配长度为255所以有可能会超出长度范围所以用ush来表示
ush curmatch_head = match_head;//当前的match_head
uch cur_lenth = 0;//当前的匹配长度
while (pstart < pend &&_pWin[pstart] == _pWin[curmatch_head])
{
pstart++;
curmatch_head++;
cur_lenth++;
}
if (cur_lenth>max_lenth)
{
matchdis = start - match_head;
max_lenth = cur_lenth;
}
} while ((_ht.GetPrevMatch(match_head)>limit)&&(MaxMachthcount--));
//这里如果最大匹配距离大于MAX_DIST那么我们就舍弃本次匹配：
if (matchdis > MAX_DIST)
{
max_lenth = 0;
}
return max_lenth;
}
解压缩相关
void wbxzip::UNCompressFile(const string& filename)
{
//1.打开解压缩文件
FILE*fin = fopen(filename.c_str(), "rb");
//2.首先读取压缩文件中的文件后缀
string Fileprofix;
Fileprofix = Getfilename(filename);
Fileprofix += "unzip.";
get_line(Fileprofix, fin);
//3.打开要写入的解压缩文件：
fout = fopen(Fileprofix.c_str(), "wb");
FILE* fout2 = fopen(Fileprofix.c_str(), "rb");//用于长度距离对的时候将读取之前的字符
//4.开始解压缩
while (true)
{
//1.首先要读取保存的第一个字段判断当前是否为最后一个块
_islast = fgetc(fin);//如果是最后一块压缩文件那么保存的标志为0
//2.开始解压缩：
uch ch=0;
uch bitcount=0;
//1.首先读取编码位长信息，当时我们将所有的编码信息都写入到了文件当中
Getcodelenthinfo(fin);
//2.构造解码表
//长度字符解码表：
vector<DecodeTable> lenthcodetable;
GenerateDecode(lenthcodetable, _ByteLenthInfo);
//距离解码表：
vector<DecodeTable> disttable;
GenerateDecode(disttable, _DistInfo);
//接下来就是将文件中的数据一个一个进行解压缩：每次获取到一个编码我们就来判断
while (true)
{
ush symbol = UNCopressSymbol(fin, _ByteLenthInfo, lenthcodetable, ch, bitcount);
if (symbol < 256)
{
//当前解压出了一个字符：直接写入解压文件
fputc(symbol, fout);
}
else if (256 == symbol)
{
break;
}
else
{//解压缩出来了一个距离：那么我们要获取长度就需要获取长度的额外编码，
//因为当前长度在压缩的时候存入的是编码距离范围所以我们解压出来的也
//是长度的范围编码所以要获取到长度的额外编码长度将其从文件中读
//取出来然后用编码范围的开始加上额外编码那么就可以得到长度
size_t index = symbol - 257;
uch extencodelen = lengthInterval[index].extraBit;//扩展码的长度
ush extencode = 0;//扩展码
while (extencodelen--)
{//读取扩展码
GetNextBit(fin, extencode, ch, bitcount);
}
ush lenth = lengthInterval[index].interval[0] + extencode;//长度
//然后再求距离：
ush symbol = UNCopressSymbol(fin, _DistInfo, disttable, ch, bitcount);
extencodelen = distInterval[symbol].extraBit;//距离扩展码的长度
extencode = 0;
while (extencodelen--)
{//读取扩展码
GetNextBit(fin, extencode, ch, bitcount);
}
ush dist = distInterval[symbol].interval[0] + extencode;
//当读取到距离和长度之后那么我们就和LZ77一样向文件中写入信息：//
fflush(fout);//在用匹配还原前先将文件缓冲区中的数据刷新出去。
//如果当前位置为1那么就利用长度距离对来读取数据：
fseek(fout2, 0 - dist, SEEK_END);//将文件指针偏移到匹配字符串的位置
while (lenth--)
{//这里我们在前文中读取一个匹配字符就向后文中写一个匹配字符
uch ch = fgetc(fout2);//从解压缩文件中读取
fputc(ch, fout);
fflush(fout);//这里注意要及时刷新缓冲区，因为如果前文匹配字符串与后文匹配字符串又重叠那么就会造成
//还原不完整例如abc abc abc这里当前文匹配读取到第二个abc的时候后文写入的abc还在文件缓冲区中那么后文还原
//的字符就不完整。
}
}
}
if (!_islast)
{
break;
}
}
fclose(fout2);
fclose(fin);
fclose(fout);
}
//构造解码表
void wbxzip::GenerateDecode(vector<DecodeTable> &table, vector<bytelenthinfo> &eleminfo)
{
//用这里生成编码表我们就首先要将编码位长和符号数量统计出来这里我们采用map来统计，将每个编码位长对应一个符号数量那么我们再来进行操作就可以获得编码表
//1.统计每个编码位长对应的符号数量(这里的符号数量不用给太大只要给ush就可以了因为我们这里是按块解码所以符号数量不会超过32K)：
std::map<uch, ush> m;
for (auto &e : eleminfo)
{
m[e._codelength]++;
}
int index = 0;
//2.获取解码表中其余两个字段：首编码和符号索引
sort(eleminfo.begin(), eleminfo.end());//这里要排序是因为我们在解码的时候要通过字符索引来到字符长度信息中寻找相应信息
for (auto &e : m)
{
DecodeTable decode;
decode._decodelen = e.first;//编码位长
decode._lencount = e.second;//相同编码位长符号数量
if (index == 0)
{
decode._code = 0;//首字符编码
decode._charindex = 0;//字符索引
}
else
{//这里如果不是第一个解码信息那么就用上一个解码信息的中的首字符编码和字符个数来求出首字符编码
decode._code = (table[index - 1]._code + table[index - 1]._lencount) << (decode._decodelen - table[index - 1]._decodelen);
decode._charindex = table[index - 1]._lencount + table[index - 1]._charindex;
}
table.push_back(decode);
index++;
}
}
//解压缩算法：
//这里解压缩的时候需要解码表和长度距离表
ush wbxzip::UNCopressSymbol(FILE* fin, vector<bytelenthinfo>& codeinfo, vector<DecodeTable>& decTable,uch& ch,uch& bitcount)
{
ush i = 0;
ush codelen = decTable[0]._decodelen;
ush code = 0;
while (codelen--)
{
GetNextBit(fin, code, ch, bitcount);
}
ush num = 0;
while ((num = code - decTable[i]._code) >= decTable[i]._lencount)
{
i++;
//中间有可能会有一些长度没有出现：
//len:7--->code:126
//len:9--->code:508
//次数需要一次性读取两位，但是i只加一次
ush lenGap = decTable[i]._decodelen - decTable[i - 1]._decodelen;
while (lenGap--)
{
GetNextBit(fin, code, ch, bitcount);
}
}
//找出扩展的bit位
num += decTable[i]._charindex;
return codeinfo[num]._elem;
}
//获取下一个bit位：
//参数含义：fin：表示待解压缩的文件。
//code：从文件中获取的bit位保存到code中，这里的code可以是字符长度也可以是距离所以这里用ush表示
//ch：从文件文件中读取的bit位信息
//bitcount：当前从文件中已经读取了多少位到ch中
void wbxzip::GetNextBit(FILE* fin, ush& code, uch& ch, uch& bitcount)
{
if (0 == bitcount)
{
ch = fgetc(fin);
bitcount = 8;
}
code <<= 1;
if (ch & 0x80)
{
code |= 1;
}
ch <<=1;
bitcount--;
}
//将压缩文件中的编码位长信息读取到buf当中
//这里我们就不需要将全部的编码位长信息都读取到buf了，我们只需要读取那些编码位长不为0的信息
void wbxzip::Getcodelenthinfo(FILE* fin)
{
_ByteLenthInfo.clear();//这里将保存长度字符信息的buf清空来存储压缩文件当中出现次数不为0的字节
for (size_t i = 0; i < 286; i++)
{
uch codelenth = fgetc(fin);
if (codelenth)
{
bytelenthinfo elem;
elem._codelength = codelenth;
elem._elem = i;
_ByteLenthInfo.push_back(elem);
}
}
_DistInfo.clear();//录入距离信息
for (size_t i = 0; i < sizeof(distInterval)/sizeof(distInterval[0]); i++)
{
uch codelenth = fgetc(fin);
if (codelenth)
{
bytelenthinfo elem;
elem._codelength = codelenth;
elem._elem = i;
_DistInfo.push_back(elem);
}
}
}
//获取文件名
string wbxzip::Getfilename(const string& filename)
{
return filename.substr(0, filename.find('.'));
}
//获取文件后缀名
string wbxzip::Getfilepostfix(const string& file_name)
{
return file_name.substr(file_name.find_first_of('.') + 1);
}<main.cpp>//文件
#include "common.h"
#include "wbxzip.h"
#include "file_compress_huffman.h"
#include "LZ77.h"
//开始菜单
void manu1()
{
cout << "*——*——*——*——*——*——*——*——*——*——*——*——*" << endl;
cout << "|输入0：清屏 输入5：LZ77压缩 |" << endl;
cout << "*输入1：刷新菜单 输入6：LZ77解压缩 * " << endl;
cout << "|输入2：退出系统 输入7：ZIP压缩 |" << endl;
cout << "*输入3：Huffman压缩 输入8：ZIP解压缩 *" << endl;
cout << "|输入4：Huffman解压缩 |"<< endl;
cout << "*——*——*——*——*——*——*——*——*——*——*——*——*" << endl;
}
void lz77Compress()
{
cout << "请输入要压缩文件名:" ;
string filename;
cin >> filename;
LZ77 l;
l.CompressFile(filename);
string outfilename;
outfilename = l.Getfilename(filename);
outfilename += ".lz";
cout << "LZ77压缩完成,压缩文件名为：" << outfilename << endl;
}
void lz77UNCompress()
{
cout << "请输入要解压缩文件名:";
string filename;
cin >> filename;
LZ77 l;
l.UNCompressFile(filename);
string outfilename;
outfilename = l.Getfilename(filename);
outfilename += "lzun.";
outfilename += l.Getfilepostfix(filename);
cout << "LZ77解压缩完成,解压缩文件名为：" << outfilename << endl;
}
void HuffmanCompress()
{
cout << "请输入要解压缩文件名:";
string filename;
cin >> filename;
file_compress_huffman f;
f.compress_file(filename);
string outfilename;
outfilename = f.get_file_name(filename);
outfilename += ".hz";
cout << "HUFFMAN压缩完成,压缩文件名为：" << outfilename << endl;
}
void HuffmanUNCompress()
{
cout << "请输入要解压缩文件名:";
string filename;
cin >> filename;
file_compress_huffman f;
f.un_compress_file(filename);
string outfilename;
outfilename = f.get_file_name(filename);
outfilename += "huffun.";
outfilename += f.get_postfix(filename);
cout << "HUFFMAN解压缩完成,解压缩文件名为：" << outfilename<< endl;
}
void ZIPCompress()
{
cout << "请输入要解压缩文件名:";
string filename;
cin >> filename;
wbxzip w;
w.CompressFile(filename);
string outfilename;
outfilename = w.Getfilename(filename);
outfilename += ".wbxzip";
cout << "ZIP压缩完成,压缩文件名为：" << outfilename << endl;
}
void ZIPUNCompress()
{
cout << "请输入要解压缩文件名:";
string filename;
cin >> filename;
wbxzip w;
w.UNCompressFile(filename);
string outfilename;
outfilename = w.Getfilename(filename);
outfilename += "unzip.";
outfilename += w.Getfilepostfix(filename);
cout << "ZIP解压缩完成,解压缩文件名为：" << outfilename << endl;
}
void manu2()
{
int option = 0;
manu1();
while (1)
{
cin >> option;
switch (option)
{
case 0:system("cls"); break;
case 1:manu1(); break;
case 2:exit(1); break;
case 3:HuffmanCompress(); break;
case 4:HuffmanUNCompress(); break;
case 5:lz77Compress(); break;
case 6:lz77UNCompress(); break;
case 7:ZIPCompress(); break;
case 8:ZIPUNCompress(); break;
default:cout << "输入非法选项请重新从1，2，3，4，5，6中选择输入"; break;
}
cout << "请做出下一步选择(提示可以通过1来查看菜单)" << endl;
}
}
int main()
{
manu2();
return 0;
}4.压缩测试
4.1压缩文本
这里我们压缩一个文本文件这里还原之后也是百分百还原的，这里我就不做演示了，读者有兴趣可以自己尝试这里我们就不放对比结果了这里可以看到我们的压缩率差不多为72%
在看一下Huffman压缩和LZ77压缩：
上面是LZ77的压缩结果我们可以看到压缩率为：差不多为62%
再看Huffman压缩
压缩率为18%果然还是Huffman最次
当然以上测试结果的压缩率每次并不都是一样的对于真正的ZIP压缩压缩率可以达到97%这是因为真正的zip还对保存的字符长度信息做了压缩处理。我们这里并没有。
4.2.图片压缩
这里我们来看压缩率几乎为0，但是我们看到ZIP对于图片压缩的压缩率也为0我们心里一下就平衡许多了，这是因为对于二进制文件不同于文本文件对于一些字符的重复出现次数较少，那么无论是对于Huffman压缩还是LZ77压缩都是不利的，一般的图片压缩都采用有损压缩这里我们的GZIP是无损压缩。
以上测试只测试了一组结果，对于压缩率的测试可能有偏差。如果读者有兴趣可以复制全部代码自己进行实现测试。