Кодирование Шеннона – Фано

В области данных сжатия кодирование Шеннона-Фано , названное в честь Клода Шеннона и Роберта Фано , представляет собой один из двух родственных методов построения префиксного кода на основе набора символов и их вероятностей (оценочных или измеренных).

Метод Шеннона выбирает префиксный код, в котором исходный символ $i$ задана длина кодового слова $l_{i}=\lceil -\log _{2}p_{i}\rceil$ . Один из распространенных способов выбора кодовых слов использует двоичное разложение кумулятивных вероятностей. Этот метод был предложен Шенноном в « Математической теории связи » (1948), его статье, вводящей в область теории информации .
Метод Фано делит исходные символы на два набора («0» и «1») с вероятностями, максимально близкими к 1/2. Затем эти наборы сами делятся на две части и так далее, пока каждый набор не будет содержать только один символ. Кодовое слово для этого символа представляет собой строку из «0» и «1», которая записывает, на какую половину деления он попал. Этот метод был предложен в более позднем (напечатанном) техническом отчете Фано (1949).

Коды Шеннона-Фано неоптимальны в том смысле, что они не всегда достигают минимально возможной ожидаемой длины кодового слова, как это делает кодирование Хаффмана . ^{[ 1 ]} Однако коды Шеннона-Фано имеют ожидаемую длину кодового слова в пределах 1 бита от оптимальной. Метод Фано обычно обеспечивает кодирование с более короткими ожидаемыми длинами, чем метод Шеннона. Однако метод Шеннона легче анализировать теоретически.

Кодирование Шеннона-Фано не следует путать с кодированием Шеннона-Фано-Элиаса (также известным как кодирование Элиаса), предшественником арифметического кодирования .

Мы

Что касается путаницы в двух разных кодах, называемых одним и тем же названием, Крайчи и др. писать: ^{[ 2 ]}

Примерно в 1948 году Клод Э. Шеннон (1948) и Роберт М. Фано (1949) независимо друг от друга предложили два разных алгоритма кодирования источника для эффективного описания дискретного источника без памяти. К сожалению, несмотря на различие, обе схемы стали известны под одним и тем же названием « Кодирование Шеннона–Фано» .
Есть несколько причин этой путаницы. Во-первых, при обсуждении своей схемы кодирования Шеннон упоминает схему Фано и называет ее «по существу такой же» (Shannon, 1948, стр. 17 [перепечатка]). ^{[ 3 ]} С другой стороны, схемы кодирования Шеннона и Фано схожи в том смысле, что они обе являются эффективными, но неоптимальными схемами кодирования без префиксов с одинаковой производительностью.

Метод Шеннона (1948), использующий заранее определенную длину слова, называют кодированием Шеннона-Фано . Ковер и Томас ^{[ 4 ]} Голди и Пинч, ^{[ 5 ]} Джонс и Джонс, ^{[ 6 ]} и Хан и Кобаяши. ^{[ 7 ]} назвал это кодированием Шеннона . Юнг ^{[ 8 ]}

Метод Фано (1949), использующий двоичное деление вероятностей, называет кодированием Шеннона – Фано. Саломон ^{[ 9 ]} и Гупта. ^{[ 10 ]} назвали это кодированием Фано . Крайчи и др. ^{[ 2 ]}

Код Шеннона: предопределенная длина слов

Алгоритм Шеннона

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

Учитывая источник с вероятностями $p_{1},p_{2},\dots ,p_{n}$ желаемая длина кодового слова равна $l_{i}=\lceil -\log _{2}p_{i}\rceil$ . Здесь, $\lceil x\rceil$ — это функция потолка , означающая наименьшее целое число, большее или равное $x$ .

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

Второй метод использует кумулятивные вероятности. Сначала вероятности записываются в порядке убывания $p_{1}\geq p_{2}\geq \cdots \geq p_{n}$ . Тогда кумулятивные вероятности определяются как

c_{1}=0,\qquad c_{i}=\sum _{j=1}^{i-1}p_{j}{\text{ for }}i\geq 2,

так $c_{1}=0,c_{2}=p_{1},c_{3}=p_{1}+p_{2}$ и так далее. Кодовое слово для символа $i$ выбран первым $l_{i}$ двоичные цифры в двоичном представлении $c_{i}$ .

