شنبه 27 آبان 1396 | Saturday 18 th of November 2017 صفحه اصلی گروه الکترونیکی کامپیوتر
الگوریتم ضمن (Haffman)

فشرده سازی داده ها به معنی تبدیل رشته ای از کاراکترها به رشته دیگری است. به طوری که رشته حاصل مفهموم همان رشته اولیه را داشته ، ولی طول رشته حاصل کوتاهتر باشد. برای اینکه یک روش رمزگذاری (coding)و برای بازیابی رشته به یک روش رمزگشایی نیاز داریم. انتخاب یک روش رمزگذاری بر اساس تولید رشته با طول کمتر می باشد. یعنی روشی مناسب تر است که بتواند رشته ای با طول یا حجم کمتر تولید نماید.

مشکلی که در روشهای  رمزگذاری با طول متغیر وجود دارد اینست که ، وقتی یک کلمه یا جمله را تبدیل می کنیم، بین رمز کاراکترهای متوالی باید جدا کننده وجود داشته باشد. همچنین کلمه رمز کاراکترهای مختلف ، متفاوت می باشند. بنابراین طوری عمل می کنیم که اولا طول رمزها یکسان نباشد ثانیا نیازی به استفاده از جداکننده وجود نداشته باشد.

روش رمزگذاری هافمن ، یک روش رمزگذاری با طول متغیر بوده که مشکلات بیان شده در بالا را نیز حل کرده است .

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

 همانطور که قبلا نیز اشاره کردیم ، برای رمزگذاری متن باید تعداد تکرار هر کدام از حروف را بدانیم. همچنین باید به تعداد تکرار هر کاراکتر توجه ویژه ای داشته باشیم . کاراکتری که تعداد تکرار بیشتری دارد ، باید طول رمز کمتری داشته باشد .

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

1)     تعداد تکرار کاراکترها را در متن می یابیم .

2)     هر کدام از تکرارهای به دست امده را در یک گروه قرار می دهیم ، حاصل یک جنگل خواهد بود.

3)     گره ها را به صورت صعودی مرتب می کنیم.

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

مرحله قبل را تا زمانی که تمام درخت های جنگل با هم ادغام نشده ، ادامه می دهیم. درخت ساخته شده با ساختار بالا را درخت ادغام می نامند

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26