1. По полученному распределению вероятностей строится код Хаффмана для алфавита А.
2. Очередная буква кодируется при помощи построенного кода.
3. Окно передвигается на один символ вправо, вновь подсчитываются частоты встреч в окне букв алфавита, строится новый код для очередного символа, и так далее, пока не будет получен код всего сообщения.

Рассмотрим пример адаптивного кодирования с помощью метода Хаффмана для алфавита А={a₁, a₂, a₃, a₄} и длины окна W=6 (см. рис. 5).

Рисунок 5 Кодирование адаптивным кодом Хаффмана

Рассмотрим подробно этапы кодирования сообщения.

При кодировании буквы a₃получаем следующие частоты встреч символов в окне: q(a₁)=3, q(a₂)=1, q(a₃)=1, q(a₄)=1. Тогда вероятности символов алфавита A оцениваются так

Строим код Хаффмана для полученного распределения вероятностей (см. рис. 6 (а)) и кодируем символ а₃ кодовым символом 001.

a)

Символы	Вероятности	Построение кода	Кодовые cлова
а1	1/2	1	1
а2	1/6	1/2 0	01
а3	1/6	1/3	001
а4	1/6		000

б)

Символы	Вероятности	Построение кода	Кодовые слова
а1	1/3	1	1
а2	1/6	1/3 2/3 0	011
а3	1/3		00
а4	1/6		010

в)

Символы	Вероятности	Построение кода	Кодовые слова
а1	1/3	1/2 1	11
а2	0	1/6 0	101
а3	1/2		0
а4	1/6		100

---

Рисунок 6 Построение адаптивного кода Хаффмана

Далее передвигаем окно на один символ вправо и снова подсчитываем частоты встреч символов в окне q(a₁)=2, q(a₂)=1, q(a₃)=2, q(a₄)=1 и оцениваем вероятности:

Строим код на основе полученных оценок вероятностного распределения (см. рис. 6 (б)) и кодируем очередной символ а₃ другим кодовым словом  00. В этом случае частота встречи в окне символа а₃увеличилась, соответственно уменьшилась длина его кодового слова.

Снова передвигаем окно на один символ вправо, подсчитываем частоты встреч символов в окне q(a₁)=2, q(a₂)=0, q(a₃)=3, q(a₄)=1 и оцениваем вероятности:

Строим код на основе полученных оценок вероятностного распределения (см. рис. 6 (в)) и кодируем очередной символ а₂ кодовым словом  101. Таким образом, после кодирования символов a₃a₃a₂ получаем кодовую последовательность 00100101.

• 1. Код «Стопка книг»

Этот метод был предложен Б. Я. Рябко в 1980 году. Название метод получил по аналогии со стопкой книг, лежащей на столе. Обычно сверху стопки находятся книги, которые недавно использовались, а внизу стопки – книги, которые использовались давно, и после каждого обращения к стопке использованная книга кладется сверху стопки.

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

Приведем описание кода на примере алфавита A={a₁,a₂,a₃,a₄}. Пусть кодируется сообщение а₃а₃а₄а₄а₃…

• Символ а₃находится в третьей позиции стопки, кодируется кодовым словом 110 и перемещается на первую позицию в стопке, при этом символы а₁и а₂ смещаются на одну позицию вниз.
• Следующий символ а₃ уже находится в первой позиции стопки, кодируется кодовым словом 0 и стопка не изменяется.
• Символ а₄ находится в последней позиции стопки, кодируется кодовым словом 111 и перемещается на первую позицию в стопке, при этом символы а₁, а₂, а₃ смещаются на одну позицию вниз.
• Следующий символ а₄ уже находится в первой позиции стопки, кодируется кодовым словом 0 и стопка не изменяется.
• Символ а₃ находится во второй позиции стопки, кодируется кодовым словом 10 и перемещается на первую позицию в стопке, при этом символ а₄ смещается на одну позицию вниз.

---

Рисунок 7 Кодирование методом «стопка книг»

Таким образом, закодированное сообщение имеет следующий вид:

110 0   111 0 10 …

а₃ а₃ а₄ а₄ a₃

Рассмотренный метод сжимает сообщение за счет того, что часто встречающиеся символы будут находиться в верхних позициях «стопки книг» и кодироваться более короткими кодовыми словами. Эффективность метода особенно заметна при кодировании серий одинаковых символов. В этом случае все символы серии, начиная со второго, будут кодироваться самым коротким кодовым словом, соответствующим первой позиции «стопки книг».

При декодировании используется такая же «стопка книг», находящаяся первоначально в том же состоянии. Над «стопкой» проводятся такие же преобразования, что и при кодировании. Это гарантирует однозначное восстановление исходной последовательности.

Приведение описание данного алгоритма на псевдокоде.

• 1. Интервальный код

Интервальный код был предложен П. Элиасом в 1987 году. В нем используется окно длины W, т.е. при кодировании символа x_i исходной последовательности учитываются W предыдущих символов:

