18.8. Задачи кодирования сообщений. Код Шеннона-Фэно .Алгоритм Шеннона - Фано

Привет, Вы узнаете о том , что такое задачи кодирования сообщений код шеннона-фэно алгоритм шеннона - фано, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое задачи кодирования сообщений код шеннона-фэно алгоритм шеннона - фано , настоятельно рекомендую прочитать все из категории Теория информации и кодирования.

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

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

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

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

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

Задачи кодирования сообщений

Вообще кодированием называется отображение состояния одной физической системы с помощью состояния некоторой другой. Например, при телефонном разговоре звуковые сигналы кодируются в виде электромагнитных колебаний, а затем снова декодируются, превращаясь в звуковые сигналы на другом конце линии. Наиболее простым случаем кодирования является случай, когда обе системы и (отображаемая и отображающая) имеют конечное число возможных состояний. Так обстоит дело при передаче записанных буквами сообщений, например, при телеграфировании. Мы ограничимся рассмотрением этого простейшего случая кодирования.

Пусть имеется некоторая система (например, буква русского алфавита), которая может случайным образом принять одно из состояний . Мы хотим отобразить ее (закодировать) с помощью другой системы , возможные состояния которой . Если (число состояний системы меньше числа состояний системы ), то нельзя каждое состояние системы закодировать с помощью одного-единственного состояния системы . В таких случаях одно состояние системы приходится отображать с помощью определенной комбинации (последовательности) состояний системы . Так, в азбуке Морзе буквы отображаются различными комбинациями элементарных символов (точка, тире). Выбор таких комбинаций и установление соответствия между передаваемым сообщением и этими комбинациями и называется «кодированием» в узком смысле слова.

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

Одно и то же сообщение можно закодировать различными способами. Возникает вопрос об оптимальных (наивыгоднейших) способах кодирования. Естественно считать наивыгоднейшим такой код, при котором на передачу сообщений затрачивается минимальное время. Если на передачу каждого элементарного символа (например 0 или 1) тратится одно и то же время, то оптимальным будет такой код, при котором на передачу сообщения заданной длины будет затрачено минимальное количество элементарных символов.

Предположим, что перед нами поставлена задача: закодировать двоичным кодом буквы русской азбуки так, чтобы каждой букве соответствовала определенная комбинация элементарных символов 0 и 1 и чтобы среднее число этих символов на букву текста было минимальным.

Рассмотрим 32 буквы русской азбуки: а, б, в, г, д, е, ж, з, и, й, к, л, м, н, о, п, р, с, т, у, ф, х, ц, ч, ш, щ, ъ, ы, ь, э, ю, я плюс промежуток между словами, который мы будем обозначать «–». Если, как принято в телеграфии, не различать букв ъ и ь (это не приводит к разночтениям), то получится 32 буквы: а, б, в, г, д, е, ж. з, и, й, к, л, м, н, о, п, р, с, т, у. ф, х, ц, ч, ш, щ, (ъ, ь). ы. э, ю, я, «–».

Первое, что приходит в голову - это, не меняя порядка букв, занумеровать их подряд, приписав им номера от 0 до 31, и затем перевести нумерацию в двоичную систему счисления. Двоичная система - это такая, в которой единицы разных разрядов представляют собой разные степени двух. Например, десятичное число 12 изобразится в виде

и в двоичной системе запишется как 1100.

Десятичное число 25 -

- запишется в двоичной системе как 11001.

Каждое из чисел может быть изображено пятизначным двоичным числом. Тогда получим следующий код:

а – 00000

б – 00001

в – 00010

г – 00011

………

я – 11110

«-» – 11111

В этом коде на изображение каждой буквы тратится ровно 5 элементарных символов. Возникает вопрос, является ли этот простейший код оптимальным и нельзя ли составить другой код, в котором на одну букву будет в среднем приходиться меньше элементарных символов?

Действительно, в нашем коде на изображение каждой буквы - часто встречающихся «а», «е», «о» или редко встречающихся «щ», «э», «ф» - тратится одно и то же число элементарных символов. Очевидно, разумнее было бы, чтобы часто встречающиеся буквы были закодированы меньшим числом символов, а реже встречающиеся - большим.

