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

Алгоритмы сжатия данных

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

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

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

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

Нейминг

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

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

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

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

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

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

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

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

При наличии источника с вероятностями желаемые длины кодовых слов равны . Здесь — это функция потолка , то есть наименьшее целое число, большее или равное . ${\displaystyle p_{1},p_{2},\dots ,p_{n}}$ ${\displaystyle l_{i}=\lceil -\log _{2}p_{i}\rceil }$ ${\displaystyle \lceil x\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_{j}{\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 символов со следующими частотами, из которых мы можем оценить вероятности символов.

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

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

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

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

Обратите внимание, что хотя кодовые слова в этих двух методах различны, длина слов одинакова. У нас есть длина 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}}}}\approx 2.62\,{\text{bits per symbol,}}}$$

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

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

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

${\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формата файла . ^[11]

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

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

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

Пример

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

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

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

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

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

Это приводит к длинам в 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}}}}\approx 2.28\,{\text{bits per symbol.}}}$$

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

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

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

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

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

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

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

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

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

Алгоритм Хаффмана

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

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

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

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

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

Примечания

1. Каур, Сандип; Сингх, Сукхджит (май 2016 г.). «Энтропийное кодирование и различные методы кодирования» (PDF) . Журнал сетевых коммуникаций и новых технологий . 6 (5): 5. S2CID  212439287. Архивировано из оригинала (PDF) 2019-12-03 . Получено 3 декабря 2019 г. .
2. Станислав Крайчи, Чин-Фу Лю, Ладислав Микеш и Стефан М. Мозер (2015), «Анализ производительности кодирования Фано», Международный симпозиум IEEE по теории информации (ISIT) 2015 г.
3. Bell System Technical Journal 1948-07: Том 27, выпуск 3. AT & T Bell Laboratories. 1 июля 1948 г., стр. 403.
4. Томас М. Кавер и Джой А. Томас (2006), Элементы теории информации (2-е изд.), Wiley–Interscience. «Исторические заметки» к главе 5.
5. Чарльз М. Голди и Ричард GE Пинч (1991), Теория коммуникации , Cambridge University Press. Раздел 1.6.
6. Гарет А. Джонс и Дж. Мэри Джонс (2012), Теория информации и кодирования (Springer). Раздел 3.4.
7. Те Сун Хан и Кинго Кобаяши (2007), Математика информации и кодирования , Американское математическое общество. Подраздел 3.7.1.
8. Raymond W Yeung (2002), Первый курс теории информации , Springer. Подраздел 3.2.2.
9. Дэвид Саломон (2013), Сжатие данных: полный справочник , Springer. Раздел 2.6.
10. Пракаш С. Гупта (2006), Передача данных и компьютерные сети , Phi Publishing. Подраздел 1.11.5.
11. "APPNOTE.TXT - .ZIP File Format Specification". PKWARE Inc. 2007-09-28 . Получено 2008-01-06 . Алгоритм Imploding на самом деле является комбинацией двух отдельных алгоритмов. Первый алгоритм сжимает повторяющиеся последовательности байтов с помощью скользящего словаря. Второй алгоритм используется для сжатия кодировки выходных данных скользящего словаря с помощью нескольких деревьев Шеннона–Фано.
12. Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 апреля 2014 г.). Основы мультимедиа. Springer Science & Business Media. ISBN 978-3-319-05290-8.
13. Хаффман, Д. (1952). «Метод построения кодов с минимальной избыточностью» (PDF) . Труды IRE . 40 (9): 1098–1101. doi :10.1109/JRPROC.1952.273898.

Ссылки

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