ифрування даних алгоритмом LZW
абораторна робота 3
Мета роботи: вивчення кодування та декодування інформації алгоритмом LZW для стиснення даних.
1. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
1.1. Стиснення даних.
Характерною особливістю більшості типів даних є їх надлишковість. Для людини надлишковість даних часто пов'язана з якістю інформації, оскільки надлишковість, як правило, покращує зрозумілість та сприйняття інформації. Однак, коли мова йде про зберігання та передачу інформації засобами комп'ютерної техніки, то надлишковість відіграє негативну роль, оскільки вона приводить до зростання вартості зберігання та передачі інформації. Особливо актуальною є ця проблема у випадку необхідності обробки величезних обсягів інформації при незначних об'ємах носіїв даних. У зв'язку з цим постійно виникає проблема позбавлення надлишковості або стиснення даних.
Основний принцип, на якому базується стиснення даних, полягає в економічному описі повідомлення, згідно якому можливе відновлення початкового його значення з похибкою, яка контролюється.
Навіщо ж потрібна архівація (стиснення даних) в криптографії? Справа в тому, що в сучасному криптоаналізі, тобто науці про протистояння криптографії, з очевидністю доведено, що ймовірність злому криптосхеми при наявності кореляції між блоками вхідної інформації значно вище, ніж при відсутності такої. А алгоритми стиснення даних за визначенням і мають своїм основним завданням усунення надмірності, тобто кореляцій між даними у вхідному тексті.
На даний час існує величезна кількість програм для стиснення даних, заснованих на декількох основних способах.
Всі алгоритми стиснення даних якісно діляться на:
1) алгоритми стиснення без втрат, при використанні яких дані на приймаючій стороні відновлюються без найменших змін;
2) алгоритми стиснення з втратами, які видаляють з потоку даних інформацію, що не надто сильно впливає на суть даних, або взагалі не сприймається людиною (такі алгоритми зараз розроблені тільки для аудіо- та відео зображень). В криптосистемах, природно, використовується тільки перша група алгоритмів.
Існує два основних методи архівації без втрат:
• алгоритм Лемпеля-Зива (англ. Lempel, Ziv), орієнтований на стиск будь-яких видів текстів, тобто використовує факт неодноразового повторення "слів" - послідовностей байт. Алгоритм Лемпеля-Зива заснований на кореляціях між розташованими поруч символами алфавіту (словами, керуючими послідовностями, заголовками файлів фіксованою структури);
• алгоритм Хаффмана (англ. Huffman), орієнтований на стиск послідовностей байт, не пов'язаних між собою.
Практично всі популярні програми архівації без втрат (ARJ, RAR, ZIP тощо) використовують об'єднання цих двох методів - алгоритм LZH.
Існує багато практичних алгоритмів стиснення даних. Однак, в основі цих методів лежать чотири теоретичних алгоритми: алгоритм RLE (Run Length Encoding); алгоритми групи KWE (KeyWord Encoding); алгоритм Хафмана; сімейство алгоритмів LZ78 (LZW, MW, AP, Y)
В основі алгоритму RLE лежить ідея виявлення послідовностей даних, що повторюються, та заміни цих послідовностей більш простою структурою, в якій вказується код даних та коефіцієнт повторення. В основі алгоритму KWE покладено принцип кодування лексичних одиниць групами байт фіксованої довжини. Результат кодування зводиться в таблицю, утворюючи так званий словник. В основі алгоритму Хафмана лежить ідея кодування бітовими групами. Після частотного аналізу вхідної послідовності символи сортуються за спаданням частоти входження. Чим частіше зустрічається символ, тим меншою кількістю біт він кодується. Результат кодування зводиться в словник, що необхідний для декодування.
Методи стиснення даних групуються в залежності від характеру інформації, що стискається: стиснення символьної інформації (документів), стиснення нерухомих графічних зображень (JPEG) і стиснення рухомих графічних зображень (MPEG). Основним параметром, що характеризує рівень стиснення інформації є коефіцієнт стиснення, який визначається відношенням обсягу не стиснених даних до обсягу стиснених (наприклад 5:1).
етод LZW.
Відомі методи оптимального кодування різнозначними кодами (кодами різної довжини), які базуються на врахуванні різної частоти символів в тексті. Найбільш відомі з них: метод Шеннона-Фано та метод Хаффмана. Ці методи забезпечують достатньо ефективне стиснення без втрат. Для підвищення рівня стиснення даних доцільно перейти від оптимального кодування окремих символів до кодування буквосполучень. Саме таке кодування забезпечує метод LZW. Алгоритм відрізняється високою швидкістю роботи при кодуванні та декодуванні, невибагливістю до пам’яті та простою апаратної реалізації. Недолік – менший коефіцієнт компресії порівняно зі схемою двоступеневого кодування.
• Приклад кодування фрази abbacbbcac
Таблиця 1
| Рядок | Символ | Вихід | Код |
| 1 = A | |||
| 2 = B | |||
| 3 = C | |||
| A | B | 4 = AB | |
| B | B | 5 = BB | |
| B | A | 6 = BA | |
| A | C | 7 = AC | |
| C | B | 8 = CB | |
| B | B | ||
| BB | C | 9 = BBC | |
| C | A | 10 = CA | |
| A | C | ||
| AC |
В результаті отримуємо послідовність: 1 2 2 1 3 5 3 7
• Приклад кодування послідовності: 1 2 2 1 3 5 3 7
Таблиця 2
| Попередній символ послідовності | Новий символ послідовності | Символ | Вихід | Код |
| 1 = A | ||||
| 2 = B | ||||
| 3 = C | ||||
| A | A | |||
| B | B | 4 = AB | ||
| B | B | 5 = BB | ||
| A | A | 6 = BA | ||
| C | C | 7 = AC | ||
| B | BB | 8 = CB | ||
| C | C | 9 = BBC | ||
| A | AC | 10 = CA | ||
В результаті отримуємо послідовність: A B B A C B B C A C
2. ЛАБОРАТОРНЕ ЗАВДАННЯ
1. Ознайомтесь з методом LZW.
2. Для заданого варіанту виконайте кодування заданого тексту
3. Виконайте декодування результуючої послідовності
3. ОФОРМЛЕННЯ ЗВІТУ
1. Загальна характеристика методу LZW.
2. Результати кодування та декодування тексту для заданого варіанту.
Варіанти індивідуальних завдань
Стиснути заданий текст методом LZW. Показати як відновлюється початковий текст.
м-41
| Варіант 1 | ЛІМПОПОНАПОПОНІ |
| Варіант 2 | АНАШАНАШАНАШАФІ |
| Варіант 3 | ГАННАНАНАГАНІАНА |
| Варіант 4 | ТАНАНАКАНАНАКАНА |
| Варіант 5 | ПОПОНАНАПОПОНІПО |
| Варіант 6 | МОМОНОМАМОМАНО |
| Варіант 7 | НООНОТОПОТОТОПООП |
| Варіант 8 | ЛАЛАМЕЛАМЕЛАЛАМЕ |
| Варіант 9 | ВАЛАВАЛЕВАЛЕЛЕВА |
| Варіант 10 | КАЛЕВАЛАВАЛКАКЕКЕВ |
| Варіант 11 | РАДОГОМУДОРОДОГАДО |
| Варіант 12 | НАПАВАПАНАВАНАПА |
| Варіант 13 | ЛОЛОВАВАЛОВАВАЛОЛО |
| Варіант 14 | ТАТАМІМІТАТАМІТАТА |
| Варіант 15 | ЖОЖОБАБАЖОЖОЖОБА |
| Варіант 16 | АМАМАЛАМАЛОМАМАЛИ |
| Варіант 17 | ВАКАРОРОКАВАКАРОВА |
| Варіант 18 | НАНАГАГАНАГАНАНА |
| Варіант 19 | ШАНАНАШАШААШАНА |
| Варіант 20 | ШАКАЛКАЛАШЛАШКА |
| Варіант 21 | КАЛАННАЛАКЛАККАЛА |
| Варіант 22 | ВАДАДАВАЛАВАЛАДА |
| Варіант 23 | ЕГЕРРЕГЕНТЕНТРЕГЕГЕ |
| Варіант 24 | УЛУКАНКАНЛУКАНАЛУК |
| Варіант 25 | ПРОРОПОРОПРОПОРОПО |
| Варіант 26 | ДОДОРОДОРОДОДОРОДО |
| Варіант 27 | БОБАРОРОБАБАРОБОРОБА |
| Варіант 28 | НОГОРОРОГОНООРОГОНОР |
| Варіант 29 | ШОШОКАНКАНОШОКАНК |
| Варіант 30 | ЦАЦАПЕЦАПЕПЕЦАПЕЦАП |
| Варіант 31 | РЕРУПЕУЕРЕПРЕРУПРРЕР |
| Варіант 32 | ЛАКЛАККАЛАКАЛАННА |
м-42
| Варіант 1 | УНЛАКУНУЛАКАЛАКУНК |
| Варіант 2 | ЛУВУЛКУКОКОКУЛОВУВ |
| Варіант 3 | УМУУЛЕМИММУЛИМУУЛУ |
| Варіант 4 | ТУНУНУКУНУНУКУНУУТ |
| Варіант 5 | ПЕПЕНУНУПЕПЕНИПЕН |
| Варіант 6 | МЕМЕНЕМУМЕМУНЕ |
| Варіант 7 | НЕЕНЕТЕПЕТЕТЕПЕЕП |
| Варіант 8 | ЛУЛУМОЛУМОЛУЛУМОМ |
| Варіант 9 | ВУЛУВУЛОВУЛОЛОЛУЛО |
| Варіант 10 | УНУШУНУШУНУШУФІ |
| Варіант 11 | ГУННУНУНУГУНІУНУ |
| Варіант 12 | ВУКУРЕРЕКУВУКУРЕВУ |
| Варіант 13 | НУНУГУГУНУГУНУНУ |
| Варіант 14 | ШУНУНУШУШУУШУНУ |
| Варіант 15 | ШУКУЛКУЛУШЛУШКУ |
| Варіант 16 | КУЛУННУЛУКЛУККУЛУ |