سورس کد الگوریتم هافمن (Huffman) در سی پلاس پلاس ++C

در این بخش سورس کد الگوریتم هافمن (Huffman) در سی پلاس پلاس ++C قرار داده شده است. این سورس کد برای افراد علاقه مند به برنامه نویسی به زبان سی پلاس پلاس مناسب است زیرا دارای کدهای روان می‌باشد. در ادامه به توضیح و تشریح الگوریتم هافمن خواهیم پرداخت.

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

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

تشریح الگوریتم هافمن

فرض کنید می‌خواهید تکه اطلاعات زیر رافشرده کنید:

ACDABA

از آنجایی که ۶ کاراکتر داریم، این متن ۶ بایت یا ۴۸ بیت می‌باشد. (یعنی برای هر کاراکتر یک بایت ) با رمز گزاری هافمن، فایل برای بیشترین تکرار ظاهر شدن کاراکترها(در این مثال نماد A سه بار تکرار می شود) جستجو می‌شود و سپس یک درخت ساخته می‌شود که کاراکترها را با رشته بیت‌های کوتاه تر جایگزین می‌کند. در این حالت خاص الگوریتم از جدول جایگزینی زیر استفاده می‌کند:

A=0 , B=10 , C=110 , D=111.

اگر این کد برای فشرده سازی فایل استفاده شود، اطلاعات فشرده شده به صورت زیر در می‌آیند:

۰۱۱۰۱۱۱۰۱۰۰

این به این معنی است که ۱۱ بیت به جای ۴۸ بیت مصرف می‌شود. کد گذاری به روش هافمن، روشی است برای بهینه سازی مقدار حجم استفاده شده برای نگهداری داده‌های معلوم است.

مراحل روش هافمن

1. چگالی هر کاراکتر را محاسبه میکنیم (تعداد دفعات حضور کاراکتر در متن مورد نظر).
2. دو کاراکتر با کمترین میزان تکرار (چگالی) را انتخاب میکنیم.
3. کاراکترهای مرحله ۲ را با کاراکتر جدیدی که دارای چگالی برابر با مجموع چگالی دو کاراکتر فوق است جایگزین میکنیم.
4. تا زمانی که فقط یک کاراکتر باقی مانده باشد، به مرحله ۲ میرویم.
5. از عملیات فوق یک درخت حاصل می شود، بر روی این درخت هر مسیر به سمت چپ با ۰ و هر مسیر به سمت راست با ۱ وزن دهی می‌شود.
6. کد هر کاراکتر با کنار هم گذاشتن وزن‌ها از ریشه تا آن کاراکتر به دست می‌آید.

در الگوریتم هافمن مسئله ادغام دودویی فایل‌ها استفاده می‌شود که جهت فشرده سازی فایل‌ها یا ارسال کم حجم تر اطلاعات بر روی خطوط شبکه مورد استفاده قرار می‌گیرد . در ابتدا یک جدول درنظر می‌گیریم در ستون ابتدایی مقادیر (داده ها) را وارد می‌کنیم در ستون دوم تعداد تکرار داده‌ها را محاسبه کرده و براساس آن درخت می‌سازیم سپس یال‌های چپ را صفر و یال‌های راست را یک.

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

مثالی از نحوه ساختن درخت هافمن

فایل متنی زیر را در نظر بگیرید

xxyzpxxsxyyxpyzrrrzxxqyttq

در این متن تعداد کلمات تکرار شده را مطابق جدول زیر بدست می‌آوریم.

نمودار درخت هافمن بصورت زیر خواهد بود. که از fiهای کوچک باهم جمع شده و تا ریشه درخت ادامه پیدا می‌کند.

سپس سمت چپ با صفر و سمت راست با یک برچسب گذاری می‌شود و در نهایت برای پیدا کردن کد یک کاراکتر از ریشه به سمت آن کاراکتر در برگ پی می‌رویم. جدول زیر کد تولید شده را نشان می‌دهد.

فضای مصرفی در روش معمولی:

۲۶×۸=۲۰۸ bit

فضای مصرفی در روش هافمن:

∑ fi ×n=16+10+9+8+4+9+8+8=72  bit

سورس کد الگوریتم هافمن در ++C

1. یک رشته را بعنوان ورودی می‌گیرد آنرا به لیستی از CharInfo تبدیل می‌کند.
2. لیست را بر اساس فراوانی sort می‌کند (صعودی)
3. با دو عضو اول لیست یک درخت تشکیل می‌دهد بطوریکه نود والد جمع دو نود فرزند باشد.
4. دو عضو بعدی لیست را انتخاب می‌کند وبرای انجام مرحله بعدی یک شرط را بررسی می‌کند.
5. توضیح شرط: اگر فراوانی تک تک این دو عضو از مجموع فراوانی‌های دو نود ساخته شده در مرحله قبل کمتر باشد تشکیل یک زیردرخت جدید می‌دهد و درصورت برقرار نبودن شرط تنها یک عضو از لیست انتخاب کرده و با توجه به فراوانی آن تشخیص می‌دهد که آنرا در سمت چپ درخت قبلی قرار دهد یا در سمت راست.
6. به همین منوال درخت پوشای مینیمم تشکیل می‌شود.

تکه کد تابع اصلی یا Main الگوریتم در سی پلاس پلاس بصورت زیر است:

int main()
{

   char str[100],S;
   int strarray[124];
   int ss=0;
   char checkCharacter;
   int count = 0;
   cout<<"Type the String <1-100> : "<<endl;
   gets(str);

   for(int i=0;i<124;i++)
   {
       checkCharacter=i;
       count = 0;
       for(int j=0;j<strlen(str);j++)
    {
        if (str[j] ==  checkCharacter)
        {
            ++ count;
        }
    }


    strarray[i]= count;

   }

   for(int i=0;i<124;i++)
      if(strarray[i]>0)
         ss++;


   char *arr=new char[ss];
   int *freq=new int[ss];

   int j=0;
    for(int i=0;i<124;i++)
      {
         if(strarray[i]>0)
         {
            S=i;
            arr[j]=S;
            freq[j]= strarray[i];
            j++;
         }

       }


     cout<<"frequency of unique character : "<<endl;
         for(int i=0;i<strlen(arr);i++)
      {
           cout<< arr[i]<<" = " <<freq[i]<<endl;

       }

  cout<<"\nHuffman Codes:\n";
  HuffmanCodes(arr, freq, strlen(arr));
   getch();
  return 0;
}

برای دانلود کامل کد محصول را خریداری نمایید.

درباره محصول

سورس کد الگوریتم هافمن به زبان سی پلاس پلاس با استفاده از محیط ++Dev-C نوشته شده است و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است و دارای نشان تضمین کیفیت پی استور می‌باشد. برای دانلود اثر مذکور آن را خریداری کنید.