Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Коды переменной длины

Читайте также:
  1. Dim Имя_Переменной As Тип_Переменной
  2. Аппараты, используемые при определении рабочей длины зуба
  3. Вопрос24.Экстремум функции одной переменной.
  4. Вопрос37. Интегрирование методом замены переменной (подстановкой) и по частям.
  5. Встроенные функции, определенные над данными строковых типов переменной длины
  6. График обработки в приемоотправочном парке транзитного поезда без изменения веса и длины
  7. График обработки в приемоотправочном парке транзитного поезда без изменения веса и длины
  8. Дифференциальное исчисление функции одной переменной.
  9. Дифференцируемые функции одной переменной
  10. Единицы измерения длины двоичного кода сообщений.

Первое правило построения кодов переменной длины, состоит в том, что короткие коды следует присваивать часто встречающимся символам, а длинные – редко встречающимся. При этом коды следует назначать так, чтобы из можно было декодировать однозначно, а не двусмысленно. Например, рассмотрим четыре символа a1, a2, a3, a4. Если они появляются в сообщении с равной вероятностью (p = 0,25), то присвоим им четыре двухбитовых кода: 00, 01, 10, 11. Все вероятности равны, поэтому коды переменной длины не сожмут данные. Для каждого символа с коротким кодом найдётся символ с длинным кодом и среднее число битов на символ будет не меньше 2. Избыточность данных равновероятными символами равна 0, и строку таких символов невозможно сжать с помощью кодов переменной длины (или какого-либо другого метода).

Пусть теперь эти четыре символа появляются с разными вероятностями (см. табл. 12.1). В этом случае имеется избыточность, которую можно удалить с помощью кодов переменной длины и сжать данные так, чтобы потребуется меньше 2 бит на символ. Наименьшее среднее число бит на символ равно 1,57, то есть энтропии этого множества символов.

В таблице 12.1 предложен код Код_1, который присваивает самому часто встречающемуся символу самый короткий код. Среднее число бит на символ равно 1,77. Это число близко к теоретическому минимуму.

Таблица 12.1

Символ Вероятность Код_1 Код_2
a1 0,49
a2 0,25
a3 0,25
a4 0,01

Рассмотрим последовательность из 20 символов

a1 a3 a2 a1 a3 a3 a4 a2 a1 a1 a2 a2 a1 a1 a3 a1 a1 a3 a1,

в которой четыре символа появляются, примерно, с одинаковыми частотами. Этой строке будет соответствовать кодовое слово длины 37 бит:

1|010|01|1|010|010|001|01|1|1|01|01|1|1|010|1|1|01|010|1.

Среднее число бит на символ составляет 1,85, что не слишком далеко от вычисленной минимальной средней длины. Однако если попытаться декодировать последовательность, то окажется, что Код_1 имеет существенный недостаток. Первый бит кодового слова равен 1, поэтому первым символом последовательности может быть только a1, так как код никакого другого символа не начинается с 1. Следующий символ равен 0, но коды для символов a2, a3, a4 все начинаются с 0, поэтому декодер должен считать следующий символ. Он равен 1, но коды для a2 и a3 оба имеют в начале 01. Поэтому декодер не знает, как действовать дальше: декодировать строку как 1|010|01…, то есть a1a3a2…, или как 1|01|001…, то есть a1a2a4.... Дальнейшие биты последовательности не могут исправить положения. Поэтому Код­_1 является двусмысленным. От этого недостатка свободен Код_2.

Код_2 обладает так называемым префиксным свойством, которое можно сформулировать так: если некоторая последовательность битов выбрана в качестве кода какого-либо символа, то ни один код какого-либо другого символа не должен иметь в начале эту последовательность (код символа не может быть префиксом кода другого символа). Если строка 01 является кодом для a2, то другие коды не должны начинаться с 01. Поэтому коды для a3 и a4 должны начинаться с 00. Естественно для этого выбрать 000 и 001.

Следовательно, выбирая множество кодов переменной длины необходимо соблюдать два принципа: 1) следует назначать более короткие кодовые последовательности часто встречающимся символам; 2) полученные коды должны обладать префиксным свойством. Следуя этим принципам можно построить короткие, однозначно декодируемые коды, но необязательно наилучшие (то есть самые короткие) коды. В дополнение к этим принципам необходим алгоритм, который всегда порождает множество самых коротких кодов (имеющих наименьшую среднюю длину). Исходными данными этого алгоритма должны быть частоты (или вероятности) символов алфавита. Таким алгоритмом является кодирование по методу Хаффмана.

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

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

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

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


Дата добавления: 2015-01-05; просмотров: 38 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2020 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав