Page 41 - 6126

той же символ зустрічається кілька разів поспіль. При кодуванні рядок
однакових символів, що становлять серію, замінюється рядком, який
містить сам повторюваний символ і кількість його повторів) встановлений
принцип виявлення послідовностей даних, що повторюються і заміни їх
простою структурою, в якій вказується код даних і коефіцієнт повтору.
Наприклад, для послідовності: 0; 0; 0; 127; 127; 0; 255; 255; 255; 255
(усього, 10 байтів) утвориться наступний вектор:
Коефіцієнт
Значення
повтору
0 3
127 2
0 1
255 4
При записі в рядок він має вигляд: 0; 3; 127; 2; 0; 1; 255; 4 (всього 8 байтів).
У даному прикладі коефіцієнт стиснення рівний 8/10 (80 %).
Ефективність даного методу істотно залежить від довжини документа,
оскільки через необхідність прикладати до архіву словник довжина
коротких документів не тільки не зменшується, але навіть зростає. Даний
алгоритм найбільш ефективний для англомовних текстових документів і
файлів баз даних. Для російськомовних документів, відмінних збільшеною
довжиною слів і великою кількістю префіксів, суфіксів і закінчень, не
завжди вдається обмежитися двобайтними токенами, і ефективність
методу помітно знижується.
В основі алгоритму Хафмана лежить кодування не байтами, а бітовими
групами.
Перед початком кодування проводиться частотний аналіз коду
документа і виявляється частота повтору кожного з символів, що
зустрічаються. Чим частіше зустрічається той або інший символ, тим
меншою кількістю бітів він кодується (відповідно, чим рідше зустрічається
символ, тим довше його кодова бітова послідовність). Ієрархічна
структура, що утворюється внаслідок кодування, прикладається до
стиснутого документа як таблиця відповідності.

Приклад. Закодувати по алгоритму Хафмана повідомлення, що мають
такі ймовірності:

повідомлення 1 2 3 4 5 6 7

ймовірність 0,4 0,2 0,1 0,1 0,1 0,05 0,05
Крок 1.

42