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

KWE

Обратимость сжатия

Несмотря на изобилие алгоритмов сжатия теоретически существует 3 способа уменьшения их избыточности:

- изменение содержания данных

- изменение их структуры

- и то и другое вместе

Если при сжатии данных происходит изменение их содержания, то метод сжатия необратим и при восстановлении данных из сжатого файла не происходит полного восстановления. Такие методы называют методами сжатия с регулируемой потерей информации. Они применимы только для тех типов данных, для которых формальная утрата части содержания не приводит к значительному снижению потребительских свойств (видео-файлы, музыкальные записи).

Методы сжатия с потерей информации обычно обеспечивают гораздо более высокую степень сжатия, чем обратимые методы, но их нельзя применять к текстовым данным к базам данных и т.д.

Если при сжатии данных происходит изменение только их структуры, то метод сжатия обратим. Обратимые методы применяют для сжатия любых типов данных.

Степень сжатия - это отношения размера исходного файла к размеру упакованного файла. Характеризуется коэффициентом Kc, отражающим отношение объема сжатого файла, к объему конечного файла:

Kc=Vc/Vu *100%

RLE - в основу этого алгоритма положен принцип выявления повторяющихся Последовательностей данных и замены их простой структурой, в которой указывается код данных и коэффициент повтора

Ex: 0,0,0,127,127,0,255,255,255,255

Значение. Код повтора

0. 3

127. 2

0. 1

255. 4

Ex: 0,3,127,2,0,1,255,4 Vc= 8 байт

Лучшими объектами для данного алгоритма лучше всего графические данные, где большие участки кодируются длинными последовательностями одинаковых байтов, для текстовых документов этот алгоритм не эффективен.

В основу этого алгоритма по ключевым словам положено кодирование лексических единиц исходного документа группами байтов фиксированной длины.

Результат кодирования сводится в таблицу, которая прикладывается к результрующему коду и представляет собой словарь. Обычно для англоязычных текстов принято использовать буквальную кодировку слов. Эффективность данного метода существенно зависит от длины документа.

В основе алгоритма лежит кодирование не байтами, а битами.

1. Перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся символов

2. Чем чаще встречается то или иной символ, тем меньшим количеством битов он кодируется

3. Образующиеся в результате кодирования иерархическая структура прикладывается к сжатому документу в качестве таблицы соответствия.

Пример

1бит. А - 1

2бит. О - 01

4бит. Е - 00 10. Т - 00 11

6бит. С - 000100. И- 000101. К - 000110. Р- 000111

Всего: 256 значений

Дата добавления: 2014-01-04