Алфавитное кодирование

Алфавитное кодирование — вид кодирования слов некоторого алфавита при помощи замены каждой буквы некоторым словом того же или какого-либо другого алфавита^[1]. Основоположником этого направления в России^{[прояснить]} считается математик из Нижнего Новгорода Александр Александрович Марков^[2]. В алфавитном кодировании преимущественно используются^{[прояснить]} префиксные коды, так как свойство префикса гарантирует однозначную декодируемость^[3].

Пусть заданы конечный алфавит (множество) ${\displaystyle A=\left\{a_{1},a_{2},...,a_{n}\right\}}$ и конечный алфавит ${\displaystyle B=\left\{b_{1},b_{2},...,b_{m}\right\}}$.

Схемой^[4] алфавитного кодирования называется отображение ${\displaystyle \Sigma :A\to B^{+}}$, где ${\displaystyle B^{+}}$ — множество всех непустых слов алфавита ${\displaystyle B}$. Слова ${\displaystyle \beta _{1}=\Sigma (a_{1}),\ldots ,\beta _{n}=\Sigma (a_{n})}$ называются элементарными кодами схемы ${\displaystyle \Sigma }$. Множество слов ${\displaystyle \{\beta _{1},\ldots ,\beta _{n}\}}$ называется кодирующей системой слов. Алфавитным кодированием называется отображение ${\displaystyle \sigma :A^{*}\to B^{*}}$, определяемое следующим образом:

${\displaystyle \sigma (a_{i_{1}}\ldots a_{i_{r}})=\Sigma (a_{i_{1}})\ldots \Sigma (a_{i_{r}})}$^[1]

Слово ${\displaystyle \beta =\sigma (\alpha )}$ называется кодом слова ${\displaystyle \alpha \in A^{*}}$^[5]. Также термином «код» часто обозначают множество всех элементарных кодов^[5]. Иногда кодируемый алфавит считают упорядоченным и кодом называют кортеж из соответствующих элементарных кодов. Такой код может содержать повторения и, по сути, полностью определяет алфавитное кодирование^[6].

Термином побуквенное кодирование некоторые авторы называют схему алфавитного кодирования^[7], а некоторые само алфавитное кодирование^[8].

Алфавитное кодирование ${\displaystyle \sigma }$ называется взаимо-однозначным, если у отображения ${\displaystyle \sigma }$ существует обратное^[9]. Также используются термины разделимый код^[7] и однозначно-декодируемый код^[10].

Простейший пример взаимо-однозначного алфавитного кодирования — равномерное кодирование. Равномерное кодирование — такое алфавитное кодирование, при котором элементарные коды для разных символов ${\displaystyle a}$ различны и имеют одинаковую длину^[5]. Минимальная длина элементарных кодов при равномерном кодировании для заданных кодируемого алфавита ${\displaystyle A}$ и кодирующего алфавита ${\displaystyle B}$ равна ${\displaystyle \lceil \log _{m}n\rceil }$, где ${\displaystyle n=|A|,m=|B|}$^[11].

Равномерное кодирование за счёт использования слов одинаковой длины позволяет очень легко декодировать слова, а также легко находить нужную позицию оригинального слова в закодированном слове. Однако такое кодирование может быть довольно неэкономичным, многие неравномерные кодирования позволяют получить более короткие коды для тех же слов^[12]. Примеры равномерных кодирований в информатике: ASCII, UTF-32.

Алфавитное кодирование называется префиксным, если для него выполняется следующее условие, называемое (прямым) условием Фано: для любых двух символов кодируемого алфавита ни один из их элементарных кодов не является префиксом другого^[10].

Алфавитное кодирование называется постфиксным, если для него выполняется следующее условие, называемое обратным условием Фано: для любых двух символов кодируемого алфавита ни один из их элементарных кодов не является постфиксом другого^[13].

Префиксное и постфиксное кодирование являются взаимо-однозначными^[13]. Равномерное кодирование является частным случаем как префиксного, так и постфиксного кодирования. Префиксный код называется полным, если для каждого префикса элементарного кода ${\displaystyle b_{i_{1}}\ldots b_{i_{k}}b_{i_{k+1}}}$ и для каждого символа ${\displaystyle b\in B}$ существует элементарный код с префиксом ${\displaystyle b_{i_{1}}\ldots b_{i_{k}}b}$. Постфиксный код называется полным, если для каждого постфикса элементарного кода ${\displaystyle b_{0}b_{i_{1}}\ldots b_{i_{k}}}$ и для каждого символа ${\displaystyle b\in B}$ существует элементарный код с постфиксом ${\displaystyle bb_{i_{1}}\ldots b_{i_{k}}}$^[14].