При кодировании символа x_i определяется расстояние (интервал) до его предыдущей встречи в окне длины W. Обозначим это расстояние (x_i). Если символ есть x_i в окне, то значение (x_i) равно номеру позиции символа в окне. Позиции в окне нумеруются справа налево. Если символа x_i нет в окне, то (x_i) присваивается значение W+1, а x_i кодируется словом, состоящим из (x_i) и самого символа x_i. После кодирования очередного символа окно сдвигается вправо на один символ.

Возьмем описание кода для исходного алфавита A={a₁,a₂,a₃,a₄}, пусть длина окна W=3. Возьмем некоторый префиксный код для записи числа (X_i):

 (хi)	1	2	3	4
σi	0	10	110	111

Пусть кодируется последовательность а₁а₁а₂а₃а₂а₂… (см. рис. 8)

---

1. Сначала символа а₁ нет в окне, поэтому на выход кодера передается 111 и восьмибитовый ASCII-код символа а₁ Затем окно сдвигается на одну позицию вправо.
2. При кодировании следующего символа а₁ на выход кодера передается 0, так как теперь символ а₁ находится в первой позиции окна. Далее окно снова сдвигается на одну позицию вправо.
3. Следующий символ а₂ кодируется комбинацией 111 и восьмибитовым ASCII-кодом символа а₂, так как символа а₂ нет в окне. Окно снова сдвигается на одну позицию вправо.
4. Следующий символ а₃ кодируется комбинацией 111 и восьмибитовым ASCII-кодом символа а₃ , так как символа а₃ нет в окне. Окно снова сдвигается на одну позицию вправо.
5. Следующий кодируемый символ а₂ находим во второй позиции окна и поэтому кодируем комбинацией 10. Окно снова сдвигается на одну позицию вправо.
6. И последний символ а₂ находим во первой позиции окна и поэтому кодируем комбинацией 0. Таким образом, закодированное сообщение имеет следующий вид:

111 а₁ 0 111 а₂ 111 а₃ 10 0

Рисунок 8 Кодирование интервальным кодом

При декодировании используется такое же окно, как и при кодировании. По принятому кодовому слову можно определить, в какой позиции окна находится данный символ. Если поступает код 111, то декодер считывает следующий за ним символ. Каждая декодированная буква полностью включается в окно.

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

• 1. Частотный код

В 1990 году Б. Я. Рябко предложил алгоритм кодирования, использующий алфавитный код Гилберта-Мура, и названный частотным. Частотный код относится к адаптивным методам сжатия с постоянной избыточностью. Средняя длина кодового слова для этого метода определяется только длиной окна, по которому оценивается статистика кодируемых данных, к тому же частотный код имеет достаточно высокую скорость кодирования и декодирования.

Рассмотрим алгоритм построения частотного кода для источника с алфавитом А={a₁, a₂, ..., a_n}. Пусть используется окно длины W, т.е. при кодировании символа x_i исходной последовательности учитываются W предыдущих символов:

---

Возьмем размер окна такой, что W=(2^r  1)·n, где n=2^k  размер исходного алфавита, r, k  целые числа.

Порядок построения кодовой последовательности, следующий:

1. Сначала оценивается число встреч в окне x_i-W...x_i-1 всех букв исходного алфавита. Обозначим эти величины через P(a_j), j=1,…,n
2. P(a_j) увеличивается на единицу и обозначается как
3. Вычисляются суммы Q_i, i=1,…,n

…

1. Для кодового слова символа а_j берется k знаков от двоичного разложения Q_j, где .
2. Далее окно сдвигается на один символ вправо и для кодирования следующего символа алгоритм вновь повторяется.
3. словарные коды класса Lz

Словарные коды класса LZ широко используются в практических задачах. На их основе реализовано множество программ-архиваторов. Эти методы также используются при сжатии изображений в модемах и других цифровых устройствах передачи и хранения информации.

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

Словарные коды интенсивно исследуются и конструируются, начиная с 1977 года, когда появилось описание первого алгоритма, предложенного А. Лемпелом и Я. Зивом. В настоящее время существует множество методов, объединенных в класс LZ-кодов, которые представляют собой различные модификации метода Лемпела-Зива.

Общая схема кодирования, используемая в LZ-методах, заключается в следующем. При кодировании сообщение разбивается на слова переменной длины. При обработке очередного слова ведется поиск ему подобного в ранее закодированной части сообщения. Если слово найдено, то передается соответствующий ему код. Если слово не найдено, то передается специальный символ, обозначающий его отсутствие, и новое обозначение этого слова. Каждое новое слово, не встречавшееся ранее, запоминается, и ему присваивается индивидуальный код.

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

---

Смотрите также файлы

• Методы кодирования данных (Кодирование целых И действительных чисел).pdf

• Особенности семейного воспитания(Семья – основа семейного воспитания).pdf

• Тенденции развития международной валютной системы ( Понятие и сущность международной валютной системы).pdf

• Социальное страхование и его функции (Проблемы и перспективы развития).pdf

• Государственная служба в Российской Федерации: опыт, современное состояние и направления совершенствования (История и опыт государственной службы в Российской Федерации ).pdf