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

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

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

- метод словарей (разбиение данных на слова и замена их на индексы в словаре)-служит экономией передаваемой информации.

- вероятностные методы (в основе вероятностных методов сжатия (алгоритмов Шеннона-Фано (Shannon Fano) и Хаффмена (Huffman)) лежит идея построения "дерева", положение символа на "ветвях" которого определяется частотой его появления. Каждому символу присваивается код, длина которого обратно пропорциональна частоте появления этого символа)

- математические методы

Алгоритмы делятся на:

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

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

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

Сжатие данных (compression) — алгоритмическое преобразование данных, производимое с целью уменьшения их объёма. Применяется для более рационального использования устройств хранения и передачи данных.

M-метка В- символ 4-счетчик

Выполнять замену имеет смысл только при выгоде ‘МАМВ4СССD’

Легче всего сжимаются черно-белые рисунки, чертежи и схемы.

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

Сжатие данных (compression) — алгоритмическое преобразование данных, производимое с целью уменьшения их объёма. Применяется для более рационального использования устройств хранения и передачи данных.

Message= object ACollection is a part of class TCollection

M|9|A

M-метка 9-адресс А-счетчик(10); счетчик- цифры от 0 до 9 и буквы от A до Z

RATIO=43/49*100%=87.75 (количество символов после сжатия делить на количество символов до сжатия)

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

Сжатие данных (compression) — алгоритмическое преобразование данных, производимое с целью уменьшения их объёма. Применяется для более рационального использования устройств хранения и передачи данных.

Файл(1000 байт: А=100, B=300, C=200, D=300, E=100)

1-направо 0-налево

A=000(3 бита) B=10(2 бита) C=01(2 бита) D=11(2 бита) E=001(2 бита)

3*100+2*200+2*300 +2*300+3*100=2200

RATIO=2200/8*1000

Реальная степень сжатия несколько хуже, так как нужно хранить словарь

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

Сжатие данных (compression) — алгоритмическое преобразование данных, производимое с целью уменьшения их объёма. Применяется для более рационального использования устройств хранения и передачи данных.

Основан на преобразовании сообщения в дробное двоичное число

{A=0,1; B=0,2; C=0,2; D=0,5} message=’BAC’

0,106*2=0,212 0,212*2=0,424 0,424*2=0,848 0,848*2=1,696 0,696*2=1,392 0,392*2=0,784

0,11*2=0,22 0,22*2=0,44 0,44*2=0,88 0,88*2=1,76 0,76*2=1,52 0,52*2=1,4

0,000111-закодированное сообщение