Если для набора длин ${\displaystyle l_{1},\ldots ,l_{n}}$ существует взаимо-однозначное алфавитное кодирование со схемой ${\displaystyle \Sigma \colon A\to B^{+},|A|=n}$, элементарные коды которого ${\displaystyle \beta _{i}=\Sigma (a_{i})}$ имеют указанные длины, то есть ${\displaystyle l_{i}=|\beta _{i}|}$, то тогда существует префиксное (постфиксное) кодирование, элементарные коды которого имеют указанные длины. Поэтому, задачу о существовании взаимо-однозначного кодирования с заданными длинами элементарных кодов можно свести к задаче о существование префиксного (постфиксного) кодирования с заданными длинами элементарных кодов^[15].

Примеры префиксных и постфиксных кодов (одновременно) в информатике: UTF-8, UTF-16.

Для префиксных (постфиксных) кодов существует способ представлять их графически в виде дерева. Такое дерево называется кодовым деревом. Каждой дуге дерева приписывается символ кодирующего алфавита, причём из одной вершины может выходить только одна дуга с определённым символом. Такое дерево задаёт множество элементарных кодов префиксного (постфиксного) кодирования следующим образом. Каждой листовой вершине соответствует элементарный код, который определяется по пути от корня до этой вершины: он получается приписыванием символов дуг этого пути от корня до листа (от листа до корня). Каждый префиксный (постфиксный) код можно представить в виде такого дерева и каждое такое дерево задаёт префиксный (постфиксный) код. Схема кодирования (а значит и само алфавитное кодирование) задаётся приписыванием к каждой из листовых вершин соответствующего символа кодируемого алфавита^[16].

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

Неконцевая вершина кодового дерева называется насыщенной, если из неё выходит ровно ${\displaystyle m}$ дуг, где ${\displaystyle m}$ — количество символов кодирующего алфавита. Кодовое дерево называется полным, если каждая неконцевая вершина является насыщенной. Префиксный (постфиксный) код является полным тогда и только тогда, когда его кодовое дерево полно. Кодовое дерево называется насыщенным, если все неконцевые вершины насыщенные, кроме, возможно, одной, лежащей в предпоследнем ярусе дерева, количество дуг, исходящих из которой, равно ${\displaystyle m_{0},2\leqslant m_{0}<m}$. Такая вершина называется исключительной. Если у насыщенного дерева нет исключительной вершины, то ${\displaystyle m_{0}}$ считается равным ${\displaystyle m}$. ${\displaystyle m_{0}}$ однозначно определяется, по количеству символов алфавитов ${\displaystyle A,B}$^[17][18].

Теорема, доказанная Александром Марковым, позволяет свести вопрос о взаимной однозначности кодирования всех слов алфавита ${\displaystyle A}$ к вопросу о взаимной однозначности кодирования некоторого конечного множества слов алфавита ${\displaystyle A}$. Для её формулировки понадобится ввести предварительные обозначения:

• ${\displaystyle L}$ — длина кода слова ${\displaystyle a_{1}\ldots a_{n}}$, где ${\displaystyle a_{1},\ldots ,a_{n}\in A}$ — все символы алфавита ${\displaystyle A}$;
• для каждого элементарного кода ${\displaystyle \beta _{i}}$ рассматриваются разложения вида ${\displaystyle \beta _{i}=\gamma '\beta _{j_{1}}\ldots \beta _{j_{w}}\gamma ''}$, отличные от разложения вида ${\displaystyle \beta _{i}=\beta _{i}}$, где ${\displaystyle \beta _{j_{1}},\ldots ,\beta _{j_{w}}}$ — другие элементарные коды, ${\displaystyle w\geq 0}$, а ${\displaystyle \gamma ',\gamma ''\in \mathbb {B^{*}} }$ — произвольные слова в алфавите ${\displaystyle B}$, отличные от элементарных кодов. Тогда ${\displaystyle W}$ определяется как максимум ${\displaystyle w}$ по всем таким разложениям.

Теорема Маркова в этих обозначениях формулируется так:

существует такое ${\displaystyle N\leqslant \left\lfloor {\dfrac {(W+1)(L-n+2)}{2}}\right\rfloor }$, что проблема взаимной однозначности кодирования сводится к проблеме взаимной однозначности кодирования слов, длины не более, чем N^[19].

В оригинальном докладе Маркова ${\displaystyle N}$ определялась следующим образом:

${\displaystyle N={\dfrac {(L-n)(W+1)}{2}}-\delta (L-n){\dfrac {W-1}{2}}}$,

где ${\displaystyle \delta }$ для чётных равна ${\displaystyle 0}$, а для нечётных ${\displaystyle 1}$^[1].

Теорема позволяет алгоритмически решить проблему взаимной однозначности алфавитного кодирования простым перебором всех слов длины до ${\displaystyle N}$, однако даже для довольно простых кодирований количество слов, которое нужно перебрать, может оказаться настолько огромным, что алгоритм будет неприменим на практике^[20].

Более эффективный алгоритм проверки взаимной-однозначности кодирования был сформулирован Марковым на языке теории графов.

1. Рассматриваются все разложения кодовых слов вида ${\displaystyle \beta _{i}=\gamma '\beta _{j_{1}}\ldots \beta _{j_{w}}\gamma ''}$, отличные от разложения вида ${\displaystyle \beta _{i}=\beta _{i}}$, где ${\displaystyle \beta _{j_{1}},\ldots ,\beta _{j_{w}}}$ — другие элементарные коды, ${\displaystyle w\geq 0}$, а ${\displaystyle \gamma ',\gamma ''\in B^{*}}$ — произвольные слова в алфавите ${\displaystyle B}$, отличные от элементарных кодов.
2. Строится ориентированный граф следующим образом. В качестве вершин берутся все слова ${\displaystyle \gamma \in B^{*}}$ такие, что ${\displaystyle \gamma }$ входит и в некоторое разложение в качестве ${\displaystyle \gamma '}$, и в некоторое разложение (возможно другое) в качестве ${\displaystyle \gamma ''}$. Также к множеству вершин обязательно добавляется пустое слово. Из вершины ${\displaystyle \gamma _{1}}$ исходит дуга в вершину ${\displaystyle \gamma _{2}}$ тогда и только тогда, когда существует разложение с ${\displaystyle \gamma _{1}=\gamma ',\gamma _{2}=\gamma ''}$.
3. Алфавитное кодирование является взаимно-однозначным тогда и только тогда, когда построенный граф не содержит ориентированных циклов, проходящих через вершину, являющуюся пустым словом^[22].

Для взаимо-однозначных кодирований выполняется Неравенство Крафта — Макмиллана:

${\displaystyle \sum _{i=1}^{n}m^{-l_{i}}\leqslant 1}$,

где ${\displaystyle l_{i}}$ есть длина элементарного кода ${\displaystyle \beta _{i}}$^[23]. Неравенство Крафта — Макмиллана является необходимым и достаточным условием того, что для ${\displaystyle A,B}$ и заданного набора длин ${\displaystyle l_{1},\ldots ,l_{n}}$ (${\displaystyle l_{i}}$ и ${\displaystyle l_{j}}$ могут совпадать для ${\displaystyle i\neq j}$) существует взаимо-однозначное (и даже префиксное) кодирование, для которого ${\displaystyle l_{i}}$ — длина элементарного кода ${\displaystyle \beta _{i}}$^[24].

Пусть на кодируемом алфавите ${\displaystyle A=\{a_{1},\ldots ,a_{n}\}}$ задано распределение вероятностей, то есть каждому символу ${\displaystyle a_{i}}$ сопоставлено число ${\displaystyle p_{i}\in \mathbb {R} ,p_{i}\geqslant 0}$ так, что ${\displaystyle p_{1}+\ldots +p_{n}=1}$. Средней длиной^[25] элементарного кода или стоимостью^[7] кодирования называется математическое ожидание длины элементарного когда:

${\displaystyle l_{cp}=p_{1}|\beta _{1}|+\ldots +p_{n}|\beta _{n}|}$

Для заданных ${\displaystyle A,B}$ и распределении вероятностей ${\displaystyle P}$ на ${\displaystyle A}$ взаимо-однозначное кодирование называется оптимальным^[26] или кодированием с минимальной избыточностью^[11], если оно имеет минимальную среднюю длину элементарного кода среди всех взаимо-однозначных алфавитных кодирований ${\displaystyle A^{*}\to B^{*}}$. Оптимальное кодирование существует для любых ${\displaystyle A,B,P}$, и даже существует префиксное и постфиксное оптимальное кодирование. Пример оптимального префиксного кодирования для заданных ${\displaystyle A,B,P}$ — код Хаффмана^[26]. Некоторые авторы называют кодом Хаффмана любое оптимальное кодирование^[11].

Для двух символов кодируемого алфавита ${\displaystyle a_{i},a_{j}}$ таких, что ${\displaystyle p_{i}<p_{j}}$, в оптимальном кодирование выполняется ${\displaystyle |\beta _{i}\geqslant \beta _{j}|}$. В кодовом дереве оптимального префиксного кодирования вероятности символов кодируемого алфавита, приписанные листовым вершинам меньшего яруса не больше, чем вероятности символов, приписанные листовым вершинам большего яруса^[27]. Среди оптимальных кодов существует префиксный код с насыщенным кодовым деревом^[28].

