پیاده سازی الگوریتم کد هافمن با سی

پیاده سازی الگوریتم کد هافمن با

قیمت :   ۸۵۰۰ تومان ( هشت هزار و پانصد تومان)

رشته :

کامپیوتر

نوع فایل:

C ,

توضیحات:


توضیحات :

پیاده سازی الگوریتم کد هافمن 

درعلوم کامپیوتر و تئوری اطلاعات، کدگذاری هافمن یک الگوریتم کدگذاری برای فشرده‌سازی بی‌اتلاف اطلاعات است.

این تعبیر بر می‌گردد به استفاده از جدول کدطول متغیر برای کد کردن هر کدام از نشانه‌های مبدا (مانند نویسه‌های یک پرونده). جدول کد طول متغیر از روشی بخصوص مبنی بر احتمال وقوع هر کدام از نشان‌های مبدا بدست می‌آید. این روش بوسیلهٔ دیویدهافمن توسعه یافت. وی دانشجوی دورهٔ دکتری در دانشگاه MIT بود و در سال ۱۹۵۲ مقالهٔ «روشی برای تولید کدی با کمترین تکرار زوائد» را منتشر کرد.

در کدگذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود. روشی به نام کدهای بدون پیشوند (گاهی هم روش «کدهای پیشوندی» گفته می‌شود. یعنی در این روش رشته‌ای که نشان دهندهٔ یک نویسه خاص است هیچ گاه پیشوند رشتهٔ دیگر که نمایانگر نویسهٔ دیگر است، نمی‌باشد.). در این روش نویسه‌های پرکاربردتر با رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند.

هافمن موفق شد کارآمدترین روش فشرده سازی از این نوع را طراحی کند: نگاشت نکردن نشان‌های منفرد مبدا به رشته‌های بیتی یکتا، هرگاه تعداد تکرار نمادهای اصلی با آنهایی که برای ایجاد این کد مورد استفاده قرار گرفتند مطابقت کند، خروجی‌هایی با اندازهٔ کمتر تولید می‌کند. بعدها روشی برای انجام این کار پیدا شد که این کار را در زمانی خطی انجام می‌داد.

برای مجموعه‌ای از نمادها با توزیع احتمالی یکنواخت و تعداد عضوهایی برابر با توانی از۲، کد گذاری هافمن هم ارز با قطعهکدسادهٔ دوجمله‌ای است. مانند کد گذاری اسکی. کد گذاری هافمن روشی متداول برای ایجاد کدهای بدون پیشوند است بطوریکه عبارت «کد هافمن» به گستردگی به عنوان مترادفی برای «کد بدون پیشوند» استفاده می‌شود، هرچند چنین کدی با بدست نیامده باشد.

پیاده سازی برنامه کد گذاری و رمزگشایی توسط الگوریتم هافمن

همراه با فایلهای EXE , C

== تصویری از محیط  فایل اجرایی این پروژه : 

در تصویر اول مشاهده می کنید که ابتدا یک فایل متنی را جهت فشرده سازی و کدینگ معرفی نموده ایم و خروجی را نیز تعیین کرده ایم : 
huff1

در تصویر دوم برای خارج نمودن فایل کد شده بروش هافمن مراحل را مشاهده می کنید : 

huff2

مشاهده بخشهایی از سورس کد این پروژه :

# <stdio.h>
# include <stdlib.h>
# include <dir.h>
# include <io.h>

/*Global variable declarations ***/
struct node
{
unsigned char c;
unsigned long int freq;
struct node *up,*left,*right;
};
struct ftable
{
unsigned long int freq;
};
struct ftable ft;
struct node leaf[256];
struct node *t[256];
struct node *a,*b;
int i,j,k;
int buf[50],bc;
int buft[15],bct;
int buftv[15];
unsigned char q;

