В области сжатия данных , Шеннона-Фано кодирования , названный в честь Клода Шеннона и Роберта Фано , это имя , данное два различных , но взаимосвязанных методов для построения кода префикса на основе набора символов и их вероятностей (оценивается или измеряется).
- Метод Шеннона выбирает код префикса, где исходный символ дается длина кодового слова . Один из распространенных способов выбора кодовых слов использует двоичное разложение кумулятивных вероятностей. Этот метод был предложен Шенноном в его статье « Математическая теория коммуникации » (1948), посвященной теории информации .
- Метод Фано делит исходные символы на два набора («0» и «1») с вероятностями, максимально близкими к 1/2. Затем эти наборы сами делятся на две части и так далее, пока каждый набор не будет содержать только один символ. Кодовое слово для этого символа - это строка из «0» и «1», которая записывает, на какую половину делений он попал. Этот метод был предложен в более позднем техническом отчете Фано (1949).
Коды Шеннона – Фано субоптимальны в том смысле, что они не всегда достигают минимально возможной ожидаемой длины кодового слова, как кодирование Хаффмана . [1] Однако коды Шеннона – Фано имеют ожидаемую длину кодового слова в пределах 1 бита от оптимальной. Метод Фано обычно производит кодирование с меньшей ожидаемой длиной, чем метод Шеннона. Однако метод Шеннона легче анализировать теоретически.
Кодирование Шеннона-Фано не следует путать с кодированием Шеннона-Фано-Элиаса (также известным как кодирование Элиаса), предшественником арифметического кодирования .
Именование
Что касается путаницы в двух разных кодах, называемых одним и тем же именем, Крайчи и др. [2] пишут:
Примерно в 1948 году Клод Э. Шеннон (1948) и Роберт М. Фано (1949) независимо друг от друга предложили два разных алгоритма кодирования источника для эффективного описания дискретного источника без памяти. К сожалению, несмотря на различие, обе схемы стали известны под одним и тем же названием кодирования Шеннона – Фано .
Причин такой путаницы несколько. Во-первых, при обсуждении своей схемы кодирования Шеннон упоминает схему Фано и называет ее «практически такой же» (Шеннон, 1948, стр. 17). С другой стороны, схемы кодирования Шеннона и Фано схожи в том смысле, что они обе являются эффективными, но неоптимальные схемы кодирования без префиксов с аналогичной производительностью.
Метод Шеннона (1948), использующий предопределенную длину слова, называется кодированием Шеннона – Фано Кавер и Томасом [3] Голди и Пинчем [4] Джонсом и Джонсом [5] и Ханом и Кобаяши. [6] Юнг назвал это кодированием Шеннона . [7]
Метод Фано (1949), использующий двоичное деление вероятностей, Саломон [8] и Гупта назвал кодированием Шеннона – Фано . [9] Это называется кодированием Фано Крайчи и др. [2]
Код Шеннона: предопределенная длина слова
Алгоритм Шеннона
Метод Шеннона начинается с определения длин всех кодовых слов, а затем выбирается префиксный код с этими длинами слов.
Учитывая источник с вероятностями желаемая длина кодового слова . Здесь,это функция потолок , а это означает наименьшее целое число , большее или равное.
Как только длины кодовых слов определены, мы должны выбрать сами кодовые слова. Один из методов состоит в том, чтобы выбрать кодовые слова в порядке от наиболее вероятных до наименее вероятных символов, выбирая каждое кодовое слово как лексикографически первое слово правильной длины, которое поддерживает свойство отсутствия префиксов.
Второй метод использует кумулятивные вероятности. Сначала вероятности записываются в порядке убывания. Тогда кумулятивные вероятности определяются как
так и так далее. Кодовое слово для символа выбран первым двоичные цифры в двоичной записи из.
Пример
В этом примере показано построение кода Шеннона – Фано для небольшого алфавита. Есть 5 разных исходных символов. Предположим, что наблюдались всего 39 символов со следующими частотами, по которым мы можем оценить вероятности символов.
Символ А B C D E Считать 15 7 6 6 5 Вероятности 0,385 0,179 0,154 0,154 0,128
У этого источника есть энтропия биты.
Для кода Шеннона – Фано нам нужно вычислить желаемые длины слов .
Символ А B C D E Вероятности 0,385 0,179 0,154 0,154 0,128 1,379 2,480 2,700 2,700 2,963 Длина слова 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 Длина слова 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 Длина слова 2 3 3 3 3 Кодовые слова 00 011 100 101 110
Обратите внимание, что хотя кодовые слова в двух методах различаются, длины слов одинаковы. У нас есть длина 2 бита для A и 3 бита для B, C, D и E, что дает среднюю длину
что находится в пределах одного бита энтропии.
Ожидаемая длина слова
Для метода Шеннона длины слов удовлетворяют
Следовательно, ожидаемая длина слова удовлетворяет
Здесь, - энтропия , а исходная теорема Шеннона о кодировании говорит, что любой код должен иметь среднюю длину не менее. Следовательно, мы видим, что код Шеннона – Фано всегда находится в пределах одного бита от оптимальной ожидаемой длины слова.
Код Фано: двоичное расщепление
Наброски кода Фано
В методе Фано символы располагаются в порядке от наиболее вероятного к наименее вероятному, а затем делятся на два набора, суммарные вероятности которых максимально близки к равенству. Затем всем символам присваиваются первые цифры их кодов; символы в первом наборе получают «0», а символы во втором наборе получают «1». Пока остаются любые наборы с более чем одним элементом, тот же процесс повторяется для этих наборов, чтобы определить последовательные цифры их кодов. Когда набор сокращен до одного символа, это означает, что код символа завершен и не будет образовывать префикс кода любого другого символа.
Алгоритм производит довольно эффективные кодировки переменной длины; когда два меньших набора, полученные в результате разделения, на самом деле имеют равную вероятность, один бит информации, используемый для их различения, используется наиболее эффективно. К сожалению, кодирование Шеннона – Фано не всегда дает оптимальные префиксные коды; набор вероятностей {0,35, 0,17, 0,17, 0,16, 0,15} является примером того, которому будут назначены неоптимальные коды с помощью кодирования Шеннона – Фано.
Версия кодирования Шеннона – Фано Фано используется в методе сжатия IMPLODE , который является частью формата файла ZIP . [10]
Дерево Шеннона – Фано
Дерево Шеннона – Фано строится в соответствии со спецификацией, разработанной для определения эффективной кодовой таблицы. Фактический алгоритм прост:
- Для данного списка символов составьте соответствующий список вероятностей или частотных подсчетов, чтобы была известна относительная частота появления каждого символа.
- Отсортируйте списки символов по частоте: наиболее часто встречающиеся символы находятся слева, а наименее распространенные - справа.
- Разделите список на две части, при этом общее количество частот левой части должно быть как можно ближе к общему количеству правой части.
- Левая часть списка получает двоичную цифру 0, а правая часть - цифру 1. Это означает, что все коды для символов в первой части будут начинаться с 0, а коды во второй части будут все. начать с 1.
- Рекурсивно применяйте шаги 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, что дает среднюю длину
Мы видим, что метод Фано со средней длиной 2,28 превосходит метод Шеннона со средней длиной 2,62.
Ожидаемая длина слова
Крайчи и др. [2] показали, что ожидаемая длина метода Фано имеет ожидаемую длину, ограниченную сверху величиной, где - вероятность наименее распространенного символа.
Сравнение с другими методами кодирования
Ни один из алгоритмов Шеннона – Фано не гарантирует генерации оптимального кода. По этой причине коды Шеннона – Фано практически не используются; Кодирование Хаффмана почти так же просто в вычислительном отношении и создает префиксные коды, которые всегда достигают минимально возможной ожидаемой длины кодового слова при ограничениях, заключающихся в том, что каждый символ представлен кодом, сформированным из целого числа битов. Это ограничение, которое часто не требуется, так как коды будут упакованы непрерывно в длинные последовательности. Если мы рассматриваем группы кодов одновременно, посимвольное кодирование Хаффмана оптимально только в том случае, если вероятности символов независимы и равны некоторой степени половины, т. Е.. В большинстве ситуаций арифметическое кодирование может производить большее общее сжатие, чем либо Хаффмана, либо Шеннона – Фано, поскольку оно может кодировать дробным числом битов, которые более точно соответствуют фактическому информационному содержанию символа. Однако арифметическое кодирование не заменило Хаффмана, как Хаффмана заменяет Шеннона – Фано, как потому, что арифметическое кодирование требует больших вычислительных затрат, так и потому, что оно защищено множеством патентов. [11]
Кодирование Хаффмана
Несколькими годами позже Дэвид А. Хаффман (1949) [12] дал другой алгоритм, который всегда дает оптимальное дерево для любой заданной вероятности символа. В то время как дерево Шеннона – Фано Фано создается путем деления от корня до листьев, алгоритм Хаффмана работает в противоположном направлении, сливаясь от листьев к корню.
- Создайте листовой узел для каждого символа и добавьте его в очередь с приоритетом , используя его частоту появления в качестве приоритета.
- Пока в очереди более одного узла:
- Удалите из очереди два узла с наименьшей вероятностью или частотой.
- Добавьте 0 и 1 соответственно к любому коду, уже назначенному этим узлам.
- Создайте новый внутренний узел с этими двумя узлами в качестве дочерних и с вероятностью, равной сумме вероятностей двух узлов.
- Добавьте новый узел в очередь.
- Оставшийся узел является корневым узлом, и дерево завершено.
Пример с кодировкой Хаффмана
Мы используем те же частоты, что и в приведенном выше примере Шеннона – Фано, а именно:
Символ А 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, что дает среднюю длину
Мы видим, что код Хаффмана превзошел оба типа кода Шеннона – Фано, которые имели ожидаемые длины 2,62 и 2,28.
Заметки
- ^ Каур, Сандип; Сингх, Сукджит (май 2016 г.). «Энтропийное кодирование и различные методы кодирования» (PDF) . Журнал сетевых коммуникаций и новых технологий . 6 (5): 5. Архивировано из оригинального (PDF) 03.12.2019 . Проверено 3 декабря 2019 .
- ^ a b c Станислав Крайчи, Чин-Фу Лю, Ладислав Микеш и Стефан М. Мозер (2015), «Анализ производительности кодирования Фано», Международный симпозиум IEEE по теории информации (ISIT) 2015 года .
- ^ Томас М. Кавер и Джой А. Томас (2006), Элементы теории информации (2-е изд.), Wiley – Interscience. «Исторические заметки» к главе 5.
- ^ Чарльз М. Голди и Ричард Г. Э. Пинч (1991), Теория коммуникации , Cambridge University Press. Раздел 1.6.
- ^ Гарет А. Джонс и Дж. Мэри Джонс (2012), Теория информации и кодирования (Springer). Раздел 3.4.
- ^ Те Сун Хан и Кинго Кобаяши (2007), Математика информации и кодирования , Американское математическое общество. Подраздел 3.7.1.
- ^ Raymond W Енг (2002), A Первый курс по теории информации , Springer. Подраздел 3.2.2.
- ^ Дэвид Саломон (2013), Сжатие данных: полный справочник , Springer. Раздел 2.6.
- ^ Пракаш С. Гупта (2006), Передача данных и компьютерные сети , Phi Publishing. Подраздел 1.11.5.
- ^ « APPNOTE.TXT - спецификация формата файла .ZIP» . PKWARE Inc. 2007-09-28 . Проверено 6 января 2008 .
Алгоритм взрыва на самом деле представляет собой комбинацию двух различных алгоритмов. Первый алгоритм сжимает повторяющиеся последовательности байтов с помощью скользящего словаря. Второй алгоритм используется для сжатия кодирования вывода скользящего словаря с использованием нескольких деревьев Шеннона – Фано.
- ^ Зэ-Нянь Ли; Марк С. Дрю; Цзянчуань Лю (9 апреля 2014 г.). Основы мультимедиа . Springer Science & Business Media. ISBN 978-3-319-05290-8.
- ^ Хаффман, Д. (1952). «Метод построения кодов с минимальной избыточностью» (PDF) . Труды ИРЭ . 40 (9): 1098–1101. DOI : 10.1109 / JRPROC.1952.273898 .
Рекомендации
- Фано, RM (1949). «Передача информации» . Технический отчет № 65 . Кембридж (Массачусетс), США: Исследовательская лаборатория электроники Массачусетского технологического института .
- Шеннон, CE (июль 1948 г.). «Математическая теория коммуникации» . Технический журнал Bell System . 27 : 379–423.