Что такое посимвольное кодирование
Скачай курс
в приложении
Перейти в приложение
Открыть мобильную версию сайта
© 2013 — 2023. Stepik
Наши условия использования и конфиденциальности
Public user contributions licensed under cc-wiki license with attribution required
6. Эффективное посимвольное кодирование для сжатия данных.
Идея неравномерного кодирования, в котором длина кодовой цепочки зависит от частоты появления соответствующего символа, реализована еще в знаменитой «азбуке Морзе». Однако там наряду с «точками» и «тире» использовался третий кодовый символ – разделитель «пауза». Если ограничиться только «O» и «1», то при построении кода необходимо учесть дополнительное требование: чтобы все кодовые цепочки однозначно выделялись в непрерывном потоке битов, ни одна из них не должна входить как начальный участок в кодовую, цепочку другого символа. Такое свойство кода называется префиксностью.
Наибольшее распространение получил способ построения эффективного кода предположенный Хаффманом. Рассмотрим его на примере. Пусть задан алфавит из 5 разновидностей символов Z1 – Z5, и их вероятности. В таблице 6.1 наряду с этими исходными данными приведены так же результаты кодирования по Хаффману: кодовые цепочки Ki их длинны li. Процедуру построения кода иллюстрирует таблица 6.2 и рисунок 5
Пример кода Хаффмана
Объединение вероятностей символов
На первом этапе символы упорядочивают по убыванию вероятностей, а затем выполняют несколько шагов «объединения», на каждом из которых суммируются вероятности наиболее редко встречающихся символов и столбец вероятностей пересортировывается (см. табл.6.2).
На втором этапе строится «дерево кода», ветви которого отображают в обратном порядке процесс «объединения вероятностей». При построении дерева принимается правило соответствия большей вероятности одному из направлений ветви (например «левому») и определенному значению бита кода (например, «1») (рис.5). Цепочки битов от «корня» до конца каждой ветви соответствуют кодам исходных символов (табл.6.1 – 6.2).
В табл.6.2 наглядно видны следующие закономерности кода:
— часто встречающиеся символы получили более короткие кодовые цепочки. В частности, за счет этого средняя длина цепочки составила lср = 2,23, что значительно меньше, чем lср = 3,00 при равномерном кодировании;
— ни одна из цепочек не входит как начальный участок в другую (выполняется так называемое правило «префиксности», благодаря чему коды символов легко можно выделить в потоке битов.
Рис.5 «Дерево кода» по Хаффману
Процедура кодирования сводится к выбору из кодовой таблицы цепочек, соответствующих каждому символу источника. Декодирование предусматривает выделение в битовом потоке кодов символов и их расшифровку в соответствии с таблицей. Пример показан на рис.6.
Передаваемые символы Z1, Z2, Z3, Z4 , Z5
Битовая последовательность 00 11 10 011 111
Принятые символы Z1 * , Z2 * , Z3 * , Z4 * , Z5 *
(результат декодирования)
Рис.6 Пример кодирования и декодирования по Хаффмену
Код Хаффмена может быть двухпроходным и однопроходным. Первый строится по результатам подсчета частот (вероятностей) появления различных символов в данном сообщении. Второй использует готовую таблицу кодирования, построенную на основе вероятностей символов в сообщениях похожего типа. Например, кодирование текста на русском языке в первом случае включает его предварительный анализ, подсчет вероятностей символов, построение дерева кода и таблицы кодирования индивидуально для данного сообщения. Во втором случае будет работать готовая таблица, построенная по результатам анализа множества русскоязычных текстов. Двухпроходный код более полно использует возможности сжатия. Однако, при этом вместе с сообщением нужно передавать и кодовую таблицу. Однопроходный код не оптимален, однако прост в использовании, поэтому на практике обычно применяют именно его.
В целом код Хаффмена проигрывает по сравнению с «цепочечными» кодами и его редко используют самостоятельно, однако он часто фигурирует как элемент более сложных алгоритмов сжатия.
Теория кодирования. Кодирование источника. Посимвольное кодирование
Теория кодирования изучает свойства различных кодов и их применимость в конкретных задачах.
В рамках теории кодирования, кодом называется некое правило (алгоритм), которое однозначно ставит неким словам над исходным алфавитом некие новые кодовые слова, возможно над другим, целевым, алфавитом.
Код Пусть \(S\) и \(T\) – конечные множества, называемые соответственно исходным и целевым алфавитами. Код \(C: S^* \to T^*\) есть всюду определённая функция, отображающая элементы \(S^*\) – слова (последовательностей символов) над исходным алфавитом – на элементы множества \(T^*\) – слова над целевым алфавитом.
В соответствии с исследуемыми задачами, выделяют четыре различных направления в теории кодирования:
- Кодирование источника (сжатие данных)
- Кодирование канала (обнаружение и исправление ошибок)
- Криптографическое кодирование
- Физическое кодирование (модуляция)
Сжатие данных
Сжатие данных в общем случае – это представление информации в меньшем информационном объёме, чем исходные данные. Выделяют сжатие данных без потерь (lossless) и сжатие данных с потерями (lossy).
Сжатие данных без потерь позволяет в точности восстановить исходный сигнал. Сжатие данных с потерями позволяет восстановить некую “достаточно хорошую” аппроксимацию исходного сигнала.
Модель сжатия без потерь:
В качестве меры “успешности” сжатия без потерь вводится коэффициент сжатия: \[r = \frac,\] где \(I_S\) – информационный объем данных источника, \(I_C\) – информационный объём кодированных данных.
В случае посимвольного кодирования, для сообщения длиной \(n\) , \(I_S = n\log |A|,\) где \(A\) – алфавит источника.
Модель сжатия с потерями:
В модели сжатия с потерями перед кодером добавляется квантователь, задачей которого является понижение размерности алфавита источника таким образом, чтобы в итоге \(X^*\) являлся “достаточно близким” образом исходного сообщения \(X\) . Например, в простейшем случае, квантователь может округлять значения. Среднеквадратичное отличие принятых сообщений \(X^*\) и отправленных сообщений \(X\) называется искажением: \[D = \frac \sum_^ (x_i — x^*_i)^2.\]
Кроме требования однозначности, как правило, требуется так же обеспечить возможность каким-то образом разделять кодовые слова, соответствующие различным исходным сообщениям. Для достижения этого могут использоваться следующие подходы:
- Использование разделительных кодовых слов – специальных кодовых слов, не соответствующих ни одному символу исходного алфавита
- Использование кодов одинаковой длины (равномерное кодирование)
- Использование префиксных кодов
Определение энтропии так же даёт нам некоторые указания касательно свойств оптимального кода, исходя из того, что энтропия кодированного сигнала должна быть максимальна (т.е. количество информации на символ кода – максимально):
- Символы целевого алфавита должны быть практически равновероятны
- Последовательные символы на выходе кодера практически независимы
Наиболее экономным для большинства применений оказывается использование префиксных кодов.
Предел оптимального кодирования без потерь нам даёт теорема Шеннона о кодировании источника: средняя (в смысле теории вероятностей) длина кодового слова не может быть меньше энтропии источника.
Основные методы посимвольного кодирования
Посимвольное кодирование, или кодирование без памяти, является простейшим методом кодирования.
Посимвольный код Пусть \(S\) и \(T\) – конечные множества, называемые соответственно исходным и целевым алфавитами. Код \(C: S \to T^*\) есть всюду определённая функция, отображающая элементы \(S\) – символы исходного алфавита – на элементы \(T^*\) – слова над целевым алфавитом. Расширение посимвольного кода Обобщение посимвольного кода \(C: S \to T^*\) на код \(C^*: S^* \to T^*\) , совершаемое конкатенацией посимвольных кодов. Префиксный код Такой код, в котором ни одно кодовое слово меньшей длины не является префиксом никакого кодового слова большей длины.
Понятно, что, по крайней мере в случае кодирования без потерь, код должен быть однозначно декодируемым.
Однозначно декодируемый посимвольный код Посимвольный код \(C: S \to T^*\) является однозначно декодируемым, если в расширенном коде \(C^*\) , любые две различных исходных строки \(\mathbf, \mathbf \in S^*,\) \(\mathbf\neq \mathbf\) , имеют различные коды: \(C^*(\mathbf) \neq C^*(\mathbf)\)
Мы так же хотим, чтобы средний (ожидаемый) информационный объем кода был минимальный.
Ожидаемая длина кодового слова (средняя длина кода) Математическое ожидание длины кодового слова из кода \(C\) над источником \(X\) обозначается \(L(C, X)\) и называется ожидаемой (средней) длиной кодового слова: \[L(C,X) = \sum_
Необходимое и достаточное условие существования однозначно декодируемых префиксных кодов (и вообще однозначно декодируемых кодов переменной длины) устанавливается неравенством Крафта-МакМиллана:
Теорема (неравенство Крафта-МакМиллана) Пусть каждый символ исходного алфавита \(S=\\) кодируется однозначно декодируемым кодом с кодовыми словами над алфавитом размерности \(r,\) имеющими длины соответственно \(\.\) Тогда: \[\sum_^ r^ \le 1.\] Обратно, для последовательности чисел \(\,\) удовлетворяющей данному неравенству, существует однозначно декодируемый код. Доказательство (прямая теорема)
Пусть \(S = \sum_i r^.\) Рассмотрим число \[S^N = \sum_\ldots\sum_ r^<-(l_+\ldots+l_)>,\] где \(N\in\mathbb N.\)
Число \((l_+\ldots+l_)\) соответствует длине кода для строки длины \(N\) \(\mathbf = a_\ldots a_.\) В сумме выше, для каждой возможной строки длины \(N\) имеется ровно один такой член. Введём дискретную функцию \(g_N(l),\) значением которой является количество строк \(\mathbf\) длины \(N\) , коды которых имеют длину \(l\) . Тогда, определяя \(l_ = \underset i \min~l_i,\) \(l_ = \underset i \max~l_i,\) получаем: \[S^N = \sum_
Доказательство (обратная теорема) Пусть \(l_1 \le \ldots \le l_n\) удовлетворяют неравенству Крафта. Тогда, можно составить однозначный префиксный код, выбирая на каждом шаге \(i=\<1,\ldots, n\>\) код длины \(l_i\) и исключая все коды длин \(l \ge l_i\) с префиксами, совпадающими с этим кодом. На каждом шаге таким образом исключается \(r^\) из всех возможных кодовых слов. Тогда всего при построении кода исключается \(\sum_^n r^\) кодовых слов. Ясно, что такой код можно построить, если число исключённых кодовых слов не превышает число всех возможных кодовых слов \(r^\) . Из неравенства Крафта, \[\sum_^ r^ \le 1,\] \[\sum_^ r^ \le r^,\] то есть это условие выполняется и код можно построить. Полный префиксный код Если префиксный код удовлетворяет неравенству Крафта равенством, т.е. \[\sum_^ r^ = 1,\] такой код называется полным.
Теорема Шеннона о кодировании источника ограничивает снизу максимально достижимое сжатие энтропией источника. Сохраняется ли это ограничение при посимвольном кодировании? Вообще говоря, ответ может быть неочевиден. Поэтому, найдём нижнюю границу ожидаемой длины кода \(L(C, X).\) Сперва докажем неравенство Гиббса.
Расстояние Кульбака-Лейблера неотрицательно: \[D_(P||Q) = \sum_
Рассмотрим \(f(u) = -\log u\) и \(u(x) = \frac\) . \(f(u)\) – выпуклая вниз функция, т.к. \(f»(u) = u^ > 0\) . Тогда из нер-ства Йенсена, \[\begin \sum_
Для упрощения выкладок, без ограничения общности, положим двоичный целевой алфавит. Упрощение достигается за счёт того, что информационный объем кодового слова в битах в таком случае численно совпадает с его длиной.
Пусть \(X=\\) , \(P(x_i) = p_i\) , \(|C(x_i)| = l_i\) , \(i=1, \ldots, n\) . Тогда, \[L(C,X) = \sum_ p_i l_i.\]
Пусть \(q_i = \frac>\) , где \(z = \sum_i 2^\) . Тогда \(l_i = — \log_2 q_i — \log_2 z\) , тогда \[\begin L(C,X) & = -\sum_ p_i \log_2 q_i — \log_2 z & (\sum_i p_i = 1) \\& \ge -\sum_ p_i \log_2 p_i — \log_2 z & \text <(из н-ва Гиббса)>\\& \ge -\sum_ p_i \log_2 p_i — \log_2 1 & \text <(из н-ва Крафта)>\\& = H(X). \end\]
Равенство соответственно достигается в случае \(p_i=q_i\) и \(z=1\) , то есть, если \(l_i = — \log_2 p_i,\) т.е. длина двоичного кодового слова \(i\) -го символа равна количеству собственной информации этого символа, и код является полным.
Это важный результат, поэтому повторимся.
Оптимальные длины кодовых слов посимвольного префиксного кода Ожидаемая длина посимвольного префиксного кода достигает минимума и равняется энтропии источника \(H(X)\) тогда и только тогда, когда длины кодовых слов соответствующих символов равны количеству собственной информации соответствующих символов \[|C(x)| = -\log_2 P(x)\]
Верно так же и обратное: любой выбор длин кодовых слов неявно определяет оптимальный источник.
Оптимальный источник для посимвольного кодера \(C\)
Определяется распределением вероятностей \[P(x) = \frac<2^<-|C(x)|>> <\sum_
Мы установили нижнюю границу. Но насколько близко к ней можно подойти? Оказывается, в пределах одного бита.
Для источника случайной переменной \(x\) из ансамбля \(X\) существует префиксный код \(C\) , удовлетворяющий неравенствам \[H(X) \le L(C,X) < H(X)+1\]
\(\Delta\) : Первое неравенство \(L(C,X) \ge H(X)\) уже доказано выше.
Выберем длины кодовых слов, округлив теоретически оптимальные длины до ближайшего целого вверх: \[l(x) = \left\lceil -log_2 P(x) \right\rceil.\]
Покажем, что префиксный код с такими длинами кодовых слов существует (удовлетворяет нер-ству Крафта): \[\sum_
Тогда, \[\begin L(C,X) & = \sum_ P(x) \left\lceil -log_2 P(x) \right\rceil \\& < \sum_P(x) \left( -log_2 P(x) + 1 \right) \\& = H(x)+1 \end\]
Отметим, что если для кодирования источника с вероятностями \(p_i\) используется полный префиксный код с длинами кодов \(l_i\) , то ожидаемая длина кода будет отличаться от энтропии на расстояние Кульбака-Лейблера от оптимального источника данного кода с вероятностями \(q_i = 2^\) : \[\begin L(C,X) — H(X) & = \sum_i p_i l_i + \sum_i p_i \log_2 p_i \\ & = -\sum_i p_i \log_2 q_i + \sum_i p_i \log_2 p_i \\ & = \sum_i p_i \log_2 \frac \\ & = D_(p||q) \end\]
Алгоритм Хаффмана
Один из способов построить оптимальный посимвольный код – алгоритм Хаффмана.
- Возьмём два наименее вероятных символа исходного алфавита. Этим символам будут назначены кодовые слова максимальной (одинаковой) длины, и они будут отличаться только последним битом.
- Отождествим эти символы.
- Если в рассмотрении более 1 символа, перейдём к шагу 1.
Более подробное описание доступно здесь
Поскольку каждая итерация уменьшает число рассматриваемых символов на 1, алгоритм завершится за \(|X|-1\) итераций, где \(|X|\) – размер алфавита источника \(X\) .
Код, составленный по алгоритму Хаффмана, оптимален.
Доказательство индукцией по размеру алфавита \(|X|\) .
База. \(|X| = 2\) , ожидаемая длина кода Хаффмана \(L=1\) . Код очевидно оптимален.
Пусть алгоритм Хаффмана даёт оптимальный код для алфавита размера \(|X|=n-1\) .
Тогда для алфавита \(A_X=\
В процессе работы алгоритма, будет так же построен код для источника \(X’\) с алфавитом \(A_=\
Пусть средняя длина кодового слова для источника \(X\) по алгоритму Хаффмана \(L\) . Допустим, такой код не оптимален. Тогда существует другой код со средней длиной кодового слова \(\widetilde L < L\) . Мы можем построить полный префиксный код, такой, что коды для \(x_\) и \(x_n\) отличаются только последним битом, а его средняя длина \(\hat L \le \widetilde L\) .
Из нового префиксного кода с длиной \(\hat L\) мы можем построить код для \(X’\) , сохранив коды для \(x_1,\ldots,x_\) и назначив общий префикс кодов \(x_\) и \(x_n\) в качестве кода \(x’\) . Пусть его средняя длина \(\hat L’\)
Тогда, поскольку \(X’\) отличается от \(X\) тем, что два символа из \(X\) в нём отождествляются, а отождествлённый символ в наших кодах имеет кодовое слово на 1 бит короче, имеем \[L = L’ + P(x’),\] \[\hat L = \hat L’ + P(x’).\]
Поскольку по предположению индукции \(L’\) является длиной оптимального кода, \(\hat L’ \ge L’\) , но тогда \(\hat L \ge L\) , что противоречит \(\hat L \le \widetilde L < L\) . Следовательно, код Хаффмана для алфавита размера \(|X|=n\) оптимален.
По индукции, код Хаффмана для любого алфавита размерности \(|X|\ge 2\) оптимален.
Другие алгоритмы посимвольного кодирования
Код Шеннона
Все символы алфавита источника упорядочиваются по убыванию вероятности. Каждому символу ставится в соответствие “кумулятивная вероятность” \(q_i = \sum_^ p_j\) . Кодовым словом для \(i\) -го символа являются \(l_i = \left\lceil -log_2 p_i \right\rceil\) разрядов дробной части из двоичного представления \(q_i\) .
Код Шеннона использовался Шенноном при доказательстве теоремы о кодировании источника, однако он не является оптимальным, и никогда не лучше (но иногда эквивалентен) коду Шеннона-Фано.
Код Шеннона-Фано
Все символы алфавита источника упорядочиваются по убыванию вероятности. Полученный массив делится на две непрерывные части, максимально близкие по сумме вероятностей входящих в них символов. Одной из этих частей присваивается метка “0”, второй – метка “1”. Алгоритм рекурсивно повторяется для каждой из частей, пока не дойдёт до единственного символа. Кодом этого символа является последовательность меток частей.
Код Шеннона-Фано даёт оценку средней длины \(L(C,X) \le H(X)+2\) . Понятно, что он не является оптимальным.
Следует отметить, что подход похож на подход Хаффмана, однако алгоритм Хаффмана строит дерево “снизу вверх”, от листьев, в то время как алгоритм Шеннона-Фано строит дерево “сверху вниз”, от корня.
Код Элиаса (Шеннона-Фано-Элиаса)
Так же известен как код Гильберта-Мура 1
Каждому символу ставится в соответствие число \[F_i = \frac + \sum_^ p_j.\]
Кодовым словом \(i\) -го символа выбираются первые \(l_i = \left\lceil -\log_2 p_i \right\rceil + 1\) дробных разрядов двоичного представления числа \(F_i\) .
Код Элиаса даёт оценку средней длины \(L(C,X) \le H(X)+2\) .
- Gilbert E. N., Moore E. F. Variable‐Length Binary Encodings //Bell System Technical Journal. – 1959. – Т. 38. – №. 4. – С. 933-967.↩︎
infoegehelp.ru
В некоторой стране автомобильный номер состоит из 7 символов. В качестве символов используют 18 различных букв и десятичные цифры в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байтов, при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов.
Определите объем памяти, отводимый этой программой для записи 60 номеров.
- 240 байт
- 300 байт
- 360 байт
- 420 байт
Решение:
Необходимо закодивовать: 10 цифр (от 0 до 9)+18 букв=28 символов.
Для кодирования необходимо 5 бит, т.к. 16
Для кодирования 1 автомобильного знака нужно: 5*7=35 бит.
35 нацело не делится на 8. А нам по условию дано,что 1 автомобильный номер должен кодироваться целым количеством байтов. Поэтому округляем 35 до 40.
40\8=5 байт-отводится на 1 автомобильный номер.
Для кодирования 60 номеров нужно: 5*60= 300 байт .