當前位置:首頁 » 文件管理 » 哈夫曼壓縮解壓

哈夫曼壓縮解壓

發布時間: 2022-11-27 21:12:02

A. 用huffman演算法實現「文件的壓縮解壓」怎麼做啊

我寫過一個Huffman編碼,但只是生成了編碼表,沒做成壓縮,但可以利用查表做成文件壓縮,另外用的是C++,改成C的話比較容易,只要把動下內存分配就行了,想要的話,msn:[email protected]

B. 有關哈夫曼編碼壓縮與解壓縮的問題.

壓縮代碼非常簡單,首先用ASCII值初始化511個哈夫曼節點:
CHuffmanNode nodes[511];
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
然後,計算在輸入緩沖區數據中,每個ASCII碼出現的頻率:
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然後,根據頻率進行排序:
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
現在,構造哈夫曼樹,獲取每個ASCII碼對應的位序列:
int nNodeCount = GetHuffmanTree(nodes);
構造哈夫曼樹非常簡單,將所有的節點放到一個隊列中,用一個節點替換兩個頻率最低的節點,新節點的頻率就是這兩個節點的頻率之和。這樣,新節點就是兩個被替換節點的父節點了。如此循環,直到隊列中只剩一個節點(樹根)。
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;
這里我用了一個好的訣竅來避免使用任何隊列組件。我先前就直到ASCII碼只有256個,但我分配了511個(CHuffmanNode nodes[511]),前255個記錄ASCII碼,而用後255個記錄哈夫曼樹中的父節點。並且在構造樹的時候只使用一個指針數組(ChuffmanNode *pNodes[256])來指向這些節點。同樣使用兩個變數來操作隊列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接著,壓縮的最後一步是將每個ASCII編碼寫入輸出緩沖區中:
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex>>3): >>3 以8位為界限右移後到達右邊位元組的前面
(nDesIndex&7): &7 得到最高位.
注意:在壓縮緩沖區中,我們必須保存哈夫曼樹的節點以及位序列,這樣我們才能在解壓縮時重新構造哈夫曼樹(只需保存ASCII值和對應的位序列)。
解壓縮
解壓縮比構造哈夫曼樹要簡單的多,將輸入緩沖區中的每個編碼用對應的ASCII碼逐個替換就可以了。只要記住,這里的輸入緩沖區是一個包含每個ASCII值的編碼的位流。因此,為了用ASCII值替換編碼,我們必須用位流搜索哈夫曼樹,直到發現一個葉節點,然後將它的ASCII值添加到輸出緩沖區中:
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft)
{
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}
過程
#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#include<math.h>
#define M 10
typedef struct Fano_Node
{
char ch;
float weight;
}FanoNode[M];
typedef struct node
{
int start;
int end;
struct node *next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode *front;
LinkQueueNode *rear;
}LinkQueue;
void EnterQueue(LinkQueue *q,int s,int e)
{
LinkQueueNode *NewNode;
NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
if(NewNode!=NULL)
{
NewNode->start=s;
NewNode->end=e;
NewNode->next=NULL;
q->rear->next=NewNode;
q->rear=NewNode;
}
else printf("Error!");
}
//***按權分組***//
void Divide(FanoNode f,int s,int *m,int e)
{
int i;
float sum,sum1;
sum=0;
for(i=s;i<=e;i++)
sum+=f.weight;
*m=s;
sum1=0;
for(i=s;i<e;i++)
{
sum1+=f.weight;
*m=fabs(sum-2*sum1)>fabs(sum-2*sum1-2*f.weight)?(i+1):*m;
if(*m==i)
break;
}
}
main()
{
int i,j,n,max,m,h[M];
int sta,mid,end;
float w;
char c,fc[M][M];
FanoNode FN;
LinkQueueNode *p;
LinkQueue *Q;
//***初始化隊Q***//
Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
Q->rear=Q->front;
Q->front->next=NULL;
printf("\t***FanoCoding***\n");
printf("Please input the number of node:"); /*輸入信息*/
scanf("%d",&n);
i=1;
while(i<=n)
{
printf("%d weight and node:",i);
scanf("%f %c",&FN.weight,&FN.ch);
for(j=1;j<i;j++)
{
if(FN.ch==FN[j].ch)
{
printf("Same node!!!\n");
break;
}
}
if(i==j)
i++;
}
for(i=1;i<=n;i++) /*排序*/
{
max=i+1;
for(j=max;j<=n;j++)
max=FN[max].weight<FN[j].weight?j:max;
if(FN.weight<FN[max].weight)
{
w=FN.weight;
FN.weight=FN[max].weight;
FN[max].weight=w;
c=FN.ch;
FN.ch=FN[max].ch;
FN[max].ch=c;
}
}
for(i=1;i<=n;i++) /*初始化h*/
h=0;
EnterQueue(Q,1,n); /*1和n進隊*/
while(Q->front->next!=NULL)
{
p=Q->front->next; /*出隊*/
Q->front->next=p->next;
if(p==Q->rear)
Q->rear=Q->front;
sta=p->start;
end=p->end;
free(p);
Divide(FN,sta,&m,end); /*按權分組*/
for(i=sta;i<=m;i++)
{
fc[h]='0';
h++;
}
if(sta!=m)
EnterQueue(Q,sta,m);
else
fc[sta][h[sta]]='\0';
for(i=m+1;i<=end;i++)
{
fc[h]='1';
h++;
}
if(m==sta&&(m+1)==end) //如果分組後首元素的下標與中間元素的相等,
{ //並且和最後元素的下標相差為1,則編碼碼字字元串結束
fc[m][h[m]]='\0';
fc[end][h[end]]='\0';
}
else
EnterQueue(Q,m+1,end);
}
for(i=1;i<=n;i++) /*列印編碼信息*/
{
printf("%c:",FN.ch);
printf("%s\n",fc);
}
system("pause");
}
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define N 100
#define M 2*N-1
typedef char * HuffmanCode[2*M];
typedef struct
{
char weight;
int parent;
int LChild;
int RChild;
}HTNode,Huffman[M+1];
typedef struct Node
{
int weight; /*葉子結點的權值*/
char c; /*葉子結點*/
int num; /*葉子結點的二進制碼的長度*/
}WNode,WeightNode[N];
/***產生葉子結點的字元和權值***/
void CreateWeight(char ch[],int *s,WeightNode *CW,int *p)
{
int i,j,k;
int tag;
*p=0;
for(i=0;ch!='\0';i++)
{
tag=1;
for(j=0;j<i;j++)
if(ch[j]==ch)
{
tag=0;
break;
}
if(tag)
{
(*CW)[++*p].c=ch;
(*CW)[*p].weight=1;
for(k=i+1;ch[k]!='\0';k++)
if(ch==ch[k])
(*CW)[*p].weight++;
}
}
*s=i;
}
/********創建HuffmanTree********/
void CreateHuffmanTree(Huffman *ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
for(i=1;i<=n;i++)
{
(*ht).weight =w.weight;
(*ht).parent=0;
(*ht).LChild=0;
(*ht).RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
(*ht).weight=0;
(*ht).parent=0;
(*ht).LChild=0;
(*ht).parent=0;
}
for(i=n+1;i<=2*n-1;i++)
{
for(j=1;j<=i-1;j++)
if(!(*ht)[j].parent)
break;
s1=j; /*找到第一個雙親不為零的結點*/
for(;j<=i-1;j++)
if(!(*ht)[j].parent)
s1=(*ht)[s1].weight>(*ht)[j].weight?j:s1;
(*ht)[s1].parent=i;
(*ht).LChild=s1;
for(j=1;j<=i-1;j++)
if(!(*ht)[j].parent)
break;
s2=j; /*找到第一個雙親不為零的結點*/
for(;j<=i-1;j++)
if(!(*ht)[j].parent)
s2=(*ht)[s2].weight>(*ht)[j].weight?j:s2;
(*ht)[s2].parent=i;
(*ht).RChild=s2;
(*ht).weight=(*ht)[s1].weight+(*ht)[s2].weight;
}
}
/***********葉子結點的編碼***********/
void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode *h,WeightNode *weight,int m,int n)
{
int i,j,k,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
c=i;
p=ht.parent;
while(p)
{
start--;
if(ht[p].LChild==c)
cd[start]='0';
else
cd[start]='1';
c=p;
p=ht[p].parent;
}
(*weight).num=n-start;
(*h)=(char *)malloc((n-start)*sizeof(char));
p=-1;
strcpy((*h),&cd[start]);
}
system("pause");
}
/*********所有字元的編碼*********/
void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode *hc,WeightNode weight,int n,int m)
{
int i,j,k;
for(i=0;i<m;i++)
{
for(k=1;k<=n;k++) /*從(*weight)[k].c中查找與ch相等的下標K*/
if(ch==weight[k].c)
break;
(*hc)=(char *)malloc((weight[k].num+1)*sizeof(char));
for(j=0;j<=weight[k].num;j++)
(*hc)[j]=h[k][j];
}
}
/*****解碼*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf("***StringInformation***\n");
while(i<m)
{
p=2*n-1;
for(j=0;hc[j]!='\0';j++)
{
if(hc[j]=='0')
p=ht[p].LChild;
else
p=ht[p].RChild;
}
printf("%c",w[p].c); /*列印原信息*/
i++;
}
}
main()
{
int i,n,m,s1,s2,j; /*n為葉子結點的個數*/
char ch[N],w[N]; /*ch[N]存放輸入的字元串*/
Huffman ht; /*二叉數 */
HuffmanCode h,hc; /* h存放葉子結點的編碼,hc 存放所有結點的編碼*/
WeightNode weight; /*存放葉子結點的信息*/
printf("\t***HuffmanCoding***\n");
printf("please input information :");
gets(ch); /*輸入字元串*/
CreateWeight(ch,&m,&weight,&n); /*產生葉子結點信息,m為字元串ch[]的長度*/
printf("***WeightInformation***\n Node "); /*輸出葉子結點的字元與權值*/
for(i=1;i<=n;i++)
printf("%c ",weight.c);
printf("\nWeight ");
for(i=1;i<=n;i++)
printf("%d ",weight.weight);
CreateHuffmanTree(&ht,weight,n); /*產生Huffman樹*/
printf("\n***HuffamnTreeInformation***\n");
for(i=1;i<=2*n-1;i++) /*列印Huffman樹的信息*/
printf("\t%d %d %d %d\n",i,ht.weight,ht.parent,ht.LChild,ht.RChild);
CrtHuffmanNodeCode(ht,ch,&h,&weight,m,n); /*葉子結點的編碼*/
printf(" ***NodeCode***\n"); /*列印葉子結點的編碼*/
for(i=1;i<=n;i++)
{
printf("\t%c:",weight.c);
printf("%s\n",h);
}
CrtHuffmanCode(ch,h,&hc,weight,n,m); /*所有字元的編碼*/
printf("***StringCode***\n"); /*列印字元串的編碼*/
for(i=0;i<m;i++)
printf("%s",hc);
system("pause");
TrsHuffmanTree(ht,weight,hc,n,m); /*解碼*/
system("pause");
}

