خب بعد یه مدت اومدم که ادامه بدم.
فشرده سازی چیز ساده ای نیست که بگیم فقط به کد نویسی و الگوریتم ختم میشه.تو پست بعدی یه مثال خوب در این رابطه براتون میزنم.
اما فعلا بریم سراغ فشرده سازی به روش هافمن.در این روش شما میاین میزان تکرار هر حرف رو پیدا میکنین و براش درخت هافمن رو میسازین و بعد با استفاده از دستور هافمن و درخت نوشته رو کد میکنین.بزارین یه مثال بزنم تا بیشتر روشن شین.
فرض کنین شما یه متنی دارین که فقط توش عدد هست حالا جدول زیر رو براش تشکیل میدیم:
حرف-----تکرار
1 5
2 7
3 10
4 15
5 20
6 45
خب حلال از روی این جدول درخت هافمن رو تشکیل میدیم.
به این صورت که 2تا مقدار اول جدولو بر میداریم و دو راس گراف قرار میدیم و ارcش راس سوم رو مجموع این دو راس قرار میدیم به شکل زیر.12:*
\ /
5:1 7:2
بعد دو مقدار اول جدولو پاک میکنیم و به جاش مجموع اون دوتا رو مینویسیم وجدول رو بر اساس میزان تکرار مرتب میکنیم یعنی:10:3
12:*
15:4
20:5
45:6
حالا دوباره مراحل بالا رو تکرار میکنیم تا فقط یک مقدار باقی بمونه.حالا ما میایم از رو گراف ماتریس مجاورت رو تشکیل میدیم و بر اساس دستور هافمن کدینگ میکنیم.
یه کد مختصرهم میزارم که ماتریس مجاورت رشته ی مرتب شده رو تشکیل میده.کد مرتب نیست و فقط برای این هست که شما دیدی به مساله پیدا کنین.
#include <iostream>
using namespace std;
void huffman_tree_genrator(long int [],int,long int []);
void gsrt_f_t(long int [2][500],int,int);
void make_it_true(long int [2][500],int);
int main() {
long int s[10]={1,2,3,4,5,6,7,8,9,11},bc[10]={1,2,3,4,5,6,7,8,9,11};
huffman_tree_genrator(s,9,bc);
return 0;
}
void huffman_tree_genrator(long int a[],int k,long int back[])
{
int seed=0,r=0,d_g[200][200]={0},q=1,d,count;
long int sum,m_r[200][200]={0},graph[2][500]={0};
int i=0,j;
count=2*(k+1)-1;
d=k;
for(i;i<=k;i++)
{
graph[0][i]=a[i];
}
while(count>=0)
{
sum=graph[0][r]+graph[0][r+1];
if(graph[1][r]==0)
{
graph[1][r]=q;
q=q+1;
}
if(graph[1][r+1]==0)
{
graph[1][r+1]=q;
q=q+1;
}
graph[0][d+1]=sum;
if(graph[1][d+1]==0)
{
graph[1][d+1]=q;
q=q+1;
}
d++;
r=r+2;
gsrt_f_t(graph,r,d);
count--;
}
i=0;
count=2*(k+1)-1;
make_it_true(graph,count);
for(i;i<=count-1;i+=2)
{
j=i+2;
for(j;j<=count-1;j++)
if(graph[0][i]+graph[0][i+1]==graph[0][j] && graph[2][j]!=-1)
{
d_g[graph[1][i]][graph[1][j]]=1;
d_g[graph[1][j]][graph[1][i]]=1;
d_g[graph[1][i+1]][graph[1][j]]=1;
d_g[graph[1][j]][graph[1][i+1]]=1;
graph[2][j]=-1;
j=count+1;
}
}
i=1;
for(i;i<=count;i++)
{
j=1;
for(j;j<=count;j++)
{
cout<<d_g[i][j]<<" ";
}
cout<<endl;
}
}
void gsrt_f_t(long int x[2][500],int p,int z)
{
int i,j;
long int t;
i=p;
for(i;i<=z;i++)
{
j=i;
for(j;j<=z;j++)
{
if(x[0][i]>x[0][j])
{
t=x[0][i];
x[0][i]=x[0][j];
x[0][j]=t;
t=x[1][i];
x[1][i]=x[1][j];
x[1][j]=t;
}
}
}
}
void make_it_true(long int x[2][500],int k)
{
long int tmp;
int j;
j=1;
for(j;j<=k-1;j++)
{
if(x[0][j-1]==x[0][j] && x[1][j-1]>x[1][j])
{
tmp=x[1][j-1];
x[1][j-1]=x[1][j];
x[1][j]=tmp;
}
if(x[0][j+1]==x[0][j] && x[1][j+1]<x[1][j])
{
tmp=x[1][j+1];
x[1][j+1]=x[1][j];
x[1][j]=tmp;
}
}
}
یه توضیح کوچولو بدم که تابع gsrt_f_t گراف ما رو ازیک خونه ی دلخواه تا یه خونه ی دلخواه دیگه از کوچیک به بزرگ مرتب میکنه.
تابع make_it_true برای اینه که از انجام کار اطمینان حاصل بشه آخه بعضی وقتا کامپایلر هایی مثل codeblocks گیج بازی در میارن دستوراتو درست انجام نمیدن(سر خودم اومده که میگم).
شما حالا رشتتو توی sوbc قرار میدی رشته bc در مراحل بعدی کدینگ استفاده میشه و عملیات رو s انجام میشه.بعد به تابع huffman_tree_genrator مقدار دهی میکنین مقدار دوم برابر طول رشتست که باید یک واحد ازش کم کنین یعنی اگر طول 10 هست باید بهش 9 داده بشه.