Пример

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

Символ	А	Б	С	Д	И
Считать	15	7	6	6	5
Вероятности	0.385	0.179	0.154	0.154	0.128

Этот источник имеет энтропию $H(X)=2.186$ биты.

Для кода Шеннона – Фано нам нужно вычислить желаемые длины слов. $l_{i}=\lceil -\log _{2}p_{i}\rceil$ .

Символ	А	Б	С	Д	И
Вероятности	0.385	0.179	0.154	0.154	0.128
$-\log _{2}p_{i}$	1.379	2.480	2.700	2.700	2.963
Длина слов $\lceil -\log _{2}p_{i}\rceil$	2	3	3	3	3

Мы можем выбирать кодовые слова по порядку, выбирая лексикографически первое слово правильной длины, сохраняющее свойство отсутствия префиксов. Очевидно, что A получает кодовое слово 00. Чтобы сохранить свойство отсутствия префиксов, кодовое слово B может не начинаться с 00, поэтому лексикографически первое доступное слово длины 3 — это 010. Продолжая таким образом, мы получаем следующий код:

Символ	А	Б	С	Д	И
Вероятности	0.385	0.179	0.154	0.154	0.128
Длина слов $\lceil -\log _{2}p_{i}\rceil$	2	3	3	3	3
Кодовые слова	00	010	011	100	101

В качестве альтернативы мы можем использовать метод кумулятивной вероятности.

Символ	А	Б	С	Д	И
Вероятности	0.385	0.179	0.154	0.154	0.128
Кумулятивные вероятности	0.000	0.385	0.564	0.718	0.872
...в двоичном формате	0.00000	0.01100	0.10010	0.10110	0.11011
Длина слов $\lceil -\log _{2}p_{i}\rceil$	2	3	3	3	3
Кодовые слова	00	011	100	101	110

Обратите внимание: хотя кодовые слова в этих двух методах различаются, длина слов одинакова. У нас есть длина 2 бита для A и 3 бита для B, C, D и E, что дает среднюю длину

{\frac {2\,{\text{bits}}\cdot (15)+3\,{\text{bits}}\cdot (7+6+6+5)}{39\,{\text{symbols}}}}\approx 2.62\,{\text{bits per symbol,}}

что находится в пределах одного бита энтропии.

Ожидаемая длина слова

Для метода Шеннона длины слов удовлетворяют

l_{i}=\lceil -\log _{2}p_{i}\rceil \leq -\log _{2}p_{i}+1.

Следовательно, ожидаемая длина слова удовлетворяет

\mathbb {E} L=\sum _{i=1}^{n}p_{i}l_{i}\leq \sum _{i=1}^{n}p_{i}(-\log _{2}p_{i}+1)=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}+\sum _{i=1}^{n}p_{i}=H(X)+1.

Здесь, $H(X)=-\textstyle \sum _{i=1}^{n}p_{i}\log _{2}p_{i}$ — энтропия , а теорема исходного кодирования Шеннона гласит, что любой код должен иметь среднюю длину не менее $H(X)$ . Следовательно, мы видим, что код Шеннона–Фано всегда находится в пределах одного бита от оптимальной ожидаемой длины слова.

Код Фано: двоичное расщепление

Краткое описание кода Фано

В методе Фано символы располагаются в порядке от наиболее вероятного к наименее вероятному, а затем делятся на два набора, общие вероятности которых максимально близки к равным. Затем всем символам присваиваются первые цифры их кодов; символы в первом наборе получают «0», а символы во втором наборе получают «1». Пока остаются какие-либо наборы, содержащие более одного члена, тот же процесс повторяется для этих наборов для определения последовательных цифр их кодов. Когда набор сокращен до одного символа, это означает, что код символа является полным и не будет формировать префикс кода любого другого символа.

Алгоритм создает довольно эффективные кодировки переменной длины; когда два меньших набора, созданных в результате разделения, фактически имеют одинаковую вероятность, один бит информации, используемый для их различения, используется наиболее эффективно. К сожалению, кодирование Шеннона-Фано не всегда дает оптимальные префиксные коды; набор вероятностей {0,35, 0,17, 0,17, 0,16, 0,15} является примером того, которому будут присвоены неоптимальные коды с помощью кодирования Шеннона – Фано.