C. 基於哈夫曼樹的文件壓縮/解壓程序 源代碼

哈夫曼的C++演算法

#define INT_MAX 10000
#define ENCODING_LENGTH 1000
#include "stdio.h"
#include "string.h"
#include "malloc.h"
typedef enum{none,left_child,right_child} Which;//標記是左孩子還是右孩子
typedef char Elemtype;
typedef struct TNode{
Elemtype letter;
int weight;
int parent;
Which sigh;
char *code;
}HTNode,*HuffmanTree;
int n;
char coding[50];//儲存代碼
char str[ENCODING_LENGTH];//保存要翻譯的句子
void InitTreeNode(HuffmanTree &HT)
{//初始前N個結點,後M-N個結點置空
int i;int w;char c;
int m=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((m)*sizeof(HTNode));
printf("input %d database letter and weight",n);
p=HT;
getchar();
for (i=1;i<=n;i++){
scanf("%c%d",&c,&w);
p->code='\0';
p->letter=c;
p->parent=0;
p->sigh=none;
p->weight=w;
p++;
getchar();
}
for (;i<=m;i++,p++){
p->code='\0';
p->letter=' ';
p->parent=0;
p->sigh=none;
p->weight=0;
}
}//INITTREENODE
void Select(HuffmanTree HT,int end,int *s1,int *s2)
{//在0~END之間,找出最小和次小的兩個結點序號,返回S1,S2
int i;
int min1=INT_MAX;
int min2;
for (i=0;i<=end;i++){//找最小的結點序號
if (HT[i].parent==0&&HT[i].weight<min1){
*s1=i;
min1=HT[i].weight;
}
}
min2=INT_MAX;
for(i=0;i<=end;i++){//找次小結點的序號
if (HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight){
*s2=i;
min2=HT[i].weight;
}
}
}
void HuffmanTreeCreat(HuffmanTree &HT)
{//建立HUFFMAN樹
int i;int m=2*n-1;
int s1,s2;
for(i=n;i<m;i++){
Select(HT,i-1,&s1,&s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[s1].sigh=left_child;
HT[s2].sigh=right_child;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}

void HuffmanTreeCode(HuffmanTree HT)
{//HUFFMAN解碼
int i;
char *temp;
temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
int p;int s;
for (i=0;i<n;i++){
p=i;
s=n-1;
while (HT[p].parent!=0){//從結點回溯,左孩子為0,右孩子為1
if (HT[p].sigh==left_child)
temp[--s]='0';
else if (HT[p].sigh==right_child)
temp[--s]='1';
p=HT[p].parent;
}
HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配結點碼長度的內存空間
strcpy(HT[i].code,temp+s);
printf("%s\n",HT[i].code);
}
}
void GetCodingSen(char *sencence)
{//輸入要編碼的句子
int l;
gets(sencence);
l=strlen(sencence);
sencence[l]='\0';
}
void HuffmanTreeEncoding(char sen[],HuffmanTree HT)
{//將句子進行編碼
int i=0;int j;
while(sen[i]!='\0'){
for(j=0;j<n;j++){
if (HT[j].letter==sen[i]) //字母吻合則用代碼取代
{strcat(coding,HT[j].code);
break;
}
}
i++;
if (sen[i]==32) i++;
}
printf("\n%s",coding);
}
void HuffmanTreeDecoding(HuffmanTree HT,char code[])
{//HUFFMAN解碼過程,將代碼翻譯為句子
char sen[100];
char temp[50];
char voidstr[]=" ";
int i;int j;
int t=0;int s=0;
for(i=0;i<strlen(code);i++){
temp[t++]=code[i];
for(j=0;j<n;j++){
if (strcmp(HT[j].code,temp)==0){//代碼段吻合
sen[s]=HT[j].letter;s++;
strcpy(temp,voidstr);//將TEMP置空
t=0;
break;
}
}
}
printf("\n%s",sen);
}

void main()
{
HTNode hnode;
HuffmanTree huff;
huff=&hnode;
printf("input the letter for coding number\n");
scanf("%d",&n);
InitTreeNode(huff);
HuffmanTreeCreat(huff);
HuffmanTreeCode(huff);
GetCodingSen(str);
HuffmanTreeEncoding(str,huff);
HuffmanTreeDecoding(huff,coding);
}

D. 基於哈夫曼樹的文件壓縮與解壓演算法(C++版)

static unsigned int out = 0x01;

void write_bit(bool bit)
{
out <<= 1; // shift byte to make room
if (bit) out |= 0x01; // set lowest bit id desired

if (out & 0x100) { // was the sentinel bit shifted out?
write_byte(out & 0xff); // final output of 8-bit chunk
out = 0x01; // reset to sentinel vylue
}
}

void flush_bit()
{
while (out != 0x01) write_bit(false);
}

int main()
{
write_bit(1);
write_bit(0);
write_bit(1);
// ...
flush_bit();

return 0;
}

E. 如何用哈夫曼編碼實現英文文本的壓縮和解壓縮

根據信源壓縮編碼——Huffman編碼的原理,製作對英文文本進行壓縮和解壓縮的軟體。要求軟體有簡單的用戶界面,軟體能夠對運行的狀態生成報告,分別是:字元頻率統計報告、編碼報告、壓縮程度信息報告、碼表存儲空間報告。

F. 演算法解析:哈夫曼(huffman)壓縮演算法

本篇將介紹 哈夫曼壓縮演算法(Huffman compression)

眾所周知,計算機存儲數據時,實際上存儲的是一堆0和1(二進制)。

如果我們存儲一段字元:ABRACADABRA!

那麼計算機會把它們逐一翻譯成二進制,如A:01000001;B: 01000010; !: 00001010.

每個字元佔8個bits, 這一整段字元則至少佔12*8=96 bits。

但如果我們用一些特殊的值來代表這些字元,如:

圖中,0代表A; 1111代表B;等等。此時,存儲這段字元只需30bits,比96bits小多了,達到了壓縮的目的。

我們需要這么一個表格來把原數據翻譯成特別的、占空間較少的數據。同時,我們也可以用這個表格,把特別的數據還原成原數據。

首先,為了避免翻譯歧義,這個表格需滿足一個條件: 任何一個字元用的值都不能是其它字元的前綴

我們舉個反例:A: 0; B: 01;這里,A的值是B的值的前綴。如果壓縮後的數據為01xxxxxx,x為0或者1,那麼這個數據應該翻譯成A1xxxxxx, 還是Bxxxxxxx?這樣就會造成歧義。

然後,不同的表格會有不同的壓縮效果,如:

這個表格的壓縮效果更好。

那麼我們如何找到 最好的表格 呢?這個我們稍後再講。

為了方便閱讀,這個表格是可以寫成一棵樹的:

這棵樹的節點左邊是0,右邊是1。任何含有字元的節點都沒有非空子節點。(即上文提及的前綴問題。)

這棵樹是在壓縮的過程中建成的,這個表格是在樹形成後建成的。用這個表格,我們可以很簡單地把一段字元變成壓縮後的數據,如:

原數據:ABRACADABRA!

表格如上圖。

令壓縮後的數據為S;

第一個字元是A,根據表格,A:11,故S=11;

第二個字元是B,根據表格,B:00,故S=1100;

第三個字元是R,根據表格,R:011,故S=1100011;

如此類推,讀完所有字元為止。

壓縮搞定了,那解壓呢?很簡單,跟著這棵樹讀就行了:

壓縮後的數據S=11000111101011100110001111101

記住,讀到1時,往右走,讀到0時,往左走。

令解壓後的字元串為D;

從根節點出發,第一個數是1,往右走:

第二個數是1,往右走:

讀到有字元的節點,返回此字元,加到字元串D里。D:A;

返回根節點,繼續讀。

第三個數是0,往左走:

第四個數是0,往左走:

讀到有字元的節點,返回此字元,加到字元串D里。D:AB;

返回根節點,繼續讀。

第五個數是0,往左走:

第六個數是1,往右走:

第七個數是1,往右走:

讀到有字元的節點,返回此字元,加到字元串D里。D:ABR;

返回根節點,繼續讀。

如此類推,直到讀完所有壓縮後的數據S為止。

壓縮與解壓都搞定了之後 我們需要先把原數據讀一遍,並把每個字元出現的次數記錄下來。如:

ABRACADABRA!中,A出現了5次;B出現了2次;C出現了1次;D出現了1次;R出現了2次;!出現了1次。

理論上,出現頻率越高的字元,我們給它一個佔用空間越小的值,這樣,我們就可以有最佳的壓縮率

由於哈夫曼壓縮演算法這塊涉及內容較多 ,文章篇幅很長;全文全方面講解了Compose布局的各方面知識。更多Android前言技術進階,我自薦一套《 完整的Android的資料,以及一些視頻課講解 現在私信發送「進階」或者「筆記」即可免費獲取



最後我想說:

對於程序員來說,要學習的知識內容、技術有太多太多,要想不被環境淘汰就只有不斷提升自己,從來都是我們去適應環境,而不是環境來適應我們

技術是無止境的,你需要對自己提交的每一行代碼、使用的每一個工具負責,不斷挖掘其底層原理,才能使自己的技術升華到更高的層面

Android 架構師之路還很漫長,與君共勉

G. 霍夫曼 解壓縮

哈夫曼編碼(Huffman Coding)是一種編碼方式,以哈夫曼樹—即最優二叉樹,帶權路徑長度最小的二叉樹,經常應用於數據壓縮。 在計算機信息處理中,「哈夫曼編碼」是一種一致性編碼法(又稱"熵編碼法"),用於數據的無損耗壓縮。這一術語是指使用一張特殊的編碼表將源字元(例如某文件中的一個符號)進行編碼。這張編碼表的特殊之處在於,它是根據每一個源字元出現的估算概率而建立起來的(出現概率高的字元使用較短的編碼,反之出現概率低的則使用較長的編碼,這便使編碼之後的字元串的平均期望長度降低,從而達到無損壓縮數據的目的)。這種方法是由David.A.Huffman發展起來的。 例如,在英文中,e的出現概率很高,而z的出現概率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時,e極有可能用一個位(bit)來表示,而z則可能花去25個位(不是26)。用普通的表示方法時,每個英文字母均佔用一個位元組(byte),即8個位。二者相比,e使用了一般編碼的1/8的長度,z則使用了3倍多。倘若我們能實現對於英文中各個字母出現概率的較准確的估算,就可以大幅度提高無損壓縮的比例。

本文描述在網上能夠找到的最簡單,最快速的哈夫曼編碼。本方法不使用任何擴展動態庫,比如STL或者組件。只使用簡單的C函數,比如:memset,memmove,qsort,malloc,realloc和memcpy。
因此,大家都會發現,理解甚至修改這個編碼都是很容易的。

背景
哈夫曼壓縮是個無損的壓縮演算法,一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號(例如,文本文件中的字元)用一個特定長度的位序列替代。因此,在文件中出現頻率高的符號,使用短的位序列,而那些很少出現的符號,則用較長的位序列。
編碼使用
我用簡單的C函數寫這個編碼是為了讓它在任何地方使用都會比較方便。你可以將他們放到類中,或者直接使用這個函數。並且我使用了簡單的格式,僅僅輸入輸出緩沖區,而不象其它文章中那樣,輸入輸出文件。
bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
要點說明
速度
為了讓它(huffman.cpp)快速運行,我花了很長時間。同時,我沒有使用任何動態庫,比如STL或者MFC。它壓縮1M數據少於100ms(P3處理器,主頻1G)。
壓縮
壓縮代碼非常簡單,首先用ASCII值初始化511個哈夫曼節點:
CHuffmanNode nodes[511];
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
然後,計算在輸入緩沖區數據中,每個ASCII碼出現的頻率:
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然後,根據頻率進行排序:
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
現在,構造哈夫曼樹,獲取每個ASCII碼對應的位序列:
int nNodeCount = GetHuffmanTree(nodes);
構造哈夫曼樹非常簡單,將所有的節點放到一個隊列中,用一個節點替換兩個頻率最低的節點,新節點的頻率就是這兩個節點的頻率之和。這樣,新節點就是兩個被替換節點的父節點了。如此循環,直到隊列中只剩一個節點(樹根)。
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;
這里我用了一個好的訣竅來避免使用任何隊列組件。我先前就直到ASCII碼只有256個,但我分配了511個(CHuffmanNode nodes[511]),前255個記錄ASCII碼,而用後255個記錄哈夫曼樹中的父節點。並且在構造樹的時候只使用一個指針數組(ChuffmanNode *pNodes[256])來指向這些節點。同樣使用兩個變數來操作隊列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接著,壓縮的最後一步是將每個ASCII編碼寫入輸出緩沖區中:
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex>>3): >>3 以8位為界限右移後到達右邊位元組的前面
(nDesIndex&7): &7 得到最高位.
注意:在壓縮緩沖區中,我們必須保存哈夫曼樹的節點以及位序列,這樣我們才能在解壓縮時重新構造哈夫曼樹(只需保存ASCII值和對應的位序列)。
解壓縮
解壓縮比構造哈夫曼樹要簡單的多,將輸入緩沖區中的每個編碼用對應的ASCII碼逐個替換就可以了。只要記住,這里的輸入緩沖區是一個包含每個ASCII值的編碼的位流。因此,為了用ASCII值替換編碼,我們必須用位流搜索哈夫曼樹,直到發現一個葉節點,然後將它的ASCII值添加到輸出緩沖區中:
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft)
{
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}

