انواع الگوريتم های فشرده سازی

[soorenam84]

سلام به تمام دوستان عزيزم
خوب همينجور که ميدونيد من تازه اينجا عضو شدم...
تو جستجو هايی که تو اين فروم داشتم به يه مبحث جالب رسيدم که ديدم دوستان دارن در موردش
صحبت ميکنن و اون فشرده سازی بود گفتم چه قدر خوبه که يه تاپيک جديد ايجاد کنم و چيزايی رو که
تو اين ضمينه بلدم به اشتراک بزارم(البته همين الان بگم که چيزه زيادی بلد نيستم) ولی
تقريباً يه 1 سالی هست که تو اين مبحث کار ميکنم.به هر حال اگه دوستان استقبال کنن ميتونم حدقل چند تا از الگوريتم های معروف رو توضيح بدم ضمن اينکه ميتونيم به همکاری هم اينجا يه کلاس قوی در ضمينه فشرده سازی بنويسيم(البته از اين کلاس ها زياد نوشته شده قبلاً) که به درد هممون هم بخوره...
اگه دوستان موافقن يه نظری بدن تا ايشالا شروع کنيم...
تو فکرتونم

[Mr Mohabat]

با سلام
من موافقم شروع کنید ;

[soorenam84]

خوب روشی که ميخوايم اين مبحث رو باهاش شروع کنيم يکی از ساده ترين و در عين حال مهم ترين ها در فشرده سازی هستش.
اين روش در حال حاضر هم خيلی کاربرد داره .از کاربرد های مهم اين روش ميشه به عکس های jpg اشاره کرد و يا ويديو های با فرمت h.264 و ...
پس فعلاً با اين روش پيش ميريم و بعداً ميرسيم به هافمن و ... اگه سؤالی داشتين خوشحال ميشم...

روش فشرده سازی Run-Length

خوب در اين قسمت سعی ميکنيم که اين روش فشرده سازی رو به زبون خيلی ساده اي بيان کنيم.
در اين روش ما به جای اينکه run های مشابه هم رو بنويسيم ميايم يک run مينويسيم و بعد تعداد تکرار اون رو به صورت عدد مينويسيم.
فکر کنم اگه يه مثال بزنم قضيه کاملاً جا بيفته....فرض کنيم متن ما به صورت زير است :

QQQQQQQQQQWRTTYYYUOOOOPPPPPPPPKKKKKKKKKKKKKKKKKKKK

خوب حالا بعد از اينکه ما با اين الگوريتم فشرده کرديمش به صورت زير در مياد:

QQ8WRTT0YY1UOO2PP6KK18

خوب همينجور که می بينيد 50 byte رو تونستيم تبديل به 22 byte بکنيم که خوب نسبتاً خوب هستش.

خوب حالا حتماً با خودتون ميگين که آخه کدوم متن به صورت اين چيزی هست که تو اينجا نوشتی که ما بخوايم اينجوری فشرده کنيمش؟؟؟
در جواب بايد بگم که يکی از کاربرد های اصلی اين روش فشرده سازی در فشرده کردن عکس های باينری هستش و خيلی هم خوب جواب ميده....چون همينجور که ميدونيد اين عکس ها همون عکس های سياه-سفيد خودمون هستن که فقط شامل رنگ سياه يعنی عدد 0 و رنگ سفيد يعنی عدد 1 هستند و خوب ديگه قضيه تابلويه ديگه مثلاً اگه يک قسمت اندازه 2 سانت در 2 سانت در عکس سياه باشه يعنی يک چيزی حدود 300 تا 0 اونجا هستش که خوب با هيچ روشی از اين بهتر نميشه اون رو فشرده کرد.

[soorenam84]

هافمن کدينگ (Huffman Coding)

تاريخچه :

