با سلام خدمت دوستان
اگر ممکنه بگین چندتا الگوریتم فشرده سازی داریم
بعدش روش کاراشون چطوره
من چند نمونه رو میشناسم ولی کارکردشونو نمیدونم
مثل
rithmetic coding
Huffman Coding
Run-Length
اگه ممکنه توضیحاتی در موردشون بدین حتی اگه روش های دیگری رو بگین تا بدونیم جریان چیه
باتشکر
A ئه rithmetic افتاده، Arithmetic یا فشرده سازی حسابی. فقط یکی دو روش خاص هم نیست، فشرده سازی
Arithmetic یک مجموعه روش های نسبتا مشابهه، البته بقیه روش ها غیر حسابی نیستند اما چون در این روش ها
خیلی روی نسبت ها و اعداد اعشاری تکیه می شه بهشون روش حسابی می گویند. کلا اساس فشرده سازی
حسابی اینه که داده ورودی رو بصورت یک عدد اعشاری بین 0 الی 1 در بیاوریم و سپس با حداقل تعداد بیت لازم
برای ذخیره کردن همچنین عدد اعشاری ای ذخیره اش کنیم.
داده ورودی فرضی :
فرض کنید که یک داده ای داریم مشابه 1101110111201111 و می خواهیم تا حد امکان فشرده اش کنیم.
این داده 16 رقمه، اگر بخواهیم در بد ترین شیوه هر رقم رو در یک بایت ذخیره کنیم به 16 بایت فضا نیاز داریم،
یا به عبارتی دیگر 16 * 8 بیت، یعنی 128 بیت.
تلاش اولیه برای کاهش تعداد بیت برای هر رقم :
داخل این ارقام عدد 2 هم هست، پس یک عدد باینری فقط 0 یا 1 نیست، پس نمی توانیم برای هر رقم یک بیت
فضا در نظر بگیریم اما می توانیم برای هر رقم دو بیت (جفت بیت) در نظر بگیریم :
جفت بیت 00 برای رقم 0
جفت بیت 01 برای رقم 1
جفت بیت 10 برای رقم 2
جفت بیت 11 هم بی استفاده می ماند چون رقم 3 در ورودی وجود ندارد.
این داده ورودی 16 رقمی ما با استفاده از جفت بیت برای هر رقم جمعا 16 * 2 بیت فضا لازم دارد، یعنی 32 بیت.
که طبیعتا از 128 بیت قبلی خیلی بهتر است اما هنوز بخوبی فشرده شده نیست، چون آن جفت بیت 11 را بی استفاده
هدر داده ایم.
فشرده سازی حسابی :
در روش فشرده سازی حسابی ما ورودی را بصورت یک عدد کسری بین 0 الی 1 می نویسیم :
و سپس آنرا به یک عدد اعشاری دیگر تبدیل می کنیم، طوری که برای ذخیره کردنش تعداد بیت کمتری نیاز باشد،
فرضا اگر ارقام رو دو تا دو تا تفکیک کنیم خواهیم داشت :
کد:
0. 11 01 11 01 11 20 11 11
در این جفت های تفکیک شده هیچ حالت 10 ای وجود ندارد، همه حالت ها یا 00 هستند یا 11 و یا 01
می توانیم آن 20 داخل ورودی را با 10 جایگزین کنیم، این جایگزینی این فایده را دارد که هیچ 2 ای در ارقام نمی ماند و
برای ذخیره کردن هر رقم یک بیت کفایت خواهد کرد :
کد:
0. 11 01 11 01 11 10 11 11
برای ذخیره کردن 16 رقم بالا فقط به 16 * 1 بیت نیاز داریم، نصف حالت قبلی که هر رقم دو بیت فضا نیاز داشت.
متاسفانه اغلب روش های فشرده سازی حسابی تحت امتیاز IBM اند و به همین دلیل استفاده عمومی ندارند
اطلاعات کمتری هم در موردشون پیدا میشه.
فشرده سازی هافمن :
یک نگاه مجدد به تلاش اولیه برای کاهش تعداد بیت بیاندازید، ما برای هر رقم دو بیت در نظر گرفته بودیم،
چه رقم 1 که 12 بار تکرار شده بود و چه رقم 2 ای که فقط یک بار تکرار شده بود، همه شان دو بیتی بودند.
نکته کلیدی فشرده سازی هافمن دقیقا در همین است، هافمن برای هر رقم تعداد بیت متغیری در نظر می گیرد.
در فشرده سازی هافمن داده ورودی رو دست کاری نمی کنیم، اما بجای اینکه برای هر رقم ورودی یک تعداد بیت
ثابت در نظر بگیریم آمار تعداد تکرار هر رقم رو در ورودی رو مبنا قرار می دهیم، اگر تعداد تکرار یک رقم در ورودی
زیاد باشه برایش تعداد بیت کمتر و اگر تعداد تکرارش کم باشه طول بیت بیشتر در نظر می گیریم :
دو بیت 00 برای رقم 0
یک بیت 1 برای رقم 1
دو بیت 01 برای رقم 2
در نتیجه برای ذخیره کردن آن 16 رقم به 20 بیت فضا نیاز داریم (12 رقم 1 داریم و 3 رقم 0 و یک رقم 2 )
که از حالت غیر فشرده بهتر است، اما بخوبی فشرده سازی حسابی نیست. فشرده سازی هافمن بسیار
پر کاربرد است و نرم افزار ها و سخت افزار های زیادی ازش استفاده می کنند.
فشرده سازی Run-Length Encoding
در روش فشرده سازی RLE ما کاری به تعداد تکرار رقم در کل ورودی نداریم، فقط ارقامی که پشت سر هم
تکرار شده اند را خلاصه تر ثبت می کنیم، مثلا جایی که 6 رقم 111111 وجود دارند بجای 6 بار ذخیره کردن رقم 1
یک عدد 6 (تکرار رقم) و یکبار خود رقم (رقم 1) را ذخیره می کنیم.
این شیوه خیلی ابتدایی و در اغلب موارد ناکارآمد است، مخصوصا اگر داده ها هر کدام فقط یکبار تکرار شوند
بجای کاهش حجم ورودی حجم آن را بیشتر می کنیم، اما در برخی موارد که داده ها خیلی تکراری اند
مناسب است.
مثلا داده ورودی زیر را در نظر بگیرید :
داده ورودی بالا بصورت RLE چنین ثبت خواهد شد :
