Методи стиснення текстової інформації мають досить довгу історію. В основі алгоритмів стиснення подібної інформації лежить принцип мінімізації надмірності. Фундаментальна теорема Шеннона про кодування джерел говорить, що вартість кодування завжди не менш ентропії джерела, хоча може бути як завгодно близька до неї [1]. Це твердження встановлює теоретичні кордону стиснення даних.
Тут використовується основне поняття теорії інформації - ентропія. яку можна неформально розглядати як міру кількості інформації в повідомленні. Під вартістю кодування розуміється середня довжина кодового слова (в бітах), яка припадає на один символ вихідного тексту. Тоді надмірність кодування дорівнює різниці між вартістю кодування і ентропією вихідного повідомлення в перерахунку на один символ.
Практичний інтерес представляють однопрохідні алгоритми кодування, що стискають не просто файл прямого доступу, а потік. тобто файл, який не допускає позиціонування і перемотування.
Кодування (encoding) має справу з потоком символів у деякому алфавіті, причому частоти появи символів різні. Метою кодування є перетворення потоку символів в потік бітів мінімальної довжини. Це досягається за рахунок зменшення надмірності вихідного потоку шляхом обліку частоти появи символів на вході: довжина коду повинна бути пропорційна інформації, що міститься у вхідному потоці.
Якщо розподіл частот символів відомо, то можна побудувати оптимальне кодування. Завдання ускладнюється, якщо цей розподіл заздалегідь невідомо. У цьому випадку існує два різних підходи.
Другий підхід. використовувати адаптивний кодер (adaptive coder). Ідея полягає в тому, щоб змінювати схему кодування в залежності від вихідних даних. Такий алгоритм однопроходен і не вимагає передачі інформації про використаний кодуванні в явному вигляді. Замість цього декодер, зчитуючи кодований потік, синхронно з кодером змінює схему кодування, починаючи з деякої визначеної. Адаптивне кодування дає більший ступінь стиснення, оскільки враховуються локальні зміни частот. Прикладом є динамічне кодування Хаффмена.
Статична кодування Хаффмена зіставляє вхідним символам, представленим ланцюжками бітів однакової довжини (наприклад, 8-бітовими байтами), ланцюжки бітів змінної довжини. Довжина коду для символу пропорційна (з округленням до цілого) двійковому логарифму його частоти, взятому з негативним знаком. Це кодування є префіксним. що дозволяє легко його декодувати однопрохідним алгоритмом. У префіксному кодуванні код будь-якого символу не є префіксом коду жодного іншого символу. Префіксний код зручно представляти у вигляді двійкового дерева, у якого символи знаходяться в листі, а дуги позначені 0 або 1. Тоді код символу можна задати як шлях від кореня дерева до листа, який містить цей символ.
Приклад 3. Розглянемо реалізацію методу Хаффмана при кодуванні наступного тексту:
THIS IS A SIMPLE EXAMPLE OF HUFFMAN ENCODING.
1. Підрахуємо число повторень кожної літери алфавіту в початковому тексті:
3. Побудова дерева почнемо з самого правого символу в списку. Частоти двох найбільш рідко зустрічаються символів підсумуємо, і результат запишемо, в вузлі дерева, як показано на рис. 1. Початкові частоти стали тепер дітьми нової сумарною частоти. Якщо є більше двох символів з мінімальною частотою повторень, то потрібно просто утворити з них самостійні пари. Якщо є непарна кількість найменших значень частоти будемо об'єднувати непарну величину з наступною найменшою частотою.
У міру продовження процесу побудови дерева діти стають онуками, правнуками - і так до тих пір, поки все дерево не буде закінчено. Загальна кількість символів вихідного тексту буде представлено в вершині отриманого дерева. Таким чином, можна здійснювати ефективну перевірку правильності побудови дерева кодування.
4. Остаточний код Хаффмана для кожного символу вихідного тексту можна отримати, додавши до кожної гілки дерева певний двійковий атрибут. Всі ліві гілки, що виходять з усіх вузлів, будемо позначати 1, а всі праві гілки - 0. Таким чином, код кожної букви можна отримати, переміщаючись по гілках дерева від вершини до цікавить букві і записуючи по порядку виконавчі атрибути гілок. Результати зведемо в таблицю, яку будемо використовувати в якості «словника» при кодуванні і наступному відновленні вихідного тексту:
Отримана таблиця кодування
Наприклад, слово THIS буде кодуватися послідовністю 00010 0110 1100 0111. Загальна довжина коду слова при цьому зменшилася з 32 біт до 17 біт. Для всього пропозиції коефіцієнт стиснення складає 175/352 »0.497.
Для стиснення графічної інформації без втрат знайшов застосування метод групового кодування RLE (Run Length Encoding), суть якого полягає в тому, що файл стискається зображення «витягується» в ланцюжок байт по рядках растра. Саме стиснення в RLE відбувається за рахунок того, що в оригінальному документі зустрічаються ланцюжка однакових байт. Заміна їх на пари <счетчик повторений, значение> зменшує надмірність даних.
Наприклад, послідовність «ААААААА» за допомогою алгоритму RLE буде закодована як «(А, 7)».
В даному алгоритмі ознакою лічильника служать одиниці в двох старших бітах ліченого файлу. Відповідно залишилися 6 біт витрачаються на лічильник, який може приймати значення від 1 до 64. Рядок з 64 повторюваних байтів ми перетворюємо в два байта, тобто стиснемо в 32 рази.
Даний алгоритм реалізований у форматі PCX.
Існує і другий варіант алгоритму, що реалізує метод RLE, який має більший коефіцієнт стиснення. Ознакою повтору в даному алгоритмі є одиниця в старшому розряді відповідного байта. Як можна легко підрахувати, в кращому випадку цей алгоритм стискає файл в 64 рази (а не в 32 рази, як у попередньому варіанті), в гіршому збільшує на 1/128. Середні показники ступеня компресії даного алгоритму знаходяться на рівні показників першого варіанту. Схожа схема компресії використана в якості одного з алгоритмів, підтримуваних форматом TIFF. а також в форматі TGA.
Більш ефективним методом стиснення інформації без втрат є метод Лемпелла-Зива (ЛЗ), названий так на честь двох ізраїльських математиків, які запропонували його в 1977 році. Метод заснований на тому, що в кожному файлі, як правило, зустрічається кілька часто повторюваних довічних комбінацій. Наприклад, в тексті програми на мові програмування високого рівня постійно будуть зустрічатися комбінації символів (а в файлі з текстом - комбінації відповідних байт), що відносяться до операторів, процедур і функцій мови. Очевидно, можна виділити такі комбінації, скласти їх список і відповідно підібрати їм якісь коротші комбінації. Потім замінити довгі комбінації на короткі, а в файл записати таблицю, по якій здійснювалася заміна. Розпакування файлу зводиться до операції замін, зворотних виробленим під час запису.
На практиці для зберігання таблиці використовується хеш-таблиця. що складається з елементів в кількості не меншій, ніж 8192 (2 13). Кожен елемент таблиці містить запис:
<код предыдущей подстроки; добавленный символ; код этой строки> .
Ключ для пошуку довжиною в 20 біт формується з використанням двох перших елементів, збережених в таблиці як одне число (key). Молодші 12 біт цього числа віддані під код, а наступні 8 біт під значення символу.
Як хеш-функції використовується:
Index (key) = ((key >> 12) Å key) 8191,
де >> - побітовий зрушення вправо; Å - логічна операція побітового виключає АБО, - логічне побітовое І.
Прикладом використання методу ЛЗ є графічні формати GIF і TIFF.