C++ 使用哈夫曼编码压缩图片

哈夫曼编码是一种无损压缩算法，可以用来压缩图片。下面是使用哈夫曼编码压缩图片的步骤：

1. 读取图片数据：使用C语言中的文件操作函数读取图片数据，并将其存储到内存中。

2. 统计像素出现频率：遍历图片数据，统计每个像素值出现的次数。可以使用一个数组来记录每个像素值出现的次数。

3. 构建哈夫曼树：使用统计的像素出现频率构建哈夫曼树。可以使用一个优先队列来实现。

4. 生成哈夫曼编码表：遍历哈夫曼树，生成每个像素值对应的哈夫曼编码。可以使用一个哈希表来存储哈夫曼编码表。

5. 压缩图片数据：使用哈夫曼编码表将图片数据压缩。可以将每个像素值替换为对应的哈夫曼编码，然后将所有的哈夫曼编码拼接起来。

6. 存储压缩后的数据：将压缩后的数据存储到文件中。

7. 解压缩图片数据：读取压缩后的数据，并使用哈夫曼编码表将其解压缩。可以将压缩后的数据按照哈夫曼编码逐位解码，直到还原出原始的像素值序列。

8. 存储解压缩后的数据：将解压缩后的数据存储到文件中。

需要注意的是，使用哈夫曼编码压缩图片可能会导致压缩后的文件比原始文件还要大，这是因为哈夫曼编码只适用于具有一定重复性的数据。因此，在实际应用中需要根据具体情况选择合适的压缩算法。

相关问题

C++ 使用哈夫曼编码压缩图片的代码

哈夫曼编码是一种无损压缩方法，可以用于对图片进行压缩。下面是一个使用哈夫曼编码压缩图片的示例代码：

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

#define MAX_NODE 256

typedef struct Node {
    unsigned char ch;
    int freq;
    struct Node *left, *right;
} Node;

typedef struct Heap {
    int size;
    Node *array[MAX_NODE];
} Heap;

typedef struct Code {
    unsigned char *bits;
    int size;
} Code;

typedef struct Table {
    Code codes[MAX_NODE];
} Table;

Node *createNode(unsigned char ch, int freq) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->ch = ch;
    node->freq = freq;
    node->left = node->right = NULL;
    return node;
}

Heap *createHeap() {
    Heap *heap = (Heap*) malloc(sizeof(Heap));
    heap->size = 0;
    return heap;
}

void swap(Node **a, Node **b) {
    Node *tmp = *a;
    *a = *b;
    *b = tmp;
}

void heapify(Heap *heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < heap->size && heap->array[left]->freq < heap->array[smallest]->freq)
        smallest = left;

    if (right < heap->size && heap->array[right]->freq < heap->array[smallest]->freq)
        smallest = right;

    if (smallest != idx) {
        swap(&heap->array[idx], &heap->array[smallest]);
        heapify(heap, smallest);
    }
}

int isLeaf(Node *node) {
    return !node->left && !node->right;
}

Node *extractMin(Heap *heap) {
    Node *node = heap->array[0];
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    heapify(heap, 0);
    return node;
}

void insertHeap(Heap *heap, Node *node) {
    heap->size++;
    int i = heap->size - 1;

    while (i && node->freq < heap->array[(i - 1) / 2]->freq) {
        heap->array[i] = heap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }

    heap->array[i] = node;
}

Heap *buildHeap(int *freq) {
    Heap *heap = createHeap();

    for (int i = 0; i < MAX_NODE; i++)
        if (freq[i])
            insertHeap(heap, createNode(i, freq[i]));

    while (heap->size > 1) {
        Node *left = extractMin(heap);
        Node *right = extractMin(heap);
        Node *node = createNode('$', left->freq + right->freq);
        node->left = left;
        node->right = right;
        insertHeap(heap, node);
    }

    return heap;
}

void encode(Node *root, Code code, Table *table) {
    if (root) {
        if (isLeaf(root)) {
            table->codes[root->ch] = code;
        } else {
            Code leftCode = code;
            leftCode.bits[code.size++] = '0';
            encode(root->left, leftCode, table);
            Code rightCode = code;
            rightCode.bits[code.size++] = '1';
            encode(root->right, rightCode, table);
        }
    }
}

void writeHeader(FILE *fp, int *freq) {
    fwrite(freq, sizeof(int), MAX_NODE, fp);
}

