Теоретичні відомості

Алгоритм стиснення інформації – Run Length Encoding – RLE

Теоретичні відомості

Стиск інформації – широко використовується при зберіганні зображень, звукової та відео інформації. Вторинні алгоритми стиску інформації використовуються для стиснення зображень, звукової та відео інформації після їх попередньої обробки іншими складнішими алгоритмами.

Всі алгоритми стиснення оперують вхідним потоком інформації, який являє собою послідовність чисел, мінімальною одиницею якої є біт або байт.

Метою процесу стиснення, як правило, є отримання більш компактного вихідного потоку інформаційних одиниць з деякого спочатку некомпактного вхідного потоку за допомогою деякого їх перетворення.

Після стиснення інформації вихідний потік представляється як певна кількість нових біт або байт.

Основними технічними характеристиками процесів стиснення і результатів їх роботи є:

- Ступінь стиснення (compress rating) або відношення (ratio) обсягів вихідного і результуючого потоків;

- Швидкість стиснення - час, що витрачається на стиснення деякого обсягу інформації вхідного потоку, до отримання з нього еквівалентного вихідного потоку;

- Якість стиснення - величина, що показує на скільки сильно упакований вихідний потік, за допомогою застосування до нього повторного стиснення по цьому ж або іншому алгоритму.

Всі способи стиснення можна розділити на дві категорії: з втратами і без втрат.

Ступінь подібності вхідного і вихідного потоків інформації визначається ступенем відповідності властивостей інформації – тобто об'єкта стиснення.

З вихідного потоку, за допомогою алгоритму декомпресії, можна отримати вхідний, а процес відновлення називається декомпресією або розпакуванням і тільки після процесу розпакування дані придатні для обробки.

Кількість цифрової інформації (вхідної чи вихідної)

Байт (англ. byte) — одиниця зберігання і обробки цифрової інформації. У сучасних обчислювальних системах байт складається з восьми бітів і, відповідно, може приймати одне з 256 різних значень. Тобто число від 0 до 255 можна записати в один байт інформації.

Двійкова система	Десяткова система
І так далі

Як видно з таблиці мінімальна кількість біт (значущих) для чисел 4-7 є 3 біти, для чисел 16-31 дорівнює 5 біт.

В цифровій електроніці кожне число може представлятись одним, двома, трьома чи чотирма байтами інформації.

Для кодування текстової інформації прийнято міжнародний стандарт ASCII (American Standard Code for Information Interchange).

За цим стандартом:

· Кожен символ займає 1 байт.

· Всього є 256 символів.

· Всі символи знаходяться у спеціальній таблиці ASCII кодів.

· Кожен символ має свій внутрішній код, який співпадає з порядковим номером символа у таблиці.

· Перша половина цієї таблиці (символи з номерами з 0 по 127) стандартна. Вона містить цифри, латинські літери та інші необхідні символи.

· У другій половині таблиці (символи з номерами з 128 по 255) знаходяться літери національних алфавітів та додаткові символи. Ця частина таблиці різна для різних країн та різних кодових таблиць, встановлених у операційній системі.

Символ f у таблиці має номер 102.

Символ Б має номер 129.

Символи англійська A та кирилиця A мають однаковий вигляд, але внутрішні коди в них різні – 65 та 128.

Символ 0 (нуль) має внутрішній код 48.

Символ пробіл має внутрішній код 32.

Великі та маленькі літери мають різні ASCII–коди.

У наш час можливим є вимірювання кількості інформації лише в кодах знаків. Виміряти ж кількість семантичної інформації в повідомленні (тобто інформації, поданої в значеннях слів) у наш час — неможливо. Тому далі зупинимося лише на вимірюванні кількості інформації в кодах знаків.

Приклад. Припустімо, певне повідомлення має обсяг 344 символи й набрано традиційним шрифтом Times New Roman. Оскільки шрифт кодує кожний символ одним байтом, то кількість інформації в такому повідомлення становитиме 344 байт.

Приклад. Припустімо, те саме повідомлення, що й у попередньому прикладі, набрано традиційним шрифтом Arial MS Unocode, що кодує кожний символ двома байтами. Тоді кількість інформації в такому повідомлення становитиме 344 х 2 = 688 байт.

Якщо вхідний потік інформації становив 344 байти, а вихідний 172 байти, то коефіцієнт стиску дорівнює 2.

Отже, для того щоб визначити коефіцієнт стиску необхідно поділити кількість вхідної інформації на кількість вихідної. Зазначимо, що часто при використанні вторинних алгоритмів стиску до сучасної інформації в результаті стиску отримуємо більшу кількість вихідної інформації ніж вхідної.

Найбільш відомий простий підхід і алгоритм стиснення інформації без втрат - це кодування довжин послідовностей (Run Length Encoding - RLE).

Суть методів даного підходу полягає в заміні ланцюжків або серій повторюваних байтів на лічильник числа їх повторень та один байт, який повторюється.

Недоліком алгоритму RLE є досить низька ступінь стиснення.

Стиснення способом кодування серій (RLE)

Варіант 1 (не існуючий реально, тому що неможливо розкодувати)

Для байт, які повторюються, робиться заміна: перший байт – лічильник - вказує скільки разів потрібно повторити наступний байт.

Приклад 1:

44 44 44 11 11 11 11 11 23 22 22 - вхідна послідовність в десятковій системі

03 44 05 11 23 02 22 – вихідна стиснута послідовність в десятковій системі

Коефіцієнт стиску: 11/7

Недолік: через те що невідомо, який байт є лічильником, а який повторюється – неможливо розкодувати.

Варіант 2 (студентський - лінивий)

Для всіх байт, які повторюються і не повторюються, утворюємо пари: лічильник + байт, який повторюється, або не повторюється.

Приклад 2

44 44 44 11 11 11 11 11 23 22 22 - вхідна послідовність в десятковій системі

03 44 05 11 01 23 02 22 - вихідна стиснута послідовність в десятковій системі

Коефіцієнт стиску: 11/8

Варіант 3 (6 біт RLE)

В алгоритмі ознакою лічильника є дві одиниці у двох старших бітах. Відповідно 6 біт, які залишились, використовуються на сам лічильник, який може приймати значення від 0 до 63.

Схема алгоритму.

Послідовність 64 однакових байт стискаємо в 2 байти, тобто стискаємо в 32 рази.

Для того, щоб збільшити кількість інформації в 2 рази потрібно застосувати алгоритм до послідовності в якій всі значення більші за 192, тобто мають дві одиниці у старшому розряді.

Тобто для “найкращої послідовності” з однакових чисел максимальний коефіцієнт стиску – 32, а для “найгіршої послідовності” з усіх різних чисел коефіцієнт стиску – 0.5.

Варіант 4 (7 біт RLE)

Цей варіант алгоритму має більший максимальний коефіцієнт стиску і менше збільшує в розмірі вихідну послідовність.

В алгоритмі ознакою лічильника є одиниця у старшому біті. Відповідно 7 біт, які залишились, використовуються на сам лічильник, який може приймати значення від 0 до 127.

Схема алгоритму.

Тобто для “найкращої послідовності” з однакових чисел максимальний коефіцієнт стиску – 64, а для “найгіршої послідовності” з усіх різних чисел коефіцієнт стиску послідовність збільшується на 1/128.

Варіант 5 (може бути придуманий Вами)

Дата добавления: 2015-08-17