• آموزش

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

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

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

RLE - فشردگی یکنواختی

الگوریتم RLEاحتمالاً ساده ترین از همه است: ماهیت آن در رمزگذاری تکرارها نهفته است. به عبارت دیگر، دنباله‌هایی از عناصر یکسان را می‌گیریم و آنها را به جفت‌های «کمیت/مقدار» «جمع می‌کنیم». به عنوان مثال، رشته ای مانند "AAAAAAAABCCCC" می تواند به چیزی مانند "8×A, B, 4×C" تبدیل شود. به طور کلی، این تنها چیزی است که باید در مورد الگوریتم بدانید.

مثال پیاده سازی

فرض کنید مجموعه ای از ضرایب صحیح خاص داریم که می توانند مقادیری از 0 تا 255 را بگیرند. منطقاً به این نتیجه رسیدیم که ذخیره این مجموعه به عنوان یک آرایه بایت منطقی است:
داده کاراکتر بدون علامت = ( 0، 0، 0، 0، 0، 0، 4، 2، 0، 4، 4، 4، 4، 4، 4، 4، 80، 80، 80، 80، 0، 2، 2 , 2, 2, 255, 255, 255, 255, 255, 0, 0 );

برای بسیاری، دیدن این داده ها به شکل یک هگزا بسیار رایج تر خواهد بود:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF FF 00 00

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

بیایید داده های خود را با استفاده از دانش تازه به دست آمده رمزگذاری کنیم: 6x0، 4، 2، 0، 7x4، 4x80، 0، 4x2، 5x255، 2x0.

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

حداقل دو راه برای خروج از این وضعیت وجود دارد:

1. به عنوان نشانگر یک زنجیره فشرده، یک مقدار بایت را انتخاب کنید و در صورت برخورد با داده های واقعی، از آن فرار کنید. به عنوان مثال، اگر از مقدار 255 برای مقاصد "رسمی" استفاده کنیم، هنگامی که با این مقدار در داده های ورودی مواجه می شویم، مجبور می شویم که "255,255" بنویسیم و حداکثر بعد از نشانگر از 254 استفاده کنیم.
2. ساختار داده‌های رمزگذاری‌شده، نشان‌دهنده کمیت نه تنها برای عناصر تک‌تکرار، بلکه همچنین برای عناصر تک بعدی. سپس ما از قبل می دانیم که چه داده هایی هستند.

روش اول در مورد ما موثر به نظر نمی رسد، بنابراین، شاید، ما به روش دوم متوسل شویم.

بنابراین اکنون دو نوع دنباله داریم: زنجیره ای از عناصر منفرد (مانند "4، 2، 0") و زنجیره ای از عناصر یکسان (مانند "0، 0، 0، 0، 0، 0"). اجازه دهید یک بیت را در بایت های "سرویس" برای نوع دنباله انتخاب کنیم: 0 - عناصر تک، 1 - یکسان. برای این، مثلاً مهم‌ترین بیت بایت را در نظر بگیرید.

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

معلوم می شود که ابتدا طول دنباله را در جریان خروجی می نویسیم و سپس یک مقدار قابل تکرار یا زنجیره ای از عناصر غیرقابل تکرار با طول مشخص شده را می نویسیم.

اولین چیزی که باید توجه شما را جلب کند این است که در این شرایط چند مقدار استفاده نشده داریم. هیچ دنباله‌ای با طول صفر نمی‌تواند وجود داشته باشد، بنابراین می‌توانیم با کم کردن یک بایت از طول هنگام رمزگذاری و اضافه کردن یک در هنگام رمزگشایی، حداکثر طول را به 128 بایت افزایش دهیم. به این ترتیب می توانیم طول های 1 تا 128 را به جای طول های 0 تا 127 رمزگذاری کنیم.

دومین چیزی که می توانید متوجه شوید این است که هیچ دنباله ای از عناصر یکسان با طول واحد وجود ندارد. بنابراین، هنگام رمزگذاری، یکی دیگر را از طول چنین دنباله‌هایی کم می‌کنیم، در نتیجه حداکثر طول آنها را به 129 افزایش می‌دهیم (حداکثر طول یک زنجیره از عناصر منفرد هنوز 128 است). آن ها زنجیره های عناصر یکسان ما می توانند از 2 تا 129 طول داشته باشند.

بیایید دوباره داده های خود را رمزگذاری کنیم، اما اکنون به شکلی قابل فهم برای رایانه. بایت های سرویس را به صورت , جایی که T نوع دنباله و L طول آن است می نویسیم. بیایید فوراً در نظر بگیریم که طول ها را به شکل اصلاح شده می نویسیم: برای T=0 یک را از L کم می کنیم و برای T=1 دو را کم می کنیم.

