Файл: Методы кодирования данных (Основные понятия.pdf

№ п/п	Кодовое слово	Начальная «стопка»	Преобразования «стопки»
1	0	а1	а3	а3	а4	А4	а3
2	10	а2	а1	а1	а3	А3	а4
3	110	а3	а2	а2	а1	А1	а1
4	111	а4	а4	а4	а2	А2	а2

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

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

При декодировании применяется эта же «стопка книг», оказавшаяся изначально в том же состоянии. Над «стопкой» ведутся эти же преобразования, что и при кодировании. Это гарантирует идентичное восстановление начальной очередности [10, с. 40].

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

Адаптивный код Хаффмана применяется как составная доля во многих методах сжатия данных. В нем кодирование исполняется на базе информации, содержащейся в окне длины W.

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

3.3. Словарные коды класса Lz

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

---

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

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

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

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

По методике организации хранения и розыска слов словарные методы возможно поделить на 2-ве большие группы:

• алгоритмы, осуществляющие поиск слов в какой-нибудь части раньше закодированного текста, именуемой окном;
• алгоритмы, использующие адаптивный словарь, который подключает раньше встретившиеся слова. В случае если словарь заполняется до завершения процесса кодирования, то в кое-каких методах он обновляется (на место ранее встретившихся слов записываются новые), а в кое-каких кодирование длится без обновления словаря.

Алгоритмы класса LZ отличны размерами окна, способами кодирования слов, алгоритмами обновления словаря и т.п. Все обозначенные факторы воздействуют и на свойства данных способов: скорость кодирования, объем требуемой памяти и уровень сжатия данных, всевозможные для различных алгоритмов. Но в целом методы из класса LZ представляют значительное практическое внимание и дают возможность довольно действенно сжимать данные с неизвестной статистикой [10, с. 46].

---

Рассмотрим кодирование с применением скользящего окна.

Выделим главные этапы кодирования сообщения Х=х₁х₂х₃х₄…, которое порождается некоторым источником информации с алфавитом А. Пусть используется окно длины W, т.е. при кодировании символа x_i исходной последовательности учитываются W предыдущих символов:

Вначале происходит поиск в окне символа х₁. Если символ не находится, тогда в качестве кода происходит передача 0 как признак того, что этого символа нету в окне и двоичное представление х₁.

В случае если символ х₁ отыскан, то происходит поиск в окне слова х₁х₂, начинающегося с сего знака. В случае если слово х₁х₂ есть в окне, то происходит поиск слова х₁х₂х₃ , потом х₁х₂х₃х₄ и так далее, до тех пор пока не будет разыскано слово, состоящее из наибольшего числа входящих символов в порядке их появления. В данном случае в качестве кода передается 1 и пара чисел (i, j), показывающая позицию найденного слова в окне (i – номер позиции окна, с которой начинается это слово, j – длина данного слова, позиции в окне нумеруются справа налево). Вслед за тем окно двигается на j символов вправо по тексту и кодирование продолжается.

Для кодирования чисел (i, j) можно использовать рассмотренные раньше коды целых чисел.

Приведем пример. Пускай алфавит источника А={а, b, с}, длина окна W=6. Нужно закодировать начальное сообщение bababaabacabac. (см. рис. 3.3)

Рис. 3.3. Кодирование последовательности bаbаbааbаcаbаc [10, с. 47].

После окончания кодирования 1-ых 6-ти букв окно примет вид bababa.

• Дальше проверяется наличность в окне буквы а. Она найдена, добавляем к ней b, ищем в окне ab. Данная пара имеется в окне, добавляем букву а, делаем поиск аbа. Данное слово есть в окне, добавляется букву с, ищем abac. Данного слова нет в окне, тогда происходит кодирование aba кодовой комбинацией (1,3,3), где 1– признак того, что слово есть в «окне», 3– номер позиции в окне, с которой начинается данное слово, 3 – длина данное слова.
• Далее окно передвигается на три символа вправо и происходит поиск в окне букву с. Ее нет в данном окне, посему кодируется комбинацией (0, «с»), где 0 – признак того, что буквы нет в данном окне, «с» – двоичное представление буквы. Окно передвигается на один символ вправо.
• Производится поиск в окне букву а, она найдена, добавляется к ней b, производится поиск в окне ab. Данная пара есть в окне, добавляется буква а, производится поиск аbа. Данное слово имеется в окне, добавляется буква с, производится поиск аbаc. Это слово имеется в окне, тогда кодируется аbас кодовой комбинацией (1, 4, 4), где 1 – признак того, что слово есть в окне, 4 –номер позиции в окне, с которой начинается данное слово, 4 – длина данного слова [10, с. 48].

---

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

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

Адаптивный код Хаффмана применяется как составная доля во многих методах сжатия данных. В нем кодирование исполняется на базе информации, содержащейся в окне длины W.

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

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

Заключение

В результате нашего исследования мы пришли к следующим выводам:

1. Кодирование целых чисел осуществляется с использованием группы метод кодирования целых чисел Fixed + Variable и Variable + Variable.

В кодах класса Fixed + Variable под запись значения порядка числа дается определенное число бит, а значение порядка числа устанавливает, сколько бит необходимо под запись мантиссы. Для кодирования целого числа нужно проделать с числом две определенные операции: нахождение порядка числа и выделение бит мантиссы (есть возможность сохранять в памяти готовую таблицу кодовых слов).

В кодах класса Variable + Variable в качестве кода числа принимается двоичная очередность, выстроенная последующим способом: ряд нулей (число нулей точно равно значению порядка числа), далее единица как критерий завершения экспоненты неустойчивой длины, далее мантисса переменной длины (как это реализуется в кодах Fixed + Variable).

---

2. При кодировании сообщений является то, что символы сообщения порождаются определенным источником информации. Источник является установленным целиком, в случае если предоставлено вероятностное представление процесса появления сообщений на выходе источника. Данное значит, то что в любой момент времени установлена возможность порождения источником любой очередности символов Р(x₁x₂x₃...x_L), L≥1. Такой источник именуется дискретным вероятностным источником.

Метод оптимального побуквенного кодирования был создан Д. Хаффманом. Оптимальный код Хаффмана имеет минимальную среднюю длину кодового слова между всех побуквенных кодов для предоставленного источника с алфавитом А={a₁,…,a_n} и вероятностями p_i =P(a_i).

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

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

Адаптивный код Хаффмана применяется как составная доля во многих методах сжатия данных. В нем кодирование исполняется на базе информации, содержащейся в окне длины W.

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

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

Список литературы

1. Бахтизин В.В. Технологии разработки программного обеспечения / В.В. Бахтизин. – Минск: БГУИР, 2010. – 267 с.
2. Березкин Е.Ф. Основы теории информации и кодирования / Е.Ф. Березкин. – М.: НИЯУ МИФИ, 2010. – 312 с.
3. Брауде Э. Технология разработки программного обеспечения / Э. Брауде. – СПб.: Питер, 2004. – 655 с.
4. Вернер М. Основы кодирования / М. Вернер. – М.: Техносфера, 2004. – 288 с.
5. Верещагин Н.К. Информация, кодирование и предсказание / Н.К. Верещагин. – М.: ФМОП, МЦНМО, 2012. – 236 с.
6. Витерби А.Д. Принципы цифровой связи и кодирования / А.Д. Витерби. – М.: Радио и связь, 1982. – 536 с.
7. Гагарина Л.Г. Технология разработки программного обеспечения / Л.Г. Гагарина. – М.: Форум, ИНФРА-М, 2008. – 400 с.
8. Кудряшов Б.Д. Теория информации / Б.Д. Кудряшов. – СПб.: Питер, 2009. – 320 с.
9. Кузьмин И.В. Основы теории информации и кодирования / И.В. Кузьмин. – К.: Вища шк., 2000. – 238 с.
10. Курапова Е.В. Основные методы кодирования данных / Е.В. Курапова. – Новосибирск: СибГУТИ, 2010. – 62 с.
11. Ломакин Д.В. Прикладная теория информации и кодирования / Д.В. Ломакин. – Горький: Горьковский политехнический институт, 2015. – 219 с.
12. Мирошниченко Е.А. Технология программирования / Е.А. Мирошниченко. – Томск: ТПУ, 2008. – 124 с.
13. Панин В.В. Основы теории информации. Часть 2. Введение в теорию кодирования / В.В. Панин. – М.: МИФИ, ФГУП ИСС, 2004. – 391 с.
14. Сидельников В.М. Теория кодирования. Справочник по принципам и методам кодирования / В.М. Сидельников. – М.: МГУ, 2006. – 289 с.
15. Хэмминг Р.В. Теория кодирования и теория информации / Р.В. Хэмминг. – М.: Радио и связь, 1983. – 176 с.
16. Штарьков Ю.М. Универсальное кодирование. Теория и алгоритмы / Ю.М. Штарьков. – М.: ФИЗМАТЛИТ, 2013. – 288 с.
17. Цымбал В.П. Задачник по теории информации и кодированию / В.П. Цымбал. – К.: Вища шк., 1992. – 263 с.

---