1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;
//定义树
struct HTNode {
    char ch;
    int freq;
    HTNode *left, *right;
    HTNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};
//定义比较用的结构体
struct compare {
    bool operator()(HTNode* l, HTNode* r) {
        return l->freq > r->freq;
    }
};
//打开文件
void frqc(const char *file, unordered_map<char, int> &freq) {
    ifstream in(file, ios::in);
    if (!in.is_open()) {
        cout << "文件打开失败！" << endl;
        return;
    }

    char ch;
    while (in.get(ch)) {
        freq[ch]++;
    }
    in.close();
}
//复制粘贴来的哈夫曼树算法
HTNode* buildHuffmanTree(unordered_map<char, int> &freq) {
    priority_queue<HTNode*, vector<HTNode*>, compare> minHeap;
    for (auto pair : freq) {
        minHeap.push(new HTNode(pair.first, pair.second));
    }

    while (minHeap.size() != 1) {
        HTNode *left = minHeap.top(); minHeap.pop();
        HTNode *right = minHeap.top(); minHeap.pop();
        HTNode *top = new HTNode('\0', left->freq + right->freq);
        top->left = left;
        top->right = right;
        minHeap.push(top);
    }

    return minHeap.top();
}

//====================================================编码
void encode(HTNode* root, string str, unordered_map<char, string> &huffmanCode) {
    if (!root) return;
    if (!root->left && !root->right) {
        huffmanCode[root->ch] = str;
        cout << "字符: " << root->ch << " 编码: " << str << endl;
    }
    encode(root->left, str + "0", huffmanCode);
    encode(root->right, str + "1", huffmanCode);
}

string getEncodedString(const char *file, unordered_map<char, string> &huffmanCode) {
    ifstream in(file, ios::in);
    if (!in.is_open()) {
        cout << "文件打开失败！" << endl;
        return "";
    }

    string encodedString = "";
    char ch;
    while (in.get(ch)) {
        encodedString += huffmanCode[ch];
    }
    in.close();
    return encodedString;
}

void saveEncodedFile(const string &encodedString, const char *encodedFile) {
    ofstream out(encodedFile, ios::out | ios::binary);
    if (!out.is_open()) {
        cout << "文件保存失败！" << endl;
        return;
    }

    out << encodedString;
    out.close();
}
//===================================================计算压缩比
double calculateCompressionRatio(const char *originalFile, const char *encodedFile) {
    ifstream inOriginal(originalFile, ios::binary | ios::ate);
    ifstream inEncoded(encodedFile, ios::binary | ios::ate);
    if (!inOriginal.is_open() || !inEncoded.is_open()) {
        cout << "文件打开失败！" << endl;
        return 0.0;
    }

    double originalSize = inOriginal.tellg();
    printf("编码前的比特数：%d\n", &originalSize);
    double encodedSize = inEncoded.tellg() / 8.0; // 比特数除以8得到字节数
    inOriginal.close();
    inEncoded.close();

    return encodedSize/originalSize ;
    
}

//=================================解码
void decode(HTNode* root, const string &encodedString, const char *decodedFile) {
    ofstream out(decodedFile, ios::out);
    if (!out.is_open()) {
        cout << "文件保存失败！" << endl;
        return;
    }

    HTNode* curr = root;
    for (char bit : encodedString) {
        if (bit == '0') {
            curr = curr->left;
        } else {
            curr = curr->right;
        }

        if (!curr->left && !curr->right) {
            out.put(curr->ch);
            curr = root;
        }
    }
    out.close();
}


int main() {
    const char *inputFile = "stdio.h";//直接读取同目录下的文件
    const char *encodedFile = "encoded.bin";
    const char *decodedFile = "decoded.txt";

    unordered_map<char, int> freq;
    frqc(inputFile, freq);

    HTNode* root = buildHuffmanTree(freq);

    unordered_map<char, string> huffmanCode;
    encode(root, "", huffmanCode);

    string encodedString = getEncodedString(inputFile, huffmanCode);
    saveEncodedFile(encodedString, encodedFile);

    // 计算压缩前的比特数
    ifstream inFile(inputFile, ios::binary | ios::ate);
    streamsize inputFileSize = inFile.tellg();
    inFile.close();
    int originalBits = inputFileSize * 8;
    cout << "压缩前的比特数: " << originalBits << endl;

    // 计算压缩后的比特数
    int compressedBits = encodedString.size();
    cout << "压缩后的比特数: " << compressedBits << endl;

    double compressionRatio = calculateCompressionRatio(inputFile, encodedFile);
    cout << "压缩比: " << compressionRatio << endl;

    decode(root, encodedString, decodedFile);

    return 0;
}