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

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

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

Незворотний стискзазвичай має набагато більший ступінь стиснення, ніж кодування без втрат, але допускає деякі відхилення декодованих даних від вихідних. Насправді існує широке коло практичних завдань, у яких дотримання вимоги точного відновлення вихідної інформації після декомпресії перестав бути обов'язковим. Це, зокрема, стосується стиснення мультимедійної інформації: звуку, фото- або відеозображень. Так, наприклад, широко застосовуються формати мультимедійної інформації JPEG і MPEG, в яких використовується незворотний стиск. Необоротне стиск зазвичай не використовується спільно з криптографічним шифруванням, так як основною вимогою до криптосистеми є ідентичність розшифрованих даних вихідним. Однак при використанні мультимедіа-технологій дані, представлені в цифровому вигляді, часто піддаються незворотній компресії перед подачею криптографічної системи для шифрування. Після передачі інформації споживачеві та розшифрування мультимедіа-файли використовуються у стислому вигляді (тобто не відновлюються).

Розглянемо докладніше деякі з найпоширеніших способів оборотного стиснення даних.

Найбільш відомий простий підхід та алгоритм стиснення інформації оборотним шляхом – це кодування серій послідовностей (Run Length Encoding – RLE). Суть методів даного підходу полягає в заміні ланцюжків або серій байтів, що повторюються, на один кодуючий байт -заповнювач і лічильник числа їх повторень. Проблема всіх аналогічних методів полягає лише у визначенні способу, за допомогою якого алгоритм, що розпаковує, міг би відрізнити в результуючому потоці байтів кодовану серію від інших, - не кодованих послідовностей байтів. Вирішення проблеми досягається зазвичай простановкою міток спочатку кодованих ланцюжків. Такими мітками можуть бути характерні значення бітів у першому байті кодованої серії значення першого байта кодованої серії. Недоліком методу RLE є досить низький ступінь стиснення або вартість кодування файлів з малим числом серій і, що ще гірше – з малим числом байтів, що повторюються в серіях.

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

Одними з широко використовуються на практиці є словникові методи, до основних представників яких належать алгоритми сімейства Зіва та Лемпела. Їхня основна ідея полягає в тому, що фрагменти вхідного потоку ("фрази") замінюються покажчиком на те місце, де вони в тексті вже раніше з'являлися. У літературі такі алгоритми позначаються як алгоритми LZ стиску.

Подібний метод швидко пристосовується до структури тексту і може кодувати короткі функціональні слова, оскільки вони часто в ньому з'являються. Нові слова та фрази можуть також формуватися із частин раніше зустрінутих слів. Декодування стисненого тексту здійснюється безпосередньо, – відбувається проста заміна покажчика готовою фразою зі словника, яку той вказує. На практиці LZ-метод досягає хорошого стиску, його важливою властивістю є дуже швидка робота декодера.

Іншим підходом до стиснення інформації є код Хаффмана, кодер та декодер якого мають досить просту апаратну реалізацію. Ідея алгоритму полягає в наступному: знаючи ймовірність входження символів у повідомлення, можна описати процедуру побудови кодів змінної довжини, що складаються з цілої кількості бітів. Символам з більшою ймовірністю присвоюються більш короткі коди, тоді як символи, що рідше зустрічаються, - довші. За рахунок цього досягається скорочення середньої довжини кодового слова та більша ефективність стиснення. Коди Хаффмана мають унікальний префікс (початок кодового слова), що дозволяє однозначно їх декодувати, незважаючи на їх змінну довжину.

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

p(S 1)=0,2, p(S 2)=0,15, p(S 3)=0,55, p(S 4)=0,1. Відсортуємо символи щодо спадання ймовірності появи і подаємо у вигляді таблиці (рис. 14.3, а).

Процедура синтезу коду складається із трьох основних етапів. На першому відбувається згортка рядків таблиці: два рядки, що відповідають символам з найменшими ймовірностями виникнення, замінюються однією з сумарною ймовірністю, після чого таблиця знову переупорядковується. Згортка триває до того часу, поки таблиці не залишиться лише один рядок із сумарною ймовірністю, рівної одиниці ( рис. 14.3 , б).

Мал. 14.3.

На другому етапі здійснюється побудова кодового дерева по згорнутій таблиці (рис. 14.4 а). Дерево будується починаючи з останнього стовпця таблиці.

Корінь дерева утворює одиниця, розташована в останньому стовпці. У прикладі ця одиниця утворюється з ймовірностей 0,55 і 0,45 , зображуваних у вигляді двох вузлів дерева, пов'язаних з коренем. Перший відповідає символу S 3 і, таким чином, подальше розгалуження цього вузла не відбувається.

Другий вузол, маркований ймовірністю 0,45, з'єднується з двома вузлами третього рівня, з ймовірностями 0,25 і 0,2. Імовірність 0,2 відповідає символу S 1 , а ймовірність 0,25 у свою чергу утворюється з ймовірностей 0,15 появи символу S 2 і 0,1 появи символу S 4 .

Ребра, що з'єднують окремі вузли кодового дерева, нумеруються цифрами 0 і 1 (наприклад, ліві ребра – 0, а праві – 1). На третьому, заключному етапі, будується таблиця , у якій зіставляються символи джерела та відповідні кодові слова коду Хаффмана. Ці кодові слова утворюються в результаті зчитування цифр, якими позначені ребра, що утворюють шлях від кореня дерева до символу. Для прикладу код Хаффмана набуде вигляду, показаного в таблиці праворуч (рис. 14.4, б).

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

Інший варіант статичного кодування Хаффманаполягає у перегляді вхідного потоку та побудові кодування на підставі зібраної статистики. При цьому потрібно два проходи по файлу – один для перегляду та збирання статистичної інформації, другий – для кодування. У статичному кодуванні Хаффмана вхідним символам (ланцюжкам бітів різної довжини) ставляться у відповідність ланцюжка бітів також змінної довжини – їх коди. Довжина коду кожного символу береться пропорційною до двійкового логарифму його частоти, взятому зі зворотним знаком. А загальний набір всіх символів, що зустрілися, складає алфавіт потоку.

Існує інший метод – адаптивного або динамічного кодування Хаффмана. Його загальний принцип у тому, щоб змінювати схему кодування залежно від характеру змін вхідного потоку. Такий підхід має однопрохідний алгоритм і не вимагає збереження інформації про використане кодування у явному вигляді. Адаптивне кодування може дати більший ступінь стиснення, порівняно зі статичним, оскільки повніше враховуються зміни частот вхідного потоку. При використанні адаптивного кодування Хаффмана ускладнення алгоритму полягає в необхідності постійного коригування дерева і кодів символів основного алфавіту відповідно до статистики вхідного потоку, що змінюється.

Методи Хаффмана дають досить високу швидкість та помірно гарну якість стиснення. Однак кодування Хаффмана має мінімальну надмірність за умови, що кожен символ кодується в алфавіті коду символу окремим ланцюжком з двох біт (0, 1). Основним же недоліком даного методу є залежність ступеня стиснення від близькості ймовірностей символів до 2 деякою негативною мірою, що пов'язано з тим, що кожен символ кодується цілим числом біт .

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

Передбачувана необхідна послідовність символів при стисканні методом арифметичного кодування розглядається як деякий двійковий дріб з інтервалу)