H. 哈夫曼壓縮文件如何選中目標文件

方法如下:

1、首先,我們打開我們電腦上面的excel,然後我們在任意一個單元格中輸入文字;

2、然後我們點擊圖示中的那個按鈕;

3、然後我們任意點擊一個單元格,之後我們點擊圖示中的下拉箭頭,彈出的界面,我們點擊粘貼;

4、之後我們就可以看到被我們粘貼了,我們點擊任意的單元格,然後都可以按照之前的方法進行粘貼。

I. 如何用哈夫曼編碼實現英文文本的壓縮和解壓縮

哈夫曼壓縮是個無損的壓縮演算法,一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號(例如,文本文件中的字元)用一個特定長度的位序列替代。因此,在文件中出現頻率高的符號,使用短的位序列,而那些很少出現的符號,則用較長的位序列

J. Huffman編碼可以破解加密的壓縮文件嘛

你說的應該是WinRAR這個軟體加密的壓縮文件吧。
Huffman編碼是不可也破解的,Huffman編碼可以壓縮與解壓縮文件,只有用Huffman編碼壓縮的文件才能用Huffman編碼解壓縮。簡單講,就是用Huffman編碼加密的文件,才能用Huffman編碼解密。
WinRAR這個軟體加密的壓縮文件是目前比較安全的加密,目前網上已知的破解方法只有暴力破解。理論上講,密碼都可以用暴力破解出來;實際上,11位以上的密碼,包含數字、字母、符號的密碼是無法破解出來的。
如果你的密碼是純數字(9位以下,包含9位),一般可以破解出來。

熱點內容
c語言單詞計數 發布:2023-01-29 17:24:31 瀏覽:533
我的世界伺服器斗羅大陸網易 發布:2023-01-29 17:22:40 瀏覽:912
PC機和伺服器怎麼連接 發布:2023-01-29 17:20:35 瀏覽:535
我的世界紫霄伺服器 發布:2023-01-29 17:19:41 瀏覽:458
連接作業幫伺服器失敗怎麼辦 發布:2023-01-29 17:16:48 瀏覽:235
windowspython升級 發布:2023-01-29 17:16:36 瀏覽:635
krs解壓 發布:2023-01-29 17:08:18 瀏覽:323
如何配置宮本的銘文 發布:2023-01-29 17:05:40 瀏覽:742
操作sqlserver資料庫 發布:2023-01-29 17:02:52 瀏覽:678
sql不區分大小寫查詢 發布:2023-01-29 17:02:51 瀏覽:384