void writeBits(FILE *fp, Code code, int *pos) {
    int bytePos = *pos / 8;
    int bitPos = *pos % 8;

    for (int i = 0; i < code.size; i++) {
        if (code.bits[i] == '1')
            fp[bytePos] |= 1 << bitPos;

        bitPos++;
        (*pos)++;

        if (bitPos == 8) {
            bytePos++;
            bitPos = 0;
        }
    }
}

void compress(char *filename) {
    FILE *fp = fopen(filename, "rb");
    char outFilename[256];
    strcpy(outFilename, filename);
    strcat(outFilename, ".huff");
    FILE *outFp = fopen(outFilename, "wb");

    int freq[MAX_NODE] = {0};
    unsigned char ch;

    while (fread(&ch, sizeof(unsigned char), 1, fp))
        freq[ch]++;

    Heap *heap = buildHeap(freq);
    Node *root = extractMin(heap);
    Table *table = (Table*) malloc(sizeof(Table));

    for (int i = 0; i < MAX_NODE; i++)
        table->codes[i].bits = (unsigned char*) malloc(256);

    Code code;
    code.bits = (unsigned char*) malloc(256);
    code.size = 0;
    encode(root, code, table);

    writeHeader(outFp, freq);

    fseek(fp, 0, SEEK_SET);

    int pos = 0;
    unsigned char buffer = 0;

    while (fread(&ch, sizeof(unsigned char), 1, fp)) {
        Code code = table->codes[ch];
        writeBits(&buffer, code, &pos);

        while (pos >= 8) {
            fwrite(&buffer, sizeof(unsigned char), 1, outFp);
            buffer = buffer >> 8;
            pos -= 8;
        }
    }

    if (pos)
        fwrite(&buffer, sizeof(unsigned char), 1, outFp);

    fclose(fp);
    fclose(outFp);
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        printf("Usage: %s <filename>\n", argv[0]);
        return 1;
    }

    compress(argv[1]);

    return 0;
}

这个程序将输入的图片文件进行压缩，并将压缩后的数据写入一个新的文件中。输出的文件名为原文件名加上 ".huff" 后缀。程序使用了哈夫曼编码来压缩数据。在压缩过程中先统计每个字节出现的频率，然后使用哈夫曼树来构建编码表，并将编码表写入输出文件的头部。接着遍历输入文件的每个字节，并将其对应的编码写入输出文件中。最后，如果最后一个字节的编码不足一个字节，将其填充为 0 后写入输出文件中。

如何在c++中使用哈夫曼树进行bmp的图片的解压缩

在 C++ 中使用哈夫曼树对 BMP 图片进行解压缩通常涉及到以下几个步骤：

1. **读取 BMP 文件**：首先，你需要从 BMP 文件中读取数据，包括位深度、图像宽度、高度和像素数据。C++ 的标准库如`std::ifstream`可以用来打开并读取文件。

2. **构建哈夫曼编码表**：对于每个像素的颜色值（如果是灰度图），通常会生成一个频率统计，最常见的颜色会分配较短的码字。通过计算得到哈夫曼树，并将每个颜色与其对应的码字关联起来。

3. **解码哈夫曼码**：在原始文件中，像素是以二进制形式存储的。利用构建的哈夫曼树，从右到左读取每一位，然后查找对应的字符，逐步还原出原始的像素信息。

4. **重建图像**：当所有像素的哈夫曼码都被解码后，将它们按照原始顺序放入新的内存缓冲区中，构建出解压缩后的图像数据。

5. **保存解压缩后的图像**：最后，你可以选择将解压缩后的数据写入一个新的文件，或者直接作为内存中的 Bitmap 数据结构使用。

以下是一个简化的伪代码示例：

class HuffmanNode {
    // ... 实现哈夫曼节点
};

void buildHuffmanTree(std::vector<unsigned char>& frequencies, std::vector<HuffmanNode*>& huffNodes);
std::string decodeHuffmanCode(const HuffmanNode* node, const std::string& code);

// 使用哈夫曼树解压缩
void decompressBMP(const std::string& compressedData, std::vector<unsigned char>& decompressedImage) {
    // ... (此处省略构建哈夫曼树和读取编码部分)
    
    for (const auto& pixelCode : compressedImage) {
        std::string decodedPixel = decodeHuffmanCode(huffRoot, pixelCode);
        // 解码像素并添加到解压结果中
        decompressedImage.push_back(decodedPixel.back());
    }
}