روش های رمزگذاری فشرده سازی با روش رمزگذاری سری: الگوریتم RLE

طبقه بندی اساسی الگوریتم های فشرده سازی برگشت پذیر

بسیار متفاوت هستند روش های عملیفشرده سازی بدون از دست دادن اطلاعات، که، به عنوان یک قاعده، کارایی متفاوتی دارند انواع متفاوتداده ها و حجم های مختلف با این حال، این روش ها بر اساس سه طرح اصلی فشرده سازی کلاسیک هستند:

کدگذاری سری دنباله ای (RLE);

روش های فشرده سازی آماری؛

روش های فشرده سازی دیکشنری (اکتشافی).

فشرده سازی با روش رمزگذاری سری: الگوریتم RLE

شناخته شده ترین روش ساده و الگوریتم فشرده سازی برگشت پذیر، رمزگذاری طول اجرا (RLE) است. ماهیت روش های این رویکرد جایگزینی زنجیره ها یا سری از بایت های تکرار شونده یا توالی آنها با یک بایت رمزگذاری و یک شمارنده برای تعداد تکرارهای آنها است. مشکل همه روش‌های مشابه تعیین روشی است که در آن الگوریتم فشرده‌سازی می‌تواند سری‌های رمزگذاری‌شده را از دیگر توالی‌های بایت رمزگذاری نشده در جریان بایت حاصل تشخیص دهد. راه حل مشکل معمولاً با قرار دادن برچسب ها در ابتدای زنجیره های کدگذاری شده به دست می آید. چنین علائمی ممکن است، به عنوان مثال، مقادیر بیت مشخصه در اولین بایت اجرای کدگذاری شده، مقادیر اولین بایت اجرای کدگذاری شده و موارد مشابه باشد. این روش ها معمولا برای فشرده سازی بیت مپ بسیار کارآمد هستند. تصاویر گرافیکی(BMP، PCX، TIF، GIF)، زیرا دومی شامل چند سری طولانی از دنباله های تکراری بایت است. نقطه ضعف روش RLE نسبت فشرده سازی نسبتا کم یا هزینه رمزگذاری فایل ها با تعداد سری کم و حتی بدتر از آن، با تعداد کمی بایت های تکراری در سری است.

الگوریتم RLE مبتنی بر ایده شناسایی توالی داده های مکرر و جایگزینی آنها با ساختار ساده تری است که کد داده و ضریب تکرار را مشخص می کند. به عنوان مثال، اجازه دهید چنین دنباله ای از داده ها داده شود که در معرض فشرده سازی هستند: 1 1 1 1 2 2 3 4 4 4 . در الگوریتم RLE پیشنهاد شده است که با ساختار زیر جایگزین شود: 1 4 2 2 3 1 4 3 ، که در آن عدد اول هر جفت عدد کد داده و عدد دوم ضریب تکرار است. اگر 1 بایت برای ذخیره هر عنصر داده از دنباله ورودی اختصاص داده شود، کل دنباله 10 بایت حافظه اشغال می کند، در حالی که دنباله خروجی (نسخه فشرده) 8 بایت حافظه را اشغال می کند. واضح است که الگوریتم RLE خواهد داد بهترین اثرفشرده سازی در طول بیشتری از یک توالی داده تکراری. در مورد مثال بالا، اگر دنباله ورودی به این صورت باشد: 1 1 1 1 1 1 3 4 4 4، آنگاه نسبت تراکم 60 درصد خواهد بود. در این راستا، کارایی بیشتر الگوریتم RLE با فشرده سازی داده های گرافیکی (به ویژه برای تصاویر تک رنگ) حاصل می شود.

الگوریتم های اکتشافی (فرهنگ لغت).فشرده سازی (LZ, LZW) به دنبال خطوطی در فایل بگردید که تکرار شده اند و فرهنگ لغت عباراتی را بسازید که قبلاً با آنها روبرو شده اند. به طور معمول، چنین الگوریتم‌هایی دارای تعدادی پارامتر خاص (اندازه بافر، حداکثر طول عبارت و غیره) هستند که انتخاب آنها به تجربه نویسنده اثر بستگی دارد و این پارامترها به گونه‌ای انتخاب می‌شوند که به نسبت بهینه زمان اجرای الگوریتم، نسبت فشرده سازی و لیست فایل ها که به خوبی فشرده می شوند.

الگوریتم های آماری(هافمن، شانون فانو، حساب) الگوریتم های آماری از یک مدل داده های آماری استفاده می کنند و کیفیت فشرده سازی اطلاعات به طور مستقیم به خوب بودن این مدل بستگی دارد. حسابداری ویژگی های آماریداده در ساده ترین حالت به معنای استفاده از کدهای غیر یکنواخت برای رمزگذاری است - کاراکترهای متداول در کدهای کوتاه و به ندرت در کدهای طولانی رمزگذاری می شوند. یعنی چنین الگوریتم هایی نیاز به دانستن احتمالات ظاهر شدن کاراکترها در تصویر دارند که در حالت ساده می توان با فراوانی وقوع کاراکترها در داده های ورودی تخمین زد. به عنوان یک قاعده، این احتمالات ناشناخته هستند. هدف از رمزگذاری تبدیل جریان ورودی به یک جریان بیت با حداقل طول است که با کاهش آنتروپی (آشوب) جریان ورودی با در نظر گرفتن فرکانس های نماد به دست می آید.

طول کد نشان دهنده کاراکترهای الفبای جریان باید متناسب با مقدار اطلاعات جریان ورودی باشد و طول کاراکترهای جریان در بیت ممکن است مضربی از 8 یا حتی متغیر نباشد. اگر توزیع احتمال فراوانی‌های وقوع کاراکترها از الفبای جریان ورودی مشخص باشد، می‌توان یک مدل کدگذاری بهینه ساخت. اما به دلیل وجود تعداد زیاد فرمت های مختلففایل ها، کار بسیار پیچیده تر است، زیرا. توزیع فرکانس نماد داده از قبل مشخص نیست. در این مورد از دو رویکرد استفاده می شود.

اولینشامل مشاهده جریان ورودی و ایجاد یک رمزگذاری بر اساس آمارهای جمع آوری شده است (این به دو گذر از فایل نیاز دارد - یکی برای مشاهده و جمع آوری اطلاعات آماریدوم - برای کدگذاری، که تا حدودی دامنه چنین الگوریتم هایی را محدود می کند، زیرا، بنابراین، امکان کدگذاری تک گذر "در حال پرواز"، مورد استفاده در سیستم های مخابراتی، جایی که مقدار داده ها گاهی اوقات مشخص نیست، و آنها را محدود می کند. ارسال مجدد یا تجزیه ممکن است زمان زیادی طول بکشد). در چنین حالتی، طرح آنتروپی کدگذاری مورد استفاده در جریان خروجی نوشته می شود. این روشبه کدگذاری هافمن ایستا معروف است. جدول نمادها به همراه فایل فشرده منتقل می شود. چنین الگوریتم‌هایی اکثر فایل‌ها را به خوبی فشرده می‌کنند، اما ارسال اضافی جدول فرکانس نماد و همچنین نیاز به دو پاس از فایل منبع برای جمع‌آوری آمار و فشرده‌سازی ضروری است.

روش دوم- روش کدگذاری تطبیقی اصل آن تغییر طرح رمزگذاری بسته به ماهیت تغییرات در جریان ورودی است. تطبیقی ​​- شروع به کار با یک جدول اولیه ثابت فرکانس کاراکترها (معمولاً همه کاراکترها در ابتدا به یک اندازه محتمل هستند) و در روند کار این جدول بسته به کاراکترهایی که در فایل رخ می دهد تغییر می کند. مزایا: الگوریتم یک گذر، عدم نیاز به انتقال جدول فرکانس نمادها، فشرده سازی کلاس گسترده ای از فایل ها به طور کاملا موثر. این رویکرد دارای یک الگوریتم یک گذر است و نیازی به ذخیره صریح اطلاعات در مورد رمزگذاری مورد استفاده ندارد. کدگذاری تطبیقی ​​می تواند بدهد درجه بالاترفشرده سازی، در مقایسه با استاتیک، زیرا تغییرات در فرکانس های جریان ورودی به طور کامل در نظر گرفته می شود. این تکنیک به کدگذاری هافمن پویا معروف است.

با در نظر گرفتن این موضوع، الگوریتم های آماری را می توان به سه دسته تقسیم کرد:

1. غیر تطبیقی ​​- از احتمالات نمادهای ثابت و از پیش تعیین شده استفاده کنید. جدول احتمال نماد با فایل منتقل نمی شود زیرا از قبل مشخص شده است. نقطه ضعف: منطقه باریک استفاده برای یک جدول فرکانس خاص که نسبت فشرده سازی قابل قبولی برای آن به دست می آید.

2. نیمه تطبیقی ​​- برای هر فایل جدولی از فرکانس کاراکترها ساخته شده و فایل بر اساس آن فشرده می شود. جدول نمادها به همراه فایل فشرده منتقل می شود. چنین الگوریتم‌هایی اکثر فایل‌ها را به خوبی فشرده می‌کنند، اما ارسال اضافی جدول فرکانس نماد و همچنین نیاز به دو پاس از فایل منبع برای جمع‌آوری آمار و فشرده‌سازی ضروری است.

3. تطبیقی ​​- شروع به کار با یک جدول اولیه ثابت فرکانس کاراکترها (معمولاً همه کاراکترها در ابتدا به یک اندازه محتمل هستند) و در روند کار این جدول بسته به کاراکترهایی که در فایل رخ می دهد تغییر می کند. مزایا: الگوریتم یک گذر، عدم نیاز به انتقال جدول فرکانس نمادها، فشرده سازی کلاس گسترده ای از فایل ها به طور کاملا موثر.

الگوریتم هافمن مبتنی بر ایده رمزگذاری توسط گروه های بیتی است. ابتدا انجام شد تجزیه و تحلیل فرکانستوالی داده های ورودی، یعنی فرکانس وقوع هر کاراکتر در آن تنظیم می شود. پس از آن، کاراکترها با کاهش دفعات وقوع مرتب می شوند.

ایده اصلی این است که هر چه یک کاراکتر رایج تر باشد، بیت های کمتری را رمزگذاری می کند. نتیجه رمزگذاری به فرهنگ لغت مورد نیاز برای رمزگشایی وارد می شود. یک مثال ساده را در نظر بگیرید که عملکرد الگوریتم هافمن را نشان می دهد.

در کدنویسی هافمن ایستا، کاراکترهای ورودی (رشته‌هایی از بیت‌های با طول‌های مختلف) به رشته‌های بیتی اختصاص داده می‌شوند، همچنین با طول متغیر - کدهای آنها. طول کد هر کاراکتر متناسب با لگاریتم باینری فرکانس آن گرفته می شود که با علامت مخالف گرفته می شود. و مجموع همه کاراکترهای مختلف که با آنها روبرو می‌شویم، الفبای جریان است. این رمزگذاری پیشوند است، که رمزگشایی آن را در جریان حاصل آسان می کند، زیرا با رمزگذاری پیشوند، کد هر کاراکتری پیشوند کد هیچ کاراکتر دیگری نیست - الفبای منحصر به فرد است.

نسخه اول الگوریتم

پیاده سازی این الگوریتم بسیار آسان است. کدگذاری گروهی - از انگلیسی Run Length Encoding (RLE) - یکی از قدیمی ترین و ساده ترین الگوریتم های آرشیو گرافیکی است. تصویر موجود در آن (مانند چندین الگوریتم شرح داده شده در زیر) به زنجیره ای از بایت ها در امتداد خطوط شطرنجی کشیده می شود. خود فشرده سازی در RLE رخ می دهد با توجه به این واقعیت که در تصویر اصلی زنجیره ای از بایت های یکسان وجود دارد. آنها را با جفت جایگزین کنید<счетчик повторений, значение>افزونگی داده ها را کاهش می دهد.

الگوریتم رفع فشاربه نظر می رسد این است:

