برنامه نویسی کد هافمن

[Mohammad S]

با سلام
توضیحی کوتاه در مورد کد هافمن: یکی از روشهای فشرده سازی است که در آن به کاراکتری که بیشترین استفاده را دارد کد کوتاه تری داده می شود. مثلاً اگر در کد اسکی ، کد حرف A=65 است ممکن است در کد هافمن A=70 باشد (بستگی به تعداد تکرار آن دارد).
حال من می خواهم برنامه ای بنویسم که مثلا یک فایل متنی را باز کرده و با کد هافمن (کدی که خودم ساخته ام) ذخیره کند و سپس حجم این دو فایل را مقایسه کنم (فایلی که با کد اسکی ذخیره شده و فایلی که با کد ساختگی من ذخیره شده) و نشان دهم که واقعاً فشرده سازی انجام شده است.
مشکل من این است که نمی دانم چطور یک فایل را با کدی که خودم می سازم به جای استفاده از کد اسکی، ذخیره کنم. :roll:
لطفا راهنمایی ام کنید.
با تشکر

[hr110]

منظورتون رو کاملاً درک نکردم، ولی فکر کنم بتوانید با متغییر از نوع

file of char
هر کاری انجام بدهید، ضمناً TFileSteam هم ممکن است بکار تان بیاید

[Sepidar]

توجه داشته باشید که در الگوریتم هافمن ممکن است کاراکترهای شما طولشان بیشتر یا کمتر از 8 بیت (=1 بایت)‌ شود. به این علت باید یک آبجکت داشته باشید که شما بتوانید اطلاعات را به صورت بیت به بیت به آن بفرستید و آن آبجکت خودش اطلاعات را به صورت بایت دسته بندی کند.
فکر میکنم در یونیت classes یک چنین کلاسی به نام TBits وجود دارد.... ولی مطمئن نیستم...

در ضمن کدهای زیر را هم بنده 9-8 سال پیش زمان توربو پاسکال خدا بیامرز نوشته ام که یک پیاده سازی آزماشی و غیر بهینه از الگوریتم هافمن می باشد. خودم که یادم نیست چی کار کردم... :گیج: اما امیدوارم شما سر در بیاورید :)

موفق باشید

[Mohammad S]

دوستان عزیز با تشکر از جوابتان
ببینید کد اسکی:
A=65, B=66, C=67, ....
بر اساس فراوانی حروف در کلمات انگلیسی مثلا مشخص کرده ام که حرف A بیشتر از حرف C می آید ولی حرف B بیشتر از حرف A. در نتیجه به حرف B کد کوتاهتر و سپس حرف A‌و سپس حرف C. به این صورت:
B=65, A=66, C=67, ...
خوب حالا می خواهم یک فایل متنی را باز کرده و یک مرتبه با کد اسکی و یک مرتبه با کد خودم ذخیره کنم تا نشان دهم واقعاً این روش باعث فشرده سازی می شود.
البته خودم به نتایجی رسیدم،‌ کد هافمن زمانی جواب می دهد که بعضی از کد ها دو بایتی و بعضی یک بایتی باشند و .... مثلاً

2*2B+3*1B=7B
2*1B+3*2B=8B

می بینیم که یک مرتبه 7 بایت اشغال می کند و دفعه بعد 8 بایت پس فشرد ه شده است.
کلا من می خواهم فشرده سازی را نشان دهم حالا به هر روشی که شده حتی اگر نشد شاید مقادیر کد ساختگی خود برای حروف را در یک متن جمع بزنم که قطعاً عدد کمتری به دست می آید :roll:
ضمنا اگر امکان دارد کمی هم در مورد TFileSream توضیح دهید.
با تشکر

[Mohammad S]

دوستان عزیز
اینو هم ببینید شاید به درک شما کمک کنه
http://www.barnamenevis.org/forum/viewtopic.php?t=5247&highlight=%E5%C7%DD%E3%E4

باز هم متشکرم از لطفتان

[Sepidar]

دوست عزیز

بیا از اول شروع کنیم:

فرض کنید که اطلاعات را به صورت بایت ذخیره کرده اید. مثلا در یک فایل 20 عدد الف، 5 عدد ب و 3 عدد جیم وجود دارد. در حالت عادی این اطلاعات را به شکل کدهای 8 بیتی مثلا به شکل زیر نشان میدهیم:

الف: 10011010
ب: 00011001
جیم: 10001101

در این صورت اطلاعات فایل 20+5+3=28 بایت (یا 28*8=224 بیت) خواهد بود.

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

الف:1
ب:01
جیم:00

بر این اساس طول فایل 20*1+5*2+3*2=32 بیت (برابر با 4/32=8 بایت) خواهد بود.

این مطالب را عرض کردم چون احساس کردم خود الگوریتم خوب جا نیافتاده است.

[Sepidar]

در ضمن امروز نشستم کدهایی رو که نوشته بودم مرور کردم، خیلی هم نا خوانا نبود، یه دور روش رو بخونی راخت جا میافته :)

[Mohammad S]

جناب سپیدار عزیز
با تشکر از لطف شما
تقریبا چیزهایی متوجه شدم. خوب مشکل سر این است که ما حداقل 26 حرف انگلیسی داریم (در اصل 2*26=52) بدون علامت های سوال و تعجب و نقطه و کاما و ......
با توجه به چیزی که شما نوشته اید، حالت ثابتی مثل ذخیره سازی یک بایت یک بایت نخواهیم داشت و ممکن است حروفی که کمتر آمده و کد طولانی تری دارند چند بیتی حتی 8 بیتی باشند. درست است؟ !
بر فرض اگر به این روش ذخیره کنیم (توسط دلفی می توان چنین کاری کرد؟ اگر می شود چگونه؟) برای بازیابی یا در واقع خواندن فایلی که به این روش تولید شده چه باید کرد؟

باز هم ممنون از همکاری شما :flower:

[Sepidar]

با توجه به چیزی که شما نوشته اید، حالت ثابتی مثل ذخیره سازی یک بایت یک بایت نخواهیم داشت و ممکن است حروفی که کمتر آمده و کد طولانی تری دارند چند بیتی حتی 8 بیتی باشند. درست است؟ !
دقیقا درسته و به همین علت:

باید یک آبجکت داشته باشید که شما بتوانید اطلاعات را به صورت بیت به بیت به آن بفرستید و آن آبجکت خودش اطلاعات را به صورت بایت دسته بندی کند.
و برای این کار تو اون برنامه ای که آپلود کردم از آبجکت(شما بخونید کلاس) TBitMan استفاده کرده ام...


موفق باشید

[firouzsalary]

سلام
من می خواستم مطالبی در مورد کد هافمن و استفاده از آن در ذخیره سازی اطلاعات بدانم
ممنون
فوری

[ehemitsme]

salam doosten...man donbale source barnameye huffman migashtam ke oono peyda kardam albateh be zabane vb.net . omidvaram ke be karetooon biyad



az modir site ham tashakor mikonam.
bye