метод кодирования шеннона фано

Алгоритм вычисления кодов Шеннона-Фано

Код Шеннона-Фано строится с помощью дерева. Построение этого дерева начинается от корня. Всё множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем.

Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0, как в случае кода Хаффмана.

При построении кода Шеннона-Фано разбиение множества элементов может быть произведено, вообще говоря, несколькими способами. Выбор разбиения на уровне n может ухудшить варианты разбиения на следующем уровне (n + 1) и привести к неоптимальности кода в целом. Другими словами, оптимальное поведение на каждом шаге пути ещё не гарантирует оптимальности всей совокупности действий.

Поэтому код Шеннона-Фано не является оптимальным в общем смысле, хотя и дает оптимальные результаты при некоторых распределениях вероятностей. Для одного и того же распределения вероятностей можно построить, вообще говоря, несколько кодов Шеннона-Фано, и все они могут дать различные результаты. Если построить все возможные коды Шеннона-Фано для данного распределения вероятностей, то среди них будут находиться и все коды Хаффмана, то есть оптимальные коды.

Пример кодового дерева

Исходные символы:

A (частота встречаемости 50)

B (частота встречаемости 39)

C (частота встречаемости 18)

D (частота встречаемости 49)

E (частота встречаемости 35)

F (частота встречаемости 24)

Полученный код: A — 11, B — 101, C — 100, D — 00, E — 011, F — 010.

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

Пример 1. Закодируем буквы алфавита в коде Шеннона-Фано.

Пусть имеется случайная величина X (x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈), имеющая восемь состояний с распределением вероятностей

Для кодирования алфавита из восьми букв без учета вероятностей равномерным двоичным кодом нам понадобятся три символа:

Это 000, 001, 010, 011, 100, 101, 110, 111

Чтобы ответить, хорош этот код или нет, необходимо сравнить его с оптимальным значением, то есть определить энтропию

Определив избыточность L по формуле L=1-H/H₀=1-2,75/3=0,084, видим, что возможно сокращение длины кода на 8,4%.

Все буквы записываются в порядке убывания их вероятностей, затем делятся на равновероятные группы, которые обозначаются 0 и 1, затем вновь делятся на равновероятные группы и т.д. (см.табл.4.1)

X	P	Коды
x1	1/4	——-	——-
x2	1/4	——-	——-
x3,	1/8	——-
x4	1/8	——-
x5	1/16
x6	1/16
x7	1/16
x8	1/16

Средняя длина полученного кода будет равна

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

Возьмем 32 две буквы русского алфавита. Частоты этих букв известны. В алфавит включен и пробел, частота которого составляет 0,145. Метод кодирования представлен в таблице

Буква	Рi	Код
?	0.145	—
о	0.095	—
е	0.074
а	0.064
и	0.064
н	0.056
т	0.056	…	…	—
с	0.047	…	…
.	…
ф	0.03

Средняя длина данного кода будет равна, бит/букву;

Энтропия H=4.42 бит/буква. Эффективность полученного кода можно определить как отношение энтропии к средней длине кода. Она равна 0,994. При значении равном единице код является оптимальным. Если бы мы кодировали кодом равномерной длины , то эффективность была бы значительно ниже.

Источник

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

Алгоритм Шеннона-Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона-Фано префиксные, то есть, никакое кодовое слово не является префиксом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов.

Содержание

Основные сведения

Кодирование Шеннона-Фано (англ. Shannon-Fano coding) — алгоритм префиксного неоднородного кодирования. Относится к вероятностным методам сжатия (точнее, методам контекстного моделирования нулевого порядка). Подобно алгоритму Хаффмана алгоритм Шеннона-Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его (первичного) алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов — более длинными двоичными последовательностями.

Алгоритм был независимо друг от друга разработан Шенноном (публикация «Математическая теория связи», 1948 год) и, позже, Фано (опубликовано как технический отчёт).

Основные этапы

Когда размер подалфавита становится равен нулю или единице, то дальнейшего удлинения префиксного кода для соответствующих ему символов первичного алфавита не происходит, таким образом, алгоритм присваивает различным символам префиксные коды разной длины. На шаге деления алфавита существует неоднозначность, так как разность суммарных вероятностей p₀ − p₁ может быть одинакова для двух вариантов разделения (учитывая, что все символы первичного алфавита имеют вероятность, большую нуля).

Алгоритм вычисления кодов Шеннона-Фано

Код Шеннона-Фано строится с помощью дерева. Построение этого дерева начинается от корня. Все множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0, как в случае кода Хаффмана.

При построении кода Шеннона-Фано разбиение множества элементов может быть произведено, вообще говоря, несколькими способами. Выбор разбиения на уровне n может ухудшить варианты разбиения на следующем уровне (n+1) и привести к неоптимальности кода в целом. Другими словами, оптимальное поведение на каждом шаге пути еше не гарантирует оптимальности всей совокупности действий. Поэтому код Шеннона-Фано не является оптимальным в общем смысле, хотя и дает оптимальные результаты при некоторых распределениях вероятностей. Для одного и того же распределения вероятностей можно построить, вообще говоря, несколько кодов Шеннона-Фано, и все они могут дать различные результаты. Если построить все возможные коды Шеннона-Фано для данного распределения вероятностей, то среди них будут находиться и все коды Хаффмана, то есть оптимальные коды.

Пример кодового дерева

