# data[].attributes.body
1. Nguyễn Bá Khoa
2. Trần Hữu Thắng
3. Võ Minh Lợi
4. Nguyễn Minh Đức

# data[].attributes.body
Thuật toán Huffman coding gồm 3 bước:

Bước 1: Đếm tần suất xuất hiện của các phần tử trong chuỗi đầu vào.

Bước 2: Xây dựng cây Huffman (cây nhị phân mã hóa).

Quá trình xây dựng cây Huffman gồm các bước sau:

2.1. Tạo danh sách chứa các nút lá bao gồm phần tử đầu vào và trọng số nút là tần suất xuất hiện của nó.

2.2. Từ danh sách này, lấy ra 2 phần tử có tần suất xuất hiện ít nhất. Sau đó gắn 2 nút vừa lấy ra vào một nút gốc mới với trọng số là tổng của 2 trọng số ở nút vừa lấy ra để tạo thành một cây.

2.3. Đẩy cây mới vào lại danh sách.

2.4. Lặp lại bước 2 và 3 cho đến khi danh sách chỉ còn 1 nút gốc duy nhất của cây.

2.5. Nút còn lại chính là nút gốc của cây Huffman.

Bước 3: Từ cây Huffman, ta có được các giá trị mã hóa. Lúc này, ta có thể xây dựng chuỗi mã hóa từ các giá trị này.

# data[].attributes.body
#include<stdio.h>
#include<string.h>
struct Huffdata{
char ma[8],kt[256];
int ts;
};
struct HNode{
Huffdata Data;
HNode *L,*R;
};
void taoTBTS(char s[],Huffdata TBTS[],int &n)
{
int i,j,kt;
for (i=0;i<strlen(s);i++)
{
kt=0;
for (j=1;j<=n;j++)
if (TBTS[j].kt[0]==s[i])
{
TBTS[j].ts++;
kt=1;
}
if (kt==0)
{
n++;
TBTS[n].kt[0]=s[i];
TBTS[n].ts++;
}
}
}
void Sort(Huffdata a[], int n)
{
int i,j;
Huffdata tmp;
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++)
if ((a[i].ts > a[j].ts) || (a[i].ts==a[j].ts) && (strcmp(a[i].kt,a[j].kt)>0))
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
void Insert(Huffdata a[],Huffdata pt,int &n)
{
int vt=0,i;
while (pt.ts>a[vt].ts && vt<=n)
vt++;
for (i=1;i<vt;i++)
a[i]=a[i+1];
a[vt-1]=pt;
for (i=1;i<n;i++)
a[i]=a[i+1];
n--;
}
HNode *taoHTree(Huffdata TBTS[],HNode *HTBTS[],int &n)
{
int i=0,j=0,n1=0;
HNode *tmp,*pL,*pR;
while (TBTS[i].ts==0)
i++;
while (n>=2)
{
tmp=new HNode;
pL= new HNode;
pR= new HNode;
pL->Data=TBTS[1];
pR->Data=TBTS[2];
pL->L=NULL;
pR->L=NULL;
pL->R=NULL;
pR->R=NULL;
for (i=1;i<=n1;i++)
{
if (strcmp(pL->Data.kt,HTBTS[i]->Data.kt)==0)
pL=HTBTS[i];
if (strcmp(pR->Data.kt,HTBTS[i]->Data.kt)==0)
pR=HTBTS[i];
}
tmp->L=pL;
tmp->R=pR;
strcpy(tmp->Data.kt,"");
strcat(tmp->Data.kt,pL->Data.kt);
strcat(tmp->Data.kt,pR->Data.kt);
tmp->Data.ts=pL->Data.ts+pR->Data.ts;
n1++;
HTBTS[n1]=tmp;
Insert(TBTS,tmp->Data,n);
}
return HTBTS[n1];
}
void Duyet(HNode *Tr)
{
if (Tr!=NULL)
{
Duyet(Tr->R);
Duyet(Tr->L);
printf("%s :   %d\n",Tr->Data.kt,Tr->Data.ts);
}
}
void taoTBMB(HNode *Tr,Huffdata TBMB[],int &n,char ma[])
{
char tam[8];
if (Tr!=NULL)
{
if (Tr->R!=NULL)
{
strcat(ma,"1");
taoTBMB(Tr->R,TBMB,n,ma);
strcpy(tam,"");
strncat(tam,ma,strlen(ma)-1);
strcpy(ma,tam);
}
if (Tr->L!=NULL)
{
strcat(ma,"0");
taoTBMB(Tr->L,TBMB,n,ma);
strcpy(tam,"");
strncat(tam,ma,strlen(ma)-1);
strcpy(ma,tam);
}
if (Tr->L==NULL && Tr->R==NULL)
{
n++;
strcpy(TBMB[n].kt,Tr->Data.kt);
strcpy(TBMB[n].ma,ma);
}
}
}
void nen(char s[],char snen[],Huffdata TBMB[],int n)
{
int i,j;
for (i=0;i<strlen(s);i++)
{
for (j=1;j<=n;j++)
if (s[i]==TBMB[j].kt[0])
strcat(snen,TBMB[j].ma);
}
}
void giainen(char snen[],HNode *Tr)
{
int i,kt=0;
HNode *tmp=Tr;
for (i=0;i<=strlen(snen);i++)
{
if (snen[i]=='1')
tmp=tmp->R;
else
tmp=tmp->L;
if (tmp->L==NULL && tmp->R==NULL)
{
printf("%s",tmp->Data.kt);
tmp=Tr;
}
}
}
main()
{
char string[100]="NHOM7nhom7NHOM7",s[1000];
fflush(stdin);

printf("Xau goc:\n%s\n",string);
int n=0,nb=0,i,j;
char ma[8];
Huffdata TBTS[256],TBMB[256];
HNode *Tree=NULL,*TB[100];
taoTBTS(string,TBTS,n);
Sort(TBTS,n);
printf("\nBang tan so:\n");
for (i=1;i<=n;i++)
printf("%s  %d\n",TBTS[i].kt,TBTS[i].ts);
fflush(stdin);
Tree=taoHTree(TBTS,TB,n);
printf("\nDuyet cay Huffman \n");
Duyet(Tree);
strcpy(ma,"");
taoTBMB(Tree,TBMB,nb,ma);
printf("\nBang ma bit:\n");
for (i=1;i<=nb;i++)
printf("%s  %s\n",TBMB[i].kt,TBMB[i].ma);
strcpy(s,"");
nen(string,s,TBMB,nb);
printf("\nXau sau khi nen:\n");
printf("%s\n",s);
printf("\nXau sau khi giai nen:\n");
giainen(s,Tree);
}

# data[].attributes.body
https://padlet.com/minhloi1131130/uhkpff4qy751uzwf

# data[].attributes.body
Thuật toán Huffman coding gồm 3 bước:

Bước 1: Đếm tần suất xuất hiện của các phần tử trong chuỗi đầu vào.

Bước 2: Xây dựng cây Huffman (cây nhị phân mã hóa).

Quá trình xây dựng cây Huffman gồm các bước sau:

2.1. Tạo danh sách chứa các nút lá bao gồm phần tử đầu vào và trọng số nút là tần suất xuất hiện của nó.

2.2. Từ danh sách này, lấy ra 2 phần tử có tần suất xuất hiện ít nhất. Sau đó gắn 2 nút vừa lấy ra vào một nút gốc mới với trọng số là tổng của 2 trọng số ở nút vừa lấy ra để tạo thành một cây.

2.3. Đẩy cây mới vào lại danh sách.

2.4. Lặp lại bước 2 và 3 cho đến khi danh sách chỉ còn 1 nút gốc duy nhất của cây.

2.5. Nút còn lại chính là nút gốc của cây Huffman.

Bước 3: Từ cây Huffman, ta có được các giá trị mã hóa. Lúc này, ta có thể xây dựng chuỗi mã hóa từ các giá trị này.

# data[].attributes.body
#include<stdio.h>
#include<string.h>
struct Huffdata{
char ma[8],kt[256];
int ts;
};
struct HNode{
Huffdata Data;
HNode *L,*R;
};
void taoTBTS(char s[],Huffdata TBTS[],int &n)
{
int i,j,kt;
for (i=0;i<strlen(s);i++)
{
kt=0;
for (j=1;j<=n;j++)
if (TBTS[j].kt[0]==s[i])
{
TBTS[j].ts++;
kt=1;
}
if (kt==0)
{
n++;
TBTS[n].kt[0]=s[i];
TBTS[n].ts++;
}
}
}
void Sort(Huffdata a[], int n)
{
int i,j;
Huffdata tmp;
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++)
if ((a[i].ts > a[j].ts) || (a[i].ts==a[j].ts) && (strcmp(a[i].kt,a[j].kt)>0))
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
void Insert(Huffdata a[],Huffdata pt,int &n)
{
int vt=0,i;
while (pt.ts>a[vt].ts && vt<=n)
vt++;
for (i=1;i<vt;i++)
a[i]=a[i+1];
a[vt-1]=pt;
for (i=1;i<n;i++)
a[i]=a[i+1];
n--;
}
HNode *taoHTree(Huffdata TBTS[],HNode *HTBTS[],int &n)
{
int i=0,j=0,n1=0;
HNode *tmp,*pL,*pR;
while (TBTS[i].ts==0)
i++;
while (n>=2)
{
tmp=new HNode;
pL= new HNode;
pR= new HNode;
pL->Data=TBTS[1];
pR->Data=TBTS[2];
pL->L=NULL;
pR->L=NULL;
pL->R=NULL;
pR->R=NULL;
for (i=1;i<=n1;i++)
{
if (strcmp(pL->Data.kt,HTBTS[i]->Data.kt)==0)
pL=HTBTS[i];
if (strcmp(pR->Data.kt,HTBTS[i]->Data.kt)==0)
pR=HTBTS[i];
}
tmp->L=pL;
tmp->R=pR;
strcpy(tmp->Data.kt,"");
strcat(tmp->Data.kt,pL->Data.kt);
strcat(tmp->Data.kt,pR->Data.kt);
tmp->Data.ts=pL->Data.ts+pR->Data.ts;
n1++;
HTBTS[n1]=tmp;
Insert(TBTS,tmp->Data,n);
}
return HTBTS[n1];
}
void Duyet(HNode *Tr)
{
if (Tr!=NULL)
{
Duyet(Tr->R);
Duyet(Tr->L);
printf("%s :   %d\n",Tr->Data.kt,Tr->Data.ts);
}
}
void taoTBMB(HNode *Tr,Huffdata TBMB[],int &n,char ma[])
{
char tam[8];
if (Tr!=NULL)
{
if (Tr->R!=NULL)
{
strcat(ma,"1");
taoTBMB(Tr->R,TBMB,n,ma);
strcpy(tam,"");
strncat(tam,ma,strlen(ma)-1);
strcpy(ma,tam);
}
if (Tr->L!=NULL)
{
strcat(ma,"0");
taoTBMB(Tr->L,TBMB,n,ma);
strcpy(tam,"");
strncat(tam,ma,strlen(ma)-1);
strcpy(ma,tam);
}
if (Tr->L==NULL && Tr->R==NULL)
{
n++;
strcpy(TBMB[n].kt,Tr->Data.kt);
strcpy(TBMB[n].ma,ma);
}
}
}
void nen(char s[],char snen[],Huffdata TBMB[],int n)
{
int i,j;
for (i=0;i<strlen(s);i++)
{
for (j=1;j<=n;j++)
if (s[i]==TBMB[j].kt[0])
strcat(snen,TBMB[j].ma);
}
}
void giainen(char snen[],HNode *Tr)
{
int i,kt=0;
HNode *tmp=Tr;
for (i=0;i<=strlen(snen);i++)
{
if (snen[i]=='1')
tmp=tmp->R;
else
tmp=tmp->L;
if (tmp->L==NULL && tmp->R==NULL)
{
printf("%s",tmp->Data.kt);
tmp=Tr;
}
}
}
main()
{
char string[100]="NHOM7nhom7NHOM7",s[1000];
fflush(stdin);

printf("Xau goc:\n%s\n",string);
int n=0,nb=0,i,j;
char ma[8];
Huffdata TBTS[256],TBMB[256];
HNode *Tree=NULL,*TB[100];
taoTBTS(string,TBTS,n);
Sort(TBTS,n);
printf("\nBang tan so:\n");
for (i=1;i<=n;i++)
printf("%s  %d\n",TBTS[i].kt,TBTS[i].ts);
fflush(stdin);
Tree=taoHTree(TBTS,TB,n);
printf("\nDuyet cay Huffman \n");
Duyet(Tree);
strcpy(ma,"");
taoTBMB(Tree,TBMB,nb,ma);
printf("\nBang ma bit:\n");
for (i=1;i<=nb;i++)
printf("%s  %s\n",TBMB[i].kt,TBMB[i].ma);
strcpy(s,"");
nen(string,s,TBMB,nb);
printf("\nXau sau khi nen:\n");
printf("%s\n",s);
printf("\nXau sau khi giai nen:\n");
giainen(s,Tree);
}

# data[].attributes.body
B1: Duyệt file, lập bảng thống kê tuần suất xuất hiện của mỗi ký tự.
B2: Xây dựng cây Huffman dựa vào bảng thống kê.
B3: Sinh mã Huffman cho mỗi ký tự dựa vào cây Huffman.
B4: Duyệt file, thay toàn bộ ký tự bằng mã Huffman tương ứng.

# data[].attributes.body
#include<stdio.h>
#include<string.h>
struct Huffdata{
char ma[8],kt[256];
int ts;
};
struct HNode{
Huffdata Data;
HNode *L,*R;
};
void taoTBTS(char s[],Huffdata TBTS[],int &n)
{
int i,j,kt;
for (i=0;i<strlen(s);i++)
{
kt=0;
for (j=1;j<=n;j++)
if (TBTS[j].kt[0]==s[i])
{
TBTS[j].ts++;
kt=1;
}
if (kt==0)
{
n++;
TBTS[n].kt[0]=s[i];
TBTS[n].ts++;
}
}
}
void Sort(Huffdata a[], int n)
{
int i,j;
Huffdata tmp;
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++)
if ((a[i].ts > a[j].ts) || (a[i].ts==a[j].ts) && (strcmp(a[i].kt,a[j].kt)>0))
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
void Insert(Huffdata a[],Huffdata pt,int &n)
{
int vt=0,i;
while (pt.ts>a[vt].ts && vt<=n)
vt++;
for (i=1;i<vt;i++)
a[i]=a[i+1];
a[vt-1]=pt;
for (i=1;i<n;i++)
a[i]=a[i+1];
n--;
}
HNode *taoHTree(Huffdata TBTS[],HNode *HTBTS[],int &n)
{
int i=0,j=0,n1=0;
HNode *tmp,*pL,*pR;
while (TBTS[i].ts==0)
i++;
while (n>=2)
{
tmp=new HNode;
pL= new HNode;
pR= new HNode;
pL->Data=TBTS[1];
pR->Data=TBTS[2];
pL->L=NULL;
pR->L=NULL;
pL->R=NULL;
pR->R=NULL;
for (i=1;i<=n1;i++)
{
if (strcmp(pL->Data.kt,HTBTS[i]->Data.kt)==0)
pL=HTBTS[i];
if (strcmp(pR->Data.kt,HTBTS[i]->Data.kt)==0)
pR=HTBTS[i];
}
tmp->L=pL;
tmp->R=pR;
strcpy(tmp->Data.kt,"");
strcat(tmp->Data.kt,pL->Data.kt);
strcat(tmp->Data.kt,pR->Data.kt);
tmp->Data.ts=pL->Data.ts+pR->Data.ts;
n1++;
HTBTS[n1]=tmp;
Insert(TBTS,tmp->Data,n);
}
return HTBTS[n1];
}
void Duyet(HNode *Tr)
{
if (Tr!=NULL)
{
Duyet(Tr->R);
Duyet(Tr->L);
printf("%s : %d    \t",Tr->Data.kt,Tr->Data.ts);
}
}
void taoTBMB(HNode *Tr,Huffdata TBMB[],int &n,char ma[])
{
char tam[8];
if (Tr!=NULL)
{
if (Tr->R!=NULL)
{
strcat(ma,"1");
taoTBMB(Tr->R,TBMB,n,ma);
strcpy(tam,"");
strncat(tam,ma,strlen(ma)-1);
strcpy(ma,tam);
}
if (Tr->L!=NULL)
{
strcat(ma,"0");
taoTBMB(Tr->L,TBMB,n,ma);
strcpy(tam,"");
strncat(tam,ma,strlen(ma)-1);
strcpy(ma,tam);
}
if (Tr->L==NULL && Tr->R==NULL)
{
n++;
strcpy(TBMB[n].kt,Tr->Data.kt);
strcpy(TBMB[n].ma,ma);
}
}
}
void nen(char s[],char snen[],Huffdata TBMB[],int n)
{
int i,j;
for (i=0;i<strlen(s);i++)
{
for (j=1;j<=n;j++)
if (s[i]==TBMB[j].kt[0])
strcat(snen,TBMB[j].ma);
}
}
void giainen(char snen[],HNode *Tr)
{
int i,kt=0;
HNode *tmp=Tr;
for (i=0;i<=strlen(snen);i++)
{
if (snen[i]=='1')
tmp=tmp->R;
else
tmp=tmp->L;
if (tmp->L==NULL && tmp->R==NULL)
{
printf("%s",tmp->Data.kt);
tmp=Tr;
}
}
}
main()
{
char string[100]="baitapgiainen",s[1000];
fflush(stdin);
printf("Xau goc: %s",string);
int n=0,nb=0,i,j;
char ma[8];
Huffdata TBTS[256],TBMB[256];
HNode *Tree=NULL,*TB[100];
taoTBTS(string,TBTS,n);
Sort(TBTS,n);
printf("\nBang tan so:\n");
for (i=1;i<=n;i++)
printf("%s = %d\t",TBTS[i].kt,TBTS[i].ts);
fflush(stdin);
Tree=taoHTree(TBTS,TB,n);
printf("\nDuyet cay Huffman \n");
Duyet(Tree);
strcpy(ma,"");
taoTBMB(Tree,TBMB,nb,ma);
printf("\nBang ma bit:\n");
for (i=1;i<=nb;i++)
printf("%s = %s\t",TBMB[i].kt,TBMB[i].ma);
strcpy(s,"");
nen(string,s,TBMB,nb);
printf("\nXau sau khi nen:\n");
printf("%s\t",s);
printf("\nXau sau khi giai nen:\n");
giainen(s,Tree);
}