مقداردهی اولیه(...)؛
انجام دادن(
if(s counter(byte)) (
شمارنده = Low6bits(byte)+1;
برای (i=1 برای مقابله)
د
}
دیگر(
DecompressedFile.WriteByte(بایت)
) while(ImageFile.EOF());

در این الگوریتم، علامت شمارنده (counter) همان هایی است که در دو بیت بالای فایل خوانده شده قرار دارند:

بر این اساس، 6 بیت باقی مانده در شمارنده صرف می شود که می تواند مقادیری از 1 تا 64 داشته باشد. رشته ای از 64 بایت تکرار شده را به دو بایت تبدیل می کنیم، یعنی. 32 بار فشرده کنید.

ورزش:یک الگوریتم بسازید فشرده سازیبرای اولین نسخه از الگوریتم RLE.

سوال برای خودکنترلی:دو یا سه مثال از تصاویر بد برای الگوریتم RLE پیشنهاد کنید. دلیل حجم فایل فشرده را توضیح دهید بیش از اندازهمنبع فایل.

نسخه دوم الگوریتم

نوع دوم این الگوریتم دارای حداکثر نسبت آرشیو بیشتر است و حجم فایل منبع را کمتر افزایش می دهد.

الگوریتم رفع فشار برای آن به شکل زیر است:

مقداردهی اولیه(...)؛
انجام دادن(
byte = ImageFile.ReadNextByte();
شمارنده = Low7bits(byte)+1;
if (اگر تکرار علامت (بایت)) (
value = ImageFile.ReadNextByte();
برای (i=1 برای مقابله)
CompressedFile.WriteByte(مقدار)
}
دیگر(
برای (i=1 برای مقابله)(
value = ImageFile.ReadNextByte();
CompressedFile.WriteByte(مقدار)
}
CompressedFile.WriteByte (بایت)
) while(ImageFile.EOF());

علامت تکرار در این الگوریتم واحدی در مرتبه بالای بایت مربوطه است:

همانطور که می توان به راحتی محاسبه کرد، بهترین مورداین الگوریتم فایل را 64 بار فشرده می کند (به جای 32 بار مانند نسخه قبلی)، در بدترین حالت 1/128 افزایش می یابد. نسبت تراکم متوسط این الگوریتمدر سطح شاخص های نوع اول قرار دارند.

ورزش:یک الگوریتم فشرده سازی برای نسخه دوم الگوریتم RLE بنویسید.

ویژگی های الگوریتم RLE:

نسبت تراکم:گزینه اول: 32، 2، 0.5. گزینه دوم: 64، 3، 128/129.(بهترین، متوسط، بدترین شانس)

کلاس تصویر: الگوریتم بر روی تصاویر با تعداد کمی رنگ متمرکز است: گرافیک تجاری و علمی.

تقارن: تقریباً یک.

ویژگی های مشخصه: تنها جنبه های مثبت الگوریتم را شاید بتوان تنها به این واقعیت نسبت داد که نیازی به آن ندارد. حافظه اضافیهنگام بایگانی و باز کردن زیپ، و همچنین به سرعت کار می کند. ویژگی جالبکدگذاری گروهی به این صورت است که درجه آرشیو برای برخی از تصاویر را می توان به میزان قابل توجهی با تغییر ترتیب رنگ ها در پالت تصویر افزایش داد.

نام الگوریتم با حروف اول نام توسعه دهندگان آن - Lempel، Ziv و Welch داده شد. فشرده سازی در آن، برخلاف RLE، قبلاً به دلیل زنجیره های یکسان بایت انجام می شود.

الگوریتم LZ

خانواده نسبتاً بزرگی از الگوریتم‌های LZ مانند وجود دارد که برای مثال در روش جستجوی زنجیره‌های تکراری متفاوت هستند. یکی از کافی گزینه های سادهاین الگوریتم، برای مثال، فرض می‌کند که جریان ورودی شامل یک جفت است<счетчик, смещение относительно текущей позиции>، یا فقط<счетчик>بایت های «پرش شده» و بایت ها خودشان ارزش دارند (مانند نسخه دوم الگوریتم RLE). هنگام باز کردن زیپ برای یک زوج<счетчик, смещение>کپی شده است<счетчик>بایت ها از آرایه خروجی ناشی از زیپ کردن به<смещение>بایت قبل و<счетчик>(یعنی تعدادی برابر با شمارنده) مقادیر بایت های "پرش شده" به سادگی در آرایه خروجی از جریان ورودی کپی می شوند. این الگوریتم از نظر زمانی نامتقارن است، زیرا به جستجوی کامل بافر هنگام جستجوی زیررشته‌های یکسان نیاز دارد. در نتیجه، به دلیل افزایش شدید زمان فشرده سازی، تنظیم یک بافر بزرگ برای ما دشوار است. با این حال، به طور بالقوه ساخت یک الگوریتم که در آن<счетчик>و در<смещение>2 بایت تخصیص داده می شود (بیت بالای بایت بالای شمارنده نشانه تکرار رشته / کپی جریان است)، به ما این فرصت را می دهد که همه زیر رشته های تکراری را تا 32 کیلوبایت در یک بافر 64 کیلوبایتی فشرده کنیم.

در این صورت افزایش حجم فایل را در بدترین حالت به میزان 32770/32768 دریافت خواهیم کرد (در دو بایت نوشته شده است که 2 15 بایت بعدی باید در جریان خروجی بازنویسی شود) که اصلا بد نیست. حداکثر نسبت تراکم در حد 8192 بار خواهد بود. در حد، از آنجایی که ما حداکثر فشرده سازی را با تبدیل یک بافر 32 کیلوبایتی به 4 بایت به دست می آوریم، و بلافاصله بافری با این اندازه جمع نمی کنیم. با این حال، حداقل زیررشته ای که فشرده سازی آن برای ما مفید است، معمولاً باید حداقل از 5 بایت تشکیل شده باشد که مقدار کم این الگوریتم را تعیین می کند. از مزایای LZ می توان به سادگی بسیار زیاد الگوریتم رفع فشار اشاره کرد.

ورزش:نوع دیگری از الگوریتم LZ را پیشنهاد کنید که در آن جفت<счетчик, смещение>3 بایت تخصیص داده می شود و ویژگی های اصلی الگوریتم خود را محاسبه کنید.

نوع الگوریتم در نظر گرفته شده در زیر از یک درخت برای نمایش و ذخیره زنجیره ها استفاده می کند. بدیهی است که این یک محدودیت نسبتاً قوی در نوع زنجیره ها است و همه زیر زنجیره های یکسان در تصویر ما در هنگام فشرده سازی استفاده نمی شوند. با این حال، در الگوریتم پیشنهادی، فشرده سازی حتی زنجیرهای متشکل از 2 بایت سودمند است.

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

تابع InitTable() جدول را پاک می کند و تمام ردیف های طولی را در آن قرار می دهد.

InitTable();
CompressedFile.WriteCode(ClearCode);
CurStr=رشته خالی;
while(not ImageFile.EOF())( //تا پایان فایل
C=ImageFile.ReadNextByte();
if (CurStr+C در جدول است)
CurStr=CurStr+C;//یک کاراکتر را به یک رشته بچسبانید
دیگر(
code=CodeForString(CurStr);//code-not a byte!
AddStringToTable (CurStr+C);
CurStr=C; // رشته تک کاراکتری
}
}
code=CodeForString(CurStr);
CompressedFile.WriteCode(کد)؛
CompressedFile.WriteCode(CodeEndOfInformation);

همانطور که در بالا ذکر شد، تابع InitTable() جدول رشته را مقداردهی اولیه می کند تا شامل تمام رشته های تک کاراکتری ممکن باشد. به عنوان مثال، اگر داده های بایت را فشرده کنیم، 256 ردیف در جدول وجود خواهد داشت ("0"، "1"، ...، "255"). مقادیر 256 و 257 برای کد پاک (ClearCode) و کد برای پایان اطلاعات (CodeEndOfInformation) رزرو شده است. در نسخه در نظر گرفته شده الگوریتم، از یک کد 12 بیتی استفاده شده است و بر این اساس مقادیر از 258 تا 4095 برای کدهای خطوط باقی می ماند. خطوط اضافه شده به ترتیب در جدول نوشته می شوند و فهرست ردیف در جدول به کد آن تبدیل می شود.

تابع ReadNextByte() یک کاراکتر از یک فایل را می خواند. تابع WriteCode() یک کد (به اندازه یک بایت) در فایل خروجی می نویسد. تابع AddStringToTable() اضافه می کند خط جدیدبه جدول، نسبت دادن یک کد به آن. علاوه بر این، این تابع وضعیت سرریز جدول را کنترل می کند. در این حالت، کد سطر پیدا شده قبلی و کد پاکسازی در جریان نوشته می‌شود و پس از آن جدول توسط تابع InitTable() پاک می‌شود. تابع CodeForString() رشته ای را در جدول پیدا می کند و کد آن رشته را برمی گرداند.

مثال:

اجازه دهید دنباله 45، 55، 55، 151، 55، 55، 55 را فشرده کنیم. سپس، طبق الگوریتمی که در بالا توضیح داده شد، ابتدا کد پاکسازی را در جریان خروجی قرار می دهیم.<256>، سپس "45" را به رشته خالی اولیه اضافه کنید و بررسی کنید که آیا رشته "45" در جدول وجود دارد. از آنجایی که در هنگام مقداردهی اولیه، تمام خطوط یک کاراکتر را در جدول وارد کردیم، رشته "45" در جدول است. در مرحله بعد، کاراکتر بعدی 55 را از جریان ورودی می خوانیم و بررسی می کنیم که آیا رشته "45, 55" در جدول است. هنوز چنین ردیفی در جدول وجود ندارد. رشته "45, 55" را در جدول وارد می کنیم (با اولین کد رایگان 258) و کد را در جریان می نویسیم.<45>. به طور خلاصه می توانید آرشیو کردن را به این صورت تصور کنید:

• "45" - در جدول است.
• "45، 55" - شماره. به جدول اضافه کنید<258>"45، 55". در جریان:<45>;
• "55، 55" - شماره. به جدول:<259>"55، 55". در جریان:<55>;
• "55، 151" - شماره. به جدول:<260>"55، 151". در جریان:<55>;
• "151، 55" - شماره. به جدول:<261>"151، 55". در جریان:<151>;
• "55، 55" - در جدول است.
• "55، 55، 55" - شماره. به جدول: "55، 55، 55"<262>. در جریان:<259>;

ویژگی LZW این است که برای رفع فشرده سازی، ما نیازی به ذخیره کردن جدول رشته ها در یک فایل برای رفع فشرده سازی نداریم. الگوریتم به گونه ای ساخته شده است که می توانیم جدول رشته را تنها با استفاده از جریان کد بازیابی کنیم.

می دانیم که برای هر کد، باید یک خط به جدول اضافه کنیم که شامل خطی است که قبلاً در آنجا وجود دارد و کاراکتری که خط بعدی در جریان با آن شروع می شود.

الگوریتم رفع فشار که این عملیات را انجام می دهد به شرح زیر است:

code=File.ReadCode();
while(code != CodeEndOfInformation)(
if (کد = ClearCode) (
InitTable();
code=File.ReadCode();
if (کد = CodeEndOfInformation)
(تمام کار)؛
ImageFile.WriteString(StrFromTable(کد));
قدیمی_کد=کد;
}
دیگر(
if(InTable(کد)) (
ImageFile.WriteString(FromTable(کد));
AddStringToTable(StrFromTable(old_code)+
FirstChar(StrFromTable(کد)));
قدیمی_کد=کد;
}
دیگر(
OutString= StrFromTable(old_code)+
FirstChar(StrFromTable(old_code));
ImageFile.WriteString(OutString);
AddStringToTable (OutString);
قدیمی_کد=کد;
}
}
}

در اینجا تابع ReadCode() کد بعدی را از فایل از حالت فشرده می خواند. تابع InitTable() همان اقداماتی را انجام می دهد که در هنگام فشرده سازی، یعنی. جدول را پاک می کند و تمام خطوط یک کاراکتر را در آن قرار می دهد. تابع FirstChar() اولین کاراکتر یک رشته را به ما می دهد. تابع StrFromTable() یک ردیف از جدول را با کد برمی گرداند. تابع AddStringToTable() یک ردیف جدید به جدول اضافه می کند (با اختصاص دادن اولین کد رایگان به آن). تابع WriteString() یک رشته را در یک فایل می نویسد.

نکته 1. همانطور که می بینید، کدهای نوشته شده در جریان به تدریج در حال افزایش هستند. تا زمانی که کد 512 در جدول ظاهر شود، به عنوان مثال، برای اولین بار، همه کدها کمتر از 512 خواهند بود. علاوه بر این، در هنگام فشرده سازی و رفع فشرده سازی، هنگام پردازش همان نماد، کدهای موجود در جدول اضافه می شوند. "به طور همزمان" اتفاق می افتد. می توانیم از این ویژگی الگوریتم برای افزایش نسبت تراکم استفاده کنیم. تا زمانی که کاراکتر 512 به جدول اضافه شود، کدهای 9 بیتی را در جریان بیت خروجی می نویسیم و بلافاصله با اضافه کردن 512، کدهای 10 بیتی را می نویسیم. بر این اساس، دیکمپرسور نیز باید تمام کدهای جریان ورودی را به عنوان 9 بیتی بپذیرد تا زمانی که کد 512 به جدول اضافه شود، پس از آن همه کدهای ورودی را 10 بیتی درک می کند. هنگام اضافه کردن کدهای 1024 و 2048 به جدول همین کار را انجام می دهیم. این تکنیک به شما امکان می دهد نسبت فشرده سازی را حدود 15٪ افزایش دهید:

نکته 2. هنگام فشرده سازی یک تصویر، اطمینان از سرعت جستجوی ردیف ها در جدول برای ما مهم است. ما می توانیم از این واقعیت استفاده کنیم که هر زیر رشته بعدی یک کاراکتر طولانی تر از قبلی است، علاوه بر این، خط قبلی قبلاً توسط ما در جدول پیدا شده است. بنابراین، کافی است فهرستی از ارجاع‌ها به رشته‌هایی که با یک زیررشته مشخص شروع می‌شوند ایجاد کنیم و کل فرآیند جستجو در جدول به جستجو در رشته‌های موجود در لیست رشته قبلی خلاصه می‌شود. واضح است که چنین عملیاتی را می توان خیلی سریع انجام داد.

همچنین توجه داشته باشید که در واقعیت برای ما کافی است فقط یک زوج را در جدول ذخیره کنیم<код предыдущей подстроки, добавленный символ>. این اطلاعات برای کارکرد الگوریتم کاملاً کافی است. بنابراین یک آرایه از 0 تا 4095 با عناصر<код предыдущей подстроки; добавленный символ; список ссылок на строки, начинающиеся с этой строки>مشکل جستجو را حل می کند، هرچند بسیار کند.

در عمل، یک جدول هش برای ذخیره یک جدول استفاده می شود، به همان سرعتی که در مورد لیست ها وجود دارد، اما در حافظه فشرده تر است. جدول از 8192 (2 13) عنصر تشکیل شده است. هر عنصر شامل<код предыдущей подстроки; добавленный символ; код этой строки>. کلید جستجوی 20 بیتی با استفاده از دو عنصر اول ذخیره شده در جدول به عنوان یک عدد (کلید) تشکیل می شود. 12 بیت پایینی این عدد برای کد و 8 بیت بعدی برای مقدار نماد داده می شود.

در اینجا به عنوان یک تابع هش استفاده می شود:

Index(key)= ((key >> 12) ^ key) & 8191;

جایی که >> - شیفت بیتی به راست (کلید >> 12 - مقدار کاراکتر را دریافت می کنیم)، ^ - عملیات منطقیبیتی XOR و منطقی بیتی AND.

بنابراین، برای تعداد شمرده شده مقایسه، کد مورد نظر یا پیامی مبنی بر وجود چنین کدی در جدول دریافت می کنیم.

بیایید بهترین و بدترین نسبت فشرده سازی را برای این الگوریتم محاسبه کنیم. بدیهی است که بهترین ضریب برای زنجیره ای از بایت های یکسان با طول زیاد (یعنی برای یک تصویر 8 بیتی که همه نقاط آن برای قطعیت، رنگ 0 دارند) به دست می آید. در همان زمان، در ردیف 258 جدول، رشته "0، 0" را می نویسیم، در ردیف 259 - "0، 0، 0"، ... در ردیف 4095 - یک رشته 3839 (=4095-256) ) صفرها در این صورت، 3840 کد وارد جریان می‌شوند (بر اساس الگوریتم بررسی کنید!)، از جمله کد پاکسازی. بنابراین با محاسبه مجموع پیشرفت محاسباتی از 2 تا 3839 (یعنی طول زنجیره فشرده) و تقسیم آن بر 3840*12/8 (کدهای 12 بیتی روی جریان نوشته می شوند) بهترین نسبت فشرده سازی را بدست می آوریم. .

ورزش:مقدار دقیق بهترین نسبت تراکم را محاسبه کنید. یک کار دشوارتر: با در نظر گرفتن نکته 1، همان ضریب را محاسبه کنید.

ورزش:الگوریتمی برای تولید چنین زنجیره هایی بنویسید. سعی کنید فایل به دست آمده از این طریق را با آرشیوهای استاندارد (zip، arj، gz) فشرده کنید. اگر فشرده سازی دریافت کردید، الگوریتم تولید اشتباه نوشته شده است.

LZW پیاده سازی شده در فرمت های GIFو TIFF.

ویژگی های الگوریتم LZW:

نسبت تراکم: تقریباً 1000، 4، 5/7 (بهترین، متوسط، بدترین نسبت). فشرده سازی 1000 بار فقط در تصاویر تک رنگی که مضرب حدود 7 مگابایت هستند به دست می آید.

کلاس تصویر: LZW بر روی تصاویر 8 بیتی ساخته شده بر روی کامپیوتر تمرکز می کند. کمپرس به دلیل زنجیره های فرعی یکسان در جریان.

تقارن:تقریباً متقارن، مشروط به اجرای بهینه عملیات جستجوی ردیف در جدول.

مشخصات:موقعیتی که الگوریتم تصویر را بزرگ می کند بسیار نادر است. LZW جهانی است - انواع آن است که در بایگانی های معمولی استفاده می شود.

الگوریتم کلاسیک هافمن

یکی از الگوریتم های کلاسیک شناخته شده از دهه 60. فقط از فرکانس وقوع بایت های یکسان در تصویر استفاده می کند. کاراکترهایی را در جریان ورودی که اتفاق می‌افتد مطابقت می‌دهد بیشتربار، زنجیره ای از بیت ها با طول کمتر. و، برعکس، نادر - یک زنجیره با طول بیشتر. برای جمع آوری آمار، نیاز به دو عبور از تصویر است.

ابتدا چند تعاریف را معرفی می کنیم.

تعریف. بگذارید الفبای Y =( آ 1، ...، a r ) متشکل از تعداد متناهی حروف. دنباله متناهی از کاراکترهای Y

تماس خواهیم گرفت کلمهدر الفبای Y و عدد n - طول کلمه آ. طول یک کلمه به صورت نشان داده می شود l (A).

بگذارید الفبای W داده شود، W =( ب 1 ، ...، ب q ). از طریق بکلمه را در الفبای W و through نشان دهید اس (W)مجموعه تمام کلمات غیر خالی در الفبای W است.

اجازه دهید اس =S(Y) -مجموعه تمام کلمات غیر خالی در الفبای Y و اس"- برخی از زیرمجموعه های مجموعه اس. اجازه دهید همچنین نقشه برداری اف، که هر کلمه الف، الف؟ S(Y)، با کلمه مطابقت دارد

B=F(A)، B ? S(W) .

کلمه که درتماس خواهیم گرفت کد پیامالف، و گذار از کلمه آبه کد او - کد نویسی.

تعریف. مطابقت بین حروف الفبای Y و برخی از کلمات الفبای W را در نظر بگیرید:

آ 1 - ب 1 ,
آ 2 - ب 2 ,
. . .
آ r- ب r

این مکاتبات نامیده می شود طرحو با S نشان داده شده است. رمزگذاری را به صورت زیر تعریف می کند: هر کلمه از اس" (W)=اس (W)با کلمه ای به نام تطبیق داده می شود کد کلمهالف. کلمات ب 1 ... ب r تماس گرفت کدهای ابتدایی. این نوعکدگذاری نامیده می شود کدگذاری الفبایی

تعریف. بگذار کلمه که درفرم را دارد

B=B"B"

سپس کلمه ب"تماس گرفت شروع کنیدیا پیشوند کلمهب، الف ب" - پایان یک کلمهب- در این صورت کلمه خالی L و خود کلمه بابتدا و انتهای یک کلمه محسوب می شوند ب .

تعریف .طرح S دارای خاصیت پیشوند،اگر برای هر کداممنو j(1? من ، جی؟ ر، من؟ j) کلمه ب منپیشوند کلمه نیست ب ج .

قضیه 1.اگر طرح S دارای خاصیت پیشوند است، سپس رمزگذاری الفبایی یک به یک خواهد بود.

فرض کنید به ما الفبای Y =( آ 1 ,..., آ r} (r >1 ) و مجموعه ای از احتمالات پ 1 , . . . , پ r ظاهر نمادها آ 1 ,..., آ r. اجازه دهید، بیشتر، الفبای W داده شود، W =( ب 1 , ..., ب q} (q >1 ). سپس می توان یک سری کامل از طرح های S کدگذاری الفبایی را ساخت

یک 1 - ب 1 ,
. . .
آ r- ب r

داشتن خاصیت منحصر به فرد متقابل

برای هر مدار، می توانید طول متوسط ​​را وارد کنید ل چهارشنبه ، به عنوان انتظار ریاضی طول کد ابتدایی تعریف می شود:

- طول کلمات

طول لچهارشنبه نشان می دهد که در هنگام رمزگذاری با طرح S چند برابر طول متوسط ​​کلمه افزایش می یابد.

می توان نشان داد که ل چهارشنبه به حداقل خود می رسد ل * در برخی از S و به عنوان تعریف شده است

تعریف .کدهای تعریف شده توسط طرح S بال cf = ل * ، نامیده می شوند کدهایی با حداقل افزونگی، یا کدهای هافمن.

کدهایی با حداقل افزونگی، به طور متوسط، حداقل افزایش طول کلمات را با رمزگذاری مناسب ارائه می دهند.

در مورد ما، الفبای Y =( آ 1 ,..., آ r) نمادهای جریان ورودی و الفبای W =(0,1) را مشخص می کند. فقط از صفر و یک تشکیل شده است.

الگوریتم ساخت مدار S را می توان به صورت زیر نشان داد:

مرحله 1.همه حروف الفبای ورودی را به ترتیب احتمال نزولی مرتب می کنیم. شمارش تمام کلمات منطبق ب مناز الفبای W =(0,1) خالی هستند.

گام 2ترکیب دو شخصیت یک من r-1و یک من rکمترین احتمال پی r-1و پی rبه یک شخصیت شبه آ"{یک من r-1 a i r ) با احتمال پی r-1+پی r. 0 را به ابتدای کلمه B اضافه کنید من r-1(ب من r-1= 0B من r-1 ) و 1 تا ابتدای کلمه B من r(ب من r= 1B من r).

مرحله 3حذف از لیست کاراکترهای مرتب شده یک من r-1و یک من r، یک نماد شبه در آنجا قرار دهید آ"{یک من r-1 a i r ). ما مرحله 2 را انجام می دهیم و در صورت لزوم 1 یا صفر را برای همه کلمات اضافه می کنیم ب من، مربوط به نویسه های شبه، تا زمانی که 1 شبه کاراکتر در لیست باقی بماند.

مثال:فرض کنید 4 حرف در الفبا داریم Y =( آ 1 ,..., آ 4 } (r =4 ), پ 1 =0.5, پ 2 =0.24,پ 3 =0.15,پ 4 =0.11 سپس روند ساخت مدار را می توان به صورت زیر نشان داد:

با انجام اقدامات مربوط به مرحله 2، یک شبه کاراکتر با احتمال 0.26 بدست می آوریم (و 0 و 1 را به کلمات مربوطه اختصاص می دهیم). با تکرار این اقدامات برای لیست اصلاح شده، یک نماد شبه با احتمال 0.5 دریافت می کنیم. و در نهایت در مرحله آخر به احتمال کل 1 می رسیم.

برای بازیابی کلمات کد کننده، باید فلش ها را از کاراکترهای اولیه تا انتهای درخت باینری حاصل دنبال کنیم. بنابراین، برای یک نماد با یک احتمال پ 4، ما B 4 = 101، برای پ 3، B 3 = 100، برای پ 2 ما B 2 = 11، برای پ 1 ما B 1 را دریافت می کنیم =0. طرحواره به چه معناست: آ 1 - 0,
آ 2 - 11
آ 3 - 100
آ 4 - 101 این طرح یک کد پیشوندی است که یک کد هافمن است. شخصیتی که اغلب در جریان رخ می دهد آ 1 ما کوتاه ترین کلمه را 0 و کم ترین کلمه را رمزگذاری می کنیم آ 4 کلمه طولانی 101.

برای یک دنباله 100 کاراکتری که در آن شخصیت آ 1 50 بار ملاقات خواهد کرد، نماد آ 2 - 24 بار، نماد آ 3 - 15 بار، و نماد آ 4 - 11 بار، این کد به شما امکان می دهد دنباله ای از 176 بیت ( ). آن ها به طور متوسط ​​1.76 بیت برای هر نماد جریان هزینه خواهیم کرد.

برای اثبات قضیه، و همچنین این واقعیت که مدار ساخته شده در واقع یک کد هافمن را تعریف می کند، ببینید.

همانطور که از مطالب بالا مشخص شد، الگوریتم کلاسیک هافمن نیاز به نوشتن جدولی از متناظر کاراکترهای رمزگذاری شده و زنجیره های کدگذاری در یک فایل دارد.

در عمل از انواع آن استفاده می شود. بنابراین، در برخی موارد منطقی است که از یک جدول ثابت استفاده کنیم یا آن را "تطبیقی" بسازیم، یعنی. در فرآیند بایگانی/از بایگانی کردن. این ترفندها باعث صرفه جویی در دو عبور از تصویر و نیاز به ذخیره جدول به همراه فایل می شود. کدگذاری جدول ثابت به عنوان آخرین مرحله در بایگانی JPEG و در الگوریتم CCITT Group 3 مورد بحث در زیر استفاده می شود.

ویژگی های الگوریتم کلاسیک هافمن:

نسبت تراکم: 8، 1.5، 1 (بهترین، متوسط، بدترین شانس).

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

تقارن: 2 (با توجه به اینکه نیاز به دو گذر از آرایه داده های فشرده دارد).

مشخصات:تنها الگوریتمی که در بدترین حالت (به جز نیاز به ذخیره جدول جستجو به همراه فایل) حجم داده های اصلی را افزایش نمی دهد.

اصلاح مشابهی از الگوریتم هنگام فشرده سازی تصاویر سیاه و سفید (یک بیت در هر پیکسل) استفاده می شود. نام کامل این الگوریتم CCITT Group 3 است. یعنی این الگوریتم توسط سومین گروه استانداردسازی کمیته مشورتی بین المللی تلگراف و تلفن (Consultative Committee International Telegraph and Telephone) پیشنهاد شده است. دنباله ای از نقاط سیاه و سفید متوالی در آن با عددی برابر با تعداد آنها جایگزین می شود. و این سری نیز به نوبه خود مطابق هافمن با جدول ثابت فشرده شده است.

تعریف: مجموعه ای از نقاط تصویر متوالی هم رنگ نامیده می شود سلسلهطول این مجموعه از نقاط نامیده می شود طول سری.

جدول زیر دو نوع کد را تعریف می کند:

• کدهای تکمیل سری- از 0 تا 63 با افزایش 1 تنظیم کنید.
• کدهای ترکیبی (اضافی).- از 64 تا 2560 با افزایش 64 تنظیم می شوند.

در عمل، در مواردی که رنگ مشکی بر تصویر غالب است، تصویر را قبل از فشرده سازی معکوس می کنیم و اطلاعاتی در این مورد در هدر فایل می نویسیم.

الگوریتم فشرده سازی به شکل زیر است:

برای (در تمام خطوط تصویر) (
رشته را به مجموعه ای از طول های اجرا تبدیل کنید.
برای (بیش از همه سری ها) (
اگر (سری سفید) (
L= طول سری;
while(L > 2623) ( // 2623=2560+63
L=L-2560;
WriteWhiteCodeFor(2560);
}
if (L > 63) (
L2=MaximumConstCodeLessL(L);
L=L-L2;
WriteWhiteCodeFor(L2);
}
WriteWhiteCodeFor(L);
//این همیشه یک کد خروج است
}
دیگر(
[کد مشابه سری سفید،
با این تفاوت که نوشته شده اند
کدهای سیاه]
}
}
// پایان خط تصویر
}

از آنجایی که سری سیاه و سفید متناوب هستند، کد سری سفید و کد سری سیاه به طور متناوب عمل می کنند.

در نظر عبارات با قاعدهما برای هر خط از تصویر خود (به اندازه کافی طولانی، با یک نقطه سفید شروع می شود) یک جریان بیت خروجی از فرم دریافت می کنیم:

((<Б-2560>)*[<Б-сст.>]<Б-зв.>(<Ч-2560>)*[<Ч-сст.>]<Ч-зв.>) +

[(<Б-2560>)*[<Б-сст.>]<Б-зв.>]

جایی که ()* - تکرار 0 یا بیشتر، () + .- تکرار 1 بار یا بیشتر، - شامل 1 یا 0 بار.

برای مثال بالا: 0، 3، 556، 10 ... الگوریتم کد زیر را تولید می کند:<Б-0><Ч-3><Б-512><Б-44><Ч-10>، یا مطابق جدول 00110101 10 0110010100101101 0000100 (کدهای مختلف در تاپیک برای راحتی برجسته شده اند). این کد دارای ویژگی کدهای پیشوندی است و به راحتی می توان آن را به دنباله ای از طول اجرا برگرداند. به راحتی می توان محاسبه کرد که برای رشته داده شده 569 بیتی، ما یک کد 33 بیتی دریافت کردیم، یعنی. نسبت تراکم حدود 17 برابر است.

سوال:حجم فایل در بدترین حالت چند برابر افزایش می یابد؟ چرا؟ (پاسخ داده شده در مشخصات الگوریتم کامل نیست، زیرا ممکن است مقادیر بزرگتری از بدترین نسبت فشرده سازی وجود داشته باشد. آنها را پیدا کنید.)

ورزش:با توجه به یک رشته تصویر نوشته شده به طول اجرا - 442، 2، 56، 3، 23، 3، 104، 1، 94، 1، 231، 120 بایت در اندازه ((442+2+..+231)/8). نسبت فشرده سازی این رشته را با استفاده از الگوریتم CCITT Group 3 محاسبه کنید.

جدول کد تکمیل:

جدول کد ترکیبی:

این الگوریتم در قالب TIFF پیاده سازی شده است.

ویژگی های الگوریتم CCITT گروه 3

یک تصویر دوربین دیجیتال معمولی دارای وضوحی در حدود 3000x2000 است، یعنی. حدود 6 مگاپیکسل؛ 24 بیت در هر پیکسل معمولا برای نمایش رنگ استفاده می شود. بنابراین حجم داده های اولیه حدود 17 مگابایت است. برای دستگاه های حرفه ای ورودی تصویر، اندازه بیت مپ به دست آمده می تواند بسیار بزرگتر باشد، و عمق رنگ می تواند تا 48 بیت در هر پیکسل باشد ("سخت افزار گرافیکی بیت مپ مدرن"). بر این اساس حجم یک تصویر می تواند بیش از 200 مگابایت باشد. بنابراین، الگوریتم ها بسیار مرتبط هستند. فشرده سازیتصاویر یا به عبارت دیگر الگوریتم هایی که به شما امکان می دهد مقدار داده های نمایش دهنده یک تصویر را کاهش دهید.

دو دسته اصلی از الگوریتم ها وجود دارد:

1. A الگوریتم نامیده می شود فشرده سازی بدون تلفات(انگلیسی: فشرده سازی بدون تلفات) اگر الگوریتم A -1 (معکوس A ) وجود داشته باشد به طوری که برای هر تصویر I A (I) = I 1 و A -1 (I 1) = I . تصویر I به عنوان مجموعه ای از مقادیر ویژگی پیکسل تعریف می شود. پس از اعمال الگوریتم A به I، مجموعه داده I 1 را بدست می آوریم. فشرده سازی بدون تلفات در فرمت های گرافیکینمایش تصویر مانند: GIF، PCX، PNG، TGA، TIFF 1 به طور کلی، فرمت داده شدههمچنین از فشرده سازی با اتلاف پشتیبانی می کند.، یک دسته از فرمت های خوداز تولید کنندگان دوربین های دیجیتال و غیره)؛
2. A الگوریتم نامیده می شود فشرده سازی با اتلاف(انگلیسی: فشرده سازی با اتلاف)، در صورتی که توانایی بازیابی دقیق تصویر اصلی را نداشته باشد. الگوریتم جفت شده با A که بازیابی تقریبی را فراهم می کند به صورت A * نشان داده می شود: برای تصویر I A(I) = I 1 , A * (I 1) = I 2 و تصویر بازیابی شده حاصل I 2 لزوماً دقیقاً با I منطبق نیست. . جفت A، A * برای ارائه نسبت فشرده سازی بالا و حفظ کیفیت بصری انتخاب شده است. برای دستیابی به حداقل تفاوت در ادراک بین من و من 2 . فشرده سازی با اتلاف در فرمت های گرافیکی زیر اعمال می شود: JPEG، JPEG2000 و غیره.