Чтобы составить такой код, очевидно, нужно знать частоты букв в русском тексте. Эти частоты приведены в таблице 18.8.1. Буквы в таблице расположены в порядке убывания частот.

Таблица 18.8.1.

Пользуясь такой таблицей, можно составить наиболее экономичный код на основе соображений, связанных с количеством информации. Об этом говорит сайт https://intellect.icu . Очевидно, код будет самым экономичным, когда каждый элементарный символ будет передавать максимальную информацию. Рассмотрим элементарный символ (т. е. изображающий его сигнал) как физическую систему с двумя возможными состояниями: 0 и 1.

Информация, которую дает этот символ, равна энтропии системы и максимальна в случае, когда оба состояния равновероятны; в этом случае элементарный символ передает информацию 1 (дв. ед.). Поэтому основой оптимального кодирования будет требование, чтобы элементарные символы в закодированном тексте встречались в среднем одинаково часто.

Изложим здесь способ построения кода, удовлетворяющего поставленному условию; этот способ известен под названием «кода Шеннона - Фэно». Идея его состоит в том, что кодируемые символы (буквы или комбинации букв) разделяются на две приблизительно равновероятные группы: для первой группы символов на первом месте комбинации ставится 0 (первый знак двоичного числа, изображающего символ); для второй группы - 1. Далее каждая группа снова делится на две приблизительно равновероятные подгруппы; для символов первой подгруппы на втором месте ставится нуль; для второй подгруппы - единица и т. д.

Продемонстрируем принцип построения кода Шеннона - Фэно на материале русского алфавита (табл. 18.8.1). Отсчитаем первые шесть букв (от «-» до «т»); суммируя их вероятности (частоты), получим 0,498; на все остальные буквы (от «н» до «сф») придется приблизительно такая же вероятность 0,502. Первые шесть букв (от «-» до «т») будут иметь на первом месте двоичный знак 0. Остальные буквы (от «н» до «ф») будут иметь на первом месте единицу. Далее снова разделим первую группу на две приблизительно равновероятные подгруппы: от «-» до «о» и от «е» до «т»; для всех букв первой подгруппы на втором месте поставим нуль, а второй подгруппы"- единицу. Процесс будем продолжать до тех пор, пока в каждом подразделении не останется ровно одна буква, которая и будет закодирована определенным двоичным числом. Механизм построения кода показан на таблице 18.8.2, а сам код приведен в таблице 18.8.3.

Таблица 18.8.2.

Таблица 18.8.3

С помощью таблицы 18.8.3 можно закодировать и декодировать любое сообщение.

В виде примера запишем двоичным кодом фразу: «теория информации»

01110100001101000110110110000

0110100011111111100110100

1100001011111110101100110

Заметим, что здесь нет необходимости отделять друг от друга буквы специальным знаком, так как и без этого декодирование выполняется однозначно. В этом можно убедиться, декодируя с помощью таблицы 18.8.2 следующую фразу:

10011100110011001001111010000

1011100111001001101010000110101

010110000110110110

(«способ кодирования»).

Однако необходимо отметить, что любая ошибка при кодировании (случайное перепутывание знаков 0 и 1) при таком коде губительна, так как декодирование всего следующего за ошибкой текста становится невозможным. Поэтому данный принцип кодирования может быть рекомендован только в случае, когда ошибки при кодировании и передаче сообщения практически исключены.

Возникает естественный вопрос: а является ли составленный нами код при отсутствии ошибок действительно оптимальным? Для того чтобы ответить на этот вопрос, найдем среднюю информацию, приходящуюся на один элементарный символ (0 или 1), и сравним ее с максимально возможной информацией, которая равна одной двоичной единице. Для этого найдем сначала среднюю информацию, содержащуюся в одной букве передаваемого текста, т. е. энтропию на одну букву:

,

где - вероятность того, что буква примет определенное состояние («-», о, е, а,…, ф).

Из табл. 18.8.1 имеем

(дв. единиц на букву текста).

По таблице 18.8.2 определяем среднее число элементарных символов на букву

.

Деля энтропию на , получаем информацию на один элементарный символ

(дв. ед.).

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

Заметим, что в случае кодирования просто двоичных номеров букв мы имели бы изображение каждой буквы пятью двоичными знаками и информация на один символ была бы

(дв. ед.),

т. е. заметно меньше, чем при оптимальном буквенном кодировании.

Однако надо заметить, что кодирование «по буквам» вообще не является экономичным. Дело в том, что между соседними буквами любого осмысленного текста всегда имеется зависимость. Например, после гласной буквы в русском языке не может стоять «ъ» или «ь»; после шипящих не могут стоять «я» или «ю»; после нескольких согласных подряд увеличивается вероятность гласной и т. д.

Мы знаем, что при объединении зависимых систем суммарная энтропия меньше суммы энтропий отдельных систем; следовательно, информация, передаваемая отрезком связного текста, всегда меньше, чем информация на один символ, умноженная на число символов. С учетом этого обстоятельства более экономный код можно построить, если кодировать не каждую букву в отдельности, а целые «блоки» из букв. Например, в русском тексте имеет смысл кодировать целиком некоторые часто встречающиеся комбинации букв, как «тся», «ает», «ние» и т. п. Кодируемые блоки располагаются в порядке убывания частот, как буквы в табл. 18.8.1, а двоичное кодирование осуществляется по тому же принципу.

В ряде случаев оказывается разумным кодировать даже не блоки из букв, а целые осмысленные куски текста. Например, для разгрузки телеграфа в предпраздничные дни целесообразно кодировать условными номерами целые стандартные тексты, вроде:

«поздравляю новым годом желаю здоровья успехов работе».

Не останавливаясь специально на методах кодирования блоками, ограничимся тем, что сформулируем относящуюся сюда теорему Шеннона.

Пусть имеется источник информации и приемник , связанные каналом связи (рис. 18.8.1).

Рис. 18.8.1.

Известна производительность источника информации , т. е. среднее количество двоичных единиц информации, поступающее от источника в единицу времени (численно оно равно средней энтропии сообщения, производимого источникам в единицу времени). Пусть, кроме того, известна пропускная способность канала , т. е. максимальное количество информации (например, двоичных знаков 0 или 1), которое способен передать канал в ту же единицу времени. Возникает вопрос: какова должна быть пропускная способность канала, чтобы он «справлялся» со своей задачей, т. е. чтобы информация от источника к приемнику поступала без задержки?

Ответ на этот вопрос дает первая теорема Шеннона. Сформулируем ее здесь без доказательства.

1-я теорема Шеннона

Если пропускная способность канала связи больше энтропии источника информации в единицу времени

,

то всегда можно закодировать достаточно длинное сообщение так, чтобы оно передавалось каналом связи без задержки. Если же, напротив,

,

то передача информации без задержек невозможна

Основные этапы Алгоритма Шеннона — Фано

Пример построения кодовой схемы для шести символов a1 - a6 и вероятностей pi

1. Символы первичного алфавита m1 выписывают по убыванию вероятностей.
2. Символы полученного алфавита делят на две части, суммарные вероятности символов которых максимально близки друг другу.
3. В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1».
4. Полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде.

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

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

Код Шеннона — Фано строится с помощью дерева. Построение этого дерева начинается от корня. Все множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 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.

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

Вау!! 😲 Ты еще не читал? Это зря!

• Арифметическое кодирование
• кодирование Хаффмана
• Методы сжатия информации
• Энтропийное сжатие информации
• Словарные методы сжатия информации
• Сжатие информации с потерями

Представленные результаты и исследования подтверждают, что применение искусственного интеллекта в области задачи кодирования сообщений код шеннона-фэно алгоритм шеннона - фано имеет потенциал для революции в различных связанных с данной темой сферах. Надеюсь, что теперь ты понял что такое задачи кодирования сообщений код шеннона-фэно алгоритм шеннона - фано и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория информации и кодирования