# data[].attributes.body
Bước 1: tạo hàm RLE, cho chạy từ 1 đến độ dài mảng -1,cho đếm cộng 1 và nếu phần tử trước khác phần tử sau thì thực hiện các việc giao mảng đếm giá trị trị rỗng
Bước 2: tạo đếm từ d và gán cho dem bằng giá trị của dữ liệu file tại vị trí phần tử trước,
Bước 3: tiếp theo nối chuổi dem với mảng của compressFile, cuối cùng cho d bằng 0 trở lại.

# data[].attributes.body
#include<stdio.h>
#include<string.h>
void compressFile(
char fileData[],
char compressFileData[]
)
{
int d=0;
char dem[100];
for (int i = 0; i <= strlen(fileData) - 1; i++)
{
d++;
if (fileData[i] != fileData[i + 1] )
{
strcpy(dem,"");
sprintf(dem,"%d",d);
dem[strlen(dem)]=fileData[i];
strcat(compressFileData,dem);
d=0;
}
}
}
main()
{
char fileData[1000];
char compressFileData[2000];
strcpy(compressFileData,"");
printf("Nhap chuoi can nen:\n");
fflush(stdin);
gets(fileData);
compressFile(fileData,compressFileData);
printf("\nChuoi sau khi nen:\n");
printf("%s",compressFileData);
}