این سخنرانی در مورد فشرده سازی بدون تلفات است که در مواردی که اطلاعات با هزینه زیادی به دست آمده است (مثلاً تصاویر پزشکی یا تصاویر ماهواره ای) یا در موارد دیگری که حتی کوچکترین تحریفنامطلوب

13.2. عدم وجود الگوریتم ایده آل

همانطور که قبلاً در پاراگراف قبل ذکر شد، تصویر I به عنوان مجموعه ای (توالی) از مقادیر ویژگی پیکسل در نظر گرفته می شود. در ادامه این سخنرانی، همه الگوریتم‌ها و عبارات هم برای تصاویر و هم برای توالی‌های دلخواه اعمال می‌شوند که عناصر آن می‌توانند تعداد محدودی از مقادیر را بگیرند.

بیانیه 13.2.1. هیچ الگوریتمی وجود ندارد که بتواند مجموعه داده ای را بدون اتلاف فشرده کند.

2 N دنباله با اندازه N بیت وجود دارد (ما یک بیت را به عنوان حداقل حامل اطلاعات در نظر خواهیم گرفت). بگذارید یک الگوریتم A وجود داشته باشد که در آن |I| - حجم داده (طول دنباله). فرض کنید M = حداکثر M k، سپس M< N . Существует 2 1 + 2 2 + ... + 2 M последовательностей длины, меньшей или равной M . Но 2 1 + 2 2 +... + 2 M = 2 M + 1 -2< 2 N . تناقض.