0, , 4, 2, 0, , 4, , 80, , 0, , 2, , 255, , 0

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

• . T=1، یعنی بایت بعدی L+2 (4+2) بار تکرار می شود: 0، 0، 0، 0، 0، 0.
• . T=0، یعنی ما به سادگی بایت های L+1 (2+1) را می خوانیم: 4، 2، 0.
• . T=1، بایت بعدی را 5+2 بار تکرار کنید: 4، 4، 4، 4، 4، 4، 4.
• . T=1، بایت بعدی را 2+2 بار تکرار کنید: 80، 80، 80، 80.
• . T=0، خواندن 0+1 بایت: 0.
• . T=1، بایت را 2+2 بار تکرار کنید: 2، 2، 2، 2.
• . T=1، بایت را 3+2 بار تکرار کنید: 255، 255، 255، 255، 255.
• . T=1، بایت را 0+2 بار تکرار کنید: 0، 0.

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

در نتیجه موارد زیر را بدست می آوریم:
0000: 84 00 02 04 02 00 85 04 82 80 00 00 82 02 83 FF
0010: 80 00

به این روش ساده در این مثالما 18 بایت از 32 بایت داده ورودی دریافت کردیم. نتیجه بدی نیست، به خصوص با توجه به اینکه در زنجیره های طولانی تر می تواند بسیار بهتر باشد.

بهبودهای احتمالی

اثربخشی یک الگوریتم نه تنها به خود الگوریتم، بلکه به نحوه اجرای آن نیز بستگی دارد. بنابراین، انواع مختلفی از رمزگذاری و نمایش داده های رمزگذاری شده را می توان برای داده های مختلف توسعه داد. به عنوان مثال، هنگام رمزگذاری تصاویر، می توانید زنجیره ایجاد کنید طول متغیر: یک بیت را برای نشان دادن یک زنجیره بلند اختصاص دهید و اگر روی یک تنظیم شد، طول را در بایت بعدی نیز ذخیره کنید. به این ترتیب طول زنجیره های کوتاه را قربانی می کنیم (65 عنصر به جای 129)، اما رمزگذاری زنجیره هایی تا 16385 عنصر طولانی (2 14 + 2) را تنها با سه بایت ممکن می کنیم!

با استفاده از روش های کدگذاری اکتشافی می توان کارایی بیشتری به دست آورد. به عنوان مثال، بیایید زنجیره زیر را با استفاده از روش خود رمزگذاری کنیم: "ABBA". ما " , A, , B, , A" - i.e. ما 4 بایت را به 6 تبدیل کردیم و داده های اصلی را به اندازه یک و نیم برابر افزایش دادیم! و هر چه این توالی های متناوب کوتاه از انواع مختلف بیشتر باشد، داده های اضافی بیشتری وجود دارد. اگر این را در نظر بگیریم، می‌توانیم نتیجه را به صورت «، A، B، B، A» رمزگذاری کنیم - فقط یک بایت اضافی را هدر می‌دهیم.

LZ77 - اختصار در تکرار

LZ77 یکی از ساده ترین و معروف ترین الگوریتم های خانواده LZ است. به نام سازندگان آن: آبراهام لمپل Lامپل) و یعقوب زیو (یعقوب ز IV). اعداد 77 در عنوان نشان دهنده سال 1977 است که در آن مقاله ای در توصیف این الگوریتم منتشر شده است.

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

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

مثال پیاده سازی

بیایید سعی کنیم چیزی را کدنویسی کنیم. بیایید یک خط مناسب برای این ایجاد کنیم (پیشاپیش از پوچ بودن آن عذرخواهی می کنم):

"فشرده سازی ورفع فشار تاثیری بر جای می گذارد. هاهاهاهاها!»

این چیزی است که در حافظه به نظر می رسد (رمزگذاری ANSI):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20 فشرده سازی
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65 و تجزیه
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69 ssion ترک یک i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 mppression. هههه
0040: 61 68 61 68 61 21 آهاها!

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

فشرده‌سازی و ترک[an] i . هه!

برای وضوح بیشتر، بیایید به نمودار نگاه کنیم، جایی که می‌توانیم مطابقت بین دنباله‌های تکراری و اولین رخدادهای آنها را ببینیم:

