Реферат Архівація і стиснення даних

Тема: Курсовые обзорные

і компресором, на основі вже отриманих символів. Якщо декодировщик виявляє (по префіксу), що надійшов chr-код, він просто копіює symbol у вихідний потік і в словник, пересуваючи потім словник на одну позицію слідом за текстом. Якщо ж вступив ptr-код, декодировщик копіює length символів, починаючи з позиції distance у словнику. Нагадаємо, що distance відраховується від кінця словника до початку. p> Всі характеристики класичного варіанта алгоритму майже цілком визначаються розміром словника | V | і максимальною довжиною рядків у словнику smax (див. Завдання).

Високоефективним виявляється спосіб двоступеневого кодування інформації, коли вихідний потік кодувальника LZ77 надходить на вхід блоку арифметичного кодера (LZARI) або кодера Хаффмена (LZHUF).

Таке можливо, тому що коди length і distance розподілені далеко не випадково і непогано описуються моделлю для монотонних джерел. Дійсно, більш довгі збіги зустрічаються явно рідше коротких, а ймовірність збігу слів на невеликій відстані вище, ніж вірогідність зустріти схоже слово в глибинах словника. Решта після першого проходу коди symbol і раніше підпорядковуються моделі Бернуллі. Подібне рішення, використовуване в архіваторах LHA, ARJ, PKZIP, RAR робить їх одними з найбільш ефективних і популярних в даний момент. br/>

Висновки

АлгорітмСтепень сжатіяСко-ростьПамятьСжатіе без потерьПро-ходиРОВІLZ77 LZSS932Да1ДаРедкоLZHUF LZARI1022Да2ДаРедко

Робота: в реальному масштабі часу і в потоці (крім LZARI, LZHUF).

Основне застосування: універсальний, стиснення текстів (LHA, ICE, ARJ, PKZIP, PAK, LZEXE).

Практична реалізація алгоритму LZ77

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

Лістинг 1. Реалізація алгоритму LZ77 на мові С + +

# define DICBITS 12// Log (DICSIZE)

# define DICSIZE (1 <

# define THRESHOLD 2// Поріг

# define STRBITS 6// Log (STRMAX-THRESHOLD)

# define STRMAX ((1 <