Сетевые информационные технологии. Сжатие без потерь

Август 4, 2022

Главная
Информатика
Сетевые информационные технологии. Сжатие без потерь

Содержание

2. Сжатие без потерь Cжатие без потерь (lossless compression). Информация не теряется. Распакованные данные идентичны исходным несжатым
3. Сжатие без потерь Метод подавления нулей (null suppression): BISYNC IBM 3780 Передатчик сканирует данные в поиске
4. Сжатие без потерь Групповое кодирование : Обобщение метода подавления нулей и применяется для сжатия повторяющихся данных
5. Сжатие без потерь 0000000000 0000000000 0001111000 0001001000 0001111000 0000001000 0000001000 0001111000 0000000000 0000000000 Длина равна 100
6. Сжатие без потерь Факсимильное сжатие: Страница, отсканированная с разрешением 200 пел (белых или черных точек на
7. Сжатие без потерь Модифицированный код Хаффмана: W7, В7, W4, В8, W4, В7, W10 ITU-T: 1728 точек
8. Сжатие без потерь Арифметическое кодирование. Основная концепция. H(X) - энтропия множества символов X, E[L] – средняя
9. Сжатие без потерь Арифметическое кодирование. Основная концепция. Таким образом, существует способ повышения эффективности алгоритма сжатия. Если
10. Сжатие без потерь Арифметическое кодирование. Основная концепция.
11. Сжатие без потерь Арифметическое кодирование. Основная концепция. Теперь результату каждого сообщения поставлен в соответствие интервал, пропорциональный
12. Сжатие без потерь Чистое арифметическое кодирование: БАЗОВЫЙ АЛГОРИТМ: Каждый шаг алгоритма начинается с полуоткрытого интервала [L,
13. Сжатие без потерь Арифметическое кодирование : ПРИМЕР1: Пусть имеются два символа, a и b, вероятности которых
15. Скачать презентацию

Слайд 2

Сжатие без потерь
Cжатие без потерь (lossless compression). Информация не теряется. Распакованные

данные идентичны исходным несжатым данным.
Сжатие с потерями (lossy compression). Распакованные данные могут быть приемлемым приближением к исходным несжатым данным.

Слайд 3

Сжатие без потерь
Метод подавления нулей (null suppression):
BISYNC IBM 3780
Передатчик сканирует данные

в поиске строк пробелов и заменяет каждую такую строку двухсимвольным кодом. Код состоит из специального управляющего символа, за которым следует число пробелов в строке. Например, пусть имеется код с символами пробела, обозначенными знаком “b”:
XYZbbbbbQRX
Эта строка заменяется следующей строкой, в которой Sc представляет собой специальный управляющий символ:
XYZSc5QRX
Такая схема позволяет сделать короче все строки из трех и более пробелов.

Слайд 4

Сжатие без потерь
Групповое кодирование :
Обобщение метода подавления нулей и применяется для

сжатия повторяющихся данных любого типа. На рисунке иллюстрируется применение данного метода к символьным данным. Здесь используются следующие обозначения:
Sc — специальный символ, указывающий на то, что за ним следуют сжатые данные;
X — любой повторяющийся символ;
Сс — счетчик символов, то есть количество повторений сжатого символа.
Пример сжатия при групповом кодировании

Слайд 5

Сжатие без потерь
0000000000
0000000000
0001111000
0001001000
0001111000
0000001000
0000001000
0001111000
0000000000
0000000000
Длина равна 100 бит
ДВОИЧНЫЙ КОД:
23W 4B 6W 1B 2W

1B 6W 4B 9W 1B
9W 1B 6W 4B 23W
или
23 4 6 1 2 1 6 4 9 1 9 1 6 4 23
Длина равна 15 символов или 120 бит

ИЗОБРАЖЕНИЕ

Слайд 6

Сжатие без потерь
Факсимильное сжатие:
Страница, отсканированная с разрешением 200 пел (белых или

черных точек на дюйм): 3 740 000 бит (8.5’’ x 11’’ x 40 000 пелов на кв. дюйм)
ISDN (64 Кбит/с) – время передачи ~1 мин.
Два метода сжатия данных без потерь для факсимильной связи:
модифицированный код Хаффмана - группа 3.
модифицированный код READ (Relative Element Address Designate — относительное назначение адресов элементов) - группа 4.

Группа 3. Кодирование черных и белых значений с плотностью в 200 точек на дюйм (гориз.) и 100…200 (верт.). Предполагается, что передача сигнала осуществляется через модем по аналоговой телефонной линии. Передача данных ускоряется в три и более раз по сравнению с группой 2.
Группа 4. Черно-белый цифровой факсимильный стандарт. Эта группа предназначена для использования в цифровых сетях со скоростями до 64 Кбит/с. Стандартизированы разрешения от 200 до 400 точек на дюйм.Время передачи одной страницы сокращено до нескольких секунд по сравнению с несколькими минутами в предыдущих стандартах.

Слайд 7

Сжатие без потерь
Модифицированный код Хаффмана:
W7, В7, W4, В8, W4, В7, W10
ITU-T:

1728 точек на линию
Длина серии N рассматривается как сумма двух слагаемых:
P: строка из 200 черных точек: 64*3 + 8
EOL (End Of Line — конец строки)

Слайд 8

Сжатие без потерь
Арифметическое кодирование. Основная концепция.
H(X) - энтропия множества символов X,

E[L] – средняя длина кода для множества X.
В схеме сжатия без потерь H(X) всегда будет нижней границей объема сжатых данных, так как H(X) определяет среднее количество информации, содержащейся в символьном наборе. Эффективность алгоритма сжатия может быть повышена путем объединения символов и одновременного кодирования блоков по К символов каждый. В результате мы получаем следующее неравенство:

Слайд 9

Сжатие без потерь
Арифметическое кодирование. Основная концепция.
Таким образом, существует способ повышения эффективности

алгоритма сжатия. Если нам нужно отправить сообщение длиной в N символов, мы можем использовать блок длиной N. Таким образом, мы обращаемся с каждым сообщением как с одним из MN возможных результатов, где М представляет собой количество атомарных символов, а N — длину сообщения.
PAAA=0.512, PBAA=0.128,
PAAB=0.128, PBAB=0.032,
PABA=0.128, PBBA=0.032,
PABB=0.032, PBBB=0.032.
Для сообщения с восемью возможными результатами это разумно, но при очень длинных сообщениях использование этого метода приведет к большим вычислительным затратам.

Слайд 10

Сжатие без потерь
Арифметическое кодирование. Основная концепция.

Слайд 11

Сжатие без потерь
Арифметическое кодирование. Основная концепция.
Теперь результату каждого сообщения поставлен в

соответствие интервал, пропорциональный вероятности сообщения. Таким образом, каждый результат может быть представлен двоичным дробным числом, равным некоторой точке на интервале.

Слайд 12

Сжатие без потерь
Чистое арифметическое кодирование:
БАЗОВЫЙ АЛГОРИТМ:
Каждый шаг алгоритма начинается с полуоткрытого

интервала
[L, Н), вначале инициализируемого как [0,1)
Текущий интервал разбивается на подынтервалы по одному для каждого возможного символа. Каждый подынтервал пропорционален вероятности, с которой соответствующий символ встречается в тексте.
Выбирается подынтервал, соответствующий текущему символу. Этот подынтервал становится текущим интервалом.
Если обработано все сообщение, выполняется следующий шаг, если нет, возвращаемся к шагу 1.
Выводится количество битов, достаточное для того, чтобы можно было отличить данный интервал от двух соседних интервалов.
Выводится некий специальный код конца сообщения, чтобы уведомить получателя.

Слайд 13

Сжатие без потерь
Арифметическое кодирование :
ПРИМЕР1:
Пусть имеются два символа, a и b,

вероятности которых зависят от положения в трехсимвольном общении:
Здесь Рr(аi) представляет собой вероятность того, что символ а встретится в i-й позиции сообщения. В данном случае кодируется сообщение «bab».

Сетевые информационные технологии. Сжатие без потерь

Содержание

Сжатие без потерьCжатие без потерь (lossless compression). Информация не теряется. Распакованные

Сжатие без потерьМетод подавления нулей (null suppression):BISYNC IBM 3780Передатчик сканирует данные

Сжатие без потерьГрупповое кодирование :Обобщение метода подавления нулей и применяется для

Сжатие без потерь0000000000000000000000011110000001001000000111100000000010000000001000000111100000000000000000000000Длина равна 100 битДВОИЧНЫЙ КОД:23W 4B 6W 1B 2W

Сжатие без потерьФаксимильное сжатие:Страница, отсканированная с разрешением 200 пел (белых или

Сжатие без потерьМодифицированный код Хаффмана:W7, В7, W4, В8, W4, В7, W10ITU-T:

Сжатие без потерьАрифметическое кодирование. Основная концепция.H(X) - энтропия множества символов X,

Сжатие без потерьАрифметическое кодирование. Основная концепция.Таким образом, существует способ повышения эффективности

Сжатие без потерьАрифметическое кодирование. Основная концепция.

Сжатие без потерьАрифметическое кодирование. Основная концепция.Теперь результату каждого сообщения поставлен в

Сжатие без потерьЧистое арифметическое кодирование:БАЗОВЫЙ АЛГОРИТМ:Каждый шаг алгоритма начинается с полуоткрытого

Сжатие без потерьАрифметическое кодирование :ПРИМЕР1:Пусть имеются два символа, a и b,

Похожие презентации