Главная | Обратная связь

Понятие о сжатии информации. Методы и алгоритмы сжатия.

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

Текст. Каждому символу соответствует двоичный код. ASCII- код фиксированной длины, где каждому символу присваивается 8-битовая последовательность. Код фикс длины явл. избыточным, т к он присваивает каждому символу одно и то же число бит (восемь). Чтобы удалить такую избыточность, используют код переменной длины, в котором короткие коды присваиваются буквам, встречающимся чаще, а редко встречающимся буквам достаются более длинные коды. Так работает кодирование Хаффмана.

Графика. Цифровое изображение – это прямоугольная матрица окрашенных точек, называемых пикселями. Каждый пиксель представляется в компьютере с помощью цветового кода. Для упрощения цифровой обработки изображений предполагается, что все пиксели имеют один и тот же размер. Размер пикселя зависит от числа цветов в изображении, которое, обычно, является степенью 2. Если в нем содержится 2^к разных цветов, то каждый пиксель – это А-битовое число.

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

Эффективность компрессии определяется прежде всего количеством избыточности.

Методы сжатия: 1)Метод неадаптивногосжатия подразумевает неспособность алгоритма менять свои операции, параметры и настройки в зависимости от сжимаемых данных. Лучше всего сжимает однотипные данные. Они специально разработаны для сжатия в факс-машинах и слабо работают на других типах данных. 2) Адаптивныеметоды сначала тестируют исходные данные, а затем подстраивают свои параметры и операции в соответствии с результатом проверки. 3) Полу адаптивны. Исп. двухпроходные алгоритмы: на первом проходе по файлу собирается некоторая статистика сжимаемых данных, на втором проходе происходит непосредственно сжатие с использованием параметров, вычисленных на первой стадии. 4) Локально адаптивные.Алгоритм способен настраивать свои параметры исходя из локальных особенностей файла и менять их, перемещаясь от области к области входных данных.

Типы сжатия:

1)Без потерь/с потерями. К тексту применим только первый тип. Но, если текстовый файл содержит исходный код компьютерной программы, то из него можно удалить большинство пробелов, а также можно удалить информацию о шрифтах, если того захочет автор.

2)Симметричное/ассиметричное.Первый тип: кодер и декодер используют один и тот же базовый алгоритм, но в противоположных направлениях. Второй: у кодера и декодера алгоритмы разные. А)Компрессия делается долго и тщательно с помощью сложнейшего алгоритма, а декомпрессия делается быстро и просто: архивы, создание и прослушивание аудиофайлов формата mрЗ. Б)Обратный случай: внешние файлы часто меняются и сохраняются в виде резервных копий.

Эффективность сжатия определяется несколькими величинами:

1) Принято измерять в bpb/bpp/bpc (бит на бит/пиксель/символ), он показывает, сколько в среднем понадобится бит сжатого файла для представления одного бита/пикселя/символа файла на входе. Выражение 100 X (1 — к), к – коэфф. сжатия, отражает качество сжатия. Его значение равное 60 означает, что в результате сжатия информация занимает на 60% меньше, чем исходный файл.

2) Битовая скорость (bitrate).Целью компрессии информации является представление данных с наименьшей битовой скоростью.

3) Битовый бюджет (bit budget) означает некоторый довесок к каждому биту в сжатом файле. Например, в файл, в котором 90% размера занимают коды переменной длины, соответствующие конкретным символам исходного файла, оставшиеся 10% , которые используются для хранения некоторых таблиц, которые будут использоваться декодером при декомпрессии, составляют битовый бюджет.

4) Величина, обратная коэффициенту сжатия, называется фактором сжатия:

< 1 - сжатие, >1 – расширение. Чем больше значение коэффициента, тем лучше компрессия.