Методи стиснення інформації на основі неадаптивних та адаптивних інформаційних технологій

Вступ

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

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

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

Існує багато практичних алгоритмів стиснення даних [1]. Однак, в основі цих методів лежать три теоретичних алгоритми: алгоритм RLE (Run Length Encoding); алгоритми групи KWE (KeyWord Encoding); алгоритм Хафмана.

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

Методи стиснення на основі рандомізації.

Нехай заданий масив Х з групами однакових відліків (рис. 1).

Рис. 1 Приклад процесу з групами однакових відліків.

Класичний метод адаптивного стиснення полягає в тому, що кодуються тільки “значимі” відліки сигналу, а також їх номери. Відлік вважається значимим, якщо значення наступного не дорівнює значенню поточного [2]. Коефіцієнт стиснення при цьому рівний:

(1)

де N – кількість відліків у вибірці, j – кількість значимих відліків, - розрядність кількості елементів у вибірці, — розрядність коду, А – діапазон квантування, - цілочисельна функція округлення до більшого.

Для послідовності X (рис.1) кількість значимих відліків j=5:

Введемо поняття “групового значимого” відліку – відліку, значення якого відмінне від наступного, і окрім того його значення рівне одному з “значимих” попередніх відліків.

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

Впорядкуємо масив за зростанням (рис.2 а) та закодуємо амплітуду і номер значимих відліків. Позначивши через xa – значимі, xг – групові значимі відліки, послідовність Х можна записати в наступному вигляді:

де , – номера відповідно групових і значимих відліків у початковому неупорядкованому масиві Х,

“0”– означає що за ним слідує номер відліку з амплітудою, значення якої слідує після кожної нової “1”.

На рис. 2 (б) наведено послідовність, яка отримана після стиснення масиву Х розглянутим методом.

а) б)

Рис. 2 Впорядкована (а) та стиснута (б) послідовність X.

В такому випадку коефіцієнт стиснення рівний:

(2)

де na і nг – кількість відповідно “значимих” і “групових значимих” відліків.

Для послідовності Х при застосуванні запропонованого методу стиснення:

На рис. 3 наведено графік значень коефіцієнта стиснення в залежності від кількості “значимих” відліків для класичного методу та методу рандомізації.

Аналіз отриманих залежностей коефіцієнта стиснення представлених на рис. 3 дозволяє зробити висновки: якщо класичний метод стиснення ефективний при кількості значимих відліків j<0.5N, то при застосуванні рандомізації метод ефективний при j<(0.70.9)N в залежності від співвідношення “значимих” і “групових значимих” відліків.

Застосування базису Галуа для стиснення алфавітно-цифрової інформації

Коди Галуа утворюються згідно наступної формули:

Gi+1 = Gi Gi-n

Щоб генерувати коди Галуа треба знати ключ.

Приклад коду Галуа з об’ємом коду V=N [3]:

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

0 | 0 | 0 | 1 | 0 | 1 | 1 | 1

Нехай заданий наступний текст:

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

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

Необхідно 255 біт Галуа, щоб позначити всі літери, цифри та символи, що можуть зустрічатися в текстах. Тому, прогенеруємо послідовність Галуа з ключем 1 0 0 0 1 1 1 0. Отримаємо:

1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 0 1 1