計算哈夫曼編碼長度

2019-11-10 17:45:02

字體：大中小

來源：轉載

供稿：網友

本篇文章向大家介紹一個不用構造哈夫曼樹的方法來計算哈夫曼編碼的長度,這對于較大字符集有極大的優勢,因為構造一個樹要花費相當大的空間和時間,本算法的時間復雜度為O(nlogn),空間復雜度為O(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]; //緩沖區 int hash[HASH_SIZE]; //統計每個字符出現的次數int heap[(HASH_SIZE<<1)+2];int pos[HASH_SIZE+1][3];//內部節點 , 0和1記錄子結點位置,3節錄當前的深度int tlen[HASH_SIZE+1]; //記錄每個葉子結點的深度int fd; //文件描述符int sym_num ; //文件中出現的符號數量int SUM(0); //文件中字符總數//初始化程序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); }}//統計文件中每個符號出現的次數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)]++; } //記錄出現的符號數量; for(int i = HASH_SIZE - 1; i >= 0; i--) if(hash[i])sym_num++;}//建立一個最小堆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; } }}//每次取出最小數之后重新調整堆,//h 指推中元素的個數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; }}//計算每個字符編碼的長度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){ //取出最小數 m1 = heap[heap[1]]; pos[h][0] = heap[1]; heap[1] = heap[h]; h--; heap_adjust(h); //取出次小數 m2 = heap[heap[1]]; pos[h+1][1] = heap[1]; //最后數和次小數之和放在堆的最后一個位置 heap[h+1] = m1 + m2; //重新指向最新合并的結點 heap[1] = h+1; heap_adjust(h); } //統計編碼長度 , 線性時間統計 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;}

上一篇：藍橋測試2->2013年第四屆藍橋杯省賽A組

下一篇：異常捕獲