Приведённым кодом называется оптимальный префиксный код, дерево которого насыщенно и ${\displaystyle m_{0}}$ листовых вершин, соответствующих ${\displaystyle m_{0}}$ минимальных вероятностей, присоединены к исключительной вершине (а если исключительной вершины нет, то ${\displaystyle m_{0}=m}$ таких листовых вершин присоединены к одной произвольной вершине предпоследнего яруса; она и будет считаться исключительной вершиной для приведённого кода). Среди оптимальных кодов существует приведённый код^[29].

Идея построения кода Хаффмана строится на следующей теореме об оптимальных префиксных кодах. Для её формулировки нужно будет ввести дополнительные термины.

Пусть кодовое дерево префиксного кода ${\displaystyle \sigma '}$ получается из кодового дерева префиксного кода ${\displaystyle \sigma }$ следующим образом:

1. Берётся некоторая концевая вершина ${\displaystyle \nu }$, к которой приписана вероятность ${\displaystyle p}$.
2. К дереву добавляется какое-то количество новых концевых вершин, к которым ведутся дуги из ${\displaystyle \nu }$.
3. Новым вершинам ставятся в соответствие некоторые вероятности ${\displaystyle p_{1},\ldots ,p_{s}}$, удовлетворяющие условию ${\displaystyle p=p_{1}+\ldots +p_{s}}$.

Тогда говорят, что префиксный код ${\displaystyle \sigma '}$ получен из префиксного кода ${\displaystyle \sigma }$ путём замены концевой вершины пучком рёбер^[30].

Если оптимальный префиксный код ${\displaystyle \sigma '}$ получен из префиксного кода ${\displaystyle \sigma }$ путём замены концевой вершины пучком рёбер, то код ${\displaystyle \sigma }$ — тоже оптимальный. Если префиксный код ${\displaystyle \sigma '}$ получен из оптимального префиксного кода ${\displaystyle \sigma }$ путём замены концевой вершины пучком из ${\displaystyle m_{0}}$ рёбер и вероятности добавленных вершин являются наименьшими вероятностями в дереве ${\displaystyle \sigma '}$, то ${\displaystyle \sigma '}$ тоже оптимален^[31]. Это свойство позволяет сформулировать алгоритм построения оптимального префиксного кода:

1. Пока это возможно проводится замена списка вероятностей ${\displaystyle p_{1}\geqslant \ldots \geqslant p_{n}}$ на более меньший. Делается это так: на первой итерации берётся ${\displaystyle m_{0}}$ наименьших вероятностей и складывается, на последующих шагах берётся ${\displaystyle m}$ наименьших вероятностей и складывается. Затем, вероятности, использованные в сумме, убираются из списка, а полученная сумма добавляется в нужную позицию этого списка так, чтобы упорядоченность списка не нарушалась.
2. Когда вероятностей в списке осталось слишком мало, чтобы продолжать их замену, строится кодовое дерево префиксного кода для полученного списка вероятностей. Это дерево состоит из корня и листовых вершин; к каждой из листовых вершин проведена дуга из корня и каждой приписана одна вероятность из списка. Очевидно, это является оптимальным кодированием для нового списка вероятностей.
3. Далее замены списка вероятностей начинают выполняться в обратную сторону. При каждой итерации происходит замена листовой вершины, соответствующей заменяемой вероятности из списка, пучком рёбер, количество и вероятности новых концевых вершин которого соответствуют добавленным вероятностям в список.
4. Так происходит до того, как будет достигнут оригинальный список вероятностей. Кодовое дерево искомого оптимального префиксного кода построено^[32].

Код, полученный в результате этого алгоритма, называется кодом Хаффмана.

• Яблонский С. В. Введение в дискретную математику. — 5-е изд. — М.: Высшая школа, 2008. — 384 с. — ISBN 978-5-06-005943-4.
• Васильев Ю. Л., Ветухновский Ф. Я., Глаголев В. В., Журавлёв Ю. И., Левеншейн В. И., Яблонский С. В. Дискретная математика и математические вопросы кибернетика. Том 1. — М.: Наука, 1974. — 312 с.
• Марков А. А. Об алфавитном кодировании : [арх. 29 января 2023] // Доклады Академии наук СССР. — 1960. — Т. 132, № 3. — С. 521–523.
• К. Ю. Поляков. Ещё раз про однозначное декодирование (рус.) // Информатика : Журнал. — 2012. — 1 декабря (№ 11). — С. 16-20.
• Чашкин А. В. Лекции по дискретной математике. — М., 2007. — 261 с.
• Марков А. А. Вопросы взаимной однозначности и сложности в алфавитном кодировании : Автореф. дис. … д-ра физ.-мат. наук. — М., 1983. — 17 с.
• Марков А. А. Кодирование алфавитное // Математическая энциклопедия. — М.: Советская энциклопедия, 1979. — Т. 2. — С. 935—937.