Методи стиснення даних мають досить довгу історію розвитку, яка почалася задовго до появи першого комп'ютера. У цій статті буде зроблена спроба дати короткий огляд основних теорій, концепцій ідей і їх реалізацій, що не претендує, однак, на абсолютну повноту. Більш докладні відомості можна знайти, наприклад, в Кричевський Р.Е. , Рябко Б.Я. , Witten I.H. , Rissanen J., Huffman D.A., Gallager R.G. , Knuth D.E. , Vitter J.S. та ін.
Стиснення інформації - проблема, що має досить давню історію, набагато давнішу, ніж історія розвитку обчислювальної техніки, яка (історія) зазвичай йшла паралельно з історією розвитку проблеми кодування і шифрування інформації. Всі алгоритми стиснення оперують вхідним потоком інформації, мінімальною одиницею якої є біт, а максимальної - кілька біт, байт або кілька байт. Метою процесу стиснення, як правило, є отримання більш компактного вихідного потоку інформаційних одиниць з деякого спочатку некомпактного вхідного потоку за допомогою деякого їх перетворення. Основними технічними характеристиками процесів стиснення і результатів їх роботи є:
Ступінь стиснення (compress rating) або відношення (ratio) обсягів вихідного і результуючого потоків;
Швидкість стиснення - час, що витрачається на стиснення деякого обсягу інформації вхідного потоку, до отримання з нього еквівалентного вихідного потоку;
Якість стиснення - величина, що показує на скільки сильно упакований вихідний потік, за допомогою застосування до нього повторного стиснення з цього ж або іншому алгоритму.
Існує кілька різних підходів до проблеми стиснення інформації. Одні мають досить складну теоретичну математичну базу, інші засновані на властивостях інформаційного потоку і алгоритмічно досить прості. Будь-який спосіб підхід і алгоритм, який реалізує стиснення або компресію даних, призначений для зниження обсягу вихідного потоку інформації в бітах за допомогою її оборотного або незворотного перетворення. Тому, перш за все, за критерієм, пов'язаному з характером або форматом даних, всі способи стиснення можна розділити на дві категорії: оборотне і необоротне стиснення.
Під незворотних стисненням на увазі таке перетворення вхідного потоку даних, при якому вихідний потік, заснований на певному форматі інформації, являє, з деякою точки зору, досить схожий за зовнішніми характеристиками на вхідний потік об'єкт, однак відрізняється від нього обсягом. Ступінь подібності вхідного і вихідного потоків визначається ступенем відповідності деяких властивостей об'єкта (тобто стислій і незжатої інформації, відповідно до деяким певним форматом даних), яку представляють даними потоком інформації. Такі підходи і алгоритми використовуються для стиснення, наприклад, даних растрових графічних файлів з низьким ступенем повторюваності байтів в потоці. При такому підході використовується властивість структури формату графічного файлу і можливість представити графічну картинку приблизно схожу за якістю відображення (для сприйняття людським оком) декількома (а точніше n) способами. Тому, крім ступеня або величини стиснення, в таких алгоритмах виникає поняття якості, тому що вихідне зображення в процесі стиснення змінюється, то під якістю можна розуміти ступінь відповідності вихідного і результуючого зображення, що оцінюється суб'єктивно, виходячи з формату інформації. Для графічних файлів таке відповідність визначається візуально, хоча є і відповідні інтелектуальні алгоритми і програми. Необоротне стиснення неможливо застосовувати в областях, в яких необхідно мати точну відповідність інформаційної структури вхідного і вихідного потоків. Даний підхід реалізований в популярних форматах уявлення відео і фото інформації, відомих як JPEG і JFIF алгоритми і JPG і JIF формати файлів.
Оборотний стиск завжди призводить до зниження обсягу вихідного потоку інформації без зміни його інформативності, тобто - без втрати інформаційної структури. Більш того, з вихідного потоку, за допомогою відновлюючого або декомпресивні алгоритму, можна отримати вхідний, а процес відновлення називається декомпресією або розпакуванням, і тільки після процесу розпакування дані придатні для обробки відповідно до їхнього внутрішнього форматом.
В оборотних алгоритмах кодування як процес можна розглядати зі статистичної точки зору, що ще більш корисно, не тільки для побудови алгоритмів стиснення, а й для оцінки їх ефективності. Для всіх оборотних алгоритмів існує поняття вартості кодування. Під вартістю кодування розуміється середня довжина кодового слова в бітах. Надмірність кодування дорівнює різниці між вартістю і ентропією кодування, а хороший алгоритм стиснення завжди повинен мінімізувати надмірність (нагадаємо, що під ентропією інформації розуміють міру її невпорядкованості.). Фундаментальна теорема Шеннона про кодування інформації говорить про те, що "вартість кодування завжди не менш ентропії джерела, хоча може бути як завгодно близька до неї". Тому, для будь-якого алгоритму, завжди є певний межа ступеня стиснення, який визначається ентропією вхідного потоку.
Перейдемо тепер безпосередньо до алгоритмическим особливостям оборотних алгоритмів і розглянемо найважливіші теоретичні підходи до стиснення даних, пов'язані з реалізацією кодують систем і способи стиснення інформації.
Стиснення способом кодування серій
Найбільш відомий простий підхід і алгоритм стиснення інформації оборотним шляхом - це кодування серій послідовностей (Run Length Encoding - RLE). Суть методів даного підходу полягає в заміні ланцюжків або серій повторюваних байтів або їх послідовностей на один кодує байт і лічильник числа їх повторень. Проблема всіх аналогічних методів полягає лише в визначенні способу, за допомогою якого розпаковувати алгоритм міг би відрізнити в результуючому потоці байтів кодовану серію від інших - некодованих послідовностей байтів. Рішення проблеми досягається зазвичай простановкой міток на початку кодованих ланцюжків. Такими позначки можна використати, наприклад, характерні значення бітів в першому байті кодованої серії, значення першого байта кодованого серії і т.п. Дані методи, як правило, досить ефективні для стиснення растрових графічних зображень(BMP, PCX, TIF, GIF), тому що останні містять досить багато довгих серій повторюваних послідовностей байтів. Недоліком методу RLE є досить низька ступінь стиснення або вартість кодування файлів з малим числом серій і, що ще гірше - з малим числом повторюваних байтів в серіях.
Стиснення без застосування методу RLE
Процес стиснення даних без застосування методу RLE можна розбити на два етапи: моделювання (modelling) і, власне, кодування (encoding). Ці процеси і їх реалізують алгоритми досить незалежні і різнопланові.
Процес кодування та його методи
Під кодуванням зазвичай розуміють обробку потоку символів (в нашому випадку байтів або напівбайтів) в деякому алфавіті, причому частоти появи символів в потоці різні. Метою кодування є перетворення цього потоку в потік біт мінімальної довжини, що досягається зменшенням ентропії вхідного потоку шляхом обліку частот символів. Довжина коду, що представляє символи з алфавіту потоку повинна бути пропорційна обсягу інформації вхідного потоку, а довжина символів потоку в бітах може бути не кратна 8 і навіть змінної. Якщо розподіл ймовірностей частот появи символів з алфавіту вхідного потоку відомо, то можна побудувати модель оптимального кодування. Однак, з огляду на існування величезного числа різних форматів файлів завдання значно ускладнюється тому розподіл частот символів даних заздалегідь невідомо. В такому випадку, в загальному вигляді, використовуються два підходи.
Перший полягає в перегляді вхідного потоку і побудові кодування на підставі зібраної статистики (при цьому потрібно два проходи по файлу - один для перегляду та збору статистичної інформації, другий - для кодування, що дещо обмежує сферу застосування таких алгоритмів, тому що, таким чином , виключається можливість однопрохідного кодування "на льоту", що застосовується в телекомунікаційних системах, де і обсяг даних, часом, не відомий, а їх повторна передача або розбір може зайняти невиправдано багато часу). В такому випадку, в вихідний потік записується статистична схема використаного кодування. Даний метод відомий як статичну кодування Хаффмена.
|
|
Розробка алгоритмів стиснення інформації відноситься до однієї з галузей прикладної математики. В їх основі лежить принцип усунення природної надмірності.
Методи стиснення інформації умовно діляться на два непересічних класи: стиснення з втратою інформаціїі стиснення без втрати інформації.
Стиснення з втратою інформаціїозначає, що після розпакування ущільненого архіву виходять дані, що трохи відрізняються від тих, які були на самому початку. Очевидно, що чим більше ступінь стиснення, тим більше величина втрати і навпаки.
Зрозуміло, такі алгоритми застосовуються для текстових документів, Таблиць баз даних і програм. Незначні спотворення в простому звичайний текст ще якось можна пережити, але спотворення хоча б одного біта в програмі зробить її абсолютно непрацездатною.
У той же час, існують дані, в яких можна пожертвувати кількома відсотками інформації, щоб отримати стиснення в десятки разів, наприклад, фотографії, відео-та аудіо матеріали. Втрата інформації при стисненні і подальшої розпакування таких даних сприймається як поява деякого додаткового «шуму».
До алгоритмів стиснення з втратою інформації відносяться такі алгоритми як JPEG(Використовуються при стисненні фотозображень) і MPEG(Використовуються при стисненні відео та аудіо). Алгоритми стиснення з втратою інформації застосовують тільки для споживчих завдань.
Величиною допустимої втрати при стисненні зазвичай можна управляти, що дозволяє досягти оптимального співвідношення «розмір / якість». На фотографічних ілюстраціях, призначених для відтворення на екрані, втрата 5% інформації зазвичай некритична, а в деяких випадках можна допустити втрату і в 20-25%.
методи стиснення без втрати інформаціїзастосовуються при роботі з текстовими документами і програмами і не можуть допустити втрату інформації. Вони засновані тільки на усунення її надмірності.
Приклад 1. В українській мові 32 букви, десять цифр і ще приблизно півтора десятка знаків пунктуації та інших спеціальних символів. Для тексту, який записаний тільки прописними буквами (як в телеграмах) цілком вистачило б шістдесяти різних значень. Проте, кожен символ зазвичай кодується байтом, який містить 8 бітів і може висловлювати 256 різних кодів. Це перша підстава для надмірності. Для «телеграфного» тексту цілком вистачило б шести бітів на символ.
Мал. 1. Азбука Морзе
Приклад 2. У міжнародній кодуванні символів ASCII для кодування будь-якого символу відводиться однакова кількість бітів (8). Разом з тим очевидно, що найбільш часто зустрічаються символи має сенс кодувати меншою кількістю знаків. Так, наприклад, в азбуці Морзелітери «Е» і «Т», які зустрічаються часто, кодуються одним знаком (відповідно це точка і тире). А такі рідкісні букви, як «Ю» (-) і «Ц» (- -) кодуються чотирма знаками. Неефективна кодування - друга підстава для надмірності.
Програми, що виконують стиснення інформації, можуть вводити свою систему кодування (різну для різних файлів) і приписувати до стиснення файлу якусь таблицю (словник), з якої розпаковувати програма дізнається, як в даному файлізакодовані ті чи інші символи або їх групи. Алгоритми, засновані на перекодуванні інформації, називають алгоритмами Хаффмана.
Наявність повторюваних фрагментів - третя підстава для надмірності. У текстах це зустрічається рідко, але в таблицях і в графіці повторення кодів - звичайне явище. Так, наприклад, якщо число 0 повторюється двадцять разів поспіль, то немає сенсу ставити двадцять нульових байтів. Замість них ставлять один нуль і коефіцієнт 20. Такі алгоритми, засновані на виявленні повторів, називають методами кодування довжин серій(RLE,Run Length Encoding). Великими повторюваними послідовностями однакових байтів особливо відрізняються графічні ілюстрації. Метод досить ефективний для графічних зображень у форматі «байт на піксель» (наприклад, формати PCXабо BMP).
При створенні резервних копійна жорстких дисках є ще одна можливість отримання виграшу в робочому просторі при стисненні файлів, яка пов'язана не з надмірністю інформації, а з тим, як організована файлова система комп'ютера. Суть її полягає в тому, що будь-який файл, великий чи маленький, може займати на диску тільки ціле число кластерів. В файлової системи FAT16 на жорсткому диску не може бути більше 65536 кластерів (2 16). А це означає, що для дисків розміром від 1 до 2 Гбайт розмір кластера складає 32 Кбайт.
При ущільненні великої групи файлів в один файл економія становить мінімум по 16 Кбайт на кожен файл тільки за рахунок скорочення втрат від нераціональної організації файлової системи.
Для FAT32 виграш виявляється менше, але і в цьому випадку мінімальний розмір кластера дорівнює 4 Кбайт, так що якщо мати справу з великою кількістю малих файлів, то тут теж є, що економити.
Незважаючи на те, що існує чимало різних методів стиснення, є деякі принципи і правила, Які є загальними для всіх методів стиснення. Їх треба знати і правильно використовувати.
1. У всякого стиснення є межа,тобто ущільнення раніше ущільненого файлу в кращому випадку не дає виграшу, а в гіршому випадку може привести і до програшу в розмірі результуючого файлу.
Мета уроку: розвивати уважність, кмітливість, виховувати інтерес до предмету.
Обладнання: комп'ютери, лабораторні диски, відповідне програмне забезпечення, Карти з тестовим завданням.
Хід уроку
1. Організаційна частина.
2. Актуалізація опорних знань.
3. Вивчення нового матеріалу
4. Закріплення нового матеріалу.
5. Домашнє завдання.
6. Підведення підсумків уроку.
Вивчення нового матеріалу
1. Що таке архівування. Поняття про стиснення даних.
2. Основні види програм-архіваторів.
3. Програма-архіватор WIN-RAR.
4. Як додавати файл в архів, а також витягувати його з архіву.
З розвитком інформаційних технологійгостро постало питання про способи зберігання даних. Починаючи з 40-х років ХХ ст., Вчені розробляють методи представлення даних, при яких простір на носіях інформації використовувався б економніше. Результатом цього стала технологія стиснення даних і архівації даних (backup).
Архівація даних - це злиття декількох файлів або каталогів в єдиний файл-архів.
Стиснення даних - скорочення обсягу вихідних файлів шляхом усунення надлишкової інформації.
Для виконання цих завданнях є програми-архіватори, які забезпечують стиснення даних: зокрема, архівування файлів. За допомогою спеціальних алгоритмів архіватори видаляють з файлів всю надлишкову інформацію, а при зворотних операціях розпаковування вони відновлюють інформацію в первинному вигляді. Розмір стиснутого файлу від двох до десяти разів менше файлу-оригіналу. При цьому стиснення та відновлення інформації відбувається без втрат. Стиснення без втрат актуальне при роботі з текстовими і програмними файлами, В задачах криптографії. Існують також методи стиснення з втратами.
Ступінь стиснення залежить від типу файлів і від програми - архіватора. Найбільше стискаються текстові файли, менш всіх - звукові і відеофайли.
Архівування файлів. завдання
До цих пір мова йшла про одне призначення архівації даних - економніше використанняносіїв інформації. Однак за допомогою архівації можна виконувати цілий комплекс завдань:
1. Зменшення обсягу файлів (актуально не тільки для економії місця на носіях, а й для швидкого перенесенняфайлів по мережі).
2. Резервне копіюванняна зовнішні носії для зберігання важливої інформації.
3. Архівація при шифруванні даних з метою зменшення ймовірності злому криптосистеми.
Процес запису інформації в архівний файл називається - архівування.
Витяг файлів з архіву - розархівування.
Перші програми-архіватори з'явилися в середині 80-х років. Вони були орієнтовані на роботу в MS-DOC і підтримували популярні архівні формати: ARC, ICE, ARJ, ZIP і RAR і ін. Існувала також група архіваторів, які упаковували дані в архіви - файли з розширенням. eхе ,. cоm. Для стиснення всього диска були створені резидент архіватори. Вони дозволяли підняти ефективність використання дискового простору шляхом створення великих архівних файлів - «стиснень» дисків.
Значно більш зручною стала робота з архівами при появі Windowsі Windows-версій архиваторов. З колишніх архівних форматів серед користувачів Windowsпо-справжньому прижилися ARJ, ZIP - програми які розпаковують файли. Великі за обсягом архівні файли можуть бути розміщені на кількох дискетах (томах). Такі архіви називаються багатотомними.
Том - це складова частинабагатотомного архіву.
Зараз використовується десятки програм-архіваторів, які відрізняються переліком функцій і параметрами роботи, проте найкращі з них мають приблизно однакові характеристики. Ми знаємо, що упаковка і розпакування файлів виконується однією і тією ж програмою, але в деяких випадках це здійснюється різними програмами, Наприклад, програма РКZIP упаковує файли, а РКUNZIP - розпакування файлів.
Програми-архіватори дозволяють створювати такі архіви, для вилучення з яких не потрібні будь-які програми, так як архівні файли містять в собі програму самі розпаковуються. Такі архіви називаються SFX-архівами.
Приміщення файлів в архів: Пуск Програми WINRAR або у вигляді ярлика на Робочому столі.
Універсальний архіватор WINRAR
Архіватор WINRAR також призначений для архівування файлів. Він має зручну графічну оболонку і підтримує технологію Drag and Drop. Програма WINRAR дозволяє працювати не тільки з архівними файлами rar, Але і з іншими архівними форматами: zip, cab, arj, lzh. Запускається WINRAR будь-яким з можливих способів, Передбачених в Windows. Запуск програми за допомогою Головного меню кнопки Пуск Програми WINRAR WINRAR або за допомогою ярлика на Робочому столі.
Тестове опитування з основ роботи з дисками.
Домашнє завдання.
Самоаналіз уроку.
Для виконання цих завданнях є програми-архіватори, які забезпечують як архівування, так і стиснення даних.За допомогою спеціальних алгоритмів архіватори видаляють з файлів всю надлишкову інформацію, а при зворотних операціях розпаковування вони відновлюють інформацію в первинному вигляді. Розмір стиснутого файлу від двох до десяти разів менше файлу-оригіналу.
Всі алгоритми стиснення оперують вхідним потоком інформації з метою отримання більш компактного вихідного потоку за допомогою деякого перетворення. Основними технічними характеристиками процесів стиснення і результатів їх роботи є:
· Ступінь стиснення - відношення обсягів вихідного і результуючого потоків;
· Швидкість стиснення - час, що витрачається на стиснення деякого обсягу інформації вхідного потоку, до отримання з нього еквівалентного вихідного потоку;
· Якість стиснення - величина, що показує, на скільки сильно упакований вихідний потік при застосуванні до нього повторного стиснення за тим же або іншим алгоритмом.
Алгоритми, які усувають надмірність записи даних, називаються алгоритмами стиснення даних, або алгоритмами архівації. В даний час існує величезна безліч програм для стиснення даних, заснованих на декількох основних способи.
Всі алгоритми стиснення даних діляться на:
) Алгоритми стиснення без втрат, при використанні яких дані на приймальні відновлюються без найменших змін;
) Алгоритми стиснення з втратами, які видаляють з потоку даних інформацію, незначно впливає на суть даних, або взагалі не сприймається людиною.
Існує два основні методи архівації без втрат:
алгоритм Гоффмана (англ. Huffman), орієнтований на стиснення послідовностей байт, не пов'язаних між собою,
алгоритм Лемпеля-Зива (англ. Lempel, Ziv), орієнтований на стиснення будь-яких видів текстів, тобто використовує факт неодноразового повторення "слів" - послідовностей байт.
Практично всі популярні програми архівації без втрат (ARJ, RAR, ZIP тощо) використовують об'єднання цих двох методів - алгоритм LZH.
Алгоритм Хаффмана.
Алгоритм заснований на тому факті, що деякі символи зі стандартного 256-символьного набору в довільному тексті можуть зустрічатися частіше середнього періоду повтору, а інші, відповідно, - рідше. Отже, якщо $ + o записи поширених символів використовувати короткі послідовності біт, довжиною менше 8, а для запису рідкісних символів - довгі, то сумарний обсяг файлу зменшиться.
Алгоритм Лемпеля-Зива. Класичний алгоритм Лемпеля-Зива -LZ77, названий так по році свого опублікування, гранично простий. Він формулюється так: якщо в минулому раніше вихідному потоці вже зустрічалася подібна сукупність електронних даних, причому запис про її довжині і зміщення від поточної позиції коротше ніж сама ця послідовність, то у вихідний файл записується посилання (зміщення, довжина), а не сама послідовність.
4.Показатели ступеня стиснення файлів
Стиснення інформації в архівних файлах виробляється за рахунок усунення надмірності різними способами, наприклад за рахунок спрощення кодів, виключення з них постійних бітів або подання повторюваних символів або повторюваної послідовності символів у вигляді коефіцієнта повторення і відповідних символів. Алгоритми подібного стиснення інформації реалізовані в спеціальних програмах-архіваторах (найбільш відомі з яких arj / arjfolder, pkzip / pkunzip / winzip, rar / winrar) застосовуються певні стискає можуть як один, так і декілька файлів, які в стислому вигляді поміщаються в так званий архівний файл або архів.
Метою упаковки файлів зазвичай є забезпечення більш компактного розміщення інформації на диску, скорочення часу і відповідно вартості передачі інформації по каналах зв'язку в комп'ютерних мережах. Тому основним показником ефективності тієї чи іншої програми-архіватора є ступінь стиснення файлів.
Ступінь стиснення файлів характеризується коефіцієнтом Кс, який визначається як відношення обсягу стисненого файлу Vc до обсягу вихідного файлу Vо, виражене у відсотках (в деяких джерелах використовується зворотне співвідношення):
Кс = (Vc / Vo) * 100%
Ступінь стиснення залежить від використовуваної програми, методу стиснення і типу вихідного файлу.
Найбільш добре стискаються файли графічних образів, текстові файли і файли даних, для яких коефіцієнт стиснення може досягати 5 - 40%, менше стискуються файли виконуваних програм і завантажувальних модулів Кс = 60 - 90%. Майже не стискуються архівні файли. Це неважко пояснити, якщо знати, що більшість програм-архіваторів використовують для стиснення варіанти алгоритму LZ77 (Лемпеля-Зива), суть якого полягає в особливому кодуванні повторюванихпослідовностей байт (читай - символів). Частота народження таких повторів найбільш висока в текстах і точкової графіку і практично зведена до нуля в архівах.
Крім того, програми для архівації все-таки різняться реалізаціями алгоритмів стиснення, що відповідно впливає на ступінь стиснення.
В деякі програми-архіватори додатково включаються кошти, спрямовані на зменшення коефіцієнта стиснення Кс. Так в програмі WinRAR реалізований механізм безперервного (solid) архівування, при використанні якого може бути досягнута на 10 - 50% вищий ступінь стиснення, ніж дають звичайні методи, особливо якщо упаковується значна кількість невеликих файлів однотипного змісту.
Характеристики архиваторов - назад залежні величини. Тобто, чим більше швидкість стиснення, тим менше ступінь стиснення, і навпаки.
На комп'ютерному ринку пропонується безліч архіваторів - у кожного свій набір підтримуваних форматів, свої плюси і мінуси, своє коло шанувальників, котрі щиро вірять в те, що вони використовують архіватор найкращий. Не будемо нікого і ні в чому переконувати - просто спробуємо неупереджено оцінити найпопулярніші архіватори в плані функціональності і ефективності. До таких віднесемо WinZip, WinRAR, WinAce, 7-Zip - вони лідирують за кількістю скачувань на софтових серверах. Розглядати інші архіватори навряд чи доцільно, оскільки відсоток застосовують їх користувачів (судячи по числу завантажень) невеликий.
Архів - Стиснення файлів: Як це відбувається? - Журнал «Комп'ютер»Вітаю! Чи не могли б ви пояснити початківцю, як стискаються файли всякими архиваторами? Хоча б в загальних рисах. А то я насилу собі уявляю, як це взагалі може бути.
Віталій
Абсолютно вірно, Віталій, це дійсно не так просто собі уявити, тим більше, якщо не знаєш алгоритму. Але читачам журналу «Комп'ютер» пощастило;), оскільки я свого часу багато цікавився алгоритмами стиснення даних і, як програміст, навіть пробував писати власний архіватор.
Стиснення даних (англ. Data compression) - алгоритмічне перетворення даних, яке виробляється з метою зменшення їх обсягу. Застосовується для більш раціонального використання пристроїв зберігання і передачі даних. Процес стиснення ще називають упаковкою даних або компресією. Зворотна процедура називається відновленням даних (розпакуванням, декомпресією).
Стиснення засноване на усуненні надмірності, що міститься у вихідних даних. Найпростішим прикладом надмірності є повторення в тексті фрагментів (наприклад, слів природної або машинного мови).
Отже, давайте почнемо з простого прикладу. Припустимо, у нас є текстовий файл, який містить рядок тексту:
АААГГДЕЕЕЕЖЖУУУККККІІІ
Текст досить дивний, погодьтеся, але зараз ми його стиснемо, і він у нас буде займати менше місця. Основний принцип стиснення досить простий і зводиться до наступного: кожна комбінація поспіль повторюваних символів замінюється одним таким символом і числом його повторень. Тобто наш вихідний текст в стислому вигляді буде виглядати так:
А3Г2Д1Е4Ж2У3К4І3
Таким чином, замість 22 символів ми отримали 16 символів. Звичайно, такі тексти як наш вихідний зустрічаються досить рідко, не кажучи вже про нісенітницю, яка укладена в ньому. Але ж файли, що піддаються стисненню, бувають не тільки текстові, але і всякі картинки, музика, відео, програми.
Даний приклад досить спрощений і не відображає ефективність, яку зазвичай демонструють при стисненні архіватори. Так у нас вийшло стиснення в 22/16 = 1,375 рази, хоча архіватори, як правило, здатні стискати файли в 2-10000 раз. Все залежить від повторюваності значень байт в файлі.
Які архіватори бувають
Наприклад, за часів незабутньої MS-DOS були архіватори ARJ, PKZIP, HA, RAR, ARC, ACE і пакувальники програм LZEXE і PKLITE. Пізніше для операційної системи Windowsбули створені WinAce, WinZIP, WinRAR, 7Zip і відомий мені пакувальник UPX.
Стиснення буває з втратами і без. Стиснення без втрат дозволяє відновити вихідні дані з точністю до біта. Таке стиснення застосовується для упаковки тексту, програм, різних даних в купе і здійснюється усіма перерахованими вище архиваторами.
Стиснення з втратами можна назвати адаптивним стисканням, і застосовується для упаковки зображень, відео та звуку, оскільки такі дані стиску без втрат піддаються досить незначно (всього приблизно до 2 разів).
Завдяки стиску з втратами можна домогтися багаторазового зменшення обсягу даних, і при відображенні розпакованих даних осіб практично не відчує різниці між оригіналом.
На скільки стискаються різні файли
текстові
Дійсно, наприклад, текстові файли можуть стискатися досить щільно. Так, наприклад, книга Аркадія і Бориса Стругацьких «Важко бути богом» розміром 354 329 байт архіватором WinRARстискається до 140 146 байт, тобто в 2,5 рази.
програми
Файли програм теж можуть піддаватися стиску. При цьому стиснення як для більш щільного зберігання на диску, так і стиснення, при якому програма залишається програмою, але при запуску розтискає сама себе.
Для цього існують пакувальники програм на подобу UPX та ін. Наприклад, мій текстовий редактор Superpad.exe розміром 524 288 байт пакувальником UPX стискається до 179 200 байт (в 2,9 рази) і при цьому може як і раніше запускатися самостійно як програма.
зображення
Опису методів стиснення цих даних можна присвятити цілу статтю, а то й не одну. Справа в тому, що саме по собі зображення стискується дуже погано, якщо його стискати байт за байтом. І, тим не менш, це вдається. Особливо, якщо в зображенні багато однотонного фону.
Одним з перших алгоритмів стиснення зображень був алгоритм RLE, який я описав вище. Він застосовується в форматі зберігання зображень PCX. RLE є алгоритмом стиснення без втрат. Але в деяких випадках він міг призводити не до зменшення обсягу даних, а до його збільшення.
Тому для стиснення зображень був запропонований і використовується до цих пір алгоритм побітового стиснення LZW. Сам по собі алгоритм вже набагато ефективніше RLE і теж не передбачає втрати. Але оскільки застосовується для зображень з палітрою кольорів, то за рахунок адаптації та оптимізації (ущільнення) палітри можна домогтися істотного підвищення ефективності стиснення.
Мал. 1. Гарний жабеня в форматі BMP
Для порівняння, візьмемо гарного жабеня (рис. 1) дозвіл 799x599 пікселів (точок) і збережемо в різні формати зберігання зображень. Отримаємо файли:
frog.bmp - розмір 1 437 654 байта і тут, по суті, ніякого стиснення і ніяких втрат якості, оскільки картинка займає належні їй байти в форматі Ширина x Висота x 3 байта на піксель + заголовок формату файлу BMP згідно якості True colors (24 біт / піксель). Тобто кожна точка представлена трьома компонентами RGB (Red-червоний, Green-зелений та Blue-синій), кожна з яких займає один байт.
frog24.png - 617 059 байт, стиснення в 2,33 рази і без втрат - основна властивість формату PNG-24. Дані BMP і PNG практично ідентичні.
Мал. 2. Файл frog_256colors.gif
frog_256colors.gif - 261 956 байт (рис. 2), стиснення в 5,48 рази з втратами, базова палітра 256 кольорів (8 біт / піксель). Вловити різницю між цим файлом і оригіналом в BMP досить складно, як в тій грі «Знайди десять відмінностей».
Мал. 3. Файл frog_64colors.gif
frog_64colors.gif - 187 473 байта (рис. 3), стиснення в 7,67 рази з втратами, базова палітра ущільнена до 64 кольорів (6 біт / піксель). А ось тут кольору вже бляклі, але цілком схоже з оригіналом зображення. Особливо це помітно, якщо подивитися на око жабеня.
JPEG
Особливе місце займає в стисненні і зберіганні зображень формат JPEG. Тому йому хочу приділити особливу увагу. Алгоритм JPEG найбільшою мірою придатний для стиснення фотографій і картин, що містять реалістичні сцени з плавними переходами яскравості і кольору. Найбільшого поширення JPEG отримав в цифровій фотографії і для зберігання і передачі зображень з використанням мережі Інтернет.
З іншого боку, JPEG малопридатний для стиснення креслень, текстової та знакової графіки, де різкий контраст між сусідніми пікселями приводить до появи помітних артефактів. Такі зображення доцільно зберігати в форматах без втрат, таких як TIFF, GIF, PNG або RAW.
JPEG (як і інші методи спотворює стиснення) не підходить для стиснення зображень при багатоступінчастої обробці, так як спотворення в зображення будуть вноситися кожен раз при збереженні проміжних результатів обробки.
JPEG не повинен використовуватися і в тих випадках, коли неприпустимі навіть мінімальні втрати, наприклад, при стисненні астрономічних або медичних зображень. У таких випадках може бути рекомендований передбачений стандартом JPEG режим стиснення Lossless JPEG (який, на жаль, не підтримується більшістю популярних кодеків) або стандарт стиснення JPEG-LS.
Опис алгоритму стиснення JPEG досить не проста, тому хто захоче, може ознайомитися з ним по посиланню http://el-izdanie.narod.ru/gl4/4-3.htm. Ну і для порівняння стиснемо нашу вихідну картинку з різним рівнем якості:
frog100% .jpg - 216 168 байт, стиснення в 6,65 рази, втрати нібито 0%, тобто 100% -у якість картинки, але навіть на це розраховувати я б не став. Повірте, відмінності є, правда, на око абсолютно відрізнити.
frog60% .jpg - 85 910 байт, стиснення в 16,7 рази, тобто якість картинки 60%, але картинка знову здається однаковою, хоча, якщо придивитися до ділянок з однорідним фоном або дрібним деталям, то помітні артефакти у вигляді смазанності або квадратних одноколірних сегментів.
frog20% .jpg - 36 426 байт, стиснення в 39,5 разів, якість картинки 20% від початкового зображення, але як і раніше картинка ще здатна обдурити недосвідчений очей, але на однорідному фоні чітко видно одноколірні незграбні сегменти, а дрібні деталі остаточно втратили свої чіткі обриси.
MPEG
Це один з найперших і найпоширеніших форматів зберігання відео. Кілька разів модернізувався. Але в спрощеному вигляді, можна сказати, що алгоритм дуже нагадує стиснення як в JPEG, але з урахуванням того, що перший кадр відео завжди є вихідним і оригінальним, а наступні кадри зберігають лише різницю між попереднім і наступним кадрами. Завдяки цьому кожний наступний кадр є передбачуваним з точки зору розпакування (рис. 4 і 5).
Мал. 4. Вихідні кадри відео
Мал. 5. міжкадрового різниця без застосування алгоритмів компенсації руху
Одна з найбільш потужних технологій, що дозволяє підвищити ступінь стиснення - це компенсація руху. При будь-якій сучасній системі стиснення відео наступні кадри в потоці використовують схожість областей в попередніх кадрах для збільшення ступеня стиснення.
Однак, через рух будь-яких об'єктів в кадрі (або самої камери) використання подібності сусідніх кадрів було неповним. Технологія компенсації руху дозволяє знаходити схожі ділянки, навіть якщо вони зрушені щодо попереднього кадру.
Компенсація руху (англ. Motion Compensation) - один з основних алгоритмів, що застосовуються при обробці і стисненні відеоданих. Алгоритм використовує схожість сусідніх кадрів в відео послідовності і знаходить вектори руху окремих частин зображення (зазвичай блоків 16x16 і 8x8).
Використання компенсації дозволяє при стисненні багаторазово збільшити ступінь стиснення за рахунок видалення надмірності у вигляді співпадаючих частин кадрів. Використовується не тільки при стисканні, але і при фільтрації відео, зміну частоти кадрів і т.д.
Практично в будь-якому відео сусідні кадри схожі, мають загальні об'єкти, які, як правило, зміщуються один щодо одного. І цілком природно бажання закодувати відео так, щоб об'єкти не кодувалися багаторазово, а просто описувалися деякі їх зміщення.
При цьому, зображення розбивається на так звані ключові кадри - це групи кадрів, що йдуть підряд кілька секунд. Керуючи тривалістю таких ключових кадрів можна ефективно управляти стисненням.
Наприклад, якщо сюжет фільму не динамічний, то тривалість ключових кадрів може бути по кілька секунд. Якщо ж фільм містить динамічні сцени, то в такі моменти тривалість ключових кадрів можна зробити коротше і стиснення швидко змінюється зображення буде виконуватися ефективніше.
Ключові кадри до того ж спрощують і прискорюють перемотування в медіаплеєрах, оскільки заголовок кожного ключового кадру містить посилання (зміщення в байтах відносно початку відеофайлу) на початок наступного ключового кадру.
Звук і музика
Звук і музика можуть без втрат, або з втратами зберігатися в форматі WAV. Наприклад, формат WAV (Windows PCM) не передбачає стиснення і зберігає звуковий сигналв оригіналі, якщо можна так висловитися.
Формат WAV (ACM Waveform), по суті, є контейнером і може зберігати звук, стиснений за алгоритмом MPEG layer 3, або зберігати музику в форматі MP3, хоча багато й інших форматів OGG, FLAC і д.р.
Поділитися інформацією про цей алгоритмах стиснення звуку вже не встигаю, до того ж раніше в нашому журналі була чудова стаття на цю тему.