Huffmann哈夫曼编码实现

/*********************************************************************************************************** Huffman.c 本演示程序提供了哈夫曼编码法的压缩和解压缩函数，并实现了对图象 文件的压缩和解压缩 **********************************************************************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> /* 函数原型 */ int Huffman_Compression(char * infilename, char * outfilename); int Huffman_Decompression(char * infilename, char * outfilename); /* 内部函数 */ unsigned short generate_code_table (); void build_code_tree (); void build_initial_heap (); void compress_image (); void get_frequency_count (); void build_decomp_tree (); void decompress_image (); /* 全局变量 */ short father[512]; unsigned short code[256], heap_length; unsigned long compress_charcount, file_size, heap[257]; unsigned char code_length[256]; long frequency_count[512]; short decomp_tree[512]; FILE *ifile, *ofile; /* 主程序 */ void main(int argc, char *argv[]) { printf("Huffman compression and decompression utility\n"); if (4 != argc) { printf("\nUsage : huffman -c|d sourcefilename targetfilename\n"); exit(0); } if (! strcmp(argv[1], "-c")) { printf("\nCompress..."); Huffman_Compression(argv[2], argv[3]); } else if (! strcmp(argv[1], "-d")) { printf("\nDecompress..."); Huffman_Decompression(argv[2], argv[3]); } else printf("\nUnknow command.\n"); } /********************************************************************************* Huffman_Compression () 用Huffman编码压缩指定的文件，并将结果存为新的文件 ********************************************************************************/ int Huffman_Compression(char * infilename, char * outfilename) { if ((ifile = fopen (infilename, "rb")) != NULL) { fseek (ifile, 0L, 2); file_size = (unsigned long) ftell (ifile); fseek (ifile, 0L, 0); get_frequency_count (); build_initial_heap (); build_code_tree (); if (!generate_code_table ()) { printf ("ERROR! Code Value Out of Range. Cannot Compress.\n"); return 0; } else { if ((ofile = fopen (outfilename, "wb")) != NULL) { fwrite (&file_size, sizeof (file_size), 1, ofile); fwrite (code, 2, 256, ofile); fwrite (code_length, 1, 256, ofile); fseek (ifile, 0L, 0); compress_image (); fclose (ofile); } else { printf("\nERROR: Couldn't create output file %s\n", outfilename); return 0; } } fclose (ifile); } else { printf ("\nERROR: %s -- File not found!\n", infilename); return 0; } return 1; } /************************************************************************** COMPRESS_IMAGE () 本函数进行数据的压缩操作 **************************************************************************/ void compress_image () { register unsigned int thebyte = 0; register short loop1; register unsigned short current_code; register unsigned long loop; unsigned short current_length, dvalue; unsigned long curbyte = 0; short curbit = 7; for (loop = 0L; loop < file_size; loop++) { dvalue = (unsigned short) getc (ifile); current_code = code[dvalue]; current_length = (unsigned short) code_length[dvalue]; for (loop1 = current_length-1; loop1 >= 0; --loop1) { if ((current_code >> loop1) & 1) thebyte |= (char) (1 << curbit); if (--curbit < 0) { putc (thebyte, ofile); thebyte = 0; curbyte++; curbit = 7; } } } putc (thebyte, ofile); compress_charcount = ++curbyte; } /************************************************************************** GENERATE_CODE_TABLE () 本函数生成压缩码表 **************************************************************************/ unsigned short generate_code_table () { register unsigned short loop; register unsigned short current_length; register unsigned short current_bit; unsigned short bitcode; short parent; for (loop = 0; loop < 256; loop++) if (frequency_count[loop]) { current_length = bitcode = 0; current_bit = 1; parent = father[loop]; while (parent) { if (parent < 0) { bitcode += current_bit; parent = -parent; } parent = father[parent]; current_bit <<= 1; current_length++; } code[loop] = bitcode; if (current_length > 16) return (0); else code_length[loop] = (unsigned char) current_length; } else code[loop] = code_length[loop] = 0; return (1); } /************************************************************************** BUILD_CODE_TREE () 建立压缩编码树 **************************************************************************/ void build_code_tree () { void reheap (); register unsigned short findex; register unsigned long heap_value; while (heap_length != 1) { heap_value = heap[1]; heap[1] = heap[heap_length--]; reheap (1); findex = heap_length + 255; frequency_count[findex] = frequency_count[heap[1]] + frequency_count[heap_value]; father[heap_value] = findex; father[heap[1]] = -findex; heap[1] = findex; reheap (1); } father[256] = 0; } /************************************************************************** REHEAP () 从当前的堆树结构中建立逻辑堆结构 **************************************************************************/ void reheap (heap_entry) unsigned short heap_entry; { register unsigned short index; register unsigned short flag = 1; unsigned long heap_value; heap_value = heap[heap_entry]; while ((heap_entry <= (heap_length >> 1)) && (flag)) { index = heap_entry << 1; if (index < heap_length) if (frequency_count[heap[index]] >= frequency_count[heap[index+1]]) index++; if (frequency_count[heap_value] < frequency_count[heap[index]]) flag--; else { heap[heap_entry] = heap[index]; heap_entry = index; } } heap[heap_entry] = heap_value; } /************************************************************************** BUILD_INITIAL_HEAP () 本函数从初始的频率统计数据中建立堆结构 **************************************************************************/ void build_initial_heap () { void reheap (); register unsigned short loop; heap_length = 0; for (loop = 0; loop < 256; loop++) if (frequency_count[loop]) heap[++heap_length] = (unsigned long) loop; for (loop = heap_length; loop > 0; loop--) reheap (loop); } /************************************************************************** GET_FREQUENCY_COUNT () 本函数对需要进行压缩的数据进行频率统计 **************************************************************************/ void get_frequency_count () { register unsigned long loop; for (loop = 0; loop < file_size; loop++) frequency_count[getc (ifile)]++; } /************************************************************************** Huffman_Decompression () 本函数进行Huffman解码 **************************************************************************/ int Huffman_Decompression(char * infilename, char * outfilename) { if ((ifile = fopen (infilename, "rb")) != NULL) { fre