哈夫曼編碼壓縮文件

⑴ 哈夫曼編碼做壓縮軟體的問題c++

因為32個0、1是4個位元組。（因為8個0、1是一個位元組）
但是它這個東西算出來的是一個0、1佔一個位元組的那種
所以要變成32個0、1佔4位元組的那種

⑵ 一、實驗題目：用哈夫曼編碼實現文件壓縮用C++實現 急用

這是我的實驗報告：http://student.csdn.net/space.php?uid=395622&do=blog&id=51206/**
* @brief 哈夫曼編碼
* @date 2010-11-30
*/
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;

/**
* @brief 哈弗曼結點
* 記錄了哈弗曼樹結點的數據、權重及左右兒子
*/
struct HTNode {
char data;
HTNode *lc, *rc;
int w;

/** 節點構造函數 */
HTNode(char _d, int _w, HTNode *_l = NULL, HTNode *_r = NULL)
{
data = _d;
w = _w;
lc = _l;
rc = _r;
}

/** 節點拷貝構造函數 */
HTNode(const HTNode &h)
{
data = h.data;
lc = h.lc;
rc = h.rc;
w = h.w;
}

/** 用於優先隊列比較的運算符重載 */
friend bool operator < (const HTNode &a, const HTNode &b)
{
return a.w > b.w;
}
};

/** 哈弗曼樹葉子節點數、各葉子結點數據及權重 */
/** 權值從Lolita小說中抽樣取出 */
const char ch[] = {
10, 32, 33, 37, 40, 41, 44, 45, 46, 48,
49, 50, 51, 52, 53, 54, 55, 56, 57, 58,
59, 63, 65, 66, 67, 68, 69, 70, 71, 72,
73, 74, 75, 76, 77, 78, 79, 80, 81, 82,
83, 84, 85, 86, 87, 88, 89, 90, 91, 93,
97, 98, 99, 100, 101, 102, 103, 104, 105, 106,
107, 108, 109, 110, 111, 112, 113, 114, 115, 116,
117, 118, 119, 120, 121, 122, 123, 161, 164, 166,
168, 170, 173, 174, 175, 176, 177, 180, 186, 255,
'\r', '\0'
};

const int fnum[] = {
2970, 99537, 265, 1, 496, 494, 9032, 1185, 5064, 108,
180, 132, 99, 105, 82, 64, 62, 77, 126, 296,
556, 548, 818, 443, 543, 435, 225, 271, 260, 797,
3487, 158, 50, 1053, 589, 498, 332, 316, 61, 276,
724, 855, 54, 293, 543, 11, 185, 11, 25, 26,
42416, 7856, 12699, 23670, 61127, 10229, 10651, 27912, 32809, 510,
4475, 23812, 13993, 34096, 38387, 9619, 500, 30592, 30504, 42377,
14571, 4790, 11114, 769, 10394, 611, 1, 4397, 12, 71,
117, 1234, 81, 5, 852, 1116, 1109, 1, 3, 1,
2970
};

const int n = 91;

/** 優先隊列 */
priority_queue<HTNode> pq;

/** 哈弗曼編碼映射 */
map<string, char> dcode;
map<char, string> ecode;

/** 根節點以及總權重+邊長 */
HTNode *root;
int sum = 0;

/** 初始化葉節點，並加入到優先隊列中 */
void Init()
{
for(int i = 0; i < n; i++)
{
HTNode p(ch[i], fnum[i]);
pq.push(p);
}
}

/** 建立哈夫曼樹 */
void CreateHT()
{
HTNode *lmin, *rmin;

/** 當隊列中不止一個元素時 */
while(!pq.empty() && 1 != pq.size())
{
/** 取隊首兩個元素（權值最小） */
lmin = new HTNode(pq.top());
pq.pop();
rmin = new HTNode(pq.top());
pq.pop();

/** 合並元素重新入隊 */
HTNode p(0, lmin->w + rmin->w, lmin, rmin);
pq.push(p);
}

if(!pq.empty())
{
/** 根節點 */
root = new HTNode(pq.top());
pq.pop();
}
}

/** 創建哈夫曼編碼 */
void CreateHTCode(HTNode *p, string str)
{
if(!p) return;
if(0 != p->data)
{
/** 若是葉節點，則記錄此節點的編碼值 */
dcode[str] = p->data;
ecode[p->data] = str;
sum += (str.length() * p->w);

return;
}

CreateHTCode(p->lc, str + "0");
CreateHTCode(p->rc, str + "1");
}

/** 顯示哈夫曼編碼 */
void DispCode()
{
printf("輸出哈弗曼編碼：\n");
for(int i = 0; i < n; i++)
{
printf("\t'%c':\t%s\n", ch[i], ecode[ch[i]].c_str());
}
printf("平均長度：%.5lf\n", double(sum) / double(root->w));
}

/** 釋放哈夫曼樹 */
void Release(HTNode *p)
{
if(!p) return;
Release(p->lc);
Release(p->rc);
delete p;
}

/** 輸出壓縮文 */
void putEncode(FILE *fp, char *buf)
{
unsigned char code = 0;
for(int i = 0; i < 8; i++)
code = (code << 1) + (buf[i] - '0');

fwrite(&code, sizeof(unsigned char), 1, fp);
}

/** 判斷是否在字元串內 */
bool instr(char c, const char str[])
{
for(int i = 0; i < strlen(str); i++)
if(c == str[i]) return true;

return false;
}

