СТИСНЕННЯ ДАНИХ

(словника), яка відображає рядки символів стиснуваного повідомлення в коди фіксованої довжини. Таблиця володіє так званою властивістю передування, тобто для кожної фрази словника, що складається з деякої фрази w і символа К фраза w також міститься в словнику. Якщо всі частинки словника повністю заповнені кодування перестає бути адаптивним (кодування відбувається виходячи з вже існуючих в словнику фраз).

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

Алгоритм Хафмана

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

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

Розглянемо простий приклад, що ілюструє роботу алгоритму Хафмана. Нехай задано текст, в якому літера 'А' входить 10 разів, літера 'B' - 8 раз, 'C'- 6 разів , 'D' - 5 разів, 'E' і 'F' - по 4 рази. Тоді один з можливих варіантів кодування за алгоритмом Хафмана наведений у таблиці 1.

Таблиця 1.

Символ

Частота входження

Бітовий код

A

10

00

B

8

01

C

6

100

D

5

101

E

4

110

F

4

111

Як видно з таблиці 1, розмір вхідного тексту до стиснення рівний 37 байт, тоді як після стиснення - 93 біт, тобто майже 12 байт (без врахування довжини словника). Коефіцієнт стиснення рівний 32%. Алгоритм Хафмана універсальний, тобто його можна застосовувати для стиснення даних будь-яких типів, але він малоефективний для файлів малих розмірів (за рахунок необхідності зберігання словника)

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

Таблиця 2.

Формат стиснення

Операційна система MS DOS

Операційна система Windows

Програма архівування

Програма розархівування

Програма архівування

Програма розархівування

ARJ

Arj. exe

Arj. exe

WinArj. exe

WinArj. exe

RAR

Rar. exe

Unrar. exe

WinRar. exe

WinRar. exe

ZIP

Pkzip. exe

Pkunzip. exe

WinZip. exe

WinZip. exe

 

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

  1. створення нового архіву;
  2. додавання файлів в існуючий архів;
  3. розпакування файлів з архіву;
  4. створення архівів, що саморозпаковуються (self-extractor archive);
  5. створення розподілених архівів фіксованих розмірів для носіїв малої ємності;
  6. захист архівів паролями від несанкціонованого доступу;
  7. перегляд вмісту файлів різних форматів без попереднього розархівування;
  8. пошук файлів і даних всередині архіву;
  9. перевірка на віруси в архіві до розпакування;
  10. вибір та налаштування коефіцієнта стиснення.

 

 

1 2 3