Лидовский. Учебное пособие написано на основе односеместрового 108 часового курса лекций и материалов для практических занятий, используемых автором в учебной работе со

• Название: Учебное пособие написано на основе односеместрового 108 часового курса лекций и материалов для практических занятий, используемых автором в учебной работе со
• Анкор: Лидовский.pdf
• Дата: 20.03.2019
• Размер: 0.89 Mb.
• Имя файла: Лидовский.pdf
• Тип: Учебное пособие; #26169
• Категория: Информатика. Вычислительная техника
• страница: 4 из 11

1 s s
0/ ESC
„
„
1/A
s
2 s
1 s s
0/ ESC
„
„
1/C
s
„
„
1/A
s
3 s
1 s s
0/ ESC
„
„
1/A
s
„
„
2/C
s
4 s
2 s
1 s s
0/ ESC
„
„s
1/B
„
„s
1/A
„
„s
2/C
5 s
2 s
1 s s
0/ ESC
„
„s
1/B
„
„s
1/A
„
„s
3/C
6 s
3 s
1 s s
0/ ESC
„
„s
1/B
„
„s
2/A
„
„s
3/C
7 s s
3/C
7 7e e
4 s
1 s s
0/ ESC
„
„s
1/B
„
„s
3/A
8 s s
4/A
7 7e e
4 s
1 s s
0/ ESC
„
„s
1/B
„
„s
3/C
9 s s
4/A
7 7e e
5 s
2 s s
0/ ESC
„
„s
2/B.
Здесь получится L
1
(ACCBCAAABC) = 4.1 бит/сим.
Упражнение Закодировать сообщение BBCBBC, используя адаптивный алгоритм
Хаффмена с упорядоченным деревом

Упражнение Закодировать сообщения “AABCDAACCCCDBB”, “КИБЕРНЕТИКИ”
и СИНЯЯ СИНЕВА СИНИ, используя адаптивный алгоритм Хафф- мена с упорядоченным деревом. Вычислить длины в битах исходного сообщения в коде ASCII+ и его полученного кода.
Упражнение Распаковать сообщение ’A’0’F’00’X’0111110101011011110100101, полученное по адаптивному алгоритму Хаффмена с упорядоченным деревом, рассчитать длину кода сжатого и несжатого сообщения в битах. Адаптивное арифметическое кодирование
Для арифметического кодирования, как и для кодирования методом
Хаффмена, существуют адаптивные алгоритмы. Реализация одного из них запатентована фирмой Построение арифметического кода для последовательности символов из заданного множества можно реализовать следующим алгоритмом. Каждому символу сопоставляется его вес вначале он для всех равен 1. Все символы располагаются в естественном порядке, например, по возрастанию. Вероятность каждого символа устанавливается равной его весу, деленному на суммарный вес всех символов. После получения очередного символа и постройки интервала для него, вес этого символа увеличивается на 1 (можно увеличивать вес любым регулярным способом 1
1 1
A
[0,
1 4
]
1 4
2 1
1 1
C
[
3 20
,
1 5
]
1 4
5 2
1 2
1
C
[
7 40
,
23 120
]
1 20 6
2 1
3 1
B
[
151 840
,
51 280
]
1 60 7
2 2
3 1
C
[
19 105
,
611 3360
]
1 420 8
2 2
4 1
A
[
19 105
,
913 5040
]
1 1120 9
3 2
4 1
A
[
19 105
,
3041 16800
]
1 5040 10 4
2 4
1
A
[
19 105
,
2787 15400
]
1 16800 11 5
2 4
1
B
[
4013 22176
,
100327 554400
]
1 46200 12 5
3 4
1
C
[
434747 2402400
,
1304249 7207200
]
1 277200 13 5
3 5
1
E
[
9129739 50450400
,
1304249 7207200
]
1 900900 Рис. Заданное множество символов — это, как правило, ASCII+. Для того, чтобы обеспечить остановку алгоритма распаковки вначале сжимаемого сообщения надо поставить его длину или ввести дополнительный символ-маркер конца сообщения. Если знать формат файла для

сжатия, то вместо начального равномерного распределения весов можно выбрать распределение с учетом этих знаний. Например, в текстовом файле недопустимы ряд управляющих символов и их вес можно занулить.
Пример. Пусть заданное множество — это символы A, B, C. Сжимаемое сообщение — ACCBCAAABC. Введем маркер конца сообщения E. Кодирование согласно приведенному алгоритму можно провести согласно схеме, приведенной на рис. Вследствие того, что 2
22
= 4194304
= 0.0010111001010011101101 2
∈
9129739 50450400
,
1304249 7207200
,
code(ACCBCAAABC) = 0010111001010011101101 и) = Поэтому L
1
(ACCBCAAABC) = 2.2 бит/сим. Результат, полученный адаптивным алгоритмом Хаффмена — 4.1 бит/сим, но если кодировать буквы не 8 битами, а 2, то результат будет 2.3 бит/сим. Впервой строчке схемы выписаны суммарные веса символов, а во второй длины текущих отрезков.
Способ распаковки адаптивного арифметического кода почти аналогичен приведенному для неадаптивного. Отличие только в том, что на втором шаге после получения нового кода нужно перестроить разбиение единичного отрезка согласно новому распределению весов символов. Получение маркера конца или заданного началом сообщения числа символов означает окончание работы.
Пример. Распакуем код 0010111001010011101101, зная, что множество символов сообщения состоит из A, B, C и E, причем последний это маркер конца сообщения 2
=
759021 4194304 34

Веса
Длина
Число-код и его интервал Символ B C интервала 1
1 1
759021 4194304
∈ (0,
1 4
)
A
1 4
2 1
1 1
759021 1048576
∈ (
3 5
,
4 5
)
C
1 5
2 1
2 1
649377 1048576
∈ (
1 2
,
5 6
)
C
1 3
2 1
3 1
375267 1048576
∈ (
2 7
,
3 7
)
B
1 7
2 2
3 1
529717 1048576
∈ (
1 2
,
7 8
)
C
3 8
2 2
4 1
5429 393216
∈ (0,
2 9
)
A
2 9
3 2
4 1
16287 262144
∈ (0, 0.3)
A
0.3 4
2 4
1 27145 131072
∈ (0,
4 11
)
A
4 11 5
2 4
1 298595 524288
∈ (
5 12
,
7 12
)
B
1 6
5 3
4 1
240425 262144
∈ (
8 13
,
12 13
)
C
4 13 5
3 5
1 1028373 1048576
∈ (
13 14
, Упражнение Составить адаптивный арифметический код с маркером конца для сообщения. Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива
Методы Шеннона-Фэно, Хаффмена и арифметическое кодирование обобщающе называются статистическими методами. Словарные алгоритмы носят менее математически обоснованный, но более практичный характер.
Алгоритм LZ77 был опубликован в 1977 г. Разработан израильскими математиками Якобом Зивом (Ziv) и Авраамом Лемпелом (Многие программы сжатия информации используют ту или иную модификацию. Одной из причин популярности алгоритмов LZ является их исключительная простота при высокой эффективности сжатия.
Основная идея LZ77 состоит в том, что второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на ее первое вхождение использует уже просмотренную часть сообщения как словарь.
Чтобы добиться сжатия, он пытается заменить очередной фрагмент сообщения на указатель в содержимое словаря использует скользящее по сообщению окно, разделенное на две неравные части. Первая, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, является буфером, содержащим еще незакодированные символы входного потока

Обычно размер окна составляет несколько килобайта размер буфера не более ста байт. Алгоритм пытается найти в словаре (большей части окна) фрагмент, совпадающий с содержимым буфера.
Алгоритм LZ77 выдает коды, состоящие из трех элементов- смещение в словаре относительно его начала подстроки, совпадающей с началом содержимого буфера- длина этой подстроки- первый символ буфера, следующий за подстрокой.
Пример. Размер окна — 20 символ, словаря — 12 символов, а буфера. Кодируется сообщение ПРОГРАММНЫЕ ПРОДУКТЫ ФИРМЫ MICROSOFT”. Пусть словарь уже заполнен. Тогда он содержит строку ПРОГРАММНЫЕ ”, а буфер — строку ПРОДУКТЫ. Просматривая словарь, алгоритм обнаружит, что совпадающей подстрокой будет ПРО, в словаре она расположена со смещением 0 и имеет длину символа, а следующим символом в буфере является Д. Таким образом, выходным кодом будет тройка Д . После этого алгоритм сдвигает влево все содержимое окна на длину совпадающей подстроки и одновременно считывает столько же символов из входного потока в буфер. Получаем в словаре строку “РАММНЫЕ ПРОД, в буфере “УКТЫ ФИР”. В данной ситуации совпадающей подстроки обнаружить не удаться и алгоритм выдаст код У , после чего сдвинет окно на один символ. Затем словарь будет содержать “АММНЫЕ ПРО-
ДУ”, а буфер — “КТЫ ФИРМ. И т.д.
Декодирование кодов LZ77 проще их получения, т.к. ненужно осуществлять поиск в словаре.
Недостатки LZ77:
1) с ростом размеров словаря скорость работы алгоритма-кодера пропорционально замедляется) кодирование одиночных символов очень неэффективно.
Пример. Закодировать по алгоритму LZ77 строку “КРАСНАЯ
КРАСКА”.
СЛОВАРЬ(8)
БУФЕР(5)
КОД
"........"
"КРАСН"
<0,0,’К’>
".......К"
"РАСНА"
<0,0,’Р’>
"......КР"
"АСНАЯ"
<0,0,’А’>
".....КРА"
"СНАЯ "
<0,0,’С’>
"....КРАС"
"НАЯ К"
<0,0,’Н’>
"...КРАСН"
"АЯ КР"
<5,1,’Я’>
".КРАСНАЯ"
" КРАС"
<0,0,’ КРАСНАЯ "
"КРАСК"
<0,4,’К’>
"АЯ КРАСК"
"А...."
<0,0,’А’>
В последней строчке, буква А берется не из словаря, т. кона последняя.
Длина кода вычисляется следующим образом длина подстроки не может быть больше размера буфера, а смещение не может быть больше размера словаря −1. Следовательно, длина двоичного кода смещения будет округленным в большую сторону размер словаря, а длина двоичного кода для длины подстроки будет округленным в большую сторону размер буфера. А символ кодируется 8 битами (например, В последнем примере длина полученного кода равна 9∗(3+3+8) =
126 бит, против 14 ∗ 8 = 112 бит исходной длины строки.
В 1982 г. Сторером (Storer) и Шиманским (Szimanski) на базе был разработан алгоритм LZSS, который отличается от LZ77 производимыми кодами.
Код, выдаваемый LZSS, начинается с однобитного префикса, различающего собственно код от незакодированного символа. Код состоит из пары смещение и длина, такими же как и для LZ77. В LZSS окно сдвигается ровно на длину найденной подстроки или на 1, если не найдено вхождение подстроки из буфера в словарь. Длина подстроки в всегда больше нуля, поэтому длина двоичного кода для длины подстроки — это округленный до большего целого двоичный логарифм от длины буфера.
Пример. Закодировать по алгоритму LZSS строку “КРАСНАЯ
КРАСКА”.
СЛОВАРЬ(8)
БУФЕР(5)
КОД
ДЛИНА КОДА
"........"
"КРАСН"
0’К’
9
".......К"
"РАСНА"
0’Р’
9
"......КР"
"АСНАЯ"
0’А’
9
".....КРА"
"СНАЯ "
0’С’
9
"....КРАС"
"НАЯ К"
0’Н’
9
"...КРАСН"
"АЯ КР"
1<5,1>
7
"..КРАСНА"
"Я КРА"
0’Я’
9
".КРАСНАЯ"
" КРАС"
0’ КРАСНАЯ "
"КРАСК"
1<0,4>
7
"НАЯ КРАС"
"КА..."
1<4,1>
7
"АЯ КРАСК"
"А...."
1<0,1>
7
Здесь длина полученного кода равна 7 ∗ 9 + 4 ∗ 7 = 91 бит и LZSS обладают следующими очевидными недостатками) невозможность кодирования подстрок, отстоящих друг от друга на расстоянии, большем длины словаря) длина подстроки, которую можно закодировать, ограничена размером буфера.
Если механически чрезмерно увеличивать размеры словаря и буфера, то это приведет к снижению эффективности кодирования, т. к. с ростом этих величин будут расти и длины кодов для смещения и длины, что сделает коды для коротких подстрок недопустимо большими.
Кроме того, резко увеличится время работы алгоритма-кодера.
В 1978 г. авторами LZ77 был разработан алгоритм LZ78, лишенный названных недостатков не использует скользящее окно, он хранит словарь из уже просмотренных фраз. При старте алгоритма этот словарь содержит только одну пустую строку (строку длины нуль. Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки в словаре, которая до последнего введенного символа содержала входную строку, и символа, нарушившего совпадение. Затем в словарь добавляется введенная подстрока. Если словарь уже заполнен, то из него предварительно удаляют менее всех используемую в сравнениях фразу.
Ключевым для размера получаемых кодов является размер словаря во фразах, потому что каждый код при кодировании по методу содержит номер фразы в словаре. Из последнего следует, что эти коды имеют постоянную длину, равную округленному в большую сторону двоичному логарифму размера словаря +8 (это количество битв байт- коде расширенного Пример. Закодировать по алгоритму LZ78 строку “КРАСНАЯ
КРАСКА”, используя словарь длиной 16 фраз.
ВХОДНАЯ ФРАЗА
КОД
ПОЗИЦИЯ
(В СЛОВАРЬ)
СЛОВАРЯ
""
0
"К"
<0,’К’>
1
"Р"
<0,’Р’>
2
"А"
<0,’А’>
3
"С"
<0,’С’>
4
"Н"
<0,’Н’>
5
"АЯ"
<3,’Я’>
6
" "
<0,’ ’>
7
"КР"
<1,’Р’>
8
"АС"
<3,’С’>
9
"КА"
<1,’А’>
10
Указатель на любую фразу такого словаря — это число от 0 до для его кодирования достаточно четырех бит.
В последнем примере длина полученного кода равна 10 ∗ (4 + 8) =
120 битам

Алгоритмы LZ77, LZ78 и LZSS разработаны математиками и могут использоваться свободно.
В 1984 г. Уэлчем (Welch) был путем модификации LZ78 создан алгоритм Пошаговое описание алгоритма-кодера.
Шаг 1. Инициализация словаря всеми возможными односимвольными фразами (обычно 256 символами расширенного ASCII). Инициализация входной фразы w первым символом сообщения.
Шаг 2. Считать очередной символ K из кодируемого сообщения.
Шаг 3. Если КОНЕЦ СООБЩЕНИЯ
Выдать код для w
Конец
Если фраза wK уже есть в словаре
Присвоить входной фразе значение Перейти к Шагу 2
Иначе
Выдать код Добавить wK в словарь
Присвоить входной фразе значение Перейти к Шагу Как ив случае с LZ78 для LZW ключевым для размера получаемых кодов является размер словаря во фразах коды имеют постоянную длину, равную округленному в большую сторону двоичному логарифму размера словаря.
Пример. Закодировать по алгоритму LZW строку “КРАСНАЯ
КРАСКА”. Размер словаря — 500 фраз.
ВХОДНАЯ
ПОЗИЦИЯ
ФРАЗА, КОД для w
СЛОВАРЯ
(В СЛОВАРЬ)
ASCII+
0-255
"КР"
0’К’
256
"РА"
0’Р’
257
"АС"
0’А’
258
"СН"
0’С’
259
"НА"
0’Н’
260
"АЯ"
0’А’
261
"Я "ЯК ’
263
"КРА"
<256>
264
"АСК"
<258>
265
"КА"
0’К’
266
"А"
0’А’
39

В этом примере длина полученного кода равна 12 ∗ 9 = 108 битам.
При переполнении словаря, те. когда необходимо внести новую фразу в полностью заполненный словарь, из него удаляют либо наиболее редко используемую фразу, либо все фразы, отличающиеся от одиночного символа.
Алгоритм LZW является запатентованными, таким образом, представляет собой интеллектуальную собственность. Его безлицензионное использование особенно на аппаратном уровне может повлечь за собой неприятности.
Любопытна история патентования LZW. Заявку на LZW подали почти одновременно две фирмы — сначала IBM и затемно первой была рассмотрена заявка Unisys, которая и получила патент. Однако,
еще до патентования LZW был использован в широко известной в мире программе сжатия данных Упражнение Закодировать сообщения “AABCDAACCCCDBB”, “КИБЕРНЕТИКИ”
и СИНЯЯ СИНЕВА СИНИ, вычислить длины в битах полученных кодов, используя алгоритмы (словарь — 12 байт, буфер — 4 байта (словарь — 16 фраз (словарь — 12 байт, буфер — 4 байта (словарь — ASCII+ и 16 фраз).
Упражнение Может ли для первого символа сообщения код LZ78 быть короче кода при одинаковых размерах словарей Обосновать. Для LZW в размер словаря не включать позиции для ASCII+.
16. алгоритмы распаковки данных. Примеры. LZ77, длина словаря — 8 байт (символов. Коды сжатого сообщения 0,0,’К’
0,0,’Р’
0,0,’А’
0,0,’С’
0,0,’Н’
5,1,’Я’
0,0,’ КА ВХОДНОЙ КОД
ПЕЧАТЬ
СЛОВАРЬ
<0,0,’К’>
"К"
".......К"
<0,0,’Р’>
"Р"
"......КР"
<0,0,’А’>
"А"
".....КРА"
<0,0,’С’>
"С"
"....КРАС"
<0,0,’Н’>
"Н"
"...КРАСН"
<5,1,’Я’>
"АЯ"
".КРАСНАЯ"
<0,0,’ ’>
" "КРАСНАЯ "
<0,4,’К’>
"КРАСК"
"АЯ КРАСК"
<0,0,’А’>
"А"
"Я КРАСКА

2. LZSS, длина словаря — 8 байт (символов. Коды сжатого сообщения КР АС Н 1 5,1 Я 0’ ’ 1 0,4 1 4,1 1 0,1 ВХОДНОЙ КОД
ПЕЧАТЬ
СЛОВАРЬ
0 ’К’
"К"
".......К"
0 ’Р’
"Р"
"......КР"
0 ’А’
"А"
".....КРА"
0 ’С’
"С"
"....КРАС"
0 ’Н’
"Н"
"...КРАСН"
1 <5,1>
"А"
"..КРАСНА"
0 ’Я’
"Я"
".КРАСНАЯ"
0 ’ ’
" "КРАСНАЯ "
1 КРАСНАЯ КРАС"
1 <4,1>
"К"
"АЯ КРАСК"
1 <0,1>
"А"
"Я КРАСКА. LZ78, длина словаря — 16 фраз. Коды сжатого сообщения —
0,’К’
0,’Р’
0,’А’
0,’С’
0,’Н’
3,’Я’
0,’ ’
1,’Р’
3,’С’
1,’А’ .
ВХОДНОЙ
ПЕЧАТЬ
ПОЗИЦИЯ
КОД
(СЛОВАРЬ)
СЛОВАРЯ
""
0
<0,’К’>
"К"
1
<0,’Р’>
"Р"
2
<0,’А’>
"А"
3
<0,’С’>
"С"
4
<0,’Н’>
"Н"
5
<3,’Я’>
"АЯ"
6
<0,’ ’>
" "
7
<1,’Р’>
"КР"
8
<3,’С’>
"АС"
9
<1,’А’>
"КА"
10 4. LZW, длина словаря — 500 фраз. Коды сжатого сообщения КРАСНАЯ К 0’А’.
При распаковке нужно придерживаться следующего правила. Словарь пополняется после считывания первого символа идущего за текущим кода, те. из фразы, соответствующей следующему после раскодированного коду, берется первый символ. Это правило позволяет избежать бесконечного цикла при раскодировании сообщений вида где w — фраза, а K — символ. Конкретным примером такого сообщения является любая последовательность трех одинаковых символов,
пары которых ранее не встречались

ВХОДНОЙ КОД
ПЕЧАТЬ
СЛОВАРЬ
ПОЗИЦИЯ СЛОВАРЯ 0’К’
"К"
"КР"
256 0’Р’
"Р"
"РА"
257 0’А’
"А"
"АС"
258 0’С’
"С"
"СН"
259 0’Н’
"Н"
"НА"
260 0’А’
"А"
"АЯ"
261 0’Я’
"Я"
"Я "
262 0’ ’
" "
" К"
263
<256>
"КР"
"КРА"
264
<258>
"АС"
"АСК"
265 0’К’
"К"
"КА"
266 0’А’
"А"
Упражнение Распаковать каждое приведенное сообщение и рассчитать длину кода каждого сжатого сообщения в битах. Сообщение, сжатое LZ77 (словарь 12 байт, буфер — 4 байта, — 0,0,’A’
0,0,’F’
0,0,’X’
9,2,’F’
8,1,’F’
6,2,’X’
4,3,’A’ . Сообщение, сжатое LZSS (словарь — 12 байт,
буфер — 4 байта, — 0’A’ 0’F’ 0’X’ 1 9,2 1 8,2 1 6,3 1 4,4 1 9,1 . Сооб- щеие, сжатое LZ78 (словарь — 16 фраз, — 0,’A’
0,’F’
0,’X’
1,’F’
2,’X’
5,’A’
3,’A’
2,’F’
0,’A’ . Сообщение, сжатое LZW (словарь ASCII+ и 16 фраз, — 0’A’ 0’F’ 0’X’ 256 257 257 0’A’ 258 0’F’
0’F’ 0’A’.
17. Особенности программ-архиваторов
Если коды алгоритмов типа LZ передать для кодирования (адаптивному) алгоритму Хаффмена или арифметическому, то полученный двухшаговый (конвейерный, а не двухпроходный) алгоритм даст результаты сжатия подобные широко известным программам GZIP, ARJ,
PKZIP, Наибольшую степень сжатия дают двухпроходные алгоритмы, которые исходные данные последовательно сжимают два раза, но они работают до двух раз медленнее однопроходных при незначительном увеличении степени сжатия.