Алгоритмы сжатия без потерь

Для сжатия без потерь доказаны следующие теоремы:

• 1. Для любой последовательности данных существует теоретический предел сжатия, который не может быть превышен без потери части информации.
• 2. Для любого алгоритма сжатия можно найти такую последовательность данных, для которой он обеспечит лучшую степень сжатия, чем другие алгоритмы.
• 3. Для любого алгоритма сжатия можно найти такую последовательность данных, для которой данный алгоритм вообще не позволит получить сжатия.

Рис. 10.1. Алгоритмы сжатия без потерь

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

Статистические алгоритмы сжатия

Теоретическую основу данных алгоритмов заложил американский ученый Клод Элвуд Шеннон своей теоремой о кодировании для дискретного канала без помех. Статистические алгоритмы сжимают данные с использованием того факта, что частоты встречаемости (в теоретических исследованиях используется понятие вероятность появления) различных символов в сжимаемых данных не одинаковы, следовательно, можно сокращать объем данных присвоением часто встречающимся символам коротких кодов, а редко встречающимся — длинных. Таким образом, количество разрядов для кодирования различных символов будет разным.

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

Последовательность префиксных кодов 1 000 001 101 101 для символов Z = 00, Z₂ =01, Z₃ = 101, Z₄ = 100 декодируется однозначно:

100 00 01 101 101 101 00.

Z₄ Z Z₂ Z3 Z3 Z3 Z1.

Если использовать непрефиксные коды символов Z = 00, Z₂ = 01, Z₃ = 101, Z₄ = 010 (кодовая комбинация 01 является началом комбинации 010), то последовательность 10 101 010 101 может быть декодирована по-разному:

00 01 01 01 010 101.

Z, Z₂ Z₂ Z₂ Z₄ Z3,.

или.

00 010 101 010 101.

Zj Z₄ Z3 Z₄ Z3,.

или.

00 01 010 101 01 01.

Z Z₂ Z₄ Z3 z₂ z₂.

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

Первым статистическим алгоритмом сжатия был алгоритм Шеннона-Фэно. Алгоритм рассмотрен в большом количестве учебников и учебных пособий, но в практике сжатия не используется, т. к. алгоритм нс гарантирует однозначного построения для предложенного набора данных кода, который позволит сжать эти данные наилучшим образом. При кодировании необходимо перебрать все варианты построения кода, чтобы получить наименьший объем сжатых данных.

Широко применяются в практике сжатия данных алгоритм Хаффмана и алгоритм арифметического кодирования, которые формируют префиксные коды.