Версия кодирования Шеннона – Фано Фано используется в IMPLODE метод сжатия, который является частью ZIP формат файла . ^{[ 11 ]}

Дерево Шеннона-Фано

Дерево Шеннона-Фано строится в соответствии со спецификацией, разработанной для определения эффективной кодовой таблицы. Фактический алгоритм прост:

Для данного списка символов разработайте соответствующий список вероятностей или частот, чтобы была известна относительная частота появления каждого символа.
Отсортируйте списки символов по частоте: наиболее часто встречающиеся символы располагаются слева, а наименее распространенные — справа.
Разделите список на две части так, чтобы общее количество частот в левой части было как можно ближе к общему количеству в правой.
Левой части списка присвоена двоичная цифра 0, а правой части — цифра 1. Это означает, что все коды символов в первой части будут начинаться с 0, а все коды во второй части будут начинаться с 0. начни с 1.
Рекурсивно примените шаги 3 и 4 к каждой из двух половин, разделив группы и добавив биты к кодам, пока каждый символ не станет соответствующим кодовым листом в дереве.

Пример

Продолжаем предыдущий пример.

Символ	А	Б	С	Д	И
Считать	15	7	6	6	5
Вероятности	0.385	0.179	0.154	0.154	0.128

Все символы отсортированы по частоте слева направо (показано на рисунке а). Если провести разделительную линию между символами B и C, в общей сложности получится 22 символа в левой группе и всего 17 в правой группе. Это минимизирует разницу в итоговых показателях между двумя группами.

При таком разделении каждый из A и B будет иметь код, начинающийся с бита 0, а коды C, D и E будут начинаться с 1, как показано на рисунке b. Впоследствии левая половина дерева получает новое разделение между A и B, в результате чего A помещается на лист с кодом 00, а B — на лист с кодом 01.

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

Символ	А	Б	С	Д	И
Вероятности	0.385	0.179	0.154	0.154	0.128
Первый дивизион	0		1
Второй дивизион	0	1	0	1
Третий дивизион	0	1	0	0	1
Кодовые слова	00	01	10	110	111

Это приводит к длине 2 бита для A, B и C и по 3 бита для D и E, что дает среднюю длину

{\frac {2\,{\text{bits}}\cdot (15+7+6)+3\,{\text{bits}}\cdot (6+5)}{39\,{\text{symbols}}}}\approx 2.28\,{\text{bits per symbol.}}

Мы видим, что метод Фано со средней длиной 2,28 превзошел метод Шеннона со средней длиной 2,62.

Ожидаемая длина слова

Это показано Крайчи и др. ^{[ 2 ]} что ожидаемая длина метода Фано имеет ожидаемую длину, ограниченную сверху $\mathbb {E} L\leq H(X)+1-p_{\text{min}}$ , где $p_{\text{min}}=\textstyle \min _{i}p_{i}$ — вероятность наименьшего общего символа.

Сравнение с другими методами кодирования

Ни один из алгоритмов Шеннона – Фано не гарантирует создания оптимального кода. По этой причине коды Шеннона–Фано практически не используются; Кодирование Хаффмана почти так же просто в вычислительном отношении и создает префиксные коды, которые всегда достигают минимально возможной ожидаемой длины кодового слова при условии, что каждый символ представлен кодом, состоящим из целого числа битов. Это ограничение часто не требуется, поскольку коды будут упакованы сквозным образом в длинные последовательности. Если мы рассматриваем группы кодов одновременно, посимвольное кодирование Хаффмана является оптимальным только в том случае, если вероятности символов независимы и равны некоторой степени половины, т. е. $\textstyle 1/2^{k}$ . В большинстве ситуаций арифметическое кодирование может обеспечить большее общее сжатие, чем Хаффман или Шеннон-Фано, поскольку оно может кодировать дробными числами битов, которые более точно соответствуют фактическому информационному содержанию символа. Однако арифметическое кодирование не вытеснило Хаффмана так, как Хаффман заменяет Шеннона-Фано, как потому, что арифметическое кодирование более затратно в вычислительном отношении, так и потому, что на него распространяется множество патентов. ^{[ 12 ]}

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