هافمن در سال 1952 الگوريتمی ارائه داد که تونست به هر سمبل بر اساس تعداد تکرارش يک کد اختصاص بده بطوری که کد کوتاهتر برای سمبل با تعداد تکرار بيشتر و کد بلند تر برای سمبل با تعداد تکرار کمتر.
اين الگوريتم تو فشرده سازی بسيار مهم و کارا هستش (البته ميشه گفت بود) و خوب با آمدن الگوريتم arithmetic و قابليت پياده سازی اون ديگه کم کم هافمن کمتر استفاده شد.حالا تو قسمت های بعدی در موردش بيشتر ميگم.

مقايسه چند روش کدينگ :

اينجا يه مثالی براتون ميزنم از کتاب فشرده سازی آقای matt mahoney که فکر کنم بد نباشه.اگه زياد متوجه نشدين نگران نشيد و به خوندن ادامه بديد حتماً در آخر قضيه رو ميگيريد.(هنوز خيلی زوده برای نا اميد شدن!!!).

فرض کنيد ميخوايم عدد pi (همون که 3.14 هستش) رو فشرده کنيم و همون طور که ميدونيد اين عدد تمومی نداره و به صورت ...3.14159265358979323846264 هستش و همين طور هم ادامه داره.
حالا اگر احتمال وقوع هر کدوم از عدد های 0 تا 9 تو اين مجموعه برابر با 0.1 باشه و همه اين احتمالات هم از هم مستقل باشه (يعنی عدد بعدی بعد از مميز به احتمال 0.1 برابر 0 و به احتمال 0.1 برابر 1 و ... باشه و اين احتمالات از هم مستقل باشه.) ميتونيم 3 نوع نمايش BCD و هافمن و باينری رو به صورت زير داشته باشيم.

خوب همين طور که ميبينيد نمايش BCD برای هر کاراکتر از 4 بيت استفاده ميکنه يعنی ميزان فشرده سازی 4 bpc هستش.
يعنی اگه ورودی مون به صورت يه فايل متنی باشه خوب خروجی مون 50% فشرده تر هستش يعنی تو ورودی ما برای نمايش هر رقم از 8 بيت استفاده ميکنيم(ascii text) ولی تو خروجی برای نمايش هر رقم از 4 بيت استفاده ميکنيم يعنی انگار هر 2 رقم رو تو يک byte ميتونيم نمايش بديم.اميد وارم که گرفته باشين.

خوب حالا ميرسيم به نمايش باينری خوب همين طور که ميبينيد اين خيلی بهتره يعنی تو بدترين حالت که رقم 9 داشته باشيم از 4 بيت استفاده ميکنه و تو بقيه حالت ها از 3 يا 2 يا حتی از 1 بيت استفاده ميکنه پس خيلی خوبه و ما ميتونيم خروجی رو به صورت زير نمايش بديم :

...Output=11 1 100 1 101

که البته فاصله ها برای خوانايی بيشتر گزاشته شده.

خوب اين روش باينری خيلی خوبه فقط يه مشکل داره که غير قابل استفاده ميکندش.چه مشکلی؟؟؟ خوب موقع decode کردن از کجا بفهميم که اول بايد 2 تا 1 برداريم بعد 1 دونه 1 برداريم بد 100 بر داريم و ...؟؟؟
پس چون اين روش قابل decode کردن نيست بدرد نميخوره.

خوب حالا ميرسيم به روش هافمن و همين طور که تو جدول بالا ميبينيد اين روش يه چيزی هستش بين باينری و BCD به اين ترتيب که تعداد بيت هاش از BCD کمتره و از باينری بيشتره ولی بر خلاف باينری به صورت منحصر به فرد decode ميشه.چه جوری؟؟؟؟الان ميگم.
فرض کنيد خروجی ما به صورت زير هستش :

...Output=011 001 100 001 101

