Sourena's personal page


روش کدينگ ( lempel-ziv-storer-szymanski)

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

توضيح الگوريتم :

فرض کنيد ما در حال فشرده کردن متنی هستيم که ميدونيم توش از عبارت های تکراری زياد استفاده شده و مثلاً داريم :

"My name is Sourena , What is your name? my name is sourena too!!!"

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

"My name is sourena , what (18,4) your (31,5) ? my (40,17) too !!!!"

خوب اين عدد ها بين اين عبارت ها يعنی چی؟؟ الان توضيح ميدم.اول دقت بکنيد که متن ما به مراتب کوتاه تر شده پس اين رو که قبول داريم.عدد اولی ميگه که 18 کاراکتر برو به عقب و 4 تا کاراکتر بردار يعنی ما ميآيم کلمه is و 2 تا کاراکتر فاصله 2 طرف اون رو اينجوری آدرس دهی ميکنيم. پرانتز دومی ميگه 31 خونه برو ا عقب و 5 تا حرف بردار و اينجا بگزار يعنی "name " رو بيا از اونجا بزار اينجا. و پرانتز سوم هم ميگه 40 تا خونه برو عقب و 17 تا کاراکتر بردار و اينجا جا کن!!!

خوب همينطور که ميبينيد ما اينجا 27 تا کاراکتر از جملمون کم شد که خوب البته در عوض چند تا عدد به اون اضافه شد.حالا فقط يک مسئله ميمونه اونم اينکه ما از کجا بفهميم که موقع دکد کردم کاراکتری که داريم دکد ميکنيم يه عدد به صورت آدرس و طول هستش يا يک byte معمولی از متن هستش که کد نشده؟؟؟؟؟
ما ميآيم به اين صورت عمل ميکنيم که يک فلگ 1 بيتی برامون مشخص کننده اين هستش که داده بعدی کد شده يا بصورت معمولی فرستاده شده. حالا ميرسيم به قسمت آدرس و طول خوب اين قسمت يکمی اختياری هستش و بر اساس مقادير مختلفی که شما برای هرکدوم از اينا(آدرس و طول) انتخاب ميکنيد،ميزان فشرده سازی فرق ميکنه. مثلاً من 12 بيت به آدرس اختصاص ميدم و 4 بيت به طول . اينجوری ميتونم به 4096 کاراکتر قبلی دسترسی داشته باشم و آدرس دهی کنم ضمن اينکه هر آدرس دهی هم حد اکثر ميتونه دارای طول 16 باشه که خوب نسبتا خوبه ضمن اينکه مجموع طول و آدرس رو هم ميشه 16 بيت که ميشه 2 byte.حالا اگر طول و آدرس ما 2 byte هستش پس ما عبارت هايی رو آدرس دهی ميکنيم که کمترين طول تطبيق اونها برابر 2 باشه. موقع دکد کردن يک بيت اول ميخونيم اگه اون بيت 0 بود يعنی byte بعدی يک کاراکتر هستش و اگه اون بيت 1 بود يعنی 12 بيت بعدی آدرس و 4 بيت بعد از اون هم طول هستش که ما به اون آدرس رجوع ميکنيم و به اندازه طول کاراکتر بر ميداريم و جاگزاری ميکنيم.

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

فهرست

صفحه اصلی

(Compression) فشرده سازی

Huffman Coding
Arithmetic Coding
Delta Coding
Frequency Substitution
LZSS Coding
LZW Coding
Rice (Golomb) Coding
Run Length Encoding
Prediction by partial matching
Dynamic Markov Compression
bitio Library
Burrows-Wheeler Transform

مقالات آموزشی

free html visitor counters














Designed By S.M
Last Update : 6 Feb 2012