/*Function prototype declarations*/
int init(char *);
int sortt(int);
int maketree();
void add2buff(int);
void refreshbuffer(FILE *);
int nodecmp(struct node *,struct node *);
int nodecpy(struct node *,struct node *);
int getzero();
unsigned char oddchar();
char *getname(char *);

int getzero()
{
int h=0;
for(i=0;i<256;i++)
{
if(leaf[i].freq==0)
h++;
}
return (255-h);
}
char *getname(char *filepath)
{
char drive[4],dir[67],file[15],ext[5];
fnsplit(filepath,drive,dir,file,ext);
strcat(file,ext);
return file;
}

unsigned char oddchar()
{
for(i=bc;i<8;i++)
{
buf[i]=0;
}
return ((1*buf[7])+(2*buf[6])+(4*buf[5])+(8*buf[4])+(16*buf[3])+(32*buf[2])+(64*buf[1])+(128*buf[0]));
}

int nodecmp(struct node *a,struct node *b)
{
if(a->c==b->c && a->freq==b->freq && a->up==b->up &&a->left==b->left && a->right==b->right)
return 0;
return -1;
}

int nodecpy(struct node *a,struct node *b)
{
a->c=b->c;
a->freq=b->freq;
a->up=b->up;
a->left=b->left;
a->right=b->right;
return 0;
}

int init(char *filename)
{
FILE *p;
for(i=0;i<256;i++)
{
leaf[i].c=i;
leaf[i].freq=0;
leaf[i].up=NULL;
leaf[i].left=NULL;
leaf[i].right=NULL;
}
p=fopen(filename,”rb”);
if(p==NULL)
{
return -1; /*Could not open file */
}
while(j=fgetc(p),j!=EOF)
{
leaf[j].freq++;
if(j<0 || j>255)
{
printf(“\nError…”);
getch();
}
}
fclose(p);
for(i=0;i<256;i++)
{
t[i]=&leaf[i];
if((t[i]->up)!=NULL)
{
printf(“\nError..”);
getch();
}
}
bc=0; /*Setting the global buffer counter to 0*/
return 0;
}

int sortt(int z)/*sorts upto t[z] and not t[z-1]*/
{
for(k=0;k<=z;k++)
for(j=(k+1);j<=z;j++)
{
if((t[k]->freq)<(t[j]->freq))
{
//b=NULL;
b=t[k];
t[k]=t[j];
t[j]=b;
}
}
return 0;
}

int maketree()
{
sortt(255);
for(i=getzero();i>0;i–)
{
sortt(i);
a=NULL;
a=(struct node *)malloc(sizeof(struct node));
if(a==NULL)
{
printf(“\nMemory allocation error…”);
getch();
return -1; /*Memory allocation error*/
}
/*Assingning values*/
a->freq=(t[i]->freq)+(t[i-1]->freq);
a->right=t[i];
a->left=t[i-1];
a->up=NULL;
a->c=’\0′;
t[i]->up=a;
t[i-1]->up=a;
/*Changing the pointer*/
t[i-1]=a;
}
return 0;
}

void add2buff(int r)
{
bct=-1;
if(r>255 || r<0)
{
printf(“\nValue error…”);
getch();
}
a=&leaf[r];
while((a->up)!=NULL)
{
if(nodecmp((a->up->left),a)==0)
{
buft[++bct]=0;
}
else if(nodecmp((a->up->right),a)==0)
{
buft[++bct]=1;
}
else
{
printf(“\nParent Error”); /*For debugging*/
}
a=a->up;
}
for(i=0;i<=bct;i++)
{
buftv[bct-i]=buft[i];
}
for(i=0;i<=bct;i++)
{
buf[bc+i]=buftv[i];
}
bc=bc+bct+1;
return; /*Successful completetion of function*/
}

دانلود کامل پروژه همراه با فایل سورس کد و فایل اجرایی آن
در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنلاین پروژه

پذیرش و انجام سفارشات پروژه های شما
شماره تماس پشتیبانی سایت : ۰۹۳۹۲۷۶۱۶۳۰


Related posts

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

Translate »