Несколько лет спустя Дэвид А. Хаффман (1952) ^{[ 13 ]} предложил другой алгоритм, который всегда создает оптимальное дерево для любых заданных вероятностей символов. В то время как дерево Шеннона – Фано Фано создается путем деления от корня к листьям, алгоритм Хаффмана работает в противоположном направлении, сливаясь от листьев к корню.

Создайте листовой узел для каждого символа и добавьте его в приоритетную очередь , используя в качестве приоритета его частоту появления.
Пока в очереди более одного узла:
1. Удалите из очереди два узла с наименьшей вероятностью или частотой.
2. Добавьте 0 и 1 соответственно к любому коду, уже назначенному этим узлам.
3. Создайте новый внутренний узел с этими двумя узлами в качестве дочерних и с вероятностью, равной сумме вероятностей двух узлов.
4. Добавьте новый узел в очередь.
Оставшийся узел является корневым узлом, и дерево завершено.

Пример с кодированием Хаффмана

Мы используем те же частоты, что и в приведенном выше примере Шеннона – Фано, а именно:

Символ	А	Б	С	Д	И
Считать	15	7	6	6	5
Вероятности	0.385	0.179	0.154	0.154	0.128

В этом случае D и E имеют самые низкие частоты, поэтому им присваиваются 0 и 1 соответственно и группируются с общей вероятностью 0,282. Самой низкой парой сейчас являются B и C, поэтому им присвоены 0 и 1 и сгруппированы вместе с общей вероятностью 0,333. В результате BC и DE теперь имеют наименьшие вероятности, поэтому к их кодам добавляются 0 и 1, и они объединяются. Тогда остаются только A и BCDE, к которым добавлены 0 и 1 соответственно, а затем они объединяются. В результате у нас остается один узел, и наш алгоритм завершен.

На этот раз длины кода для разных символов составляют 1 бит для A и 3 бита для всех остальных символов.

Символ	А	Б	С	Д	И
Кодовые слова	0	100	101	110	111

В результате длина A составляет 1 бит, а для B, C, D и E — 3 бита, что дает среднюю длину

{\frac {1\,{\text{bit}}\cdot 15+3\,{\text{bits}}\cdot (7+6+6+5)}{39\,{\text{symbols}}}}\approx 2.23\,{\text{bits per symbol.}}

Мы видим, что код Хаффмана превзошел оба типа кода Шеннона-Фано, которые ожидали длины 2,62 и 2,28.

Примечания

^ Каур, Сандип; Сингх, Сукджит (май 2016 г.). «Энтропийное кодирование и различные методы кодирования» (PDF) . Журнал сетевых коммуникаций и новых технологий . 6 (5): 5. S2CID 212439287 . Архивировано из оригинала (PDF) 3 декабря 2019 г. Проверено 3 декабря 2019 г.
^ Перейти обратно: ^а ^б ^с Станислав Крайчи, Чин-Фу Лю, Ладислав Микеш и Стефан М. Мозер (2015), «Анализ производительности кодирования Фано», Международный симпозиум IEEE по теории информации (ISIT) , 2015 г.
^ Технический журнал Bell System 1948-07: Том 27, выпуск 3 . Лаборатории AT&T Bell. 1 июля 1948 г. п. 403.
^ Томас М. Кавер и Джой А. Томас (2006), Элементы теории информации (2-е изд.), Wiley – Interscience. «Исторические заметки» к главе 5.
^ Чарльз М. Голди и Ричард Дж. Э. Пинч (1991), Теория коммуникации , Издательство Кембриджского университета. Раздел 1.6.
^ Гарет А. Джонс и Дж. Мэри Джонс (2012), Теория информации и кодирования (Springer). Раздел 3.4.
^ Те Сун Хан и Кинго Кобаяши (2007), Математика информации и кодирования , Американское математическое общество. Подраздел 3.7.1.
^ Раймонд В. Юнг (2002), Первый курс теории информации , Springer. Подраздел 3.2.2.
^ Дэвид Саломон (2013), Сжатие данных: полный справочник , Springer. Раздел 2.6.
^ Пракаш К. Гупта (2006), Передача данных и компьютерные сети , Phi Publishing. Подраздел 1.11.5.
^ " APPNOTE.TXT - Спецификация формата файла .ZIP» . PKWARE Inc. 28 сентября 2007 г. Проверено 06 января 2008 г. Алгоритм Imploding на самом деле представляет собой комбинацию двух различных алгоритмов. Первый алгоритм сжимает повторяющиеся последовательности байтов с использованием скользящего словаря. Второй алгоритм Алгоритм используется для сжатия кодирования вывода скользящего словаря с использованием нескольких деревьев Шеннона – Фано.
^ Цзэнянь Ли; Марк С. Дрю; Цзянчуань Лю (9 апреля 2014 г.). Основы мультимедиа . Springer Science & Business Media. ISBN 978-3-319-05290-8 .
^ Хаффман, Д. (1952). «Метод построения кодов с минимальной избыточностью» (PDF) . Труды ИРЭ . 40 (9): 1098–1101. дои : 10.1109/JRPROC.1952.273898 .

