計(jì)算哈夫曼編碼長度

2019-11-09 19:21:21

字體：大中小

供稿：網(wǎng)友

本篇文章向大家介紹一個(gè)不用構(gòu)造哈夫曼樹的方法來計(jì)算哈夫曼編碼的長度,這對于較大字符集有極大的優(yōu)勢,因?yàn)闃?gòu)造一個(gè)樹要花費(fèi)相當(dāng)大的空間和時(shí)間,本算法的時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度為O(N);參考文獻(xiàn)<深入搜索引擎>第二章程序處理:高亮顯示#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <sys/types.h>#include <sys/stat.h>#include <fcntl.h>#include <unistd.h>using namespace std;#define BUFF_SIZE 4096#define HASH_SIZE 256char buff[BUFF_SIZE]; //緩沖區(qū) int hash[HASH_SIZE]; //統(tǒng)計(jì)每個(gè)字符出現(xiàn)的次數(shù)int heap[(HASH_SIZE<<1)+2];int pos[HASH_SIZE+1][3];//內(nèi)部節(jié)點(diǎn) , 0和1記錄子結(jié)點(diǎn)位置,3節(jié)錄當(dāng)前的深度int tlen[HASH_SIZE+1]; //記錄每個(gè)葉子結(jié)點(diǎn)的深度int fd; //文件描述符int sym_num ; //文件中出現(xiàn)的符號數(shù)量int SUM(0); //文件中字符總數(shù)//初始化程序void init(const char * pathname){ memset(buff , 0 , sizeof(buff)); memset(hash , 0 , sizeof(hash)); memset(heap , 0 , sizeof(heap)); memset(pos , 0 , sizeof(pos)); memset(tlen , 0 , sizeof(tlen)); //打開文件 fd = open(pathname , O_RDONLY); if(fd < 0){ PRintf("init: %s dont exit!/n" , pathname); exit(1); }}//統(tǒng)計(jì)文件中每個(gè)符號出現(xiàn)的次數(shù)void count_symbol(){ lseek(fd , 0 , SEEK_SET); while(read(fd , buff , BUFF_SIZE)){ SUM += strlen(buff); for(int i=strlen(buff) - 1;i>=0;i--) hash[(unsigned int)(buff[i] & 0xFF)]++; } //記錄出現(xiàn)的符號數(shù)量; for(int i = HASH_SIZE - 1; i >= 0; i--) if(hash[i])sym_num++;}//建立一個(gè)最小堆void build_min_heap(){ for(int i=sym_num;i>0;i--){ int p = i >> 1 , j = i; while(p >= 1){ if(heap[heap[p]] > heap[heap[j]]) std::swap(heap[j] , heap[p]); j = p; p >>= 1; } }}//每次取出最小數(shù)之后重新調(diào)整堆,//h 指推中元素的個(gè)數(shù)void heap_adjust(int h){ int t = 1 , p , q , l; while(t<h){ p = t<<1; q = p + 1; l = t; if(p <= h && heap[heap[p]] < heap[heap[t]])l = p; if(q <= h && heap[heap[q]] < heap[heap[l]])l = q; if(l == t)break; std::swap(heap[l] , heap[t]); t = l; }}//計(jì)算每個(gè)字符編碼的長度void huff_length(){ int i , j , p , h , m1 , m2; for(i=1 , p=0;i<=sym_num;i++){ while(!hash[p]) p++; heap[sym_num + i] = hash[p]; heap[i] = sym_num + i; p++; } h = sym_num; //對1到n建立最小堆 build_min_heap(); while(h>1){ //取出最小數(shù) m1 = heap[heap[1]]; pos[h][0] = heap[1]; heap[1] = heap[h]; h--; heap_adjust(h); //取出次小數(shù) m2 = heap[heap[1]]; pos[h+1][1] = heap[1]; //最后數(shù)和次小數(shù)之和放在堆的最后一個(gè)位置 heap[h+1] = m1 + m2; //重新指向最新合并的結(jié)點(diǎn) heap[1] = h+1; heap_adjust(h); } //統(tǒng)計(jì)編碼長度 , 線性時(shí)間統(tǒng)計(jì) int ts = sym_num << 1; for(int i=2;i<=sym_num;i++){ if(pos[i][0] <= sym_num) pos[pos[i][0]][2] = pos[i][2] + 1; else tlen[pos[i][0] - sym_num] = pos[i][2] + 1; if(pos[i][1] <= sym_num) pos[pos[i][1]][2] = pos[i][2] + 1; else tlen[pos[i][1] - sym_num] = pos[i][2] + 1; }}int main(){ init("data.dat"); count_symbol(); huff_length(); unsigned int sum = 0; for(int i=1;i<=sym_num;i++) sum += tlen[i] * heap[sym_num + i]; cout<<SUM <<"/t/t"<<sum<<"/t/t"<<sum*1.0/SUM<<endl; return 0;}

上一篇：每日一題（1）：