از این بیانیه برمی‌آید که توسعه الگوریتم‌هایی که به طور مؤثر دسته خاصی از تصاویر را فشرده می‌کنند منطقی است. در عین حال، برای این الگوریتم‌ها همیشه تصاویری وجود خواهند داشت که برای آنها فشرده‌سازی نمی‌شوند.

13.3. تکرار الگوریتم های رمزگذاری طول (RLE).

این نوع الگوریتم ها (الگوریتم های رمزگذاری طول تکرار 2 نام دیگری اغلب در ادبیات یافت می شود - کدگذاری گروهی.(RLE 3 انگلیسی رمزگذاری طول را اجرا کنید)) بر اساس ساده ترین اصل است: ما گروه های تکرار شونده از عناصر دنباله اصلی را با یک جفت (کمیت، عنصر) یا فقط با کمیت جایگزین می کنیم.

RLE - سطح بیت

ما داده های اصلی را در سطح دنباله ای از بیت ها در نظر خواهیم گرفت. به عنوان مثال، نمایندگی تصویر سیاه و سفید. معمولاً چندین 0 یا 1 در یک ردیف وجود دارد و شما فقط می توانید تعداد ارقام یکسان را در یک ردیف به خاطر بسپارید. آن ها دنباله 0000 11111 000 11111111111 مربوط به مجموعه اعداد تعداد تکرارهای 4 5 3 11 است. تفاوت ظریف زیر ایجاد می شود: اعدادی که تعداد تکرارها را نشان می دهند نیز باید در بیت کدگذاری شوند. می‌توانیم فرض کنیم که هر تعداد تکرار از 0 تا 7 متغیر است (یعنی دقیقاً می‌توان آن را با سه بیت کدگذاری کرد)، سپس دنباله‌های 11111111111 را می‌توان با اعداد 7 0 4 مرتبط کرد، یعنی. 7 یک، 0 صفر، 4 یک. به عنوان مثال، دنباله ای متشکل از 21 یک، 21 صفر، 3 یک و 7 صفر به صورت زیر کدگذاری می شود: 111 000 111 000 111 111 000 111 000 111 011 111 ، یعنی از دنباله اصلی که طول آن 51 بیت است، دنباله ای 36 بیتی به دست آمد.

ایده این روش هنگام ارسال فکس استفاده می شود.

RLE - سطح بایت

بیایید فرض کنیم که ورودی یک تصویر در مقیاس خاکستری است، که در آن 1 بایت به مقدار شدت پیکسل اختصاص داده شده است. واضح است که در مقایسه با یک شطرنجی سیاه و سفید، انتظار یک زنجیره طولانی از بیت های یکسان به طور قابل توجهی کاهش می یابد.

جریان ورودی را به بایت (حروف) تقسیم می کنیم و حروف تکرار شده را به صورت جفت (عدد، حرف) رمزگذاری می کنیم.

آن ها کد AABBBCDAA (2A) (3B) (1C) (1D) (2A) . با این حال، ممکن است گستره های طولانی از داده وجود داشته باشد که در آن هیچ چیز تکرار نمی شود، و ما هر حرف را به عنوان یک جفت (عدد، حرف) رمزگذاری می کنیم.

فرض کنید یک عدد ثابت (حرف) M (از 0 تا 255) داریم. سپس یک حرف را می‌توان به تنهایی رمزگذاری کرد، - خروجی = S، و اگر چندین حرف یا . به عنوان مثال، ما فقط الگوریتم رمزگشایی را ارائه می دهیم.

// M - مرز ثابت // خواندن کاراکترها به صورت متوالی از جریان ورودی // in - input - compressed sequence // out - output - discompressed sequence while(in.Read(c)) ( if(c > M) ( // شمارنده مورد n = c - M;in.Read(c);for(i = 0;i< n; i++) out.Write(c); } else // случай просто символа out.Write(c); } لیست 13.1. الگوریتم رمزگشایی RLE - سطح بایت

