Printable View
سلام دوستان.
به لطف عمو پیمان Payman_62 اسم تاپیک عوض شد و کار بعدی ما در مورد الگوریتم های فشرده سازی میشه که چگونه استفاده از این الگوریتم ها در ویژوال استادیو میشه.
منم انشالله سرم خلوت بشه کماکان مطالبی ارائه میکنم.
با تشکر از همه ی عزیزانی که همراهی میکنند.
من شنیدم که الگوریتم فشرده سازی هافمن بهترین الگوریتم فشرده سازی هست و چیزی بین 20 تا 90 درصد فایل رو فشرده تر می کنه
الگوریتم جالبیه البته من تا اونجایی که دیدم فقط روی کاراکتر ها ( فایل های متنی) اجرا می کردند( منظور چند مثالی که من دیدم)که می اومد اول تمام تعداد تکرار کاراکتر ها رو پیدا و در متغیری ذخیره می کرد و کاراکتر هایی که تعداد تکرارشون از همه بیشتر بود رو با بیتهای کمتر و کاراکترهای با تعداد تکرار کمتر را را با تعدادبیت های بالاتر نسبت می دادند بعد می اومدند به جای کاراکتر ها این بیتها را قرار می دادند . واسه من که خیلی جالب بود
راستی داداش علی ( hamishebahar ) اگه میشه سورس برنامه وین رر را به زبان C# برام بزارید . اگه هم بتونید برنامه ای که این کا را می کنه ( تبدبل برنامه کامپایل شده به سورس) را بزارید ممنون میشم
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ] سلام دوستان.
طبق بررسی هایی که من انجام دادم زیاد بدرد فشرده سازی فایل نمیخوره و احتمالاً فقط برای فشرده کردن متن ها باشه.نقل قول:
من شنیدم که الگوریتم فشرده سازی هافمن بهترین الگوریتم فشرده سازی هست و چیزی بین 20 تا 90 درصد فایل رو فشرده تر می کنه
راستش سورس وینرار رو من ندارم من فقط خود exe رو دیباگ میکردم که زیادم ازش سر در نیاوردم.نقل قول:
راستی داداش علی ( hamishebahar ) اگه میشه سورس برنامه وین رر را به زبان C# برام بزارید .
ولی احتمالاً بشه الگوریتمشو پیدا و پیاده سازی کرد.
انشالله بررسی میکنیم.
یه نرم افزاری هست به نام Reflector:نقل قول:
اگه هم بتونید برنامه ای که این کا را می کنه ( تبدبل برنامه کامپایل شده به سورس) را بزارید ممنون میشم
کدگذاری هافمن:کد:http://reflector.red-gate.com
درعلوم کامپیوتر و تئوری اطلاعات، کدگذاری هافمن یک الگوریتم کدگذاری برای فشرده‌سازی بی‌اتلاف اطلاعات است.
این تعبیر بر می‌گردد به استفاده از جدول کد طول متغیر برای کد کردن هر کدام از نشانه‌های مبدا (مانند کاراکترهای یک فایل). جدول کد طول متغیر از روشی بخصوص مبنی بر احتمال وقوع هر کدام از نشان‌های مبدا بدست می‌آید. این روش بوسیلهٔ دیوید هافمن توسعه یافت. وی دانشجوی دورهٔ دکتری در رشتهٔ فلسفه در دانشگاه mit بود و در سال ۱۹۵۲ مقالهٔ «روشی برای تولید کدی با کمترین تکرار زوائد» را منتشر کرد.
در کد کذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود. روشی به نام کدهای بدون پیشوند(گاهی هم روش «کدهای پیشوندی» گفته می‌شود. یعنی در این روش رشته‌ای که نشان دهندهٔ یک کاراکتر خاص است هیچ گاه پیشوند رشتهٔ دیگر که نمایانگر کاراکتری دیگر است، نمی‌باشد.).در این روش کاراکترهای پرکاربرد تر با رشته‌های بیتی کوتاهتری نسبت به آنهایی که کاربردشان کمتر است، نشان داده می‌شوند.
هافمن موفق شد کارآمد ترین روش فشرده سازی از این نوع را طراحی کند: نگاشت نکردن نشان‌های منفرد مبدا به رشته‌های بیتی یکتا، هرگاه تعداد تکرار نماد‌های اصلی با آنهایی که برای ایجاد این کد مورد استفاده قرار گرفتند مطابقت کند، خروجی‌هایی با اندازهٔ کمتر تولید می‌کند. بعدها روشی برای انجام این کار پیدا شد که این کار را در زمانی خطی انجام می‌داد.
برای مجموعه‌ای از نمادها با توزیع احتمالی یکنواخت و تعداد عضو‌هایی برابر با توانی از ۲، کد گذاری هافمن هم ارز با قطعه کد سادهٔ دوجمله‌ای است. مانند کد گذاری ascii. کد گذاری هافمن روشی متداول برای ایجاد کدهای بدون پیشوند است بطوریکه عبارت «کد هافمن» به گستردگی به عنوان مترادفی برای «کد بدون پیشوند» استفاده می‌شود، هرچند چنین کدی با الگوریتم هافمن بدست نیامده باشد.
اگرچه کد گذاری هافمن برای کد کردن نماد به نماد بهینه‌است، اما گاهی کارآمدی آن بیش از مقدار واقعی پنداشته می‌شود. برای مثال، کد کردن حسابی و کد کردن lzw، گاهی توانایی بالاتری در فشرده سازی دارند.
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
درخت هافمن، ايجاد شده از تعداد تكرار حرف هاي جمله ي «this is an example of a huffman tree».تعداد تكرارها و كد هر حرف، به همراه همان حرف در جدول زير آمده‌است. رمز كردن اين جمله به كمك اين كد، بدون در نظر گرفتن فاصله‌ها، به 135 بيت نياز دارد.
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ] تاریخچه:
در سال ۱۹۵۱ David.A.Huffman و هم شاگردی‌هایش در کلاس «تئوری اطلاعات» دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا دادن امتحان پایانی را داشتند.استاد Robert M. Fano موضوع تحقیق را مسالهٔ پیدا کردن کارآمد ترین کد دودویی تعیین کرد. هافمن ناتوان در پیدا کردن کارآمد ترین، تصمیم گرفته بود خودش را برای امتحان پایانی آماده کندکه ایده‌ای به ذهنش رسید. ایدهٔ استفاده از درخت دودیی مرتب شده بر حسب تکرار(frequency) وتوانست اثبات کند که این کارآمد ترین روش است. در انجام این کار، شاگرد از استادش که با مبدع تئوری اطلاعات، Claude Shannon برای ساختن کدی مشابه کار کرده بود، پیشی گرفت. هافمن از مشکل اصلی روش کدگذاری نیم بهینهٔ Shannon-Fano coding جلوگیری کرده، درخت را به جای ساختن از بالا به پایین، از پایین به بالا ساخت.
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ] تعریف مساله:
توضیح غیر رسمی
داریم: مجموعه‌ای از نمادها و وزن هایشان (معمولا متناسب با احتمال‌ها یشان)
پیدا کنید: کد دودویی بدون پیشوند، (مجموعه‌ای از کدها) با کمترین امید ریاضی برای طول کد.(به طور معادل، درختی با کمترین مسیر وزن دار).
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ] انواع :
انواع مختلفی از کد گذاری هافمن وجود دارد، که بعضی از آنها از الگوریتم‌هایی شبیه الگوریتم هافمن و بعضی دیگر از کدهای بهینهٔ پیشوندی (با محدودیت‌های خاص برای خروجی)استفاه میکنند. در حالت اخیر، نیاز نیست که روش، شبیه روش هافمن باشد و حتی ممکن است زمان اجرایی چند‌جمله‌ای هم نداشته باشد. لیست کاملی از مقالات مربوط به انواع مختلف کد گذاری هافمن، در «درخت‌های کد و تجزیه برای کد کردن بی زیان اطلاعات» [1] داده شده‌است.
کد هافمن n تایی
الگوریتم کد هافمن n تایی از الفبای {۰, ۱,..., n − ۱} برای کد کردن پیام‌ها و ساختن درخت n تایی استفاده می‌کند. این روش دسترسی بوسیلهٔ هافمن و در مقاله اش بررسی شده بود.
کد هافمن انطباقی
نوع دیگری به نام کد هافمن انطباقی، احتمالاتی را که به صورت پویا و بر اساس تکرار واقعی در منبع اصلی است، محاسبه می‌کند. این به گونه‌ای مربوط به خانوادهٔ الگوریتم‌های LZ است.
الگوریتم الگوي هافمن
بیشتر اوقات، وزن‌های مورد استفاده در اجرای کد هافمن، نمایانگر احتمالات عددی است ولی این الگوریتم چنین چیزی را نیاز ندارد بلکه فقط به راهی برای منظم کردن وزن‌ها و اضافه کردن آنها نیازمند است. الگوریتم الگو هافمن امکان استفاده از هر نوع وزنی را می‌دهد.(ارزش-تکرار-جفت وزن ها-وزن‌های غیر عددی) و هر کدام از روش‌های ترکیبی مختلف. اینگونه الگوریتم‌ها می‌توانند مسائل فشرده سازی دیگر را نیز حل کنند.
كد هافمن با طول محدود
كد هافمن با طول محدود نوعي ديگر از كد هافمن است. اين نوع هنگامي مورد استفاده قرار مي گيرد كه هدف هنوز بدست آوردن طول مسير با كمترين وزن است اما يك شرط ديگر نيز وجود دارد و آن اين است كه اندازه ي هر كد، بايد كمتر از مقدار ثابت خاصي باشد. الگوريتم بسته بندي-ادغام اين مشكل را بوسيله ي يك الگوريتم حريصانه ساده شبيه به هماني كه در الگوريتم هافمن بكار رفته بود، حل مي كند. پيچيدگي زماني اين الگوريتم O(nL), كه L
هيچ الگوريتمي شناخته نشده كه اين كا را در زمان linear or linearithmic انجام دهد,بر خلاف مسائل پيش مرتب شده و مرتب نشده ي هافمن. ماكزيمم طول يك كدكلمه(codeword)است.
كد هافمن با ارزش حرفي متفاوت
در كد گذاري استاندارد هافمن، فرض شده است كه هر نماد در مجموعه اي كه كد ها از آن استخراج مي شوند،ارزشي يكسان با بقيه دارد: كد كلمه اي كه طول آن N است ارزشي برابر N خواهد داشت ،مهم نيس كه چند رقم آن 1 و چند رقم آن 0 است. وقتي با اين فرض كار مي كنيم، كم كردن هزينه ي كلي پيام ، با كم كردن تعداد رقم هاي كل 2 چيز يكسانند. كد هافمن با ارزش حرفي متفاوت به نحوي عموميت يافته كه اين فرض ديگر صحيح نيست: حروف الفباي كدگذاري ممكن است طول هاي غير همساني داشته باشند ، به خاطر خصوصيت هاي واسطه ي انتقال. مثالي بر اين ادعا،الفباي كد گذاري كد مورس است، كه در آن فرستادن يك 'خط تيره' بيشتر از فرستادن يك 'نقطه' طول مي كشد ، پس ارزش خط تيره در زمان انتقال بالاتر است. درست است كه هدف هنوز كم كردن ميانگين طول وزني كد است اما ديگر كم كردن تعداد نماد هاي بكار برده شده در پيام، به تنهايي كافي نيست. هيچ الگوريتمي شناخته نشده است كه اين را به همان روش و همان كارآيي كد قراردادي هافمن انجام دهد.
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ] كد قانوني هافمن:
اگر وزن هاي مربوط به ورودي هاي مرتب شده بر اساس الفبا، به ترتيب عددي باشند، كد هافمن طولي برابر طول كد الفبايي بهينه دارد كه مي تواند از طريق محاسبه بدست آيد. كد بدست آمده از ورودي هاي مرتب شده از نظر عددي ، كد قانوني هافمن گفته مي شود و كدي است كه به خاطر سادگي رمز كردن و رمز گشايي ،در عمل استفاده مي شود. تكنيك پيدا كردن اين كد ، اكثرا كد گذاري Huffman-Shannon-Fano ناميده مي شود. و اين به خاطر آن است كه مانند كدگذاري هافمن بهينه، ولي در احتمال وزن ها مانند كد گذاريShannon-Fano coding الفبايي است. كد هافمن Shannon-Fano مربوط به اين مثال {000,001,01,10,11} است كه در آن طول كد كلمه ها ، همان مقداري است كه در حل اصلي آمده است.
نمونه پروژه ی#C:
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ] سی شارپ(#C) پروژه:
با عرض پوزش از همه ی عزیزان و برنامه نویسان.احتمالاً تا آخر فروردین نیستم:11:.کد:http://hamishebaharp30world.persiangig.com/Class/Huffman/TestHufman.zip
کسی نیست
ادامه بده ما همچنان منتظریم
داشتم تو اینترنت می گشتم که به این صفحه و این مطلب رسیدم
برام خیلی جالب بود . نزدیک به 4 یا 5 سال پیش یه همچین ایده ای به ذهنم رسید . البته اون موقع تازه داشتم می فهمیدم برنامه نویسی چیه . یه الگوریتم هایی البته خیلی مبتدیانه و به فارسی واسه درک خودم نوشتم . فکر می کردم خیلی خوب کار کنه ولی چون از برنامه نویسی هیچی نمی دونستم گذاشتم واسه بعدا . 1 الی 1.5 سال قبل رفتم سراغش دیدم که بله نمیشه اکستراکتش کرد ( دقیق نمیدونم ولی فکر کنم اون الگوریتم هنوز موجوده اگه پیداش کردم می زارم براتون فقط بهم نخندینا)و خلاصه بعدترش فهمیدم که گذشته از اکستراکت نشدتش خیلی زمان هم می بره ( جدی میگم عمر نوح براش کم بود) یه 6 ماهی روش کار کردم ولی دیدم فایده نداره بی خیالش شدم . البته نه بی خیال ولی گذاشتم برا بعدا .نقل قول:
کد:http://barnamenevis.org/showthread.php?4137-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D9%81%D8%B4%D8%B1%D8%AF%D9%87-%D8%B3%D8%A7%D8%B2%DB%8C&p=878666&viewfull=1#post878666
کل این حرفا رو زدم که بگم اگه حرفش واقعا حرف باشه کار بزرگیه . بنظرتون میشه این کار را کرد؟
اون تاپیک که دوستمون لینکشون گذاشتن آقا یا خانم mebd12 گفته برنامه ی فشرده سازی به روش بازگشتی رو نوشته :31: که هم عجیبه که تا حالا چرا سر صدایی نکرده این قضیه، هم جالب و هم غیر قابل باور .. ولی به نکته ی جالبی اشاره کردن اونم بهم ریخت نظم بیت ها س مثلا میشه ملاک کار رو بیت های 0 قرار داد و اگه بیت های 0 در یک مجموعه (که میتونه 8 بیت یا بیشتر باشه ) کمتر از نصف بود مجموعه رو NOT کرد و با اینکار تعداد تکرار رو بالا برد و ... البته با افزایش حجم چون حالت ها خیلی بیشتر میشه تعداد احتمالات هم بالا میره و زمان به بینهایت میل میکنه که شاید به صرفه نباشه ولی غیر ممکن هم نیست .
میشه درباره همین به هم ریختن نظم بیتها بیشتر توضیح بدین . یه کمی بازش کنین
مرسی
حالا من یه چیزی همینجوری پروندم شما جدی نگیر :31:
بعد از خوندن حرف ایشون به ذهنم رسید که چون اصولا جایی برای حذف کردن هیچ کدوم از بیت ها وجود نداره (چون تو این روش به ورودی توجهی نداریم و باید یک مجموعه از بیت ها هر ترکیبی که داشته باشن بشه الگوریتم رو روش پیاده کرد)، پس اصولا باید یه چیزایی رو حذف کنیم که بدون ذخیره سازی بتونیم با آزمایش و خطا جواب صحیح رو بدست بیاریم.
یه ضرب المثلی هست که میگه به شتر گفتن چرا کوهانت کجه گفت کجام درسته!؟ .. حالا همین جریال آقا شتره س از اول بگم که این روش بار علمی نداره و بر پایه ی حدس و گمانه خواهشا کوهان شتر رو بیخیال شید [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
همه ی این چیزایی که پایین میگم یه مثال غلط و کنترل شده س فقط برای توضیح حرف بالا ..
مثلا در این بایت 10111011 تعداد 0 ها کمتره. میشه این بایت رو در 6 بیت ذخیره کرد (برای ذخیره ی مکان هر 0 3 بیت در داخل یک بایت فضا لازمه) ولی همیه به این روش نمیشه عمل کرد چون 0 ها میتونه حتی 8 تا هم باشه و برای ذخیره کردن این حالت 3*8 که 24 بیت میشه عملا 3 برابر فضای اولیه استفاده میشه که ...
چیزی که به ذهنم رسید این بود که فرضا مبنا رو عدد 0 در نظر بگیریم و بیایم در هر بایتی که میخوایم ذخیره کنیم تعداد صفر ها رو بشماریم و اگه تعداد از 4 تا بیشتر شد کلا 0 های اون بایت رو به یک و یک های اون بایت رو هم به 0 تبدیل کنیم
مثلا در مجموعه ی 8 بیتی 10000100 تعداد بیت های 0 ، شش تاس. ما میایم و این مجموعه رو تبدیل میکنیم به 01111101 حالا برای ذخیره ی 0 های این مجموعه 6 بیت فضا لازمه
کلا در این حالت حداکثر تعداد بیت های مبنا (در اینجا 0) 4 تاس که در مقایسه با حالت اصلی که ممکنه 8 تا باشه نصف شده (مشکل این روش اولا اینه که برای ذخیره کردن 4 تا صفر، 12 بیت لازمه و ثانیا نمیشه گفت در جایی اصلا صفر وجود داره یا نه که اگه بخواین این رو هم از بین ببریم کلا 16 بیت فضا لازم میشه که عملا خیلی روش جالبی از آب در میاد :39: ) .. شاید با روشی بشه مکان این بیت ها رو هم مشخص کرد که کمتر از 8 بیت فضا اشغال کنه
در خارج کردن از حالت فشرده هم ما در هر مرحله از کل بیت ها یه hash میسازیم(قبل از فشرده سازی) و وقتی خواستیم اکسترکت کنیم در هر مرحله بیت ها رو از حالت فشرده خارج میکنیم و اگه hash کد بدست اومده با hash کد اصلی یکی باشه که هیچ اگه نه از اول شروع میکنیم و مجموعه ای که (در اینجا بایت) تعداد بیت های صفرش کمتر از 5 باشه not میکنیم و دوباره اکسترکت میکنیم و hash کد میسازیم و تا جواب بدست اومده همون hash کدی رو تولید کنه که فایل اصلی تولید کرده
البته در hash هم احتمال خطا وجود داره چون هش کد 100% نمیتونه بگه 2 تا فایل یکسان هستند
یه مثال کلی میزنم (اعداد این مثال رو طوری انتخاب شده که وسط کار شرمنده مون نکنه و فقط به خاطر اینه که منظور کلی رو برسونم والا در نادرست بودن راه ، شکی نیست :13:)
فرضا محتوای فایلی این 3 بایته
بایت 1 بایت 2 بایت 3
10000001 01011111 11001111 اول hash کدش رو میسازیم که مثلا میشه 1234 :31:
بایت ها رو طوری تغییر میدیم که تعداد صفر ها در هر بایت کمترین باشه . یعنی کمتر از 4 تا .. که داریم
01111110 01011111 11001111
حالا مکان 0 ها رو ذخیره میکنیم
000-111 000-010 010-011
برای ذخیره ی این 3 بایت ما به جای 24 بیت ، 18 بیت استفاده کردیم که در فایل های بزرگ جای اضافی برای ذخیره ی اطلاعات دیگه مثل hash کد یا حتی مکان بایت هایی که not شدند رو هم خواهیم داشت.
در اکسترکت فایل ها خواهیم داشت (اولین قدم)
01111110 01011111 11001111 و وقتی هش کد این فایل رو با هش فایل اصلی مقایسه کنیم میبینیم که یکی نیستن بنابراین ما حداقل 1 یک و حداکثر 2 به توان 3 بایت رو باید not کنیم، اکسترکت کنیم و با هش فایل اصلی مقایسه کنیم
در دومین قدم بعد از جا گذاری صفر ها (بقیه ی بیت ها هم که یک هستن) ما بایت اول رو not میکنیم که داریم
10000001 01011111 11001111 هش کد ، در این حالت با هش اصلی یکیه اگه نبود میریم سراغ حالت های بعدی و اونا رو not میکنیم تا جواب به دست بیاد....
حالا فرض کنید یه فایل 1 مگابایتی رو یک مرحله فشرده کردیم و میخواییم اکسترکت کنیم (2 به توان یک میلیون .. که خود عدد حدودا 100000 رقمیه ) پست قبلی هم گفتم شاید به صرفه نباشه ولی غیر ممکن هم نیست.
---
کلا تبدیل یه تعداد از بیت ها به غیر از حالت اصلی دریچه ی جدیدی در این روش باز میکنه.
مرسی جالب بود برام
من فکر می کنم اگه الگوریتم را به چند قسمت مساوی تبدیل کنیم ( در فایل های حجیم ) و این عملیات را روش انجام بدیم ( بازگشتی) شاید بد نباشه . البته باید بیشتر روش فکر کنم .