Ссылки

Фано, РМ (1949). «Передача информации» . Технический отчет №65 . Кембридж (Массачусетс), США: Исследовательская лаборатория электроники Массачусетского технологического института.
Шеннон, CE (июль 1948 г.). «Математическая теория связи [перепечатка с исправлениями]» . Технический журнал Bell System . 27 : 379–423. дои : 10.1002/j.1538-7305.1948.tb01338.x .

[Kaur-1] Каур, Сандип; Сингх, Сукджит (май 2016 г.). «Энтропийное кодирование и различные методы кодирования» (PDF) . Журнал сетевых коммуникаций и новых технологий . 6 (5): 5. S2CID 212439287 . Архивировано из оригинала (PDF) 3 декабря 2019 г. Проверено 3 декабря 2019 г.

[Kraj-2] Перейти обратно: ^а ^б ^с Станислав Крайчи, Чин-Фу Лю, Ладислав Микеш и Стефан М. Мозер (2015), «Анализ производительности кодирования Фано», Международный симпозиум IEEE по теории информации (ISIT) , 2015 г.

[3] Технический журнал Bell System 1948-07: Том 27, выпуск 3 . Лаборатории AT&T Bell. 1 июля 1948 г. п. 403.

[4] Томас М. Кавер и Джой А. Томас (2006), Элементы теории информации (2-е изд.), Wiley – Interscience. «Исторические заметки» к главе 5.

[5] Чарльз М. Голди и Ричард Дж. Э. Пинч (1991), Теория коммуникации , Издательство Кембриджского университета. Раздел 1.6.

[6] Гарет А. Джонс и Дж. Мэри Джонс (2012), Теория информации и кодирования (Springer). Раздел 3.4.

[7] Те Сун Хан и Кинго Кобаяши (2007), Математика информации и кодирования , Американское математическое общество. Подраздел 3.7.1.

[8] Раймонд В. Юнг (2002), Первый курс теории информации , Springer. Подраздел 3.2.2.

[9] Дэвид Саломон (2013), Сжатие данных: полный справочник , Springer. Раздел 2.6.

[10] Пракаш К. Гупта (2006), Передача данных и компьютерные сети , Phi Publishing. Подраздел 1.11.5.

[appnote-11] " APPNOTE.TXT - Спецификация формата файла .ZIP» . PKWARE Inc. 28 сентября 2007 г. Проверено 06 января 2008 г. Алгоритм Imploding на самом деле представляет собой комбинацию двух различных алгоритмов. Первый алгоритм сжимает повторяющиеся последовательности байтов с использованием скользящего словаря. Второй алгоритм Алгоритм используется для сжатия кодирования вывода скользящего словаря с использованием нескольких деревьев Шеннона – Фано.

[LiDrew2014-12] Цзэнянь Ли; Марк С. Дрю; Цзянчуань Лю (9 апреля 2014 г.). Основы мультимедиа . Springer Science & Business Media. ISBN 978-3-319-05290-8 .

[13] Хаффман, Д. (1952). «Метод построения кодов с минимальной избыточностью» (PDF) . Труды ИРЭ . 40 (9): 1098–1101. дои : 10.1109/JRPROC.1952.273898 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]