که فاصله های بين بيت ها برای خوانايی بيشتر گزاشته شده.
خوب تمام نکته همين جاست.decoder شروع ميکنه به decode کردن به اين ترتيب که اول 1 بيت ميخونه و تو جدول چک ميکنه ببينه همچين کدی وجود داره يا نه اگه بود معادلش رو ميزاره(خوب ما ميدونيم که هيچ کد هافمنی تو جدول بالا معادل 0 نيست.). اين کار اونقدر تکرار ميشه تا کد های معتبر از جدول هافمن استخراج بشه و رقم معادل با اونها جايگزين بشه.مثلاً اولين کد معتبر همون 011 هستش که معادل رقم 3 هستش.و به همين ترتيب ادامه ميده تا تمام خروجی رو decode کنه.خوب حالا چند تا سؤال پيش مياد:
1.اين جدول رو از کجا بياريم؟؟؟
2.آيا decoder هم بايد حتماً اين جدول رو داشته باشه تا بتونه decode کنه؟؟؟؟
3.همه اين چرندياتی که گفتی چه ربطی به اون احتمال وقوع و اين چيزا داشت؟
خوب من تو قسمت بعدی جواب اين سؤالات رو ميدم.
الگوريتم هافمن :
فرض کنيد متنی که ميخوايم فشرده کنيم همون عدد pi هستش که در بالا نمايش داديم و فرض کنيد که احتمال وقوع هر رقم در ان 0.1 باشه به صورت زير داريم:

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

به همين ترتيب داريم :


خوب حالا که همه احتمال 0.2 دارن 2 تا رو انتخاب ميکنيم.



حالا کوچکترين احتمال ها 0.2 و 0.4 هستند.

در مرحله آخر که کوچکترين احتمال ها 0.4 و 0.6 هستند ساختن درخت هافمن ما به پايان ميرسد و حالا در اين مرحله به شاخه های سمت چپ 0 و به شاخه های سمت راست 1 ميدهيم که البته اين دلبخواهی است و برعکس هم ميتوان انجام داد.

و در نهايت جدول هافمن ما به صورت زير در می آيد:

خوب پس اين از روش ساخت جدول
هافمن و اينکه در حالت عادی decoder به اين جدول نياز داره پس بايد اين رو
هم برای decoder فرستاد ولی اگر دقت کنيد ميبينيد که با فرستادن اطلاعات
کمتری هم ميشه اين جدول رو تو decoder ساخت.(چرند گفتم امکان نداره اگه
خودتونو پاره هم بکنيد از دقت نميتونيد ببينيد.)


يادتون هست گفتم مهم نيست که به شاخه های سمت چپ صفر بدين و به سمت راست يک و يا برعکس؟؟؟؟


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

خوب حالا ما بجای فرستادن همه جدول ميآيم فقط سمبل و سايز رو ميفرستيم(نگاه کنيد به جدول بالا.)اونوقت تو دکدر چی کار ميکنيم؟؟؟
1.کوچکترين سايز رو ميگيريم (در اينجا 3) و به همون تعداد صفر اختصاص ميديم(000)
2.برای سمبل بعدی اگه سايز ثابت موند(که اينجا ميمونه) يک واحد کد قبلی رو افزايش ميديم.(001).
3.اگه سايز يک دونه افزايش داشت(مثلاً از 3 به 4 رفت.)کد قبلی رو يک واحد افزايش ميديم و يک صفر هم به سمت راست آن اضافه ميکنيم(يعنی از لحاظ برنامه نويسی يک دونه شيفت به چپ ميديم.)(مثلاً اينجا ميشه 1100).
4.روند 2 و 3 رو ادامه ميديم تا سمبل ها تموم بشه.

اها فقط تنها نکته اي که مونده اينه که تو سالهای اخير ديگه هافمن زياد کارايی نداره چون روش های بهتری آمد که هم کارامد تر از هافمن بود هم عيب های هافمن رو بر طرف کرد.(کدوم عيب ها؟؟؟). فرض کنيد به جای عدد pi ميخواين يه ورودی ديگه رو فشرده کنيد مثلاً داريم:

...input=0101011000010101011101010

همين طور که ميبينيد تمام ورودی ما در اينجا 0 و 1 هستش يعنی ورودی فقط 2 حالت داره و از اونجايی که 2 حالت رو ميشه با 1 بيت نمايش داد،پس هافمن چه کمکی ميتونه تو فشده سازی اين ورودی بکنه؟؟؟سعی کنيد يک درخت برای اين ورودی بسازيد اونوقت ميبينيد که هافمن هيچ کمکی نميتونه بکنه و اين يکی از اشکالت هافمن هستش که البته راه هايی برای نه کامل رفع کردن ولی بهتر شدن وجود داره و البته روش های فشرده سازی ديگر هم که اين مشکل رو خيلی وقته رفع کردن مثلاً يکی از روش های خيلی خوب arithmetic coding هستش که حالا بعداً در موردش حرف ميزنيم.

[Mr Mohabat]

سوال

درپست شماره سه توضیحانی که دادید چه فایلهایی با چه پسوندهایی را به چه پسوندی تغییر می دهد
و اینگه اگر کدی مثلا به صورت ddddssss112gggkkk
قسمت قرمز رنگ چگونه تغییر می یابد تا در برگرداندن آن با مشکل روبرو نشویم؟
مرسی بابت راه اندازی این تایپیک

[soorenam84]

خوب همين طور که ميدونيد پسوند در مورد فايل ها يک چيز کاملاً قراردادی هستش و هيچ ربطی به کار ما نداره.چون اکثر دوستان با سيستم عامل windows کار ميکنن اينقدر پسوند براشون مهمه وگرنه تو سيستم عامل های ديگه مثل لينوکس اصلاً پسوند فاقد معنی و مفهوم هستش.
ضمن اينکه پسوند کاملاً قرارددی هستش مثلاً برنامه اي مثل winzip از چند الگوريتم برای فشرده سازی استفاده ميکنه ولی خروجی تمام فايل هاش zip. هستش...حالا کم کم يه سری پياده سازی به زبون c براتون ميزرم که بهتر درک کنيد.

در مورد سؤال دوم جواب به اين صورت هستش:

dd2ss21102gg1kk1

[Mr Mohabat]

این آخری را هم جواب بدی ممنون میشم
ddddssss12gggkkk
اگه اشتباه نکنم این الگوریتم بیشتر در فشرده سازی عکس های BMP کاربرد داره درسته ؟

[skyzare]

سلام ....

با تشکر از مطالبتون ..... من هم یه چند تا سوال دارم ... سوالام مسخره هست اخه کامپیوتری نیستم

1- بخشید تصاویرjpg با jpegچه فرقی داره ؟؟

2-فرمودید که یکی از روش های فشرده سازی در تصاویر باینری استفاده از روش run-lenght هست ..شما مثلا توی همین مثال شما دو تا از حرف رو نوشتید بعد تعدادش ....این الزام هست منظورم حتما باید دو تاش نوشته بشه یا فرقی نداره ؟؟

3-ببخشید bpc مخف چیه ؟؟

فقط اينه که به سمبل به تکرار بيشتر کدکوتاه تری اختصاص داده بشه فقط و فقط همين.

4- یعنی اگه یه سمبل احتمال وقوعش بیشتر باشه کدی که بهش اختصاص داده میشه داخل جدول هافمن کوچیک تر هست ؟؟؟

.کوچکترين سايز رو ميگيريم (در اينجا 3) و به همون تعداد صفر اختصاص ميديم(000)
2.برای سمبل بعدی اگه سايز ثابت موند(که اينجا ميمونه) يک واحد کد قبلی رو افزايش ميديم.(001).
3.اگه سايز يک دونه افزايش داشت(مثلاً از 3 به 4 رفت.)کد قبلی رو يک واحد افزايش ميديم و يک صفر هم به سمت راست آن اضافه ميکنيم(يعنی از لحاظ برنامه نويسی يک دونه شيفت به چپ ميديم.)(مثلاً اينجا ميشه 1100).

5- این رو که فرمودید فرقی نداره احتمال سمبل ها چی باشه ؟؟ اخه شما این حا همه اش رو یکسان گرفته بودید ..

ولی واقعا خوب گفتید من که اولین بار داشتم میخوندم تا حدودی گرفتم چی شد ...

با تشکر از پاسختون ....

[soorenam84]

سلام
خيلی خوشحالم که از اين مطالبم استقبال شد.خوشحال ميشام که هر ايرادی که داره بهم بگين.
خوب جواب دوست عزيزم در مورده متنی که داده بود:(ddddssss12gggkkk) :
ميشه:
dd2ss212gg1kk1
و ضمن اينکه اين مسئله رو در نظر بگيريد که run-length الگوريتم هاش تو جزئيات باهم تفاوت دارن مثلاً run-length اي که در jpeg استفاده ميشه با اونی که در تصاوير باينری استفاده ميشه با اونی که تو h.264 استفاده ميشه فرق ميکنه و اين که من گفتم فقط يه الگوريتم بود ولی در مجموع ايده اصلی run-length همونه که گفتم يعنی تکرار زياد رو تبديل به نمونه(run) و تعدادش (length) بکنه.
بله درست حدس زديد در يک نوع bmp هم استفاده ميشه.
1.تا جايی که من ميدونم jpeg همون jpg هستش و jpeg مخفف joint photographic experted group هستش و چون معمولاً پسوند ها 3 حرفی هستش بجای jpeg از jpg استفاده ميشه.
2.اگر يک دونش رو بنويسيد و بعد تعدادش رو اونوقت تو دکد کردن به مشکل ميخوريد...با يک مثال ساده ميتونيد اين رو متوجه بشيد. اگه نفهميديد بگيد يه مثال بزنم.
3.تو مبحث فشرده سازی مخفف bit per character هستش يعنی اينکه به ازای هر کاراکتر چند بيت نياز هستش که اين رو ميشه از همون جدولی که دادم محاسبه کنيد که اين کارو من همونجا کردم.
4.بله دقيقاً همونجوری هستش. و همين امر باعث فشرده سازی ميشه.
5.چرا فرق داره ببينيد ما از روي احتمال وقوع سمبل ها ميآييم درخت رو ميسازيم همين که درخت ساخته شد حالا چيزی که مهمه طول هر کد هستش نه خود کد.يعنی شما از روی طول هر کد ميتونيد جدول رو باز سازی کنيد .اميدوارم متوجه شده باشين.شرمنده اگه بد توضيح دادم.
حالا ايشالا پياده سازی بکنم با c کاملاً متوجه ميشيد.

[fuzulkhan]

سلام به تمام دوستان عزيزم
خوب همينجور که ميدونيد من تازه اينجا عضو شدم...
تو جستجو هايی که تو اين فروم داشتم به يه مبحث جالب رسيدم که ديدم دوستان دارن در موردش
صحبت ميکنن و اون فشرده سازی بود گفتم چه قدر خوبه که يه تاپيک جديد ايجاد کنم و چيزايی رو که
تو اين ضمينه بلدم به اشتراک بزارم(البته همين الان بگم که چيزه زيادی بلد نيستم) ولی
تقريباً يه 1 سالی هست که تو اين مبحث کار ميکنم.به هر حال اگه دوستان استقبال کنن ميتونم حدقل چند تا از الگوريتم های معروف رو توضيح بدم ضمن اينکه ميتونيم به همکاری هم اينجا يه کلاس قوی در ضمينه فشرده سازی بنويسيم(البته از اين کلاس ها زياد نوشته شده قبلاً) که به درد هممون هم بخوره...
اگه دوستان موافقن يه نظری بدن تا ايشالا شروع کنيم...
تو فکرتونم

سلام دوست عزیز ممنون میشم اگه در رابطه با الگوریتمای فشرده سازی مطلبی داری واسم به اشتراک بزاری آخه منم در همین رابطه پروژه دارم