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

[soorena]

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

[soorena]

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

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

QQQQQQQQQQWRTTYYYUOOOOPPPPPPPPKKKKKKKKKKKKKKKKKKKK

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

QQ8WRTT0YY1UOO2PP6KK18

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

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

[soorena]

هافمن کدينگ (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 هستش که حالا بعداً در موردش حرف ميزنيم.

[soorena]

Burrows-Wheeler Transform
خوب اين صفحه رو هم ميخوايم اختصاص بديم به تبديل Burrows-Wheeler که خوب همينطور که ميدونيد اين ها (Burrows و Wheeler) اسم های افرادی هستن که اين تبديل رو ارائه دادن. خوب من به زبون خيلی ساده اينجا براتون توضيح ميدم که چجوری اين تبديل کار ميکنه و بعد معکوسش رو ديگه به عهده خودتون ميزارم تا انجام بدين اگر چه که فکر نکنم کار سختی باشه.
توضيح مختصری در مورد الگوريتم

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

يکی از تأثيراتی که تبديل BWT روی داده ها داره اينه که تعداد run های طولانی تری رو توليد ميکنه. که خوب حتماً ميدونيد run چی هستش ديگه؟ اگه نميدونيد بريد قسمت Run Length Encoding رو بخونيد ميفهميد چی ميگم.حالا در ادامه يه مثال ميزنم که بيشتر قضيه جا بيفته.
مثال
فرض کنيم متن زير رو ميخوايم کد کنيم :

S= "this is a test."

خوب حالا شروع ميکنيم به چرخوندن متن تا تمام حالت های زير بوجود بياد:

S0="this is a test."
S1=".this is a test"
S2="t.this is a tes"
S3="st.this is a te"
S4="est.this is a t"
S5="test.this is a "
S6=" test.this is a"
S7="a test.this is "
S8=" a test.this is"
S9="s a test.this i"
S10="is a test.this "
S11=" is a test.this"
S12="s is a test.thi"
S13="is is a test.th"
S14="his is a test.t"
.

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

S8= " a test.this is"
S11= " is a test.this"
S6= " test.this is a"
S1= ".this is a test"
S7= "a test.this is "
S4= "est.this is a t"
S14= "his is a test.t"
S10= "is a test.this "
S13= "is is a test.th"
S9= "s a test.this i"
S12= "s is a test.thi"
S3= "st.this is a te"
S2= "t.this is a tes"
S5= "test.this is a "
S0= "this is a test."

خوب حالا اگه حرف آخر هر کدوم از اين s0 تا s14 رو بگيريم چی داريم؟

L="ssat tt hiies ." and I=14

همينطور که ميبينيد اين L و I که از اين مراحل بالا بدست مياد ،تبديل شده همون جمله اصلی هستش و تازه يه عدد هم بهش اضافه شده ولی ميبينيم که کاراکتر های تکراری کنار هم ظاهر شدن که اين برای بعضی روش های کدينگ خيلی مفيد هستش.

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

[skyzare]

با سلام .....

ممنون از مطالبتون .....

یه سوال این که الان مثل توی روش run برای کاراکترهای فاصله هم چیزی در نظر گرفته میشه ؟؟ اخا الان این L رو که به دست اورید بخواید به صورت run بنویسید کاراکتر space یا همون فاصله هم داخلش هست .... چه جوری می نویسندش ؟؟

چجوری اين تبديل کار ميکنه و بعد معکوسش رو ديگه به عهده خودتون ميزارم

خوب چه جوری !! حداقل یه راهنمایی !!! من اصلا کامپیوتری نیستم !!! یعنی با این L وI میتونیم به جمله اصلی برسیم ؟

نکته جالبی که بايد مد نظرتون باشه اينه که فقط با استفاده از L و I ميشه به طور منحصر به فرد به S رسيد

ببخشید منظورتون از این جمله چیه ؟؟ یعنی هر S رو به دست بیاریم ؟؟

[us1234]

دوستان این جواب نیست ولی از اعضا این سایت کسی کد هافمن را با سی شارپ نوشته من لازم دارم . توی لینک زیر با 20 زبان نوشته ولی با این سی شارپ که من عاشقشم نیست !!!!
http://rosettacode.org/wiki/Huffman_coding

[soorena]

سلام
اول اينکه روش bwt يک تبديل هستش برای فشرده سازی بهتر...خودش يه روش فشرده سازی نيست.
دوم اينکه مهم نيست کاراکتر چی باشه چه فاصله چه a چه d چه هر چی.چيزی که مهمه اينه که به هر حال يه کاراکتر هستش يعنی تو بازه 0 تا 255 هستش.
روش بازسازی خيلی سادست شما وقتی s رو داريد يعنی حروف آخر تمام 15 جمله رو داريد خوب حروف اول رو هم که داريد چون به ترتيب الفباست پس ديگه فقط کافيه که جملات رو شيفت بديد تا به جواب برسيد.

[soorena]

من کد رو با c نوشتم اگه بخوای ميتونم برات بفرستم ولی با #c ندارم..
به اينا يه نگاهی بنداز
http://geekswithblogs.net/madvisualb.../13/75126.aspx
http://www.enusbaum.com/blog/2009/05...-routine-in-c/

[soorena]

بروز رسانی الگوريتم جديد (frequency substitution)
http://www.maroofi.persiangig.com/freq/freq.html

[soorena]

http://maroofi.persiangig.com/lzss/lzss.html
بروز رسانی( الگوريتم lzss)