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

Введение

Основная задача программиста - принять решение о форме представления данных и выборе алгоритмов, применяемых к этим данным. Только тогда выбранная структура программы и данных реализуется на конкретном языке программирования. В связи с этим знание классических методов и приемов обработки данных позволяет избежать ошибок, которые могут возникнуть при разработке программного обеспечения [1].

Объект исследования: классические и современные методы кодирования данных.

Предмет исследования: алгоритм и реализация методов кодирования информации.

Цель: анализ некоторых методов кодирования информации.

Задачи работы:

• дать строгое определение кодирования информации;
• описать процесс сжатия;
• описать общий принцип действия современных методов адаптивного кодирования;
• описать принцип действия алгоритма Хаффмана;
• описать принцип действия алгоритма Гуаццо;
• описать принцип действия алгоритма Гуаццо, примененного к марковским цепям.

Методы исследования: изучение литературных источников, нормативно-правовой базы, изучение технической документации средств кодирования информации.

Виды кодирование данных

Определение кодирования информации

Теория кодирования, как и теория сжатия информации, возникли в начале двадцатого века. Начало развития этих теорий служит цикл научных работ К. Шеннона, вышедших в 1948 году статей. Они заложили основу для дальнейших исследований в этой области [2].

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

Основной моделью, которую изучает теория информации, является модель системы передачи сигнала. В ней: исследуемая информация поступает в кодер источника, от кодера источника проходит в кодер канала, далее – в декодер канала, затем – в декодер источника и, наконец, в приемник передаваемой информации [4]. При этом, при передаче информации из кодер канала к декодеру информация, как правило, зашумляется. Шум может быть довольно разной природы: от лишних, либо неправильно закодированных данных, добавленных алгоритмом кодирования (зависит от выбора метода) до помех, связанных с аппаратными средствами ЭВМ.

В дискретных источниках без памяти на выходе получается последовательность символов фиксированного алфавита. Набор всех различных символов, сгенерированных некоторым источником, называется исходным алфавитом, а количество символов в этом наборе - размером алфавита [5]. К примеру, текст на русском языке генерируется источником с алфавитом из 33 букв, пробелов, знаков препинания и некоторых других специальных символов, используемых при хранения текста.

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

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

Большой интерес представляет двоичное кодирование, то есть кодирование, размер кодового алфавита которого равен 2. В нем, конечная последовательность битов называется кодовым словом, а количество битов в этой последовательности является длиной кодового слова. Одним из самых распространенных примеров является код ASCII (американский стандартный код для обмена информацией), где каждому символу ставит в однозначное соответствие кодовое слово длиной 8 бит.

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

Если , то – кодовое слово. Обратное отображение (если оно существует) называется декодированием.

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

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

существование декодирования;

помехоустойчивость или исправление ошибок при кодировании;

обладает заданной трудоемкостью (например, ограничения на время или объем памяти) и т.д.

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

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

1.2 Сжатие данных

Сжатие данных — это алгоритмическое преобразование данных, которое производится с целью уменьшения занимаемого объёма. Сжатие данных относится к компактному представлению данных, достигаемому избыточностью информации, содержащейся в сообщениях. Большое значение для практического использования имеет неискажающее сжатие, которое позволяет полностью восстановить исходное сообщение. Неискажающее сжатие кодирует сообщение перед передачей или хранением, и после окончания процесса сообщение однозначно декодируется. Это соответствует модели канала без шума (помех).

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

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

Методы, которые позволяют, используя входные данные, изменить модель избыточности заданной информации, называются адаптивными. Неадаптивными назовем узконаправленные методы, применяемые для работы с информацией, обладающей достаточно определёнными статичными характеристиками.

Современные методы сжатия данных основаны на априорных предположениях о структуре исходных данных. Например, кодирование Хаффмана предполагает, что исходные данные состоят из случайно выбранных символов потока, в соответствии с некоторыми статистическими вероятностями [6]. Для определенности, в дальнейшем будем предполагать, что исходные данные будут являться некоторым потоком битов, которые сгенерированы с помощью дискретных цепей Маркова [7]. Подобная модель будет являться довольно общей для того чтобы описать предположения, данные в модели кодирования Хаффмана, модели кодирования по длине прогона и некоторых других часто используемых методов сжатия. В методах Зива-Лемпеля и Клири-Виттена также сделано предположение о том, что для исходных данных существует базовая марковская модель. Было доказано, что кодирование методом Зав-Лемпеля стремится к оптимальному коэффициенту сжатия для достаточно длинных сообщений, задаваемых моделью Маркова [8, 9].

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

Каждое звено в цепи Маркова представляет собой вероятность того, что следующий символ будет нулем или единицей. После использования оценки этой вероятности в описываемой схеме кодирования данных, можно использовать фактический символ для перехода к следующему звену цепи. Это новое звено будет предсказывать, какой будет следующий бит сообщения и так далее. Если оценки вероятности для каждого звена цепи Маркова отклоняются от ½, то их можно считать достаточно точными и их можно использовать как основу для метода сжатия данных. Такой подход, в котором оценки вероятностей используются для управления методом кодирования с минимальной избыточностью, называется арифметическим кодированием [10].

В работах Гуаццо [11] был получен достаточно мощный метод сжатия данных, который является модификацией метода арифметического кодирования и сочетает в себе генерацию цепной модели Маркова. Несмотря на то, что результаты производительности модификации метода сжатия данных Гуаццо похожи на результаты производительности, достижимые с помощью метода Клири и Виттена, метод Гуаццо гораздо проще реализуется, а также требует меньше памяти ЭВМ и потребляет меньше времени процессора.

Методы сжатия данных можно разделить на две группы: статические методы и адаптивные методы. Методы сжатия статических данных предназначены для кодирования определенных источников информации с известной статистической структурой, которая генерирует определенный набор сообщений. Эти методы основаны на знании статистической структуры исходных данных. Наиболее известные методы статического сжатия включают коды Хаффмана, Шеннона, Фано, Гилберта-Мура, арифметический код и другие методы, которые используют известную информацию о вероятностях источника, создающего различные символы или их комбинации.

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

Существует много различных адаптивных методов сжатия данных. Самым известным из них является адаптивный код Хаффмана, код «стопки книг», интервальные и частотные коды, а также методы из класса Лемпеля-Зива.

Адаптивные методы кодирования

Кодирование Хаффмана

Алгоритм кодирования Гуаццо генерирует коды минимальной избыточности, подходящие для дискретных источников сообщений с памятью. Термин «источник сообщений с памятью» используется для описания сообщений, которые были сгенерированы моделью цепей Маркова. На практике сообщения почти всегда демонстрируют некоторую степень совпадения между соседними символами.