2023年GESP四级图像压缩题（洛谷B3851）解析与代码实现

一、题目解读

本题要求实现图像压缩算法，通过处理输入的灰度图像数据（以十六进制表示的像素值），将其转换为压缩后的表示形式。核心目标是通过统计灰度频率，选取前16个高频灰度值构建压缩表，并利用最小距离替换将原始像素映射到压缩表索引，从而减少数据量。题目考察对数据频率统计、排序算法及优化替换策略的理解。

二、解题思路

1. 频率统计：读取输入数据，将每行十六进制字符串按每两位分组转换为灰度值，统计各灰度出现频率。

2. 压缩表构建：对频率排序（高频优先，同频则灰度值小的优先），取前16个灰度值组成压缩表。

3. 最小距离替换：遍历原始数据，计算每个灰度值与压缩表中各值的距离，选择距离最小且索引最小的替换值（避免歧义）。

4. 输出优化：压缩表以十六进制格式输出，数据行转换为对应索引字符。

三、解题步骤

1. 输入与初始化：

    读取图像行数n，存储原始数据到original_lines。

    创建频率统计mapfreq，初始化为空。

2. 统计灰度频率：

    逐行处理，每两位十六进制子串转为灰度值（stoi(hex, nullptr, 16)），更新freq计数。

3. 生成压缩表：

    将freq转为vectorgray_freq，按频率和灰度值排序（自定义cmp函数）。

    取前16个灰度值存入compressed_gray。

4. 输出压缩表：

    使用cout << hex << setw(2) << setfill('0')格式化为两位十六进制输出。

5. 数据压缩处理：

    遍历每行，计算每个灰度与压缩表的距离，更新最小距离和索引，将索引字符（'0' + index或'A' + index - 10）拼接至compressed_line。

6. 输出压缩数据：逐行输出compressed_line。

四、代码与注释

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <iomanip>
#include <sstream>
using namespace std;

// 自定义排序函数：按频率降序，同频则灰度值升序
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
    return a.second!= b.second? a.second > b.second : a.first < b.first;
}

int main() {
    int n;
    cin >> n;    // 输入图像行数
    vector<string> original_lines(n);  // 存储原始数据行

    // 统计灰度频率
    map<int, int> freq;
    for (int i = 0; i < n; ++i) {
        cin >> original_lines[i];
        for (size_t j = 0; j < original_lines[i].length(); j += 2) {
            // 每两位十六进制子串转换为灰度值
            string hex = original_lines[i].substr(j, 2);
            int gray = stoi(hex, nullptr, 16);
            freq[gray]++;
        }
    }

    // 排序并生成压缩表
    vector<pair<int, int>> gray_freq(freq.begin(), freq.end());
    sort(gray_freq.begin(), gray_freq.end(), cmp);
    vector<int> compressed_gray;
    for (int i = 0; i < 16; ++i) {
        compressed_gray.push_back(gray_freq[i].first);
    }

    // 输出压缩灰阶表（十六进制格式）
    for (int gray : compressed_gray) {
        cout << hex << uppercase << setw(2) << setfill('0') << gray << " ";
    }
    cout << endl;

    // 处理每行数据压缩
    for (const auto& line : original_lines) {
        string compressed_line;
        for (size_t j = 0; j < line.length(); j += 2) {
            string hex = line.substr(j, 2);
            int gray = stoi(hex, nullptr, 16);
            int min_dist = 256;  // 初始化最大距离
            int best_index = 0;  // 最佳索引

            // 查找压缩表中距离最小的灰度值索引
            for (int k = 0; k < 16; ++k) {
                int dist = abs(gray - compressed_gray[k]);
                if (dist < min_dist || (dist == min_dist && k < best_index)) {
                    min_dist = dist;
                    best_index = k;
                }
            }
            // 将索引转换为字符（0-9用数字，10-15用A-F）
            compressed_line += (best_index < 10)? char('0' + best_index) 
                : char('A' + best_index - 10);
        }
        cout << compressed_line << endl;
    }

    return 0;
}

五、总结

本算法通过灰度频率统计与最小距离替换实现了图像数据的无损压缩。关键优化点在于：

1. 压缩表基于频率优先级，确保高频灰度用更短编码；

2. 替换时同时考虑距离与索引顺序，避免映射歧义。

进一步优化可考虑动态调整压缩表大小或引入更高效的距离计算策略。该解法兼具逻辑清晰性与效率，适合入门级算法实践。