/** 壓縮文件 */
void Encode()
{
FILE *OF;
FILE *IF;
char ifn[255];
const char ofn[] = "Encode.txt";
char buf[9];
int cnt = 0, newcnt = 0;

printf("Input the filename: ");
scanf("%s", ifn);

IF = fopen(ifn, "rb");
if(!IF)
{
printf("Wrong file.\n");
return;
}

OF = fopen(ofn, "wb+");
if(!OF)
{
printf("Wrong file.\n");
}

/** 開始讀文件 */
memset(buf, 0, sizeof(buf));
while(!feof(IF))
{
unsigned char c;
fread(&c, sizeof(unsigned char), 1, IF);
if(instr(c, ch));
else c = ' ';
for(int i = 0; i < ecode[c].length(); i++)
{
buf[strlen(buf)] = ecode[c][i];
if(8 == strlen(buf))
{
newcnt++;
putEncode(OF, buf);
memset(buf, 0, sizeof(buf));
}
}

cnt++;
}

cnt--;
if(0 != strlen(buf))
{
for(int i = strlen(buf); i < 8; i++) buf[i] = '0';
putEncode(OF, buf);
}

fwrite(&cnt, 4, 1, OF);

fclose(IF);
fclose(OF);

printf("壓縮成功！壓縮率：%.2f%c\n", (((double)newcnt + 4.0f) / (double)cnt) * 100, '%');
}

/** 補0 */
void putZeros(char *buf)
{
char tmpbuf[9];
memset(tmpbuf, 0, sizeof(tmpbuf));
if(8 != strlen(buf))
{
for(int i = 0; i < 8 - strlen(buf); i++) tmpbuf[i] = '0';
strcat(tmpbuf, buf);
strcpy(buf, tmpbuf);
}
}

/** 解壓縮 */
void Decode()
{
char buf[256];
char oldbuf[9];
const char ifn[] = "Encode.txt";
const char ofn[] = "Decode.txt";
FILE *IF = fopen(ifn, "rb");
if(!IF)
{
printf("Wrong file.\n");
return;
}

FILE *OF = fopen(ofn, "wb+");
if(!OF)
{
printf("Wrong file.\n");
return;
}

int tot, cnt = 0;
fseek(IF, -4L, SEEK_END);
fread(&tot, 4, 1, IF);
fseek(IF, 0L, SEEK_SET);

memset(buf, 0, sizeof(buf));
while(true)
{
if(cnt == tot) break;
unsigned char c;
fread(&c, sizeof(unsigned char), 1, IF);
itoa(c, oldbuf, 2);
putZeros(oldbuf);

for(int i = 0; i < 8; i++)
{
if(cnt == tot) break;
buf[strlen(buf)] = oldbuf[i];
if(dcode.end() != dcode.find(string(buf)))
{
fwrite(&dcode[string(buf)], sizeof(char), 1, OF);
memset(buf, 0, sizeof(buf));
cnt++;
}
}
}

fclose(IF);
fclose(OF);

printf("解壓成功！文件名Decode.txt。\n");
}

int main()
{
Init();
CreateHT();
CreateHTCode(root, "");
DispCode();
Encode();
Decode();
Release(root);
system("pause");

return 0;
}

⑶ 用哈夫曼編碼壓縮一個word文檔,文件沒有變小,反而還變大了

提問者尼壕，
哈夫曼編碼是可以應用於數據壓縮
但可能文件本身被壓縮，比如docx文件，本身已經被壓縮le，所以基本沒有效果，甚至變大
好比7z壓縮一個avc mp4一樣，只會變大
但doc應該有一定效果

有問題請追問撒QAQ

⑷ 如何用哈夫曼編碼製作壓縮解壓縮軟體

去問小翠啊， 望採納，記得給分

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

壓縮代碼非常簡單，首先用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");
}

⑹ 在哈夫曼編碼壓縮程序中應該如何存儲哈夫曼編碼

我想你理解錯了……你所說的128Bit是編碼和解碼時用的
樹怎麼保存，方法很多，最簡單的辦法是為0x00到0xFF按它們出現的頻率保存順序；因為只有256個元素，所以用1位元組就能保存到它們的順序，例如
0x00 0x05
0x01 0x04
0x02 0xF5
……
……
要保存這種表示方式也只是要512位元組而已；重建樹的時候重再根據這些數據來把樹創建出來就是了；

最後建議你把哈夫曼編碼原理重新再看一次，是看「原理」

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

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

⑻ 利用huffman編碼對文件進行壓縮，不同文件類型壓縮率有差別的原因

1. 文本文件，二進制文件及數據流的操作

2. 英文字元，中文字元的存儲與識別【難點】

3. 壓縮及解壓的主要思想【重點】

4. Huffman樹的構造

5. 編碼的獲取

6. 壓縮文件的存儲形式[huffman編碼信息及數據存儲]

7. 對文本文件最後一個字元的處理[補位數：壓縮，解壓無錯誤]

⑼ 有人能給我一份哈夫曼編碼的壓縮和解壓么

把要壓縮或要解壓的文件拖拽到窗口中即可。另存為編輯框是壓縮或解壓的輸出路徑。對於壓縮來說，另存為路徑是目標文件的路徑加上一個.shc擴展名。對於解壓來說，會去掉最後一個擴展名。
壓縮的核心其實就是用了哈夫曼編碼原理。我封裝了一個哈夫曼編碼類，內部使用了一個哈夫曼樹類。

要對一個文件進行壓縮，執行如下步驟：
1.建立編碼方案。第一遍掃描文件，統計這個文件中各種不同的位元組出現的次數（256種），以這個次數作為權值，建立對應的哈夫曼樹。然後取得每個不同位元組對應的01編碼序列。