当前位置: &&&&正文
本文首先简要阐述哈夫曼算法的基本思想，然后介绍了使用哈夫曼算法进行文件压缩和解压缩的
处理步骤，最后给出了C语言实现的文件压缩和解压缩的源代码。
哈夫曼算法的主要思想是：
①首先遍历要处理的字符串，得到每个字符的出现的次数；
②将每个字符（以其出现次数为权值）分别构造为二叉树（注意此时的二叉树只有一个节点）；
③取所有二叉树种种字符出现次数最小的二叉树合并为一颗新的二叉树，新二叉树根节点的权值等于两个子节点的权值之和，新节点中的字符忽略；
④重复过程③直到所有树被合并为同一棵二叉树
⑤遍历最后得到的二叉树，自顶向下按路径编号，指向左节点的边编号0，指向右节点的边编号1，从根到叶节点的所有边上的0和1链接起来，就是叶子节点中字符的哈夫曼编码。
下图展示了哈夫曼编码的基本思想。
基于哈夫曼算法的文件压缩和解压缩过程分别说明如下：
一、文件压缩：
①统计词频：读取文件的每个字节，使用整数数组int statistic[MAX_CHARS]统计每个字符出现的次数，
由于一个字节最多表示2^8-1个字符，所以MAX_CHARS=256就足够了。在统计字符数的时候，
对于每一个byte, 有statistic[(unsigned char)byte]++。
②构造哈夫曼树：根据statistic数组，基于哈夫曼树算法造哈夫曼树，由于构造的过程中每次都要取最小权值的字符，
所以需要用优先队列来维护每棵树的根节点。
③生成编码：深度优先遍历哈弗曼树，得到每个叶子节点中的字符的编码并存入字符串数组char *dictionary[MAX_CHARS];
④存储词频：新建存储压缩数据的文件，首先写入不同字符的个数，然后将每个字符及其对应的词频写入文件。
⑤存储压缩数据：再次读取待压缩文件的每个字节byte，由dictionary[(unsigned int)byte]得到对应的编码（注意每个字符
编码的长度不一），使用位运算一次将编码中的每个位(BIT)设置到一个char类型的位缓冲中，可能多个编码才能填满一个
位缓冲，每填满一次，将位缓冲区以单个字节的形式写入文件。当文件遍历完成的时候，文件的压缩也就完成了。
二、文件解压：
①读取词频：读取压缩文件，将每个字符的出现次数存入数组statistic
②构造哈夫曼编码树：根据statistic数组构造哈夫曼编码树
③继续读取压缩文件，对于每个字节，使用位运算得到每个位（BIT）。对于每个BIT，根据BIT从根开始遍历哈夫曼树，如果BIT是0
就走左分支，如果BIT是1就走有分支，走到叶子节点的时候，输出对应的字符。走到叶子节点后，重新从哈夫曼树根节点开始匹配
每个位。当整个压缩文件读取完毕时，文件解压缩也完成了。
上文介绍了基于哈夫曼算法的文件压缩和解压缩，下面给出基于上述思想的C语言源代码，一共有5个文件，其中pq.h和pq.c
是优先队列，compress.h和compress.c是压缩和解压缩的实现，main.c是测试文件。
pq.h和pq.c请参见另外一篇文章。
另外三个文件内容如下：
* File: compress.h
* Purpose: To compress file using the Haffman algorithm
* Author: puresky
#ifndef _FILE_COMPRESSION_H
#define _FILE_COMPRESSION_H
//Haffuman Tree Node
typedef struct HaffumanTreeNode HTN;
struct HaffumanTreeNode
//character
int _ //frequency
struct HaffumanTreeNode *_ //left child
struct HaffumanTreeNode *_//rigth child
//FileCompress Struct
#define BITS_PER_CHAR 8
//the number of bits in a char
#define MAX_CHARS 256
//the max number of chars
#define FILE_BUF_SIZE 8192
//the size of Buffer for FILE I/O
typedef struct FileCompressStruct FCS;
struct FileCompressStruct
//A pointer to the root of hafumman tree
unsigned int _charsC //To store the number of chars
unsigned int _ //Total bytes in a file.
char *_dictionary[MAX_CHARS]; //to store the encoding of each character
int _statistic[MAX_CHARS]; //To store the number of each character
FCS *fcs_new();
void fcs_compress(FCS *fcs, const char *inFileName, const char *outFileName);
void fcs_decompress(FCS *fcs, const char *inFileName, const char *outFileName);
void fcs_free(FCS *fcs);
* File: compress.c
* Purpose: To compress file using the Haffman algorithm
* Author: puresky
#include &stdio.h&
#include &string.h&
#include &stdlib.h&
#include "compress.h"
#include "pq.h"
static const unsigned char mask[8] =
//static functions of HTN
static HTN *htn_new(char ch, int count)
HTN *htn = (HTN *)malloc(sizeof(HTN));
htn-&_left = NULL;
htn-&_right = NULL;
htn-&_ch =
htn-&_count =
static void htn_print_recursive(HTN *htn, int depth)
for(i = 0; i & ++i)
printf("%d:%d\n", htn-&_ch, htn-&_count);
htn_print_recursive(htn-&_left, depth + 1);
htn_print_recursive(htn-&_right, depth + 1);
static void htn_print(HTN *htn)
htn_print_recursive(htn, 0);
static void htn_free(HTN *htn)
htn_free(htn-&_left);
htn_free(htn-&_right);
free(htn);
//static functions of FCS
static void fcs_generate_statistic(FCS *fcs, const char *inFileName)
unsigned char buf[FILE_BUF_SIZE];
FILE *pf = fopen(inFileName, "rb");
fprintf(stderr, "can't open file:%s\n", inFileName);
while((ret = fread(buf, 1, FILE_BUF_SIZE, pf)) & 0)
fcs-&_total +=
for(i = 0; i & ++i)
if(fcs-&_statistic[buf[i]] == 0)
fcs-&_charsCount++;
fcs-&_statistic[buf[i]]++;
fclose(pf);
static void fcs_create_haffuman_tree(FCS *fcs)
HTN *htn, *parent, *left, *
KeyValue *kv, *kv1, *kv2;
PriorityQueue *
pq = priority_queue_new(PRIORITY_MIN);
for(i = 0; i & MAX_CHARS; ++i)
if(fcs-&_statistic[i])
htn = htn_new((char)i, fcs-&_statistic[i]);
kv = key_value_new(fcs-&_statistic[i], htn);
priority_queue_enqueue(pq, kv);
//fprintf(stdout, "the number of haffuman leaf is %d\n", priority_queue_size(pq));
while(!priority_queue_empty(pq))
//fprintf(stdout, "priority queue size:%d\n", priority_queue_size(pq));
kv1 = priority_queue_dequeue(pq);
kv2 = priority_queue_dequeue(pq);
if(kv2 == NULL)
fcs-&_haffuman = kv1-&_
key_value_free(kv1, NULL);
left = (HTN *)kv1-&_
right = (HTN *)kv2-&_
count = left-&_count + right-&_
key_value_free(kv1, NULL);
key_value_free(kv2, NULL);
parent = htn_new(0, count);
parent-&_left =
parent-&_right =
kv = key_value_new(count, parent);
priority_queue_enqueue(pq, kv);
priority_queue_free(pq, NULL);
//htn_print(fcs-&_haffuman);
static void fcs_generate_dictionary_recursively(HTN *htn, char *dictionary[], char path[], int depth)
char *code = NULL;
if(htn-&_left == NULL && htn-&_right == NULL)
code = (char *)malloc(sizeof(char) * (depth + 1));
memset(code, 0, sizeof(char) * (depth + 1));
memcpy(code, path, depth);
dictionary[(unsigned char)htn-&_ch] =
if(htn-&_left)
path[depth] = '0';
fcs_generate_dictionary_recursively(htn-&_left, dictionary, path, depth + 1);
if(htn-&_right)
path[depth] = '1';
fcs_generate_dictionary_recursively(htn-&_right, dictionary, path, depth + 1);
static void fcs_generate_dictionary(FCS *fcs)
char path[32];
fcs_generate_dictionary_recursively(fcs-&_haffuman, fcs-&_dictionary, path, 0);
//fcs_print_dictionary(fcs);
static void fcs_print_dictionary(FCS *fcs)
for(i = 0; i & MAX_CHARS; ++i)
if(fcs-&_dictionary[i] != NULL)
fprintf(stdout, "%d:%s\n", i, fcs-&_dictionary[i]);
static void fcs_write_statistic(FCS *fcs, FILE *pf)
fprintf(pf, "%d\n", fcs-&_charsCount);
for(i = 0; i & MAX_CHARS; ++i)
if(fcs-&_statistic[i] != 0)
fprintf(pf, "%d %d\n", i, fcs-&_statistic[i]);
static void fcs_do_compress(FCS *fcs, const char *inFileName, const char* outFileName)
char *dictEntry,
unsigned char inBuf[FILE_BUF_SIZE];
FILE *pfIn, *pfO
pfIn = fopen(inFileName, "rb");
fprintf(stderr, "can't open file:%s\n", inFileName);
pfOut = fopen(outFileName, "wb");
if(!pfOut)
fclose(pfIn);
fprintf(stderr, "can't open file:%s\n", outFileName);
fcs_write_statistic(fcs, pfOut);
bitBuf = 0x00;
bitPos = 0;
bytes = 0;
while((ret = fread(inBuf, 1, FILE_BUF_SIZE, pfIn)) & 0)
for(i = 0; i & ++i)
len = strlen(fcs-&_dictionary[inBuf[i]]);
dictEntry = fcs-&_dictionary[inBuf[i]];
//printf("%s\n", dictEntry);
for(j = 0; j & ++j)
if(dictEntry[j] == '1')
bitBuf |= mask[bitPos++];
if(bitPos == BITS_PER_CHAR)
fwrite(&bitBuf, 1, sizeof(bitBuf), pfOut);
bitBuf = 0x00;
bitPos = 0;
if(bitPos != 0)
fwrite(&bitBuf, 1, sizeof(bitBuf), pfOut);
fclose(pfIn);
fclose(pfOut);
printf("The compression ratio is:%f%%\n",
(fcs-&_total - bytes) * 100.0 / fcs-&_total);
static void fcs_read_statistic(FCS *fcs, FILE *pf)
int i, charsCount = 0;
fscanf(pf, "%d\n", &charsCount);
fcs-&_charsCount = charsC
for(i = 0; i & charsC ++i)
fscanf(pf, "%d %d\n", &ch, &num);
fcs-&_statistic[(unsigned int)ch] =
fcs-&_total +=
static void fcs_do_decompress(FCS *fcs, FILE *pfIn, const char *outFileName)
unsigned char buf[FILE_BUF_SIZE];
unsigned char bitC
pfOut = fopen(outFileName, "wb");
if(!pfOut)
fprintf(stderr, "can't open file:%s\n", outFileName);
htn = fcs-&_
bitCode = 0x00;
bitPos = 0;
while((ret = fread(buf, 1, FILE_BUF_SIZE, pfIn)) & 0)
for(i = 0; i & ++i)
ch = buf[i];
for(j = 0; j & BITS_PER_CHAR; ++j)
if(ch & mask[j])
htn = htn-&_
htn = htn-&_
if(htn-&_left == NULL && htn-&_right == NULL) //leaf
if(fcs-&_total & 0)
fwrite(&htn-&_ch, 1, sizeof(char), pfOut);
fcs-&_total--;
htn = fcs-&_
fclose(pfOut);
//FCS functions
FCS *fcs_new()
FCS *fcs = (FCS *)malloc(sizeof(FCS));
fcs-&_charsCount = 0;
fcs-&_total = 0;
memset(fcs-&_statistic, 0, sizeof(fcs-&_statistic));
memset(fcs-&_dictionary, 0, sizeof(fcs-&_dictionary));
fcs-&_haffuman = NULL;
void fcs_free(FCS *fcs)
if(fcs-&_haffuman)
htn_free(fcs-&_haffuman);
for(i = 0; i & MAX_CHARS; ++i)
free(fcs-&_dictionary[i]);
free(fcs);
void fcs_compress(FCS *fcs, const char *inFileName, const char *outFileName)
fprintf(stdout, "To compress file: %s ...\n", inFileName);
fcs_generate_statistic(fcs, inFileName);
fcs_create_haffuman_tree(fcs);
fcs_generate_dictionary(fcs);
fcs_do_compress(fcs, inFileName, outFileName);
fprintf(stdout, "The compressed data of file: %s stored at %s!\n",
inFileName, outFileName);
void fcs_decompress(FCS *fcs, const char *inFileName, const char *outFileName)
FILE *pfIn;
fprintf(stdout, "To decompress file: %s ...\n", inFileName);
pfIn= fopen(inFileName, "rb");
fprintf(stderr, "can't open file: %s\n", inFileName);
fcs_read_statistic(fcs, pfIn);
fcs_create_haffuman_tree(fcs);
fcs_generate_dictionary(fcs);
fcs_do_decompress(fcs, pfIn, outFileName);
fclose(pfIn);
fprintf(stdout, "The decompressed data of file: %s stored at %s\n",
inFileName, outFileName);
* File: main.c
* Purpose: testing File Compression
* Author:puresky
#include &stdlib.h&
#include "compress.h"
const int DO_COMPRESS = 1;
const int DO_DECOMPRESS = 1;
const char *InFile = "data.txt"; //The file to compress.
const char *CompressedFile = "data.hfm"; //Compressed data of the file.
const char *OutFile = "data2.txt"; //The decompressed file of the data.
int main(int argc, char **argv)
//1. compress file
if(DO_COMPRESS)
FCS *fcs1;
fcs1 = fcs_new();
fcs_compress(fcs1, InFile, CompressedFile);
fcs_free(fcs1);
//2. decompress file
if(DO_DECOMPRESS)
FCS *fcs2;
fcs2 = fcs_new();
fcs_decompress(fcs2, CompressedFile, OutFile);
fcs_free(fcs2);
system("pause");他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)求用C语言编译的文件压缩解压缩程序
本回答由提问者推荐
var sogou_ad_id=731547;
var sogou_ad_height=160;
var sogou_ad_width=690;C语言中压缩字符串的简单算法小结
转载 & & 作者：wuzhekai1985
这篇文章主要介绍了C语言中可用于实现字符串压缩的简单算法小结,列举了包括哈夫曼算法等三个核心的程序实现算法,需要的朋友可以参考下
应用中，经常需要将字符串压缩成一个整数，即字符串散列。比如下面这些问题：
（1）搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。请找出最热门的10个检索串。
（2）有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
（3）有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
（4）给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url。
（5）一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词。
这些问题都需要将字符串压缩成一个整数，或者说是散列到某个整数 M 。然后再进行取余操作，比如 M%16，就可以将该字符串放到编号为M%16的文件中，相同的字符串肯定是在同一个文件中。通过这种处理，就可以将一个大文件等价划分成若干小文件，而对于小文件，就可以用常规的方法处理，内排序、hash_map等等。最后将这些小文件的处理结果综合起来，就可以求得原问题的解。
下面介绍一些字符串压缩的算法。
方法1：最简单就是将所有字符加起来，代码如下：
unsigned long HashString(const char *pString, unsigned long tableSize)
unsigned long hashValue = 0;
while(*pString)
hashValue += *pString++;
return hashValue % tableS
分析：如果字符串的长度有限，而散列表比较大的话，浪费比较大。例如，如果字符串最长为16字节，那么用到的仅仅是散列表的前16*127=2032。假如散列表含2729项，那么2032以后的项都用不到。
方法2：将上次计算出来的hash值左移5位（乘以32），再和当前关键字相加，能得到较好的均匀分布的效果。
unsigned long HashString(const char *pString,unsigned long tableSize)
unsigned long hashValue = 0;
while (*pString)
hashValue = (hashValue && 5) + *pString++;
return hashValue % tableS
分析：这种方法需要遍历整个字符串，如果字符串比较大，效率比较低。
方法3：利用哈夫曼算法，假设只有0-9这十个字符组成的字符串，我们借助哈夫曼算法，直接来看实例：&
#define Size 10
int freq[Size];
string code[Size];
struct Node
Node(int freq_in):id(-1), freq(freq_in)
left = right = NULL;
struct NodeLess
bool operator()(const Node *a, const Node *b) const
return a-&freq & b-&
void init()
for(int i = 0; i & S ++i)
freq[i] = 0;
for(int i = 0; i & word.size(); ++i)
++freq[word[i]];
void dfs(Node *root, string res)
if(root-&id &= 0)
code[root-&id] =
if(NULL != root-&left)
dfs(root-&left, res+"0");
if(NULL != root-&right)
dfs(root-&right, res+"1");
void deleteNodes(Node *root)
if(NULL == root)
if(NULL == root-&left && NULL == root-&right)
deleteNodes(root-&left);
deleteNodes(root-&right);
void BuildTree()
priority_queue&Node*, vector&Node*&, NodeLess&
for(int i = 0; i & S ++i)
//0 == freq[i] 的情况未处理
Node *newNode = new Node(freq[i]);
newNode-&id =
nodes.push(newNode);
while(nodes.size() & 1)
Node *left = nodes.top();
nodes.pop();
Node *right = nodes.top();
nodes.pop();
Node *newNode = new Node(left-&freq + right-&freq);
newNode-&left =
newNode-&right =
nodes.push(newNode);
Node *root = nodes.top();
dfs(root, string(""));
deleteNodes(root);
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具}