عدد M معمولاً 127 است. اصلاح این الگوریتم بیشتر مورد استفاده قرار می گیرد، جایی که علامت شمارنده وجود یکی در 2 بیت مهم کاراکتر خوانده شده است. 6 بیت باقیمانده مقدار شمارنده است.

این اصلاح این الگوریتم در قالب PCX استفاده می شود. با این حال، اصلاحات این الگوریتم به ندرت به تنهایی مورد استفاده قرار می گیرند، زیرا زیر کلاس دنباله هایی که این الگوریتم بر روی آنها کارآمد است نسبتاً محدود است. اصلاحات الگوریتم به عنوان یکی از مراحل خط لوله فشرده سازی استفاده می شود (به عنوان مثال، در JPEG،

نسخه اول الگوریتم

پیاده سازی این الگوریتم بسیار آسان است. Run Length Encoding (RLE) یکی از قدیمی ترین و ساده ترین الگوریتم های آرشیو گرافیکی است. تصویر موجود در آن (همانطور که در چندین الگوریتم شرح داده شده در زیر) به یک زنجیره بایت در امتداد خطوط شطرنجی کشیده می شود. خود فشرده سازی در RLE رخ می دهد با توجه به این واقعیت که در تصویر اصلی زنجیره ای از بایت های یکسان وجود دارد.آنها را با جفت جایگزین کنید<счетчик повторений, значение>افزونگی داده ها را کاهش می دهد.

الگوریتم رفع فشاربه نظر می رسد این است:

مقداردهی اولیه(...)؛ انجام دادن(

بایت= ImageFile.ReadNextByte(); if(counter(byte)) (counter = Low6bits(byte)+1; value = ImageFile.ReadNextByte(); for(i=l به شمارنده)

DecompressedFile.WriteByte(مقدار))

DecompressedFile.WriteByte(byte)) در حالی که (UmageFile.EOF ()) ;

در این الگوریتم، علامت شمارنده (counter) همان هایی است که در دو بیت بالای فایل خوانده شده قرار دارند:

بر این اساس، 6 بیت باقیمانده روی یک شمارنده صرف می شود که می تواند مقادیری از 1 تا 64 داشته باشد. رشته ای از 64 بایت تکرار شده را به 2 بایت تبدیل می کنیم، یعنی 32 بار آن را فشرده می کنیم.

ورزش.یک الگوریتم بسازید فشرده سازیبرای اولین نسخه از الگوریتم RLE.

این الگوریتم برای گرافیک های تجاری طراحی شده است - تصاویر با مناطق بزرگ از تکرار رنگ. موقعیتی که فایل رشد می کند برای این الگوریتم ساده چندان نادر نیست. می توان آن را به راحتی با اعمال کدگذاری دسته ای در عکس های رنگی پردازش شده به دست آورد. برای افزایش 2 برابری تصویر، باید روی تصویری اعمال شود که در آن مقادیر همه پیکسل ها از 11000000 باینری بیشتر باشد و به صورت جفت پشت سر هم تکرار نشود.

ورزش. 2-3 نمونه از تصاویر "بد" را برای الگوریتم RLE پیشنهاد کنید. دلیل اندازه را توضیح دهید فایل فشردهبزرگتر از فایل اصلی

این الگوریتم در قالب PCX پیاده سازی شده است. نمونه ای را در پیوست 2 ببینید.

نسخه دوم الگوریتم

نوع دوم این الگوریتم دارای حداکثر نسبت فشرده سازی بالاتری است و حجم فایل اصلی را کاهش می دهد. الگوریتم رفع فشار برای آن به شکل زیر است:

مقداردهی اولیه(...)؛ انجام دادن(

byte = ImageFile.ReadNextByte(); شمارنده = Low7bits(byte)+1; if(if repeat flag(byte)) ( value = ImageFile.ReadNextByte(); برای (i=l برای شمارنده)

CompressedFile.WriteByte(مقدار)

برای (i"=l برای مقابله) (

value = ImageFile.ReadNextByte(); CompressedFile.WriteByte(مقدار) } ) در حالی که (!ImageFile.EOFO) ;

علامت تکرار در این الگوریتم واحدی در مرتبه بالای بایت مربوطه است:

j 0 7 bit___ من از چه چیزی بگذرم ... از چه چیزی بگذرم

^ 1 7 بیت I چه چیزی را تکرار کنم I

همانطور که می توان به راحتی محاسبه کرد، این الگوریتم در بهترین حالت فایل را 64 بار (و نه 32 برابر مانند نسخه قبلی) فشرده می کند، در بدترین حالت 1/128 افزایش می یابد. میانگین شاخص های درجه فشرده سازی این الگوریتم در سطح شاخص های نوع اول است.

(تمرین Ech.یک الگوریتم فشرده سازی برای نسخه دوم الگوریتم RLE بنویسید.

طرح های فشرده سازی مشابه به عنوان یکی از الگوریتم های پشتیبانی شده توسط فرمت TIFF و همچنین در قالب TGA استفاده می شود.

ویژگی های الگوریتم RLE:

سطوح فشرده سازی:گزینه اول: 32، 2، 0.5. گزینه دوم: 64، 3، من 128/129. (بهترین، متوسط، بدترین مدرک).

کلاس تصویر:الگوریتم بر روی تصاویر با non-I متمرکز شده است مقدار زیادرنگ: گرافیک تجاری و علمی.

تقارن:تقریبا یک

مشخصات:جنبه های مثبت الگوریتم را شاید بتوان تنها به این واقعیت نسبت داد که به حافظه اضافی نیاز ندارد. \ هنگام بایگانی و باز کردن زیپ، و همچنین به سرعت کار می کند. خاص جالب! ویژگی کدگذاری گروهی این است که درجه بایگانی برای غیر! با تغییر ترتیب رنگ ها در پالت تصویر، کدام تصاویر را می توان به میزان قابل توجهی افزایش داد.

روش کدنویسی ساده ( RUN LENGHT CODING) که با موفقیت توسط آرشیوهای محبوب استفاده می شود.

این روش بر اساس شمارش طول کاراکترهای تکرار شده در یک ردیف و نوشتن در فایل بسته بندی شده به جای دنباله ای از این کاراکترها، نوع اطلاعات: تعداد کاراکترها و خود کاراکتر تکراری است. به عنوان مثال، یک رشته مانند " AAAAABBBCCCADDDEEL". به دنباله ای مانند" بسته می شود 5A3B3CADDEELهمانطور که از مثال مشخص است، دنباله 5 حرف "الف" به دو کاراکتر "5" و "الف" بسته بندی شده است، و دنباله های "DD"، "EE"، "L" اصلاً بسته بندی نشده اند. ، زیرا هیچ سودی از جایگزینی این کاراکترها در دنباله ای از نوع "طول" + "حرف" وجود ندارد.

هنگام پیاده‌سازی بسته‌بندی فایل با استفاده از این روش، مشکلاتی از جمله اینکه چگونه بازکننده اطلاعات کنترل را از یک فایل بسته‌بندی شده از داده‌های بسته‌نشده تشخیص می‌دهد، به وجود می‌آید. به عنوان مثال، همانطور که در موردی که در بالا بحث شد، آیا بازکننده کاراکتر کنترل "5" را از یک کاراکتر بسته نشده با همان کد متمایز می کند؟ دو گزینه برای حل این مشکل وجود دارد:

(من). نمادی را پیدا کنید که کمتر از بقیه وجود دارد یا اصلاً در فایل بسته بندی شده وجود ندارد و از آن به عنوان یک کنترل استفاده کنید. برای راحتی در توضیح زیر آن را پیشوند بنامیم. اکنون دنباله "AAAAA" توسط بسته بندی به پیشوند (8 بیت)، "A" (8 بیت)، مقدار (8 بیت)، یعنی 5 بایت با سه بایت تبدیل می شود. اگر در حین بسته‌بندی، بیتی با کد پیشوندی در فایل منبع مواجه شد، دو بایت با کد پیشوند در فایل حاصل نوشته می‌شود و با این ویژگی Unpacker تعیین می‌کند که پیشوند کجا نماد است و کجا کنترل است. اطلاعات تغییراتی در این روش ممکن است، به عنوان مثال:

1. مقدار را نه با هشت بیت، بلکه با سه، چهار و ... رمزگذاری کنید، که درصد بسته بندی را افزایش می دهد، اما محدود می کند. حداکثر طولکاراکترهای تکراری که در صورت رمزگذاری با سه بیت قابل بسته بندی هستند (از 3 تا 10، یعنی 000=3، ...، 111=10)، و اگر طول آن بیش از 10 کاراکتر باشد، ده کاراکتر را بسته بندی کنید.

2. تغییر دوم امکان پذیر است، زمانی که تعداد کاراکترهای تکراری نه با هشت بیت، بلکه با سه بیت رمزگذاری شود، و طول کاراکترهای تکراری به 265 بیت محدود شود. این سوال مطرح می شود که چگونه می توان 256 طول مختلف را در 3 بیت رمزگذاری کرد. به نظر می رسد که ممکن است، اما فقط محدوده از 3 تا 9 است، اما اگر طول کاراکترهای تکراری بیش از 9 باشد، "111" در سه بیت نوشته می شود. کد باینری، که برابر با "7" است. این بدان معنی است که طول واقعی دنباله در بایت بعدی است (8 بیت برای طول های 10 تا 256 کاراکتر اختصاص داده می شود).

در اینجا چند نمونه آورده شده است:

دنباله هایی داریم:

الف) "AAAAABBBBBBBBBBCCAAAAAAAAAAAAAAA"

ب) "CBBBBBBBBBBEEEEEEEEEEEEA"

بیایید آنها را بسته بندی کنیم:

1. با روش RLE (رمزگذاری طول اجرا - بسته بندی بایت های مکرر).

الف) پیشوند برابر با "D" را بگیرید، دریافت می کنیم:
«د»، «د»، «الف»، 5، «د»، «ب»، 10، «ج»، «د»، «الف»، 15.

درصد فشرده سازی = 12 بایت / 32 بایت = 37.5٪

در یک فایل بسته بندی شده، بایت پیشوند اولین بایت است تا بسته بندی کننده بداند کدام بایت پیشوند است.

ب) یک پیشوند برابر با "A" بگیرید، اگرچه در واقع بسته بندی این کار را انجام نمی دهد، زیرا کاراکترهای زیادی در این دنباله وجود ندارد، بنابراین بایگانی یک کاراکتر استفاده نشده را به عنوان پیشوند می گیرد.

دنباله بسته بندی شده:
«الف»، «ج»، «الف»، «ب»، 10، «الف»، «ه»، 10، «الف»، «الف»

درصد فشرده سازی = 10 بایت / 22 بایت = 45.5٪

2. حالا بیایید همان خطوط را مطابق اصلاح 1 روش RLE با مقادیر پیشوند یکسان بسته بندی کنیم تا کارایی را تجزیه و تحلیل کنیم.

"د"، "د"، "الف"، 2، "د"، "ب"، 7،
8 بیت 8 بیت 8 بیت 3 بیت 8 بیت 8 بیت 3 بیت

"د"، "الف"، 7، "د"، "الف"، 2
8 بیت 8 بیت 3 بیت 8 بیت 8 بیت 3 بیت

درصد فشرده سازی = 84 بیت / (22 * 8) بیت = 32.8٪

"الف"، "ج"، "الف"، "ب"، 7، "الف"، "ه"، 7، "الف"، "الف"
8 بیت 8 بیت 8 بیت 8 بیت 4 بیت 8 بیت 8 بیت 3 بیت 8 بیت 8 بیت

درصد فشرده سازی = 70 بیت / (22 * 8) بیت = 39.8٪

3. حالا بیایید اثربخشی آخرین اصلاح را بررسی کنیم:

الف) دنباله بسته بندی شده:

"د"، "د"، "الف"، 2، "د"، "ب"، 7، 0
8 بیت 8 بیت 8 بیت 3 بیت 8 بیت 8 بیت 3 بیت 8 بیت

"د"، "الف"، 7، 5
8 بیت 8 بیت 3 بیت 8 بیت

درصد فشرده سازی = 81 بیت / (32 * 8) بیت = 31.6٪

ب) دنباله بسته بندی شده:

"A"، "C"، "A"، "B"، 7، 0، "A"، "E"
8 بیت 8 بیت 8 بیت 8 بیت 3 بیت 8 بیت 8 بیت 8 بیت

7 , 0 , "A" , "A"
3 بیت 8 بیت 8 بیت 8 بیت

درصد فشرده سازی = 86 بیت / (22 * 8) بیت = 48.9٪

این مثال‌ها نشان می‌دهند که بسته به محتوای داده‌های بسته‌بندی‌شده، یکی یا دیگری الگوریتم مؤثر است، بنابراین برای اینکه انتخاب کنید کدام الگوریتم کارآمدتر است، باید آنها را روی انواع مختلف فایل‌ها آزمایش کنید.

(II). گزینه دوم برای ثبت اطلاعات کنترل برای unpacker به این صورت است: اگر یک کاراکتر در متن وجود داشته باشد، یک بیت کنترل برابر با یک است و خود این کاراکتر در فایل خروجی نوشته می شود. اگر دنباله ای از بایت های تکراری وجود داشته باشد، به عنوان مثال "AAAAAA"، اطلاعات بسته بندی شده به این صورت خواهد بود: 0 (1 بیت)، بایت A (8 بیت)، تعداد (3-8 بیت).

برای وضوح مثالی می زنیم. برای این کار، دنباله هایی از مثال های قبلی بگیرید.

1) تعداد بایت های تکرار شده به 8 بیت کدگذاری می شود.

الف) 0 , "A" , 5 , 0 , "B" , 10 , 1 , "C" , 1 , "C" , 0 , "A" , 15
1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b. 1b. 8b. 1b. 8b. 8b.

درصد فشرده سازی = 71 بیت / 256 بیت = 27.7٪

ب) 1، "C"، 0، "B"، 10، 0، "E"، 10، 1، "A"
1b. 8b. 1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b.

درصد فشرده سازی = 52 بیت / 176 بیت = 29.5٪

2) اکنون 3 بیت برای رمزگذاری تعداد بایت های تکراری در نظر می گیریم، که در آن مقادیر 2 تا 8 (0 - 6) را می توان کدگذاری کرد، اگر طول دنباله تکرار بیشتر باشد، این سه بیت شامل "111" (7 اعشاری)، و طول واقعی در بایت بعدی است (طول 9 تا 264).

الف) 0 , "A" , 3 , 0 , "B" , 7 , 1 , 0 , "C" , 0 , 0 , "A" , 7 , 6
1b. 8b. 3b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 1b. 8b. 3b. 8b.

درصد فشرده سازی = 64 بیت / 256 بیت = 20.3٪

ب) 1، "C"، 0، "B"، 7، 1، 0، "E"، 7، 1، 1، "A"
1b. 8b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 8b. 1b. 8b.

درصد فشرده سازی = 58 بیت / 176 بیت = 33٪

اگر مقدار در 4 بیت (2..16) کدگذاری شده باشد، پس

1 , "C" , 0 , "B" , 8 , 0 , "E" , 8 , 1 , "A"
1b. 8b. 1b. 8b. 4b. 1b. 8b. 4b. 1b. 8b.

درصد فشرده سازی = 44 بیت / 176 بیت = 25٪

همانطور که از مثال‌ها می‌بینید، گزینه بسته‌بندی دوم کارآمدتر است، زیرا دنباله‌هایی را که با دو کاراکتر شروع می‌شوند، فشرده می‌کند، که معمولا اکثریت قریب به اتفاق هستند. اولین نوع توالی‌هایی داشت که از سه کاراکتر شروع می‌شدند.