Реферат: Научные проблемы Интернета

Заметим, что длина каждого подинтервала соответствует относительной частоте соответствующего символа. Нетрудно сообразить, что первый подинтервал [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-преобразования использует расчетную формулу

.

(1.31)

Заметим, что величины