Сжатие числовой информации

Упаковка.

Перекодировка.

Простое алфавитное кодирование.

Алфавитное кодирование и упаковка

Специфичный способ, основанный на том, что в текстовом файле используется только ограниченный набор 8-битовых кодов ASCII. Например, для задания всех букв английского алфавита и знаков препинания может хватить всего 64 символов выходного 6-битного алфавита. При этом размер выходного файла составит 75% от входного. В настоящее время простое алфавитное кодирование используется как предварительный проход перед запуском более серьезной программы сжатия. Подобный алгоритм применяется при сжатии текстовых файлов в архиваторе ARJ.

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

Рассмотрим пример.

Представим, что наш источник с равной вероятностью вырабатывает 6 различных сообщений. Для их кодирования приходит на ум очевидное решение использовать двоичные коды чисел от 0 до 5: 000, 001, 010, 011, 100, 101. Так же очевидно, что стоимость кодирования получилась 3 бита, но энтропия при этом Н₀ = log₂ 6 = 2.585 < 3. Причина в том, что у нас остались неиспользованными 2 кода: 110 и 111.

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

0 - 00 1 - 01 2 - 100 3 - 101 4 - 110 5 - 111.

Стоимость кодирования такого кода равна 2.667, что значительно ближе к энтропии.

Упаковка – процесс сродни укладке чемодана. Множество коробочек разного размера занимают больший объем, чем, если достать из них все вещи и сложить в один чемодан. Если путем изменения местоположения и взаимного расположения носителей информации удается сократить ее объем, то мы и будем считать такой процесс упаковкой. Упаковка отличается исключительной простотой и высокой скоростью работы. Например:

- известно, что файлы на дисках хранятся по секторам. Положим размер сектора равен 512 байтам. Размеры файлов самые разные. Поскольку кластер – минимальная, неделимая единица объема диска то файлы длиной 2 и 508 байт займут один кластер, а файлы размером в 513 и 1001 байт – уже два кластера. Таким образом мы можем потерять до 511 байт дискового пространства.

Такую же процедуру выполняют и современные архиваторы при создании так называемых Solid-архивов, выигрывая на этом несколько процентов в степени сжатия.

Одним из широко известных способов сжатия последовательности цифровых данных (например результатов измерения процесса F(t_i) в дискретные промежутки времени t_i, i=1..N) является аппроксимация. Действительно, вместо передачи длинного набора чисел можно передать лишь набор коэффициентов аппроксимирующего полинома P_j, j=0..K. Степень сжатия в этом случае равна (K+1)/N.

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

А как быть, если требуется передать данные без потерь? И здесь предложенный способ может помочь, стоит его лишь несколько расширить:

Предположим, нам надо передать массив из N чисел, каждое из которых не превышает величины n. При непосредственном представлении для этого потребуется N×élog(n)ù бит. Пусть нам удалось подобрать такой аппроксимирующий полином порядка К, что все погрешности (ошибки отклонения истинного значения от его аппроксимированного варианта) укладываются в диапазон значений k < n. Тогда, как нетрудно подсчитать, после сжатия длина массива составит N élog(k)ù + (K+1) élog(n)ù. При достаточно больших значениях N (N >> K) степень сжатия будет примерно равна

élog(k)ù / élog(n)ù.

Рассмотренный способ особенно эффективно работает для данных, описываемых моделью Маркова 1 порядка, у которых большая часть условных вероятностей сосредоточена вблизи главной диагонали, т.е. p_i,j тем больше, чем меньше разность между i и j. К таким процессам относятся, например, годовые или суточные колебания температуры. Маловероятно, что, если сегодня температура воздуха -20°С, то завтра будет +10. Скорее ожидать -19 или -21.

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

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

Пусть имеется массив размера X·Y, верхняя левая часть которого имеет вид:

	Столб.1							Столб.8
Стр. 1
Стр.6

Если каждое число представлять двумя байтами, то такая матрица займет в памяти 2XY байт. Нельзя ли сократить этот объем? Вместо массива, оказывается, можно хранить только три одномерных вектора. Назовем их FirstInCol (ПервыйВКолонке), Row (Ряд) и Value (Значение)

Длина вектора FirstInCol равна количеству столбцов матрицы, а длины Row и Value- количеству ее непустых элементов (в данном примере - 2000). i -ое число первого вектора FirstInCol показывает, с какой позиции в векторе Row начинаются значения i -го столбца. Числа в Row -номера строк, где находятся соответствующие непустые значения Value. Так, второй столбец содержит два числа - 98 во второй строке и 15 в сто тридцать девятой. При определенных условиях с помощью приведенного метода можно получить существенное снижение объема числовой и прочей информации.

Дата добавления: 2014-12-16