哈夫曼编码压缩比计算
时间: 2023-11-16 09:57:50 浏览: 132
哈夫曼编码的压缩比计算公式为:压缩比 = 原始数据位数 / 压缩后数据位数。其中,原始数据位数指的是未经过压缩的数据所占用的位数,压缩后数据位数指的是经过哈夫曼编码压缩后的数据所占用的位数。由于哈夫曼编码是一种可变字长编码,所以压缩后数据位数会根据不同的数据集而有所不同。一般来说,哈夫曼编码的压缩比比较高,可以达到30%~50%左右。
相关问题
c语言实现哈夫曼编码压缩文件并输出压缩比
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义哈夫曼树节点结构体
typedef struct HuffmanNode {
unsigned char data; // 字符数据
int freq; // 字符频率
struct HuffmanNode *left; // 左子节点
struct HuffmanNode *right; // 右子节点
} HuffmanNode;
// 定义哈夫曼编码结构体
typedef struct HuffmanCode {
unsigned char data; // 字符数据
char *code; // 字符编码
} HuffmanCode;
// 创建哈夫曼树
HuffmanNode* createHuffmanTree(unsigned char *data, int *freq, int size) {
// 创建叶子节点数组
HuffmanNode **nodes = (HuffmanNode**)malloc(size * sizeof(HuffmanNode*));
for (int i = 0; i < size; i++) {
nodes[i] = (HuffmanNode*)malloc(sizeof(HuffmanNode));
nodes[i]->data = data[i];
nodes[i]->freq = freq[i];
nodes[i]->left = NULL;
nodes[i]->right = NULL;
}
// 构建哈夫曼树
while (size > 1) {
// 找到频率最小的两个节点
int min1 = 0, min2 = 1;
if (nodes[min1]->freq > nodes[min2]->freq) {
int temp = min1;
min1 = min2;
min2 = temp;
}
for (int i = 2; i < size; i++) {
if (nodes[i]->freq < nodes[min1]->freq) {
min2 = min1;
min1 = i;
} else if (nodes[i]->freq < nodes[min2]->freq) {
min2 = i;
}
}
// 创建新节点,将两个最小频率的节点作为子节点
HuffmanNode *newNode = (HuffmanNode*)malloc(sizeof(HuffmanNode));
newNode->data = 0;
newNode->freq = nodes[min1]->freq + nodes[min2]->freq;
newNode->left = nodes[min1];
newNode->right = nodes[min2];
// 删除已经合并的节点
if (min1 < min2) {
nodes[min1] = newNode;
nodes[min2] = nodes[size - 1];
} else {
nodes[min2] = newNode;
nodes[min1] = nodes[size - 1];
}
size--;
}
// 返回根节点
return nodes[0];
}
// 生成哈夫曼编码
void generateHuffmanCode(HuffmanNode *root, char *code, int depth, HuffmanCode *codes) {
if (root->left == NULL && root->right == NULL) {
// 叶子节点,保存编码
codes[root->data].data = root->data;
codes[root->data].code = (char*)malloc((depth + 1) * sizeof(char));
strcpy(codes[root->data].code, code);
codes[root->data].code[depth] = '\0';
} else {
// 非叶子节点,递归生成编码
code[depth] = '0';
generateHuffmanCode(root->left, code, depth + 1, codes);
code[depth] = '1';
generateHuffmanCode(root->right, code, depth + 1, codes);
}
}
// 压缩文件
void compressFile(const char *inputFile, const char *outputFile, HuffmanCode *codes) {
FILE *input = fopen(inputFile, "rb");
FILE *output = fopen(outputFile, "wb");
// 写入编码表大小
int codeSize = 0;
for (int i = 0; i < 256; i++) {
if (codes[i].code != NULL) {
codeSize++;
}
}
fwrite(&codeSize, sizeof(int), 1, output);
// 写入编码表
for (int i = 0; i < 256; i++) {
if (codes[i].code != NULL) {
fwrite(&codes[i].data, sizeof(unsigned char), 1, output);
int codeLength = strlen(codes[i].code);
fwrite(&codeLength, sizeof(int), 1, output);
fwrite(codes[i].code, sizeof(char), codeLength, output);
}
}
// 压缩文件内容
unsigned char buffer = 0;
int bitCount = 0;
unsigned char ch;
while (fread(&ch, sizeof(unsigned char), 1, input) > 0) {
int codeLength = strlen(codes[ch].code);
for (int i = 0; i < codeLength; i++) {
if (codes[ch].code[i] == '1') {
buffer |= (1 << (7 - bitCount));
}
bitCount++;
if (bitCount == 8) {
fwrite(&buffer, sizeof(unsigned char), 1, output);
buffer = 0;
bitCount = 0;
}
}
}
// 写入最后一个字节
if (bitCount > 0) {
fwrite(&buffer, sizeof(unsigned char), 1, output);
}
fclose(input);
fclose(output);
}
// 计算文件大小
long long getFileSize(const char *filename) {
FILE *file = fopen(filename, "rb");
fseek(file, 0, SEEK_END);
long long size = ftell(file);
fclose(file);
return size;
}
int main() {
// 读取文件内容
const char *filename = "input.txt";
FILE *file = fopen(filename, "rb");
fseek(file, 0, SEEK_END);
int fileSize = ftell(file);
fseek(file, 0, SEEK_SET);
unsigned char *data = (unsigned char*)malloc(fileSize * sizeof(unsigned char));
fread(data, sizeof(unsigned char), fileSize, file);
fclose(file);
// 统计字符频率
int freq[256] = {0};
for (int i = 0; i < fileSize; i++) {
freq[data[i]]++;
}
// 创建哈夫曼树
HuffmanNode *root = createHuffmanTree(data, freq, 256);
// 生成哈夫曼编码
char code[256];
HuffmanCode codes[256];
memset(code, 0, sizeof(code));
generateHuffmanCode(root, code, 0, codes);
// 压缩文件
compressFile("input.txt", "output
哈夫曼编码图像压缩MATLAB代码
以下是使用哈夫曼编码进行图像压缩的 MATLAB 代码:
```matlab
% 读入图像
I = imread('image.jpg');
% 将图像转换为灰度图像
if (size(I,3)==3)
I = rgb2gray(I);
end
% 将灰度值转换为 8 位二进制数
Ibin = dec2bin(I, 8);
% 统计每个二进制数的出现次数
counts = zeros(1,256);
for i=1:size(Ibin,1)
for j=1:size(Ibin,2)
counts(bin2dec(Ibin(i,j,:))+1) = counts(bin2dec(Ibin(i,j,:))+1) + 1;
end
end
% 构建哈夫曼树
symbols = cell(1,256);
for i=1:256
symbols{i} = dec2bin(i-1, 8);
end
dict = huffmandict(symbols, counts);
% 使用哈夫曼编码压缩图像
Icomp = huffmanenco(Ibin(:), dict);
% 计算压缩比
comp_ratio = length(Icomp)/(size(I,1)*size(I,2)*8);
% 解压缩图像
Idec = huffmandeco(Icomp, dict);
% 将二进制数转换为灰度值
Idec = reshape(Idec, size(Ibin));
Idec = bin2dec(Idec);
% 将灰度图像转换为彩色图像
if (size(I,3)==3)
Icomp = reshape(Idec, size(I,1), size(I,2));
else
Icomp = reshape(Idec, size(I,1), size(I,2), 1);
end
% 显示图像和压缩比
figure;
imshow(Icomp);
title(sprintf('Compression Ratio: %f', comp_ratio));
```
在代码中,首先读入图像并将其转换为灰度图像。然后将每个像素的灰度值转换为 8 位二进制数,并统计每个二进制数的出现次数。接着,使用 `huffmandict` 函数构建哈夫曼树,并使用 `huffmanenco` 函数将图像数据压缩成一串二进制数。计算压缩比后,使用 `huffmandeco` 函数将压缩后的二进制数解码,并将二进制数转换为灰度值。最后,如果原图像是彩色图像,则将解压缩后的灰度图像转换为彩色图像并显示。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)