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

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

الگوریتم هافمن یک روش رمزگذاری محبوب است که در سیستم های ارتباطی الکترونیکی استفاده می شود. به طور گسترده در همه فرمت های فشرده سازی اصلی که ممکن است با آنها روبرو شوید، از GZIP، PKZIP (winzip و غیره) و BZIP2 گرفته تا فرمت های تصویری مانند JPEG و PNG استفاده می شود. برخی از برنامه ها فقط از روش کدگذاری هافمن استفاده می کنند، در حالی که برخی دیگر از آن به عنوان یک مرحله در فرآیند فشرده سازی چند مرحله ای استفاده می کنند.

الگوریتم کدگذاری و تصمیم گیری هافمن در فشرده سازی داده ها از کدهایی با طول متغیر استفاده می کند. کوتاه ترین کدها به پرتکرارترین کاراکترها و طولانی ترین کدها به کاراکترهای نادر اختصاص داده می شوند.
کدگذاری هافمن یک الگوریتم رمزگذاری آنتروپی است که برای فشرده سازی داده ها بدون از دست دادن اطلاعات، استفاده می شود. آنتروپی معیاری برای پیش بینی ناپذیری یک جریان اطلاعات است. حداکثر آنتروپی زمانی رخ می دهد که یک جریان داده دارای بیت های کاملاً غیرقابل پیش بینی باشد، مثلا: یک جریان کاملاً ثابت از بیت ها (همه صفر یا همه یک) کاملاً قابل پیش بینی است (یعنی آنتروپی ندارد).

روش کدگذاری هافمن تا حدودی شبیه به روش Shannon-Fano است. تفاوت اصلی بین این دو روش این است که Shannon-Fano کدهای خود را از بالا به پایین می سازد (و بیت های هر کلمه رمز از چپ به راست ساخته می شوند)، در حالی که هافمن یک درخت کد از پایین به بالا می سازد و بیت های هر کلمه رمز، از راست به چپ ساخته می شوند.

مراحل رمزگذاری داده ها با استفاده از کدگذاری هافمن

مرحله 1. احتمال هر کاراکتر را در مجموعه ای از داده ها محاسبه کنید.

مرحله 2. مجموعه داده ها را به ترتیب صعودی مرتب کنید.

مرحله 3. یک گره جدید ایجاد کنید که در آن گره فرعی سمت چپ، کمترین فرکانس را در لیست مرتب شده و گره فرعی سمت راست بعد از آن، کمترین فرکانس در لیست مرتب شده را داشته باشد.

مرحله 4. این دو بخش را از لیست مرتب شده حذف کنید چون الان بخشی از یک گره هستند و احتمالات را اضافه کنید. نتیجه احتمال گره جدید است.

مرحله 5. مرتب سازی لیست را انجام دهید.

مرحله 6. مراحل 3، 4 و 5 را تکرار کنید تا زمانی که تنها یک گره باقی بماند.[/stextbox]

اکنون که یک گره باقی مانده است، به سادگی درخت را رسم کنید.

با درخت بالا، در هر مسیری که به سمت چپ می‌رود، یک عدد 0 و در هر مسیری که به سمت راست می‌رود یک عدد 1 قرار دهید. حالا با شمارش 0 و 1 ریشه، کد باینری را به هر یک از نمادها یا کاراکترها اختصاص دهید.

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

برای مطالعه ادامه متن و دانلود کد متلب الگوریتم Huffman فایل زیر که شامل گزارش کار کامل و کد و خروجی های مربوط به الگوریتم در نرم افزار متلب می باشد، را دانلود کنید.