A (частота встречаемости 50), B (частота встречаемости 39), C (частота встречаемости 18), D (частота встречаемости 49), E (частота встречаемости 35), F (частота встречаемости 24).

A — 11, B — 101, C — 100, D — 00, E — 011, F — 010.

Кодирование Шеннона-Фано является достаточно старым методом сжатия, и на сегодняшний день оно не представляет особого практического интереса. В большинстве случаев, длина сжатой последовательности, по данному методу, равна длине сжатой последовательности с использованием кодирования Хаффмана. Но на некоторых последовательностях всё же формируются неоптимальные коды Шеннона-Фано, поэтому сжатие методом Хаффмана принято считать более эффективным.

Литература

Ссылки

Методы сжатияТеория

Информация	Собственная · Взаимная · Энтропия · Условная энтропия · Сложность · Избыточность
Единицы измерения	Бит · Нат · Ниббл · Хартли · Формула Хартли

Без потерь

Энтропийное сжатие	Алгоритм Хаффмана · Адаптивный алгоритм Хаффмана · Арифметическое кодирование ( Алгоритм Шеннона — Фано · Интервальное) · Коды Голомба · Дельта · Универсальный код (Элиаса · Фибоначчи)
Словарные методы	RLE · · LZ ( · LZSS · LZW · LZWL · · · LZX · LZRW · LZJB · LZT)
Прочее	RLE · CTW · BWT · PPM · DMC

Аудио

Теория	Свёртка · PCM · Алиасинг · Дискретизация · Теорема Котельникова
Методы	LPC (LAR · LSP) · WLPC · CELP · ACELP · A-закон · μ-закон · MDCT · Преобразование Фурье · Психоакустическая модель
Прочее	Dynamic range compression · Сжатие речи · Полосное кодирование

Изображения

Термины	Цветовое пространство · Пиксел · Chroma subsampling · Артефакты сжатия
Методы	RLE · DPCM · Фрактальный · Wavelet · EZW · SPIHT · LP · ДКП · ПКЛ
Прочее	Битрейт · Test images · PSNR · Квантование

Видео

Термины	Характеристики видео · Кадр · Типы кадров · Качество видео
Методы	Компенсация движения · ДКП · Квантование
Прочее	Видеокодек · Rate distortion theory (CBR · ABR · VBR)

См. также: Программы для сжатия данных • Стандарты и форматы сжатия

Смотреть что такое «Кодирование Шеннона-Фано» в других словарях:

Алгоритм Шеннона — Фано — Алгоритм Шеннона Фано один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано (англ. Fano). Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет … Википедия

Код Шеннона-Фано — Алгоритм Шеннона Фано один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже. Алгоритм… … Википедия

Кодирование энтропии — кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых… … Википедия

Кодирование с минимальной избыточностью — Кодирование энтропии кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных… … Википедия

Кодирование длин серий — (англ. Run length encoding, RLE) или Кодирование повторов простой алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании… … Википедия

Кодирование Хаффмана — Алгоритм Хаффмана (англ. Huffman) адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. В настоящее… … Википедия

Шеннона теорема — Теорема Котельникова (в англоязычной литературе теорема Найквиста) гласит, что, если аналоговый сигнал x(t) имеет ограниченный спектр, то он может быть восстановлен однозначно и без потерь по своим дискретным отсчётам, взятым с частотой более… … Википедия

Кодирование Голомба — Коды Голомба это семейство энтропийных кодеров, являющихся общим случаем унарного кода. Также под кодом Голомба может подразумеваться один из представителей этого семейства. Код Голомба позволяет представить последовательность символов в виде… … Википедия

Алгоритм Шеннона — Алгоритм Шеннона Фано один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано (англ. Robert Fano). Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на… … Википедия

Энтропийное кодирование — Для термина «Кодирование» см. другие значения. Энтропийное кодирование кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения… … Википедия

Источник

СОДЕРЖАНИЕ

Именование

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

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

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

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

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

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

Пример

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

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

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

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

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

2 биты ⋅ ( 15 ) + 3 биты ⋅ ( 7 + 6 + 6 + 5 ) 39 символы ≈ 2,62 бит на символ, <\ displaystyle <\ frac <2 \, <\ text > \ cdot (15) +3 \, <\ text > \ cdot (7 + 6 + 6 + 5)> <39 \, < \ text >>> \ приблизительно 2,62 \, <\ text <бит на символ,>>>

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

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

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

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

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

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

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

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

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

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

Пример

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

Символ	А	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 биты ⋅ ( 15 + 7 + 6 ) + 3 биты ⋅ ( 6 + 5 ) 39 символы ≈ 2,28 бит на символ. <\ displaystyle <\ frac <2 \, <\ text > \ cdot (15 + 7 + 6) +3 \, <\ text > \ cdot (6 + 5)> <39 \, < \ text >>> \ приблизительно 2,28 \, <\ text <бит на символ.>>>

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

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

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

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

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

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

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

Символ	А	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, что дает среднюю длину

1 немного ⋅ 15 + 3 биты ⋅ ( 7 + 6 + 6 + 5 ) 39 символы ≈ 2,23 бит на символ. <\ displaystyle <\ frac <1 \, <\ text > \ cdot 15 + 3 \, <\ text > \ cdot (7 + 6 + 6 + 5)> <39 \, <\ text <символы>>>> \ приблизительно 2,23 \, <\ text <бит на символ.>>>

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

Источник