شاید تنها نکته مبهم در اینجا دنباله "هاهاهاهاها!" باشد، زیرا زنجیره شخصیت ها "آهاهاها" با زنجیره کوتاه "آه" مطابقت دارد. اما هیچ چیز غیرعادی در اینجا وجود ندارد، ما از ترفندی استفاده کردیم که به الگوریتم اجازه می دهد گاهی اوقات مانند RLE که قبلا توضیح داده شد کار کند.

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

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

فشرده‌سازی و ترک i. هه!

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

فشرده‌سازی و ترک i. هه!

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

زمان تصمیم گیری در مورد اندازه پنجره و حداکثر طولعبارت رمز شده از آنجایی که ما با متن سروکار داریم، به ندرت دنباله های تکراری طولانی در آن وجود خواهد داشت. بنابراین بیایید مثلاً 4 بیت برای طول آنها اختصاص دهیم - محدودیت 15 کاراکتر در هر زمان برای ما کاملاً کافی است.

اما اندازه پنجره تعیین می کند که تا چه حد به دنبال زنجیره های یکسان باشیم. از آنجایی که ما با متون کوچک سروکار داریم، درست است که تعداد بیت‌هایی را که استفاده می‌کنیم به دو بایت تکمیل کنیم: پیوندهایی در محدوده 4096 بایت، با استفاده از 12 بیت برای این کار، آدرس‌دهی می‌کنیم.

ما از تجربه با RLE می دانیم که نمی توان از همه مقادیر استفاده کرد. بدیهی است که پیوند می تواند داشته باشد حداقل مقدار 1، بنابراین، برای آدرس دهی در محدوده 1..4096، باید هنگام رمزگذاری، یکی را از مرجع کم کنیم و هنگام رمزگشایی آن را دوباره اضافه کنیم. همین مورد در مورد طول های دنباله: به جای 0..15 از محدوده 2..17 استفاده می کنیم، زیرا با طول های صفر کار نمی کنیم، اما شخصیت های فردیدنباله نیستند

بنابراین، بیایید متن رمزگذاری شده خود را با در نظر گرفتن این اصلاحات ارائه کنیم:

فشرده‌سازی و ترک i. هه!

اکنون دوباره باید زنجیره های فشرده شده را از بقیه داده ها جدا کنیم. رایج ترین راه این است که دوباره از ساختار استفاده کنید و به صراحت مشخص کنید که داده ها کجا فشرده شده اند و کجا نیستند. برای انجام این کار، داده های رمزگذاری شده را به گروه های هشت عنصری (نمادها یا پیوندها) تقسیم می کنیم و قبل از هر یک از این گروه ها یک بایت درج می کنیم که هر بیت مربوط به نوع عنصر است: 0 برای نماد و 1 برای یک لینک

ما به گروه ها تقسیم می کنیم:

• "کامپیوتر"
• "واکنش"
• "و تی د"
• "ترک کردن"
• "من. هه"

بیایید گروه ها را ایجاد کنیم:

"(0,0,0,0,0,0,0,0) پاسخ comp(0,0,0,0,0,0,0,0) (0,0,0,0,0,1 ,0,0) و t de(1,0,0,0,0,0,1,0) ترک (0,1,0,0,0,0,0,1) i . هاه (0)!"

بنابراین، اگر در حین باز کردن بسته بندی با بیت 0 مواجه شدیم، آنگاه به سادگی کاراکتر را در جریان خروجی می خوانیم، اگر بیت 1 را می خوانیم، پیوند را می خوانیم، و از پیوند دنباله را از فرهنگ لغت می خوانیم.

اکنون تنها کاری که باید انجام دهیم این است که نتیجه را در یک آرایه بایت گروه بندی کنیم. بیایید قبول کنیم که از بیت ها و بایت ها به ترتیب از زیاد به پایین استفاده می کنیم. بیایید ببینیم که چگونه پیوندها با استفاده از یک مثال در بایت ها بسته بندی می شوند:

در نتیجه، جریان فشرده ما به شکل زیر خواهد بود:

0000: 00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f #The comp#ressio
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #and t##de###l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 eave## #i##. هه
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00 ###!

بهبودهای احتمالی

در اصل، هر آنچه برای RLE توضیح داده شد، در اینجا صادق خواهد بود. به طور خاص، برای نشان دادن سودمندی رویکرد اکتشافی هنگام کدنویسی، به مثال زیر توجه کنید:

"گووووونگ طولانی. محدودتر است."

بیایید دنباله هایی را فقط برای کلمه "looooooower" پیدا کنیم:

"گووووونگ طولانی. بهترین حد."

برای رمزگذاری چنین نتیجه ای به هر مرجع به چهار بایت نیاز داریم. با این حال، انجام این کار مقرون به صرفه تر است:

"گووووونگ طولانی. من مقید بودم.»

آن وقت یک بایت کمتر خرج می کردیم.

به جای نتیجه گیری

این الگوریتم‌ها علیرغم سادگی و ظاهراً نه چندان مؤثر، هنوز به طور گسترده در حوزه‌های مختلف بخش فناوری اطلاعات مورد استفاده قرار می‌گیرند.

مزیت آنها سادگی و سرعت است و الگوریتم‌های پیچیده‌تر و مؤثرتر را می‌توان بر اساس اصول و ترکیب‌های آنها استوار کرد.

من امیدوارم که ماهیت این الگوریتم‌هایی که به این شکل ارائه شده‌اند به کسی کمک کند اصول اولیه را درک کند و شروع به نگاه کردن به چیزهای جدی‌تر کند.

رمزگذاری طول اجرا (RLE) یا Repeat Coding یک الگوریتم فشرده سازی داده ساده است که بر روی اجراهای داده عمل می کند، یعنی توالی هایی که در آن یک کاراکتر چندین بار پشت سر هم ظاهر می شود. هنگام رمزگذاری، رشته ای از کاراکترهای یکسان که یک سری را تشکیل می دهند با رشته ای جایگزین می شود که حاوی خود کاراکتر تکرار شونده و تعداد تکرارهای آن است.

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

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

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

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

پیاده سازی این الگوریتم بسیار ساده است. رمزگذاری گروهی - از انگلیسی Run Length Encoding (RLE) - یکی از قدیمی ترین و ساده ترین الگوریتم های آرشیو گرافیکی است. تصویر موجود در آن (مانند چندین الگوریتم شرح داده شده در زیر) به زنجیره ای از بایت ها در امتداد خطوط شطرنجی کشیده می شود. خود فشرده سازی در RLE به این دلیل اتفاق می افتد که تصویر منبع شامل زنجیره هایی از بایت های یکسان است. آنها را با جفت جایگزین کنید<شمارشگر تکرار، ارزش> افزونگی داده ها را کاهش می دهد.

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

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

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

29. الگوریتم فشرده سازی lzw

این الگوریتم بر اساس حروف اول نام خانوادگی توسعه دهندگان آن نامگذاری شد - لمپل, Zivو ولش.

الگوریتم LZW مبتنی بر ایده گسترش الفبا است، که اجازه می دهد تا از کاراکترهای اضافی برای نمایش رشته های کاراکترهای معمولی استفاده شود. برای مثال، با استفاده از کدهای 9 بیتی ASCII به جای کدهای 8 بیتی، 256 کاراکتر اضافی دریافت می کنید. کار کمپرسور به ساخت جدولی متشکل از سطرها و کدهای مربوط به آنها ختم می شود. الگوریتم فشرده سازی به صورت زیر خلاصه می شود: برنامه کاراکتر بعدی را می خواند و آن را به رشته اضافه می کند. اگر ردیف از قبل در جدول باشد، خواندن ادامه می یابد، اگر نه، خط داده شدهبه جدول رشته اضافه می شود. هرچه خطوط تکراری بیشتر باشد، داده ها بیشتر فشرده می شوند. با بازگشت به مثال با تلفن، می توان با استفاده از یک قیاس بسیار ساده، گفت که با فشرده سازی ورودی 233 34 44 به روش LZW، به معرفی خطوط جدید - 333 و 444 و بیان آنها می رسیم. شخصیت های اضافی، می توانیم طول ضبط را کاهش دهیم.

ویژگی های الگوریتم LZW:نسبت تراکم: تقریباً 1000، 4، 5/7 (بهترین، متوسط، بدترین شانس). فشرده سازی 1000 بار فقط روی تصاویر تک رنگی که مضرب اندازه تقریباً 7 مگابایت هستند به دست می آید. کلاس تصویر: LZW بر روی تصاویر 8 بیتی ساخته شده بر روی کامپیوتر متمرکز شده است. به دلیل زیر زنجیره های یکسان در جریان فشرده می شود. تقارن: تقریباً متقارن، مشروط بر اینکه عملیات جستجوی یک ردیف در جدول به صورت بهینه اجرا شود.

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

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

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

یک تصویر معمولی که توسط یک دوربین دیجیتال گرفته می شود وضوحی در حدود 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 لزوماً دقیقاً منطبق نیست من. جفت 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، و اگر چندین حرف وجود داشته باشد یا، خروجی = CS، که در آن C > M، و C - M تعداد حروف متوالی S است. به عنوان مثال، ما فقط الگوریتم رمزگشایی را ارائه می دهیم.

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

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

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