Научные проблемы Интернета (стр. 3 из 5)
Рис. 1.18.
Для полученного дерева выполним движение с корневой вершины к исходным тройкам. При выходе из любого узла помечаем одно из двух ребер «1», а другое – «0» (рис. 1.18). Итак, запомним, что разметка выполняется при движении справа на лево по построенному дереву. Теперь новый код для любой из исходных троек получаем как комбинацию, сопоставляемую пути из корня в данную вершину. Получаем следующее соответствие исходных троек и новых комбинаций:
000 – 11
101 – 10
010 – 001
111 – 010
001 – 001
011 – 000
С учетом нового способа кодировки исходная последовательность (1.17) может быть переписана таким образом:
| 01111101110010001000. | (1.18) |
Длина последовательности (3.18) сократилась в сравнении с длиной (1.17) с 24 бит до 20 бит. Основной принцип кодирования Хаффмана состоит в том, что часто встречаемые комбинации кодируются более короткими последовательностями. Таким образом, общая длина последовательности оценивается как
 , | (1.19) |
где
– число битов в i-ой комбинации, 
– относительная частота встречаемости i-ой комбинации.Было замечено, хотя это и не обязательно верно во всех случаях, что длина кода Хаффмана комбинации
, как правило, не превосходит величину (– 
). Так, в нашем примере относительная частота комбинации 000 составляет 
. Ее код Хаффмана есть 11 (длина этого кода равна 2). Имеем 
(что справедливо).Таким образом, при кодировании Хаффмана результирующую длину кода можно ориентированно записать в виде
 . | (1.20) |
Кодирование Хаффмана модно применять повторно.
Пусть имеется последовательность  . | (1.21) |
Относительная частота символов:
, 
, 
.При арифметическом кодировании последовательность (1.21) заменяется одним единственным числом. Для получения этого числа разобьем интервал [0,1] на подинтервалы:
| [0; 0,25], (0,25; 0,75], (0,75; 1]. | (1.22) |
Заметим, что длина каждого подинтервала соответствует относительной частоте соответствующего символа. Нетрудно сообразить, что первый подинтервал [0; 0,25] соответствует
; подинтервал (0,25; 0,75] – символу 
и (0,75; 1] – символу 
. В последовательности (3.22) первый символ . Ему соответствует интервал [0; 0,25]. Поэтому выбираем этот подинтервал и делим его опять согласно относительным частотам символов: | [0; 0,0625), [0,0625; 0,1875), [0,1875; 0,25]. | (1.23) |
Следующий символ –
. Ему соответствует интервал (0,0625; 0,1875]. Делим его на подинтервалы: | [0,0625; 0,09375), [0,09375; 0,15625), [0,15625; 0,1875]. | (1.24) |
Следующий символ –
. Выбираем второй подинтервал (0,09375; 0,15625]. Делим его на три подинтервала соответственно частотам символов: | [0,09375; 0,109375), [0,109375; 0,140625), [0,140625; 0,15625]. | (1.25) |
Наконец, последний символ –
. Ему соответствует третий интервал. Поэтому в качестве окончательного кода для последовательности (1.21) можно указать любое число из интервала [0,140625; 0,15625]. Например, возьмем 0,15. Итак, последовательность (1.21) кодируется числом 0.15.Чтобы восстановить исходную последовательность, нужно действовать таким образом. Согласно частотам символов составляем исходное разбиение (1.22). Видим, что наш код 0,15 попадает в первый подинтервал [0; 0,25]. Значит первый символ –
. Далее разбиваем интервал [0; 0,25] на три подинтервала (1.23) и смотрим, к какому из них принадлежит наш код 0,15. Теперь этот второй подинтервал, поэтому следующий символ . Далее из представления (1.24) снова выбираем второй подинтервал и символ . Наконец, из (1.25) выбираем символ .Арифметическое сжатие может давать большие последовательности цифр и поэтому его применение ограничивается небольшими последовательностями символов.
Сжатие графических файлов
Сжатие графической информации основано на частичной потере информации. В самом деле, в изображении соседние пиксели (точки) мало различаются по яркости (светимости) и цвету. Особенностью является то обстоятельство, что глаз человека меньше различает именно светимость двух соседних точек. Поэтому модель данных YCbCr в большей степени ориентирована на сжатие, чем модель RGB. Для получения сжатого изображения применяют ортогональные преобразования данных. Ортогональные преобразования выполняют таким образом, чтобы большая часть данных при преобразовании получила маленькие (близкие к нулю значения) и лишь небольшая часть данных оказалась значимой. Затем выполняется квантование (округление данных) так, что малозначимые данные становятся равными 0. Дадим иллюстрацию сказанному. Пусть исходные данные представлены следующей матрицей:
.Возьмем матрицу преобразования:
 . | (1.26) |
Сначала найдем по правилам матричной алгебры произведение
,Затем
 . | (1.27) |
Получим
.В этой матрице доминирует лишь небольшое число элементов. Можно выполнить квантование, например, следующим образом:
.Именно эта операция (квантования) и приводит к потере данных, хотя эта потеря мало отражается на исходных данных. В самом деле, легко восстановить из (3.27) матрицу С:
 . | (1.28) |
и, аналогично,
 . | (1.29) |
С помощью (3.28), (3.29) получим восстановленную приближенную матрицу исходных данных:
.После квантования получим
.Эта последняя матрица очень близка к исходной матрице D (!).
Прежде всего, заметим, что матрица преобразования W должна строится специальным образом. Во-первых, она должна быть ортогональной, что означает, что векторное произведение любых ее двух строк или столбцов равно 0 (а это означает, что строки и столбцы матрицы не зависимы и, следовательно, определитель матрицы отличен от 0). Во-вторых, матрица W подбирается так, что сумма элементов только в первой строке и в первом столбце максимальны; в остальных строках и столбцах суммы элементов равны или близки к 0.
Из соображений, близких к рассмотренным, строится матрица дискретного косинусного преобразования (DCT-матрица), используемая в алгоритме JPEG. Матрица двумерного DCT-преобразования определяется из следующей формулы
 . | (1.30) |
В (3.30)
– значение пикселя в строке x и столбце y квадратной матрицы пикселей размеров 
; 
Матрица одномерного DCT-преобразования использует расчетную формулу