文件的压缩与解压
u 开发环境：vs2013
u 开发技术：vector、堆、哈夫曼树、文件部分函数的操作
u 项目描述：文件压缩是把一个占内存比较大的文件压缩成为一个占内存比较小的文件，节省了磁盘的空 间，传输时也比较方便。解压是把压缩的文件还原成原来的文件，读写比较方便。
√ 可以压缩与解压小文件，也可以压缩与解压大文件。
√ 在Debug下，压缩和解压6M左右文件，需要25s左右，在Release下，需要2s左右。
√ 有配置文件，压缩开发技术：vector、堆、哈夫曼树、文件部分函数的操作
u 遇到的问题：√ 在压缩过程中不够8位会补零，但在解压过程中会把零读出来，这样就不对了。为了解决 这个问题。我在解压过程中定义了一个总长度，它写入一个字符，总长度就减1，当长度 减为0，就不进去了。
√ 有时解压大文件时，字数不想等。于是我就把’w’换成了’wb’，把’r'换了’rb’因 为用文本模式打开时，遇到’\n’，会多加’\r’，但用二进制模式打开就不会有这样的 问题。
√ 有时读大文件时，会读不全。因此我就把EOF换成了feof。因为EOF是以-1为结束标志 的，但文件中出现-1它就不会读下去了。如果换成feof的话，它是以“文件结束”为标 志。这样就不会出现读不完的情况。
compress.h中
#ifndef __Compress_H_
#define __Compress_H_
#include <string>
typedef long long LongType;
struct CharInfo
{
unsigned char _ch;//字符
LongType _count;//出现次数
string _code;//哈夫曼编码
CharInfo(unsigned char ch = '0')
:_ch(ch)
, _count(0)
, _code("")
{}
CharInfo(LongType count)
:_count(count)
, _ch(0)
, _code("")
{}
//重载运算符“>”
bool operator >(const CharInfo& com)const
{
return _count > com._count;
}
//重载运算符“!=”
bool operator !=(CharInfo com)const
{
return _count != com._count;
}
//重载运算符“+”
CharInfo operator+(const CharInfo& com)const
{
return CharInfo(_count + com._count);
}
};
class FileCompress
{
public:
//压缩
FileCompress()
{
for (size_t i = 0; i < 256; i++)
{
_info[i]._ch = i;
}
}
void Compress(const char* file)
{
//读取文件
FILE *fout = fopen(file, "rb");
unsigned char ch = 0;
assert(fout);
//统计每个字符出现的次数
ch = fgetc(fout);
while (!feof(fout))
{
_info[(unsigned char)ch]._count++;
ch = fgetc(fout);
}
//用次数建立哈夫曼树
const CharInfo invalid((unsigned char)0);
HaffmanTree<CharInfo> tree(_info, 256,invalid);
//生成哈夫曼编码
string tmp;
_CreateHaffmanCode(tree.GetRoot(), tmp);
//压缩
fseek(fout, 0, SEEK_SET);//从文件的首字符开始压缩
//压缩后的文件名
string comfile = file;
comfile += ".haffman";
FILE *fin = fopen(comfile.c_str(), "wb");
assert(fin);
unsigned char value = 0;
size_t index = 0;//标记当前位
ch = fgetc(fout);
while (!feof(fout))
{
string code = _info[ch]._code;
for (size_t i = 0; i < code.size(); i++)
{
if (code[i] == '1')
{
value <<= 1;
value |= 1;
}
else
{
value <<= 1;
}
//满8个字节，将其写入到压缩文件中
if (++index == 8)
{
fputc(value, fin);
value = 0;
index = 0;
}
}
ch = fgetc(fout);
}
//如果写入完，value 没有写满8位，把剩余的压入压缩文件中
if (index != 0)
{
value <<= (8 - index);
fputc(value, fin);
}
//配置文件
string configfile = file;
configfile += ".config";
FILE* finfo = fopen(configfile.c_str(), "wb");
assert(finfo);
//将字符的总个数写进配置文件
char infostr[32];
//将出现的字符以及次数写进配置文件
string str;
for (size_t j = 0; j < 256; j++)
{
if (_info[j]._count > 0)
{
str.push_back((unsigned char)j);
str.push_back(',');
_itoa(_info[j]._count, infostr, 10);
str += infostr;
fputs(str.c_str(), finfo);
fputc('\n', finfo);
str.clear();
}
}
fclose(fout);
fclose(fin);
fclose(finfo);
}
//解压
void UnCompress(const char *file)
{
unsigned char ch = 0;
string fconfig = file;
fconfig += ".config";
//读压缩文件
FILE* fout = fopen(fconfig.c_str(), "rb");
assert(fout);
string tmp;
//字符出现的次数
while (ReadLine(fout, tmp))
{
if (!tmp.empty())
{
//那到字符
ch = tmp[0];
//获取字符的次数
_info[(unsigned char)ch]._count = atoi(tmp.substr(2).c_str());
tmp.clear();
}
else
{
tmp = '\n';
}
}
//重建哈夫曼树
CharInfo invalid((unsigned char)0);
HaffmanTree<CharInfo> h(_info, 256, invalid);
HaffmanTreeNode<CharInfo>*root = h.GetRoot();
//解压
string output = file;
output += ".uncom";
FILE* fin = fopen(output.c_str(), "wb");
assert(fin);
//根据压缩文件，还原文件
string Haffmanfile = file;
Haffmanfile += ".haffman";
FILE* fcom = fopen(Haffmanfile.c_str(), "rb");
assert(fcom);
HaffmanTreeNode<CharInfo>*cur = root;
ch = fgetc(fcom);
int pos = 8;
LongType len = root->_weight._count;
while (len > 0)
{
while (cur->_left &&cur->_right)
{
if (pos == 0)
{
ch = fgetc(fcom);
pos = 8;
}
--pos;
//与1，走右树
if (ch&(1 << pos))
{
cur = cur->_right;
}
//与0，走左树
else
{
cur = cur->_left;
}
}
if (cur)
{
fputc(cur->_weight._ch, fin);//写进解压文件
cur = root;
}
--len;
}
fclose(fout);
fclose(fin);
fclose(fcom);
}
protected:
//创建哈夫曼编码
void _CreateHaffmanCode(HaffmanTreeNode<CharInfo>*root, string tmp)
{
//判空
if (root == NULL)
{
return;
}
if (root->_left == NULL&&root->_right == NULL)
{
//找到下标，把编码写到_code中
int index = (root->_weight)._ch;
_info[index]._code = tmp;
}
else
{
//左树写0
if (root->_left)
{
tmp.push_back('0');
_CreateHaffmanCode(root->_left, tmp);
tmp.pop_back();
}
//右树写1
if (root->_right)
{
tmp.push_back('1');
_CreateHaffmanCode(root->_right, tmp);
tmp.pop_back();
}
}
}
//读一行
bool ReadLine(FILE* file, string& tmp)
{
assert(file);
char ch = fgetc(file);
if (feof(file))
{
return false;
}
while (ch != '\n')
{
tmp += ch;
ch = fgetc(file);
}
return true;
}
protected:
CharInfo _info[256];
};
#endif //__Compress_H_HaffmanTree.h中
#ifndef __HaffmanTree_H_
#define __HaffmanTree_H_
#include "Heap.h"
template<class T>
struct HaffmanTreeNode
{
typedef HaffmanTreeNode<T> Node;
T _weight;
Node* _left;
Node* _right;
HaffmanTreeNode(const T& weight)
:_weight(weight)
, _left(NULL)
, _right(NULL)
{}
};
template<class T>
class HaffmanTree
{
typedef HaffmanTreeNode<T> Node;
public:
HaffmanTree()
:_root(NULL)
{}
HaffmanTree(const T* arr, size_t size)
{
_root = _Create(arr, size);
}
//构造函数
HaffmanTree(const T* arr, size_t size, const T& invalid)
{
_root = _Create(arr, size, invalid);
}
~HaffmanTree()
{
if (_root)
{
_Destroy(_root);
}
}
Node* GetRoot()
{
return _root;
}
protected:
//创建哈夫曼树
Node* _Create(const T* arr, size_t size, const T& invalid)
{
struct compare
{
bool operator ()(const Node *left, const Node *right)
{
return left->_weight > right->_weight;
}
};
Heap<Node*,compare> _heap;
//把值放到vector中
for (size_t i = 0; i < size; ++i)
{
if (arr[i] != invalid)
{
Node *tmp = new Node(arr[i]);
_heap.Push(tmp);
}
}
//构造哈夫曼树
while (_heap.Size() > 1)
{
Node *left = _heap.Top();
_heap.Pop();
Node*right = _heap.Top();
_heap.Pop();
Node *parent = new Node(left->_weight + right->_weight);
parent->_left = left;
parent->_right = right;
_heap.Push(parent);
}
return _heap.Top();
}
//释放节点
void _Destroy(Node* root)
{
if (root->_left == NULL && root->_right == NULL)
{
delete root;
root = NULL;
}
else
{
_Destroy(root->_left);
_Destroy(root->_right);
}
}
private:
Node *_root;
};
#endif //__HaffmanTree_H_Heap.h中
#ifndef __Heap_H_
#define __Heap_H_
#include<vector>
#include<assert.h>
template<class T>
//比较器
class Less
{
public:
bool operator() (const T& left, const T& right)
{
return left > right;
}
};
template<class T>
class Greater
{
public:
bool operator() (const T& left, const T& right)
{
return left < right;
}
};
template<class T, class Compare = Less<T> >
class Heap
{
public:
//构造函数
Heap()
:_arr(NULL)
{}
Heap(const T* arr, int size)
{
assert(arr);
_arr.reserve(size);
for (int i = 0; i < size; i++)
{
_arr.push_back(arr[i]);
}
int begin = _arr.size() / 2 - 1;
while (begin >= 0)
{
_AdjustDown(begin);
begin--;
}
}
//拷贝构造
Heap(vector<T>& s)
{
_arr = s;
int begin = _arr.size() / 2 - 1;
while (begin >= 0)
{
_AdjustDown(begin);
begin--;
}
}
void Push(const T& x)
{
_arr.push_back(x);
int begin = _arr.size();
_AdjustUp(begin);
}
void Pop()
{
_arr[0] = _arr[_arr.size() - 1];
_arr.pop_back();
_AdjustDown(0);
}
void Clear()
{
_arr.clear();
}
bool Empty()
{
return _arr.empty();
}
T& Top()
{
if (!Empty())
{
return _arr[0];
}
exit(1);
}
size_t Size()
{
return _arr.size();
}
protected:
//下调
void _AdjustDown(int parent)
{ // 从根节点向下调整
int size = _arr.size();
int left = parent * 2 + 1;
int right = left + 1;
int key = left;
while (left < size)
{//Compare()仿函数
//if (right < size && array[left] > array[right])
if (right < size && Compare()(_arr[left], _arr[right])) //右边小
{
key = right;
}
else
{
key = left;
}
//if ((array[key] > array[parent]))
if (Compare()(_arr[key], _arr[parent]))
{
break;
}
//else if (array[parent] > array[key])
else if (Compare()(_arr[parent], _arr[key])) //左边小
{
swap(_arr[key], _arr[parent]);
}
parent = key;
left = parent * 2 + 1;
right = left + 1;
}
}
//上调
void _AdjustUp(int child)
{ //从叶子节点或子节点向上调整
int size = _arr.size();
if (size == 0 || size == 1)
{
return;
}
int parent = (child - 2) / 2;
int left = parent * 2 + 1;
int right = left + 1;
int key = 0;
while (parent >= 0)
{
//if (right < size && array[left] > array[right])
if (right < size && Compare()(_arr[left], _arr[right]))
{
key = right;
}
else
{
key = left;
}
//if (array[parent] > array[key])
if (Compare()(_arr[parent], _arr[key]))
{
swap(_arr[parent], _arr[key]);
}
else
{
break;
}
if (parent == 0)
{
break;
}
parent = (parent - 1) / 2;
left = parent * 2 + 1;
right = left + 1;
}
}
private:
vector<T> _arr;
};
#endif //__Heap_H_test.cpp中
#define _CRT_SECURE_NO_WARNINGS 1
#include<time.h>
#include <iostream>
using namespace std;
#include "HaffmanTree.h"
#include "Compress.h"
void Test()
{
double t1;
double t2;
FileCompress f;
//f.Compress("input.txt");
f.Compress("mnt.txt");
t1 = clock();
printf("压缩文件需要的时间: %f s \n", t1 / CLOCKS_PER_SEC);
//f.UnCompress("input.txt");
f.UnCompress("mnt.txt");
t2 = clock();
printf("解压缩文件需要的时间: %f s \n", t2 / CLOCKS_PER_SEC);
}
int main()
{
Test();
system("pause");
return 0;
}免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
