1.需求分析
利用小堆，huffman編碼，文件流操作，二進制文件的讀寫實現對普通文件的壓縮和解壓過程。
2.能力要求
A.熟悉對文件的讀寫操作。
B.熟悉小堆的原理。
C.熟悉HuffmanTree的實現原理、
D.會編碼的獲取。
E.對編碼信息處理和存儲。
F.最重要一點，要理解壓縮和解壓縮的過程。
3.模塊介紹。
A設計的存儲結構。.
B.壓縮過程.
C.解壓縮過程。
D.編碼的獲取。.
E.HuffmanTree的實現。
F.小堆的實現。
G.讀文件的操作。
4.壓縮和解壓縮的原理。
壓縮過程：利用數據結構，對文件裡面的字符進行統計。以字符出現的頻率構建小堆，再利用小堆，構建HuffmanTree。以HuffmanTree左右孩子遍歷，左為0，右為1.將統計出來的結果存放到自己設計的結構中。在通過對字符編碼進行位進制壓縮，可以實現壓縮過程。
解壓縮過程：利用字符和統計次數寫配置文件，解壓縮就可以通過配置文件建立一顆HuffmanTree，在根據壓縮文件內容遍歷HuffmanTree，葉子節點即為原來的一個字符。
5.模塊具體分析。
A設計的存儲結構。
typedef long longtype;
struct FileInfo
{
unsigned char _ch; //字符
longtype _count; //計數器
string _code; //Huffman編碼
}
B.壓縮過程.
1.先把文件內容讀進來，並進行字符統計。
2.統計字符出現字數，存入_count。
3.依據每個節點的_count值，構建相應的huffman樹。
4.將編碼壓縮，存入文件。
5.把字符和出現次數按照（字符，次數）的形式，每行的保存到配置文件裡。
C.解壓縮過程。
1.讀取配置文件裡的內容，構建HuffmanTree。
2.根據壓縮文件，和重建的huffman樹解壓.
3.根據壓縮文件字符編碼解壓文件.
D.編碼的獲取
void huffmancode(HuffManNode* root, string& code)
E.HuffmanTree的實現。
struct HuffManNode
{
HuffManNode *_parent;
HuffManNode *_right;
HuffManNode *_left;
T _weight;
}
class HuffManTree
{
public:
typedef HuffManNode Node;
//仿函數
template
struct Compare
{
bool operator()(Node*& L, Node*& R)
{
return L->_weight < R->_weight;
}
};
private:
Node* _root;
F.小堆的實現。
Heap(const T* array, size_t size)
{
_array.reserve(size);
for (size_t i = 0; i < size; ++i)
{
_array.push_back(array[i]);
}
for (int begin = _array.size() / 2 - 1;
begin >= 0; begin--)
{
_AdjustDown(begin);
}
}
G.讀文件的操作。
bool readline(FILE* str, string& code)
小堆代碼：
#pragma once
#include
#include
template
class Less
{
public:
bool operator()(const T& l, const T& r)
{
return l < r;
}
};
template
class Greater
{
public:
bool operator()(const T& l, const T& r)
{
return l > r;
}
};
// 小堆
//template
template class Compare = Less>
class Heap
{
public:
Heap()
{}
Heap(const T* array, size_t size)
{
_array.reserve(size);
for (size_t i = 0; i < size; ++i)
{
_array.push_back(array[i]);
}
for (int begin = _array.size() / 2 - 1;
begin >= 0; begin--)
{
_AdjustDown(begin);
}
}
Heap(vector& array)
{
_array.swap(array);
for (int begin = _array.size() / 2 - 1;
begin >= 0; begin--)
{
_AdjustDown(begin);
}
}
void Push(const T& x)
{
_array.push_back(x);
//?
_AdjustUp(_array.size() - 1);
}
void Pop()
{
_array[0] = _array[_array.size() - 1];
_array.pop_back();
_AdjustDown(0);
}
bool Empty()
{
return _array.empty();
}
const T& Top()
{
return _array[0];
}
protected:
void _AdjustDown(int root)//size
{
int left = root * 2 + 1;
int right = left + 1;
// 左孩子已不存在，則root為葉子節點，不用再調整
while (left < _array.size())
{
// 找左右孩子裡面小的那個
int key = left;
if (right < _array.size()
&& Compare()(_array[right], _array[left]))
{
key = right;
}
// 如果min小則跟根節點交換
//Compare com;
//if (_array[min] < _array[root])
if (Compare()(_array[key], _array[root]))
{
swap(_array[key], _array[root]);
root = key;
left = 2 * root + 1;
right = left + 1;
}
else
{
break;
}
}
}
void _AdjustUp(int child)
{
while (1)
{
int root = (child - 1) / 2;
//if (_array[root] > _array[child])
if (Compare()(_array[root], _array[child]))
{
swap(_array[root], _array[child]);
child = root;
}
else
{
break;
}
if (root == 0)
break;
}
}
private:
vector _array;
};
HuffmanTree代碼：
#pragma once
#include"heap.h"
template
struct HuffManNode
{
HuffManNode *_parent;
HuffManNode *_right;
HuffManNode *_left;
T _weight;
HuffManNode(T weight)
: _parent(NULL)
, _right(NULL)
, _left(NULL)
, _weight(weight)
{
}
};
template
class HuffManTree
{
public:
typedef HuffManNode Node;
//仿函數
template
struct Compare
{
bool operator()(Node*& L, Node*& R)
{
return L->_weight < R->_weight;
}
};
public:
void CreatHuffmanTree(const T* array, size_t size, const T& invalid)
{
_CreatHuffmanTree(array, size, invalid);
}
HuffManTree()
:_root(NULL)
{
}
~HuffManTree()
{
_Destory(_root);
}
Node* GetRoot()
{
return _root;
}
protected:
void _CreatHuffmanTree(const T* array, size_t size, const T& invalid)
{
//將數據存到最小堆中(構建結點)
Heap> H;
for (int i = 0; i < size; i++)
{
if (array[i] != invalid)
{
Node* node = new Node(array[i]);
H.Push(node);
}
}
//取堆中的最小兩個值，作為節點構建Huffman樹。
Node* parent = H.Top();
while (H.Size() > 1)
{
Node* left = H.Top();
H.Pop();
Node* right = H.Top();
H.Pop();
parent = new Node(left->_weight + right->_weight);
//構建父節點
parent->_left = left;
parent->_right = right;
left->_parent = parent;
right->_parent = parent;
H.Push(parent);
}
_root = parent;
}
bool _Destory(Node*& root)
{
if (root)
{
_Destory(root->_left);
_Destory(root->_right);
delete root;
root = NULL;
}
return true;
}
private:
Node* _root;
};
文件壓縮實現：
#pragma once
//#include"HuffMan.h"
//#include
//#include
typedef long longtype;
struct FileInfo
{
unsigned char _ch; //字符
longtype _count; //計數器
string _code; //Huffman編碼
FileInfo(longtype count = 0)
:_ch(0)
, _count(count)
, _code(NULL)
{}
FileInfo operator+(const FileInfo& info) const
{
FileInfo tmp;
tmp._count = _count + info._count;
return tmp;
}
bool operator!=(const FileInfo& info) const
{
return _count != info._count;
}
bool operator<(const FileInfo& info) const
{
return _count < info._count;
}
};
ostream& operator<<(ostream& os, const FileInfo& info)
{
os << info._ch << ":" << info._count;
return os;
}
class FileCompress
{
public:
FileCompress()
{
cout << "aaaaa" << endl;
/*for (int i = 0; i < 256; ++i)
{
_info[i]._ch = i;
_info[i]._count = 0;
}*/
}
void huffmancode(HuffManNode* root, string& code)
{
if (root == NULL)
{
return;// root->_right;
}
huffmancode(root->_left, code + '0');
huffmancode(root->_right, code + '1');
if (root->_left == NULL&&root->_right == NULL)
{
_info[root->_weight._ch]._code = code; //生成並保存huffman編碼
}
code.empty();//清空上次所存數據，為下次做准備
}
//文件壓縮
void filecompress(const char* filename)
{
//1.先把文件內容讀進來，並進行字符統計
FILE* read = fopen(filename, "rb");
if (read == NULL)
{
return;
}
char ch = fgetc(read);
//2.統計字符出現字數，存入_count
while (ch != EOF)
{
_info[(unsigned char)ch]._count++;//
ch = fgetc(read);
}
//3.依據每個節點的_count值，構建相應的huffman樹
HuffManTree tree;
FileInfo invalid(0);
tree.CreatHuffmanTree(_info, 256, invalid);
string code;
huffmancode(tree.GetRoot(), code);
//4.將編碼壓縮，存入文件
string compressfile = filename;
compressfile += ".compress";
FILE* fout = fopen(compressfile.c_str(), "wb");
assert(fout);
fseek(fout, 0, SEEK_SET);//fout文件指針，0位數，seek_set表示文件開頭
int index = 0;
unsigned char comch = 0;
ch = fgetc(read);
while (ch != EOF)
{
string& code = _info[(unsigned char)ch]._code;
//位進制壓縮
for (int i = 0; i < 256; i++)
{
comch << 1;
if (code[i] == '1')
{
comch |= 1;
}
if (++index == 8)
{
fputc(comch, fout);
index = 0;
comch = 0;
}
}
ch = fgetc(read);
}
if (index != 0)
{
comch << (8 - index);
fputc(comch, fout);
}
//5.把字符和出現次數按照（字符，次數）的形式，每行的保存到配置文件裡
string configfile = filename;
configfile = ".config";
FILE* config = fopen(configfile.c_str(), "w");
assert(config);
string info;
char count[20];
for (int i = 0; i < 256; i++)
{
info.clear();
if (_info[i] != invalid)
{
info = _info[i]._ch;
info += ',';
itoa(_info[ch]._count, count, 10);
info += count;
info += '\n';
fputs(info.c_str(), config);
}
}
fclose(read);
fclose(fout);//壓縮
fclose(config);//配置
}
void uncompressfile(const char* filename)
{
//讀取配置文件裡的內容
string unfile = filename;
unfile += ".comm";
FILE* file = fopen(unfile.c_str(), "rb");
assert(file);
string code;
char ch = 0;
while (readline(file, code))
{
//若讀到空行，則為‘\0’
if (!code.empty())
{
ch = code[0];
_info[(unsigned char)ch]._count = atoi(code.substr(2).c_str());
code.clear();
}
else
{
code = '\n';
}
}
//根據配置文件構建huffman樹
HuffManTree tree;
FileInfo invalid(0);
tree.CreatHuffmanTree(_info, 256, invalid);
HuffManNode* root = tree.GetRoot();
//根據壓縮文件，和重建的huffman樹解壓
string uncompress = filename;
uncompress += ".uncompress";
FILE* fin = fopen(uncompress.c_str(), "wb");
assert(fin);
string compress = filename;
compress += ".compress";
FILE* fout = fopen(compress.c_str(), "rb");
assert(fout);
//根據壓縮文件字符編碼解壓文件
HuffManNode* str = root;
int pos = 8;
ch = fgetc(fin);
assert(ch);
longtype count = root->_weight._count;
while (1)
{
if (pos == 0)
{
pos = 8;
ch = fgetc(fin);
}
--pos;
if (ch & 1 << pos)
str = str->_right;
else
str = str->_left;
if (str->_left == NULL && str->_right == NULL)
{
fputc(str->_weight._ch, fout);
str = root;
if (--count == 0)
break;
}
}
fclose(fout);
fclose(fin);
}
bool readline(FILE* str, string& code)
{
assert(str);
char ch = fgetc(str);
if (ch == EOF)
{
return false;
}
while (ch != '\n'&&ch != EOF)
{
code += ch;
ch = fgetc(str);
}
return true;
}
protected:
FileInfo _info[256];
};
