// 包含头文件
#include
#include
#include
#include
#include <Windows.h>
using namespace std;
const int N = 127; // 字符集大小
// 定义哈夫曼树结构体
typedef struct {
char data; // 存储字符
int weight; // 存储字符出现的次数
int parent, lchild, rchild; // 存储双亲节点、左孩子节点、右孩子节点的下标
} HTNode, *HuffmanTree;
// 定义哈夫曼编码结构体
typedef struct {
char data; // 存储字符
string code; // 存储哈夫曼编码
} HCNode, *HuffmanCode;
// 统计字符出现的次数
void frequencyRecord(HuffmanTree& HT) {
ifstream originFile('poem.txt'); // 打开文件
if (!originFile) {
cout << 'Can't find the file!' << endl;
}
else {
char _data;
int frequency[N + 1] = {0}; // 统计字符出现的次数，下标为字符的ASCII码值
while (!originFile.eof()) { // 读取文件内容
if (originFile.get(_data)) {
frequency[_data]++; // 统计字符出现的次数
}
}
originFile.close(); // 关闭文件
HT = new HTNode[2 * N]; // 动态分配内存空间
int k = 0; // 结点下标
for (int i = 0; i <= N; i++) { // 将字符出现次数不为0的加入哈夫曼树
if (frequency[i] != 0) {
HT[++k].data = static_cast(i); // 存储字符
HT[k].weight = frequency[i]; // 存储字符出现的次数
}
}
for (int i = k + 1; i <= 2 * N - 1; i++) { // 将剩余结点初始化
HT[i].weight = HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
}
for (int i = k + 1; i <= 2 * N - 1; i++) { // 构造哈夫曼树
int s1 = 0, s2 = 0; // s1、s2分别为最小的两个权值
int w1 = INT_MAX, w2 = INT_MAX; // w1、w2分别为最小的两个权值的下标
for (int j = 1; j < i; j++) { // 找出最小的两个权值
if (HT[j].parent == 0) { // 没有父节点
if (HT[j].weight < w1) {
w2 = w1, s2 = s1;
w1 = HT[j].weight, s1 = j;
}
else if (HT[j].weight < w2) {
w2 = HT[j].weight, s2 = j;
}
}
}
HT[s1].parent = i, HT[s2].parent = i; // 设置父节点
HT[i].lchild = s1, HT[i].rchild = s2; // 设置左右孩子节点
HT[i].weight = HT[s1].weight + HT[s2].weight; // 设置权值
}
}
}
// 生成哈夫曼编码
void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC) {
HC = new HCNode[N + 1]; // 动态分配内存空间
string code; // 存储哈夫曼编码
int child, parent; // child为当前节点的下标，parent为父节点的下标
for (int i = 1; i <= N; i++) { // 生成哈夫曼编码
code = '';
child = i, parent = HT[child].parent;
while (parent != 0) { // 从叶子节点开始向上遍历，直到根节点
if (HT[parent].lchild == child) {
code = '0' + code; // 左孩子节点编码为0
}
else {
code = '1' + code; // 右孩子节点编码为1
}
child = parent, parent = HT[child].parent; // 更新当前节点和父节点
}
HC[i].data = HT[i].data; // 存储字符
HC[i].code = code; // 存储哈夫曼编码
}
}
// 将源文件进行哈夫曼编码
void zip(HuffmanTree& HT, HuffmanCode& HC, vector& code) {
ofstream codeFile('codefile.txt'); // 打开编码文件
ifstream originFile('poem.txt'); // 打开源文件
if (!codeFile) {
cout << 'Can't find the file!' << endl;
}
else {
char _data;
cin.unsetf(ios::skipws);
while (!originFile.eof()) { // 读取源文件的每个字符
if (originFile.get(_data)) {
for (int i = 1; i <= N; ++i) {
if (HT[i].data == _data) { // 找到对应的哈夫曼编码
codeFile << HC[i]; // 将哈夫曼编码写入编码文件
code.push_back(HC[i]); // 将哈夫曼编码加入vector中，用于解码
}
}
}
}
}
codeFile.close(); // 关闭编码文件
}
// 将哈夫曼编码文件进行解码
void unzip(HuffmanTree& HT, HuffmanCode& HC, vector& code) {
ofstream decodeFile('decodefile.txt'); // 打开解码文件
if (!decodeFile) {
cout << 'Can't find the file!' << endl;
}
else {
vector::iterator v = code.begin();
while (v != code.end()) { // 读取哈夫曼编码
for (int i = 1; i <= N; ++i) {
if (HC[i] == *v) { // 找到对应的字符
decodeFile << HT[i].data; // 将字符写入解码文件
}
}
v++;
}
}
decodeFile.close(); // 关闭解码文件
}
// 将源文件以一个字节进行二进制编码后写入文件
void binaryCode() {
ofstream binaryFile('binaryfile.txt'); // 打开二进制编码文件
ifstream originFile('poem.txt'); // 打开源文件
originFile.seekg(0); // 将文件指针移到文件开头
if (!originFile) {
cout << 'Can't find the file!' << endl;
}
else {
char _data;
cin.unsetf(ios::skipws);
while (!originFile.eof()) { // 读取源文件的每个字符
if (originFile.get(_data)) {
bitset<8> data(_data); // 将字符转换为8位二进制数
binaryFile << data; // 将二进制数写入二进制编码文件
}
}
originFile.close(); // 关闭源文件
}
}
int main() {
system('color 02'); // 设置控制台颜色
cout << '' << endl;
cout << '哈夫曼编码解码器' << endl;
cout << '' << endl;
Sleep(1000); // 等待1秒
HuffmanTree HT;
HuffmanCode HC;
vector code;
cout << '\n\n\n需要进行编码的文件内容为：\n\n'; // 输出原文件内容
system('more poem.txt');
Sleep(2000); // 等待2秒
cout << '\n\n正在打开poem.txt进行二进制编码......' << endl;
Sleep(2000); // 等待2秒
binaryCode(); // 将源文件以一个字节进行二进制编码
cout << '\n\n二进制编码内容为：' << endl;
Sleep(2000); // 等待2秒
system('more binaryfile.txt'); // 输出二进制编码文件内容
Sleep(2000); // 等待2秒
cout << '\n\n正在统计字符权重......' << endl;
Sleep(2000); // 等待2秒
frequencyRecord(HT); // 统计字符出现的次数，并构造哈夫曼树
HuffmanCoding(HT, HC); // 生成哈夫曼编码
cout << '\n\n写入编码文件......' << endl;
Sleep(2000); // 等待2秒
zip(HT, HC, code); // 将源文件进行哈夫曼编码，并将哈夫曼编码写入编码文件
cout << '\n\n编码结果为：' << endl;
system('more codefile.txt'); // 输出编码文件内容
Sleep(2000); // 等待2秒
cout << '\n\n解码编码文件......' << endl;
Sleep(2000); // 等待2秒
unzip(HT, HC, code); // 将哈夫曼编码文件进行解码
cout << '\n\n解码结果为：' << endl;
Sleep(2000); // 等待2秒
system('more decodefile.txt'); // 输出解码文件内容
cout << '\n\n编码前占用字节空间：' << endl;
Sleep(1000); // 等待1秒
ifstream file_before('binaryfile.txt', ios::binary | ios::ate);
auto size_before = file_before.tellg(); // 获取文件大小
cout << size_before << endl; // 输出文件大小
file_before.close(); // 关闭文件
cout << '\n\n编码后占用字节空间：' << endl;
Sleep(1000); // 等待1秒
ifstream file_after('codefile.txt', ios::binary | ios::ate);
auto size_after = file_after.tellg(); // 获取文件大小
cout << size_after << endl; // 输出文件大小
file_after.close(); // 关闭文件
Sleep(1000); // 等待1秒
cout << '\n\n压缩率为：' << (static_cast(size_before - size_after)) / size_before * 100.0 << '%' << endl; // 计算压缩率并输出
Sleep(100000); // 等待100秒
return 0;
}
