Стиск інформації

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

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

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

Метод стиску Лемпеля-Зіва (Lempela-Ziva)

Усі методи та моделі кодування, розглянуті раніше, використовували в якості вхідних даних послідовності символів, в деякому скінченному алфавіті.

В найпростішому випадку можна використати в якості вхідного алфавіту 256 символів вхідного потоку.

Однак ступінь стиснення відносно невелика (до 50% для текстових файлів)

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

Цей метод стиску інформації розробили в 1977р. І він отримав назву LZ77. Цей метод із самого початку показав свою ефективність при відносній простоті кодування і декодування. І на основі цієї ідеї створено ряд інших методів.. Основна ідея полягає у тому, що перше введення, перший розгляд деякого рядка повідомлення запам’ятовується, а друге і наступні введення відповідного рядка повідомлення заміняється на його перше введення – на його перший розгляд. Метод використовує вже опрацьовану частину повідомлення як довідник. Щоб досягнути стиску він робить спробу замінити черговий фрагмент повідомлення на вказівник в вмісті довідника.

Метод використовує біжуче по повідомленню вікно, яке розділено на 2 нерівні частини.

1) велика за розміром- включає вже розглянуту частину повідомлення;

2) значно менша – є буфером, який включає ще не закодовані символи вхідного потоку. Звичайний розмір вікна складає декілька кілобайт, то розмір буфера має 100-200 байт.

Алгоритм шукає в довіднику фрагмент, який співпадає із вмістом буфера.

У випадку коли такого фрагмента(підрядка) не знайдено, до вхідного потоку просто копіюється черговий символ вхідного потоку. Цей алгоритм перетворює один потік вхідних символів на 2 паралельні потоки L (довжина знайденого у словнику підрядка) та D (відстань від нього до вхідного підрядка). Де крім потоків L та D можна застосувати інші способи кодування: Хаффмана, арифметичне кодування RLE і відповідно існує багато модифікацій цього алгоритму.

Метод LZ777 формує коди, які складаються із 3-ох елементів. Зміщення в довіднику відносно його початку підрядка, який співпадає з початком вмісту буфера. ; довжина цього підрядка, перший символ буфера який іде за підрядком.

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

Недоліки:

1) з ростом розміру довідника, швидкість роботи алгоритму кодера зменшується пропорційно його збільшенню .

2) кодування одиночних символів має невелику ефективність