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

Характерною особливістю більшості типів даних є їх надлишковість. Для людини надлишковість даних часто пов'язана з якістю інформації, оскільки надлишковість, як правило, покращує зрозумілість та сприйняття інформації. Однак, коли мова йде про зберігання та передачу інформації засобами комп'ютерної техніки, то надлишковість відіграє негативну роль, оскільки вона приводить до зростання вартості зберігання та передачі інформації. Особливо актуальною є ця проблема у випадку необхідності обробки величезних обсягів інформації при незначних об'ємах носіїв даних. У зв'язку з цим постійно виникає проблема позбавлення надлишковості або стиснення даних.
Основний принцип, на якому базується стиснення даних, полягає в економічному описі повідомлення, згідно якому можливе відновлення початкового його значення з похибкою, яка контролюється.
Метою даної роботи є знаходження такого способу архівації, який дозволить досягти ефективного стиснення даних і мінімізувати втрату інформації при відновленні.
Існує багато практичних алгоритмів стиснення даних [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 0 0 0 0 1 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 1 0 0 0 0
Позначимо кожен символ 8 бітами Галуа. Кожен наступний символ будемо позначати бітами попереднього, зсунутого вліво на 1 біт. Комбінацію тих літер, що зустрічаються часто розташуємо поруч. Тепер замість кожного символу тексту запишемо відповідні 8 біт коду. Якщо наступний символ тексту відповідає наступному символу кодової таблиці, то запишемо відповідний біт, в ішому випадку – інвертований біт Галуа. Розглянемо фрагмент кодової таблиці:
Caps Lock | к | а | й | м | о | в | і | р | н | я | с | у | т | е | д | о | є | ї | л | ь
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
Слово ймовірність буде зашифровано наступним чином:
й | м | о | в | і | р | н | і | c
1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1
т | ь
0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0
Дане слово займає 88 біт пам’яті. Після упаковки його за допомогою послідовності Галуа воно займатиме 51 біт. Отже Кс=1,73.
Спробуємо упакувати заданий текст згідно методу і оцінити коефіцієнт стиснення.
До моменту стиснення текст займав 2354 біт. Після стиснення – 1929. Коефіцієнт стиснення дорівнює:
Кс=2354/1929=1,22.
Якщо попробувати упакувати цей самий текст за допомогою архіватора PKZIP, то він займатиме 2216 біт, тобто Кс=1,06. Як бачимо, даний метод є доволі ефективним для стиснення текстових даних.
Висновки
В даній статті запропоновані нові методи стиснення даних на основі рандомізації та в базисі Галуа, які дозволяють в значній мірі зменшити об’єми інформації, що зберігаються, обробляються або передаються, мінімізувати втрату інформації при відновленні. Кожен з цих методів має свою сферу застосування, де він дозволяє досягти високого коефіцієнту стиснення.
Література
1. Кричевский Р.Е Сжатие и поиск информации. – М.: Радио и связь, 1989.-168с.
2. Lazarowych I.M., Nikolaychuk J.M. Method of randomization and its application for adaptive data compression // Proc. of Second IEEE International Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Application IDAACS‘2003 – Lviv, Ukraine, 2003. P.362-364.
3. Яцків Н.Г., Николайчук Я.М. Методи стиснення даних в багатоканальних системах на основі кодів Галуа // Вісник національного університету «Львівська політехніка» Радіоелектроніка та телекомунікації. – 2002.- №443. – С.135-138.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать