Компрессия данных. Метод Huffman-а

Классифкация алгоритмов компрессии данных.

Неискажающие (loseless) методы сжатия гарантируют, что декодированные данные будут в точности совпадать с исходными;

Искажающие (lossy) методы сжатия (называемые также методами сжатия с потерями) могут искажать исходные данные, например за счет удаления несущественной части данных, после чего полное восстановление невозможно.

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

Второй тип сжатия применяют, в основном, для видео изображений и звука. За счет потерь может быть достигнута более высокая степень сжатия. В этом случае потери при сжатии означают несущественное искажение изображения (звука) которые не препятствуют нормальному восприятию, но при сличении оригинала и восстановленной после сжатия копии могут быть замечены.

Компрессия данных. Метод Running и его модификации.

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

Алфавит = {A…Z} (26 символов)

Message = ”ABBBCCCCCCCDEFG” (15 символов)

Code_message = ”ABBB Х₁ Х₂ Х₃ DEFG”

Х₁ – специальный символ-метка, например, отсутствующий в исходной строке (M), по которому декодировщик узнает, что в этом месте нужно сделать обратную замену.

Х₂ – сам тиражируемый символ (C).

Х₃ – счетчик повторов (должен быть задан символами того же алфавита, в данном примере длина серии ССССССС равна 7, используем 7-й символ алфавита abcdefG) Получается, что при наилучшем раскладе удастся сжать 26 символов до 3.

Code_message = ”ABBB M C G DEFG”

Осталось только передать, какой символ выступает в роли метки. Проще всего добавить его на первое место в сообщении:

Code_message = ”MABBB M C G DEFG” (12 символов)

Ratio = 12/15 *100% = 80% (всегда считаем выгоду)

Компрессия данных. Метод LZW.

История этого алгоритма начинается с опубликования в мае 1977 г. Дж. Зивом (Jacob Ziv) и А. Лемпелем (Abraham Lempel) статьи в журнале "Информационные теории" под названием "IEEE Trans". В последствии этот алгоритм был доработан Терри А. Велчем (Terry Archer Welch) и в окончательном варианте отражен в статье "IEEE Compute" в июне 1984 . В этой статье описывались подробности алгоритма и некоторые общие проблемы с которыми можно столкнуться при его реализации. Позже этот алгоритм получил название - LZW (Lempel - Ziv - Welch).

Алгоритм LZW представляет собой алгоритм кодирования последовательностей неодинаковых символов.

M = "Класс TSuperCollection был порожден от TCollection" (50 символов)

Алфавит явно расширен = {а…яА…Яa…zA…Z…}

В сообщении обнаружен повтор. Закодируем его по схожему принципу:

C = "Класс TSuperCollection был порожден от T Х₁ Х₂ Х₃" (50 символов)

Х₂ – в этот раз данное поле содержит указатель на начало оригинальной серии

(13-я позиция = символ л)

C = "MКласс TSuperCollection был порожден от T M л и" (44 символа)

Ratio = 44/50 *100% = 88%

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

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

Компрессия данных. Метод RLE – класса в двоичной системе. Оптимизация.

Компрессия данных. Метод Huffman-а.

Первоначально, в передаваемом сообщении производится подсчет количества вхождений каждого из символов. На втором шаге происходит построение дерева путем попарного объединения вершин, из которого формируется словарь замен.

Алфавит = {00h…FFh} (256 символов – ASCII)

Message = { A=10 ; B=40 ; C=30 ; D=20 } (длина = 100 символов)

В задачах исходное сообщение может задаваться уже в виде набора символов и подсчитанных для них количеств вхождений. Тогда производить компрессию и записывать Code_message не нужно, достаточно лишь подсчитать Ratio.

Начинаем строить дерево Хаффмана: на каждом шаге ищем 2 свободные вершины, образующие наименьшую суммарную частоту – из них формируем новый узел.

В результате все начальные вершины сходятся к «корню» дерева с суммой 100.

Теперь нужно для каждой начальной вершины закодировать «обратный путь»: начиная от корня, каждый поворот соответствует одному биту: 0 или 1.

A = { влево - влево - влево } = 000 ç СЛОВАРЬ

B = { вправо } = 1

C = { влево - вправо } = 01

D = { влево - влево - вправо } = 001

Поскольку у дерева нет «висящих» ветвей, код получается полным.

Расчет компрессии: