Найпростіші алгоритми стиснення RLE та LZ77
Тому метою даної статті є дати уявлення про найпростіші алгоритми стиснення тим, кому знання та досвід поки що не дозволяють відразу розуміти більш професійну літературу, або чий профіль і зовсім далекий від подібної тематики. Тобто. я «на пальцях» розповім про найпростіші алгоритми і наведу приклади їх реалізації без кілометрових лістингів коду.
Відразу попереджу, що я не розглядатиму подробиці реалізації процесу кодування і такі нюанси, як ефективний пошук входжень рядка. Стаття торкнеться лише самих алгоритмів та способів представлення результату їхньої роботи.
RLE - компактність однаковості
Приклад реалізації
Припустимо, ми маємо набір деяких цілих коефіцієнтів, які можуть набувати значення від 0 до 255. Логічно ми дійшли висновку, що розумно зберігати цей набір як масиву байт:
Для багатьох набагато звичніше бачитиме ці дані у вигляді hex-дампа: 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 для цього підійде дуже доречно!
Закодуємо наші дані, використовуючи свіжоотримані знання: 6×0, 4, 2, 0, 7×4, 4×80, 0, 4×2, 5×255, 2×0.
Настав час якось уявити наш результат у зрозумілому комп'ютері вигляді. Для цього, в потоці даних ми повинні якось відокремлювати одиночні байти від ланцюжків, що кодуються. Оскільки весь діапазон значень байта використовується нашими даними, то просто виділити якісь діапазони значень під наші цілі не вдасться.
Є як мінімум два виходи із цієї ситуації:
- Як індикатор стисненого ланцюжка виділити одне значення байта, а у разі колізії з реальними даними екранувати їх. Наприклад, якщо використовувати в «службових» цілях значення 255, то при зустрічі цього значення у вхідних даних ми будемо змушені писати «255, 255» і після індикатора використовувати максимум 254.
- Структурувати закодовані дані, вказуючи кількість не тільки для повторюваних, а й наступних одиночних елементів. Тоді ми заздалегідь знатимемо, де які дані.
Перший спосіб у нашому випадку не здається ефективним, тому, мабуть, вдамося до другого.
Отже, тепер у нас є два види послідовностей: ланцюжки одиночних елементів (на зразок «4, 2, 0») та ланцюжки однакових елементів (на зразок «0, 0, 0, 0, 0, 0»). Виділимо в «службових» байтах один біт під тип послідовності: 0 одиночні елементи, 1 однакові. Візьмемо при цьому, скажімо, старший біт байта.
У 7 бітах, що залишилися, ми будемо зберігати довжини послідовностей, тобто. максимальна довжина кодованої послідовності - 127 байт. Ми могли б виділити під службові потреби, припустимо, два байти, але вВ нашому випадку такі довгі послідовності зустрічаються вкрай рідко, тому простіше і економічніше просто розбивати їх на більш короткі.
Виходить, у вихідний потік ми писатимемо спочатку довжину послідовності, а далі або одне повторюване значення, або ланцюжок неповторних елементів зазначеної довжини.
Перше, що має кинутись у вічі — за такого розкладу ми маємо парочка невикористовуваних значень. Не може бути послідовностей з нульовою довжиною, тому ми можемо збільшити максимальну довжину до 128 байт, забираючи від довжини одиницю при кодуванні та додаючи при декодуванні. Таким чином, ми можемо кодувати довжину від 1 до 128 замість довжин від 0 до 127.
Друге, що можна помітити, не буває послідовностей однакових елементів одиничної довжини. Тому, від значення довжини таких послідовностей при кодуванні ми будемо віднімати ще один, збільшивши тим самим їх максимальну довжину до 129 (максимальна довжина ланцюжка одиночних елементів, як і раніше, дорівнює 128). Тобто. ланцюжки однакових елементів у нас може мати довжину від 2 до 129.
Закодуємо наші дані знову, але тепер уже й у зрозумілому для комп'ютера вигляді. Записуватимемо службові байти як [TL], де T — тип послідовності, а L — довжина. Будемо відразу враховувати, що довжини записуємо в зміненому вигляді: при T = 0 віднімаємо від L одиницю, при T = 1 - двійку.
[14] , 0, [02] , 4, 2, 0, [15] , 4, [12] , 80, [00] , 0, [12] , 2, [13] , 255, [10] , 0
Спробуємо декодувати наш результат:
- [14]. T=1, отже наступний байт повторюватиметься L+2 (4+2) разів: 0, 0, 0, 0, 0, 0.
- [02]. T=0, отже, просто читаємо L+1 (2+1) байт: 4, 2, 0.
- [15]. T=1, повторюємо наступний байт 5+2 разів: 4, 4, 4, 4, 4, 4, 4.
- [12] . T=1, повторюємонаступний байт 2+2 разів: 80, 80, 80, 80.
- [00]. T=0 читаємо 0+1 байт: 0.
- [12] . T=1, повторюємо байт 2+2 разів: 2, 2, 2, 2.
- [13]. T=1, повторюємо байт 3+2 разів: 255, 255, 255, 255, 255.
- [10]. T=1, повторюємо байт 0+2 разів: 0, 0.
А тепер останній крок: збережемо отриманий результат, як масив байт. Наприклад, пара [14] , упакована в байт, виглядатиме ось так:
У результаті отримуємо таке: 0000: 84 00 02 04 02 00 85 04 82 80 00 00 82 02 83 FF 0010: 80 00
Таким ось нехитрим чином на даному прикладі вхідних даних ми з 32 байт отримали 18. Непоганий результат, особливо якщо врахувати, що на довших ланцюжках він може виявитися набагато кращим.
Можливі покращення
Ефективність алгоритму залежить тільки від власне алгоритму, а й від способу реалізації. Тому для різних даних можна розробляти різні варіації кодування та подання закодованих даних. Наприклад, при кодуванні зображень можна зробити ланцюжки змінної довжини: виділити один біт під індикацію довгого ланцюжка, і якщо він виставлений в одиницю, зберігати довжину і в наступному байті теж. Так ми жертвуємо довжиною коротких ланцюжків (65 елементів замість 129), зате даємо можливість всього трьома байтами закодувати ланцюжки довжиною до 16385 елементів (2 14 + 2)!
Додаткову ефективність можна досягти шляхом використання евристичних методів кодування. Наприклад, закодуємо нашим способом наступний ланцюжок: «ABBA». Ми отримаємо "[00], A, [10], B, [00], A" - тобто. 4 байти ми перетворили на 6, роздмухали вихідні дані аж у півтора рази! І чим більше таких коротких різнотипних послідовностей, що чергуються, тим більше надлишкових даних. Якщо це врахувати, то можна було бзакодувати результат як «[03], A, B, B, A» — ми витратили б лише один зайвий байт.
LZ77 - стислість у повторенні
Приклад реалізації
Спробуємо тепер щось закодувати. Згенеруємо для цього якийсь відповідний рядок (заздалегідь вибачаюсь за її безглуздість):
«The compression and the decompression leave an impression. Hahahahaha!»
Ось як вона виглядатиме в пам'яті (кодування ANSI): 0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20 The compression 0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65 and the decompre 0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69 ssion leave an i 0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 mpression. Hahah 0040: 61 68 61 68 61 21 ahaha!
Ми ще не визначилися з розміром вікна, але умовимося, що він більший за розмір кодованого рядка. Спробуємо знайти всі ланцюжки символів, що повторюються. Ланцюжком вважатимемо послідовність символів довжиною більше одиниці. Якщо ланцюжок входить до складу більш довгого ланцюжка, що повторюється, будемо його ігнорувати.
The compression and t [he] de [compression] leave [an] i [mpression] . Hah [ahahaha]!»
Для більшої наочності подивимося на схему, де видно відповідності повторюваних послідовностей та їх перших входжень:
Мабуть, єдиним неясним моментом тут буде послідовність "Hahahahaha!", адже ланцюжку символів "ahahaha" відповідає короткий ланцюжок "ah". Але тут немає нічого незвичайного, ми використовували деякий прийом, що дозволяє алгоритму іноді працювати як описаний раніше RLE.
Справа в тому, що при розпакуванні ми зчитуватимемо зі словника вказану кількість символів. Оскільки вся послідовність періодична, тобто. дані в нійповторюються з деяким періодом, і символи першого періоду будуть прямо перед позицією розпакування, то з них ми можемо відтворити весь ланцюжок цілком, просто копіюючи символи попереднього періоду наступного.
Із цим розібралися. Тепер замінимо знайдені повтори посилання у словник. Записуватимемо посилання у форматі [PL], де P — позиція першого входження ланцюжка в рядку, L — її довжина.
«The compression and t [223] de [512] leave [163] i [87] . Hah [617] !»
Але не варто забувати, що ми маємо справу зі ковзним вікном. Для більшого розуміння, щоб посилання не залежали від розміру вікна, замінимо абсолютні позиції на різницю між ними та поточною позицією кодування.
«The compression and t [203] de [2212] leave [283] i [427] . Hah [27] !»
Тепер нам достатньо відібрати P від поточної позиції кодування, щоб отримати абсолютну позицію в рядку.
Настав час визначитися з розміром вікна і максимальною довжиною фрази, що кодується. Оскільки ми маємо справу з текстом, рідко коли в ньому зустрічатимуться особливо довгі послідовності, що повторюються. Тож виділимо під їхню довжину, скажімо, 4 біти — ліміту на 15 символів за раз нам цілком вистачить.
Отже, представимо наш закодований текст з урахуванням цих поправок:
«The compression and t [191] de [2110] leave [271] i [415] . Hah [15] !»
Тепер, знову ж таки, нам треба якось відокремити стислі ланцюжки від інших даних. Найпоширеніший спосіб знову використовувати структуру і прямо вказувати, де стислі дані, а де ні. Для цього ми розділимо закодовані дані на групи по вісім елементів (символів або посилань), а перед кожною з таких груп вставлятимемо байт, де кожен біт відповідає типу елемента: 0 для символу та 1 для посилання.
Поділяємо на групи:
Таким чином, якщо при розпакуванні ми зустрічаємо біт 0, то просто читаємо символ у вихідний потік, якщо ж біт 1, ми читаємо посилання, а за посиланням читаємо послідовність зі словника.
Тепер нам залишається лише згрупувати результат у масив байтів. Умовимося, що ми використовуємо біти та байти в порядку від старшого до молодшого. Подивимося, як пакуються в байти посилання на прикладі [191] :
У результаті наш стислий потік виглядатиме так:
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##. Hah 0030: 00 15 00 21 ###!
Можливі покращення
В принципі, тут буде правильно все, що описувалося для RLE. Зокрема, для демонстрації користі евристичного підходу при кодуванні розглянемо наступний приклад:
«The long goooooong. The loooooower bound.»
Знайдемо послідовності лише для слова «loooooower»:
«The long goooooong. The [lo] [ooooo] wer bound.»
Для кодування такого результату нам знадобиться чотири байти на посилання. Проте, більш економічно було б зробити так:
«The long goooooong. The l [oooooo] wer bound.»
Тоді ми б витратили на один байт менше.
Замість ув'язнення
Незважаючи на свою простоту і, здавалося б, не дуже велику ефективність, ці алгоритми досі широко застосовуються в різноманітних областях IT-сфери.
Їх плюс — простота та швидкодія, а на їх принципах та їх комбінаціях можуть бути засновані складніші та ефективніші алгоритми.
Сподіваюся, викладена таким чином суть цих алгоритмів допоможе комусь розібратися в основах та почати дивитисяу бік серйозніших речей.