Кодирование Шеннона – Фано - Shannon–Fano coding

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

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

Коды Шеннона – Фано субоптимальны в том смысле, что они не всегда достигают минимально возможной ожидаемой длины кодового слова, как кодирование Хаффмана . Однако коды Шеннона – Фано имеют ожидаемую длину кодового слова в пределах 1 бита от оптимальной. Метод Фано обычно производит кодирование с меньшей ожидаемой длиной, чем метод Шеннона. Однако метод Шеннона легче анализировать теоретически.

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

Именование

Что касается путаницы в двух разных кодах, называемых одним и тем же именем, Крайчи и др. Пишут:

Примерно в 1948 году Клод Э. Шеннон (1948) и Роберт М. Фано (1949) независимо друг от друга предложили два разных алгоритма кодирования источника для эффективного описания дискретного источника без памяти. К сожалению, несмотря на различие, обе схемы стали известны под одним и тем же названием кодирования Шеннона – Фано .

Причин такой путаницы несколько. Во-первых, при обсуждении своей схемы кодирования Шеннон упоминает схему Фано и называет ее «практически такой же» (Шеннон, 1948, стр. 17). С другой стороны, схемы кодирования Шеннона и Фано схожи в том смысле, что они обе являются эффективными, но неоптимальные схемы кодирования без префиксов с аналогичной производительностью.

Метод Шеннона (1948), использующий заранее определенные длины слов, был назван Ковером и Томасом, Голди и Пинчем, Джонсом и Джонсом и Ханом и Кобаяши кодированием Шеннона – Фано . Юнг назвал это кодированием Шеннона .

Метод Фано (1949), использующий двоичное деление вероятностей, Саломон и Гупта называют кодированием Шеннона – Фано . Это называется кодированием Фано Krajči et al.

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

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

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

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

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

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

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

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

Пример

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

Символ	А	B	C	D	E
Считать	15	7	6	6	5
Вероятности	0,385	0,179	0,154	0,154	0,128

У этого источника есть биты энтропии . ${\ Displaystyle H (X) = 2,186}$

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

Символ	А	B	C	D	E
Вероятности	0,385	0,179	0,154	0,154	0,128
${\ displaystyle - \ log _ {2} p_ {i}}$	1,379	2,480	2,700	2,700	2,963
Длина слова ${\ displaystyle \ lceil - \ log _ {2} p_ {i} \ rceil}$	2	3	3	3	3

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

Символ	А	B	C	D	E
Вероятности	0,385	0,179	0,154	0,154	0,128
Длина слова ${\ displaystyle \ lceil - \ log _ {2} p_ {i} \ rceil}$	2	3	3	3	3
Кодовые слова	00	010	011	100	101

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

Символ	А	B	C	D	E
Вероятности	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
Длина слова ${\ displaystyle \ lceil - \ log _ {2} p_ {i} \ rceil}$	2	3	3	3	3
Кодовые слова	00	011	100	101	110

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

${\ displaystyle {\ frac {2 \, {\ text {bits}} \ cdot (15) +3 \, {\ text {bits}} \ cdot (7 + 6 + 6 + 5)} {39 \, { \ text {symbols}}}} \ приблизительно 2,62 \, {\ text {бит на символ,}}}$

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

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

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

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

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

${\ displaystyle \ 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.}$

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

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

Наброски кода Фано

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

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

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

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

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

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

Пример

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

Символ	А	B	C	D	E
Считать	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-битные коды, как показано в таблице ниже:

Символ	А	B	C	D	E
Вероятности	0,385	0,179	0,154	0,154	0,128
Первая дивизия	0		1
Второй дивизион	0	1	0	1
Третий дивизион				0	1
Кодовые слова	00	01	10	110	111

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

${\ displaystyle {\ frac {2 \, {\ text {bits}} \ cdot (15 + 7 + 6) +3 \, {\ text {bits}} \ cdot (6 + 5)} {39 \, { \ text {symbols}}}} \ приблизительно 2,28 \, {\ text {бит на символ.}}}$

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

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

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

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

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

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

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

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

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

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

Символ	А	B	C	D	E
Считать	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 бита для всех остальных символов.

Символ	А	B	C	D	E
Кодовые слова	0	100	101	110	111

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

${\ displaystyle {\ frac {1 \, {\ text {bit}} \ cdot 15 + 3 \, {\ text {bits}} \ cdot (7 + 6 + 6 + 5)} {39 \, {\ text {символы}}}} \ приблизительно 2,23 \, {\ text {бит на символ.}}}$

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

Заметки

Рекомендации

• Фано, RM (1949). «Передача информации» . Технический отчет № 65 . Кембридж (Массачусетс), США: Исследовательская лаборатория электроники Массачусетского технологического института.
• Шеннон, CE (июль 1948 г.). «Математическая теория коммуникации» . Технический журнал Bell System . 27 : 379–423.