香农熵编码压缩图像c语言

以下是一个简单的使用香农熵编码对图像进行压缩的C语言示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SYMBOLS 256

typedef struct {
    unsigned char symbol;
    int frequency;
} Symbol;

typedef struct {
    long long low;
    long long high;
} Range;

typedef struct {
    Symbol symbol_list[MAX_SYMBOLS];
    int symbol_count;
} FrequencyTable;

void init_frequency_table(FrequencyTable* table) {
    memset(table, 0, sizeof(FrequencyTable));
}

void update_frequency_table(FrequencyTable* table, unsigned char* data, int size) {
    for (int i = 0; i < size; i++) {
        int found = 0;
        for (int j = 0; j < table->symbol_count; j++) {
            if (table->symbol_list[j].symbol == data[i]) {
                table->symbol_list[j].frequency++;
                found = 1;
                break;
            }
        }
        if (!found) {
            Symbol symbol = { data[i], 1 };
            table->symbol_list[table->symbol_count++] = symbol;
        }
    }
}

void sort_frequency_table(FrequencyTable* table) {
    for (int i = 0; i < table->symbol_count - 1; i++) {
        for (int j = i + 1; j < table->symbol_count; j++) {
            if (table->symbol_list[i].frequency < table->symbol_list[j].frequency) {
                Symbol temp = table->symbol_list[i];
                table->symbol_list[i] = table->symbol_list[j];
                table->symbol_list[j] = temp;
            }
        }
    }
}

void build_range_table(FrequencyTable* table, Range* range_list) {
    long long total_frequency = 0;
    for (int i = 0; i < table->symbol_count; i++) {
        total_frequency += table->symbol_list[i].frequency;
    }

    long long low = 0;
    for (int i = 0; i < table->symbol_count; i++) {
        long long high = low + table->symbol_list[i].frequency * (1LL << 32) / total_frequency;
        range_list[i].low = low;
        range_list[i].high = high;
        low = high;
    }
}

void encode_data(unsigned char* data, int size, Range* range_list, FILE* output) {
    long long low = 0;
    long long high = (1LL << 32) - 1;
    for (int i = 0; i < size; i++) {
        int symbol_index = -1;
        for (int j = 0; j < MAX_SYMBOLS; j++) {
            if (range_list[j].low <= low && high < range_list[j].high) {
                symbol_index = j;
                break;
            }
        }
        if (symbol_index < 0) {
            fprintf(stderr, "Error: symbol not found in range table.\n");
            exit(1);
        }
        Range range = range_list[symbol_index];
        long long range_size = high - low + 1;
        high = low + range_size * range.high / (1LL << 32) - 1;
        low = low + range_size * range.low / (1LL << 32);
        while (1) {
            if ((low ^ high) < (1LL << 31)) {
                fputc(low >> 31, output);
                while (fputc(1, output), high_bits > 0) {
                    high_bits--;
                }
                low = (low << 1) & ((1LL << 32) - 1);
                high = ((high << 1) | 1) & ((1LL << 32) - 1);
            } else if ((low >> 30) == 1 && (high >> 30) == 0) {
                high_bits++;
                low = (low << 1) & ((1LL << 32) - 1);
                high = ((high << 1) | 1) & ((1LL << 32) - 1);
            } else {
                break;
            }
        }
    }
    for (int i = 0; i < 8; i++) {
        fputc(low >> 31, output);
    }
}

void encode_image(char* input_filename, char* output_filename) {
    FILE* input = fopen(input_filename, "rb");
    if (!input) {
        fprintf(stderr, "Error: failed to open input file.\n");
        exit(1);
    }

    FILE* output = fopen(output_filename, "wb");
    if (!output) {
        fprintf(stderr, "Error: failed to open output file.\n");
        exit(1);
    }

    unsigned char buffer[1024];
    FrequencyTable table;
    Range range_list[MAX_SYMBOLS];
    init_frequency_table(&table);
    while (!feof(input)) {
        int size = fread(buffer, 1, sizeof(buffer), input);
        update_frequency_table(&table, buffer, size);
    }
    sort_frequency_table(&table);
    build_range_table(&table, range_list);
    fwrite(&table.symbol_count, sizeof(int), 1, output);
    for (int i = 0; i < table.symbol_count; i++) {
        fwrite(&table.symbol_list[i].symbol, sizeof(unsigned char), 1, output);
        fwrite(&table.symbol_list[i].frequency, sizeof(int), 1, output);
    }
    rewind(input);
    while (!feof(input)) {
        int size = fread(buffer, 1, sizeof(buffer), input);
        encode_data(buffer, size, range_list, output);
    }
    fclose(input);
    fclose(output);
}

int main(int argc, char** argv) {
    if (argc != 3) {
        fprintf(stderr, "Usage: %s input_file output_file\n", argv[0]);
        return 1;
    }

    encode_image(argv[1], argv[2]);

    return 0;
}

这个示例程序将输入的图像文件经过香农熵编码压缩后输出到指定的文件中。具体来说，它先对输入数据中各个符号的出现频率进行统计，并按照频率从高到低排序，然后根据符号出现频率构建出每个符号的编码范围，最后使用编码范围对输入数据进行编码，并将编码后的数据输出到文件中。在解压缩时，只需要使用相同的频率表和编码范围即可还原原始数据。