Код шеннона


Код Шеннона

Допyстим тебе нyжно закодиpовать некотоpое сообщение: AABCDAABC

Длина всего сообщения 10 (Вычисляется веpоятность встpечаемости каждого символа и pасполагаем их в столбик в поpядке yбывания веpоятностей)

После этого стpоим кодовые комбинации пpостым методом. Делим столбик с веpоятностями таким обpазмо, чтобы сyмма веpоятностей веpхней части pавнялась пpиблизительно сyмме веpоятностей нижней части

Напpитив веpоятностей веpхней части пpоставляем нyли, напpотив нижней — еденицы. В нашем пpимеpе полyчим.

Пpделываем потом то же с pазделенными частями. В конце-концов пpидем к томy, что делить больше нечего.

Итого — AABCDAABC = 0 0 10 110 111 0 0 10 110

Пpичем закодиpованное сообщение (это видно) не может быть pаскодиpовано несколькими способами, хотя длина кодов символов отличается. Чтобы пpочитать закодиpованное сообщение стpоится бинаpное деpево. В нашем слyчае оно бyдет такое.

Вот еще пpимеp составления кодовых комбинаций по веpоятносям:

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

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

Содержание

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

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

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

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

Когда размер подалфавита становится равен нулю или единице, то дальнейшего удлинения префиксного кода для соответствующих ему символов первичного алфавита не происходит, таким образом, алгоритм присваивает различным символам префиксные коды разной длины. На шаге деления алфавита существует неоднозначность, так как разность суммарных вероятностей p 0 − p 1 <\displaystyle p_<0>-p_<1>> может быть одинакова для двух вариантов разделения (учитывая, что все символы первичного алфавита имеют вероятность больше нуля).

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

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

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

Код Шеннона

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

Этот метод был первым в своём роде, эта методика была использована для доказательства теоремы Шеннона о помехоустойчивом кодировании в 1948 в его статье «Математическая Теория связи» [1] .

Пример

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

Код Шеннона-Фано

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

Содержание

Основные сведения [ | ]

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

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

Основные этапы [ | ]

Когда размер подалфавита становится равен нулю или единице, то дальнейшего удлинения префиксного а для соответствующих ему символов первичного алфавита не происходит, таким образом, алгоритм присваивает различным символам префиксные ы разной длины. На шаге деления алфавита существует неоднозначность, так как разность суммарных вероятностей p 0 − p 1 <\displaystyle p_<0>-p_<1>> может быть одинакова для двух вариантов разделения (учитывая, что все символы первичного алфавита имеют вероятность больше нуля).

Алгоритм вычисления ов Шеннона — Фано [ | ]

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

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

Илон Маск рекомендует:  Глава 7 редактирование исходных файлов

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

Wikipedia open wikipedia design.

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

Содержание

Основные сведения [ править | править код ]

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

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

Основные этапы [ править | править код ]

Когда размер подалфавита становится равен нулю или единице, то дальнейшего удлинения префиксного кода для соответствующих ему символов первичного алфавита не происходит, таким образом, алгоритм присваивает различным символам префиксные коды разной длины. На шаге деления алфавита существует неоднозначность, так как разность суммарных вероятностей p 0 − p 1 <\displaystyle p_<0>-p_<1>> может быть одинакова для двух вариантов разделения (учитывая, что все символы первичного алфавита имеют вероятность больше нуля).

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

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

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

27. Код Шеннона-Фано. Код Хаффмана.

Код Шеннона-Фано

Код строится следующим образом:

1) буквы алфавита сообщений выпи­сываются в таблицу в порядке убывания вероятностей;

2) затем они разделя­ются на две группы так, чтобы суммы вероятностей в каждой из групп бы­ли по возможности одинаковы;

3) всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним — 0;

4) каждая из получен­ных групп, в свою очередь, разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д.

Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.


Пример. Рассмотрим алфавит из восьми букв (табл. 12). При обычном (не учитывающем статистических характеристик) кодировании для пред­ставления каждой буквы требуется три символа.

Таблица 8.12 Таблица 13

Буквы Вероят­ности Кодовые комбинации Буквы Вероят­ности Кодовые комбинации
0,22 11 0,22 11
0,20 101 0,20 10
0,16 100 0,16 011
0,16 01 0,16 010
0,10 001 0,10 001
0,10 0001 0,10 0001
0,04 00001 0,04 00001
0,02 00000 0,02 00000

Вычислим энтропию набора букв: Н

и среднее число символов на букву

где n() — число символов в кодовой комбинации, соответствующей букве.

Значения Н(z) и lср не очень различаются по величине. Условие теоремы Шеннона выполнено Н(z) 2 неопределенность ста­новится еще больше.

Метод Хаффмена

Метод Хаффмена свободен от недостатка связанного с неоднозначностью построения кода. Данная методика также использует статистические свойства источника сообщений. Метод гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.

В таблице 14 показаны основные шаги построения кода.

Буквы Вероятности Вспомогательные столбцы
1 2 3 4 5 6 7
0,22 0,22 0,22 0,26 0,32 0,42 0,58 1
0,20 0,20 0,20 0,22 0,26 0,32 0,42
0,16 0,16 0,16 0,20 0,22 0,26
0,16 0,16 0,16 0,16 0,20
0,10 0,10 0,16 0,16
0,10 0,10 0,10
0,04 0,06
0,02

Для двоичного кода методика сводится к следующему:

1) Буквы алфавита сообщений выписываются в основной столбец в порядке убывания вероят­ностей;

2) две последние буквы объединяются в одну вспомогательную бук­ву, которой приписывается суммарная вероятность;

3) вероятности букв, не участвовавших в объединении, и полу­ченная суммарная вероятность снова располагаются в порядке убывания ве­роятностей в дополнительном столбце, а две последние буквы снова объединяются.

Процесс продолжается до тех пор, пока не полу­чим единственную вспомогательную букву с вероятностью, равной единице.

Для составления кодовой комбина­ции, соответствующей данному сообще­нию, необходимо проследить путь пере­хода сообщений по строкам и столбцам таблицы. Для наглядности строится кодо­вое дерево(рис.1).

Рис.1 Кодовое дерево

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

Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию;

01 00 111 110 100 1011 10101 10100

Оставить комментарий Отменить ответ

Для отправки комментария вам необходимо авторизоваться.

Примерами префиксных кодов являются коды Шеннона-Фано и Хаффмана.

Код Шеннона-Фано

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

Рис. Кодовое дерево кода Шеннона – Фано

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

Код Хаффмана

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

Для нахождения кодовой комбинации необходимо проследить путь перехода знака по строкам и столбцам таблицы. Это наиболее наглядно осуществимо по кодовому дереву. Из точки, соответ­ствующей вероятности 1, направляются две ветви, причем ветви с большей вероятностью присваиваем символ 1, а с меньшей – 0. Такое последователь­ное ветвление продолжается до тех пор, пока не дойдем до вероятности каж­дой буквы. Двигаясь по кодовому дереву сверху вниз, можно записать для каждого сообщения соответствующие ему кодовые комбинации.

Код Шеннона-Фано

ЛАБОРАТОРНАЯ РАБОТА 9

Эффективное кодирование

Цель: Изучение методик эффективного кодирования.

1. Построить код Шеннона-Фано по выбранным вариантам и результаты свести в таблицы.

2. Построить код Хаффмана по выбранным вариантам и результаты свести в таблицы. Для каждого построенного кода построить кодовое дерево.

Отчет по лабораторной работе должен содержать:

– краткие теоретические сведения о коде Шеннона-Фано и коде Хаффмана;

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

Илон Маск рекомендует:  rp в HTML

Основные понятия и определения

Код Шеннона-Фано

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

Пример 1. Проведем эффективное кодирование ансамбля из восьми знаков, характеристики которого представлены в табл. 3.1.

Характеристики ансамбля из восьми знаков

Знаки Вероятность Кодовые комбинации Ступень разбиения
Z1 0.22
Z2 0.2
Z3 0.16
Z4 0.16
Z5 0.1
Z6 0.1
Z7 0.04
Z8 0.02

Рис. 3.1. Дерево группового разделения вероятностей Шеннона-Фано

Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждого знака требуется три двоичных символа. Используя методику Шеннона-Фано, получаем совокупность кодовых комбинаций, приведенных в табл. 3.1.

Так как вероятности знаков представляют собой целочисленные отрицательные степени двойки, то избыточность при кодировании устраняется полностью. Среднее число символов на знак в этом случае точно равно энтропии. Убедимся в этом, вычислив энтропию

и среднее число символов на знак

где – число символов в кодовой комбинации, соответствующей знаку .

В общем случае для алфавита из восьми знаков среднее число символов на знак будет меньше трех, но больше энтропии алфавита .

Пример 2. Определим среднюю длину кодовой комбинации при эффективном кодировании знаков ансамбля. Приведенного в табл. 3.2.

Энтропия ансамбля равна 2,76. В результате сопоставления отдельным знакам ансамбля кодовых комбинаций по методике Шеннона-Фано (табл. 3.2) получаем среднее число символов на знак, равное 2,84.

Характеристики ансамбля из восьми знаков

Знаки Вероятность Кодовые комбинации Ступень разбиения
Z1 0,22
Z2 0,20
Z3 0,16
Z4 0,16
Z5 0,10
Z6 0,10
Z7 0,04
Z8 0,02

Следовательно, некоторая избыточность в последовательностях символов осталась. Из теоремы Шеннона следует, что эту избыточность также можно устранить, если перейти к кодированию достаточно большими блоками.

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

От указанного недостатка свободна методика Хаффмана. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.

Дата добавления: 2015-09-20 ; просмотров: 714 | Нарушение авторских прав

Коды Шеннона-Фано, Хафмана, Лемпела-Зива.

Методы сжатия делятся на статистические и словарные. Словарные методы заключаются в том, чтобы в случае встречи подстроки, которая уже была найдена раньше, кодировать ссылку, которая занимает меньше места, чем сама подстрока. Классическим словарным методом является метод Лемпела-Зива (LZ). Все используемые на сегодняшний день словарные методы являются лишь модификациями LZ.
Статистическое кодирование заключается в том, чтобы кодировать каждый символ, но использовать коды переменной длины. Примером таких методов служит метод Хаффмана (Huffman). Обычно словарные и статистические методы комбинируются, поскольку у каждого свои преимущества.

Метод Шеннона-Фано.

Кодирование Шеннона-Фано — алгоритм префиксного неоднородного кодирования. Относится к вероятностным методам сжатия.

Данный метод выделяется своей простотой. Берутся исходные сообщения m(i) и их вероятности появления P(m(i)). Этот список делится на две группы с примерно равной интегральной вероятностью. Каждому сообщению из группы 1 присваивается 0 в качестве первой цифры кода. Сообщениям из второй группы ставятся в соответствие коды, начинающиеся с 1. Каждая из этих групп делится на две аналогичным образом и добавляется еще одна цифра кода. Процесс продолжается до тех пор, пока не будут получены группы, содержащие лишь одно сообщение. Каждому сообщению в результате будет присвоен код x c длиной –lg(P(x)). Это справедливо, если возможно деление на подгруппы с совершенно равной суммарной вероятностью. Если же это невозможно, некоторые коды будут иметь длину –lg(P(x))+1. На шаге делеения алфавита существует неоднозначность, так как разность суммарных вероятностей pp1 может быть одинакова для двух вариантов разделения (учитывая, что все символы первичного алфавита имеют вероятность, большую нуля). Алгоритм Шеннона-Фано не гарантирует оптимального кодирования.

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

Идея, лежащая в основе кода Хаффмана, достаточно проста. Вместо того чтобы кодировать все символы одинаковым числом бит, будем кодировать символы, которые встречаются чаще, меньшим числом бит, чем те, которые встречаются реже. Более того, потребуем, чтобы код был оптимален.

В отличие от алгоритма Шеннона-Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами.

Этот метод кодирования состоит из двух основных этапов:

1. Построение оптимального кодового дерева.


2. Построение отображения код-символ на основе построенного дерева.

1. Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).

2. Символы первичного алфавита m1 выписывают в порядке убывания вероятностей.

3.Последние n символов объединяют в новый символ, вероятность которого равна суммарной вероятности этих символов, удаляют эти символы и вставляют новый символ в список остальных на соответствующее место (по вероятности). n вычисляется из системы:
,
где a — целое число, m1 и m2 — мощность первичного и вторичного алфавита соответственно.

4. Последние m2 символов снова объединяют в один и вставляют его в соответствующей позиции, предварительно удалив символы, вошедшие в объединение.

5. Предыдущий шаг повторяют до тех пор, пока сумма всех m2 символов не станет равной 1.

Этот процесс можно представить как построение дерева, корень которого — символ с вероятностью 1, получившийся при объединении символов из последнего шага, его m2 потомков — символы из предыдущего шага и т.д.

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

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

Алгори́тм Ле́мпеля — Зи́ва —это универсальный алгоритм сжатия данных без потерь. Алгоритм разработан так, чтобы его можно было быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных.

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

Декодирование LZW-данных производится в обратном порядке. Декомпрессор читает код из потока данных и, если этого кода еще нет в словаре, добавляет его туда. Затем этот код переводится в строку, которую он представляет, и заносится в выходной поток несжатых данных.

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

Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту. **/

5.Коды Хэмминга, свойство оптимальности

Помехоустойчивый код — двоичный код, позволяющий обнаруживать и корректировать ошибки при передаче данных. Код Хэмминга обнаруживает ошибки в двух битах и позволяет корректировать один бит. Контрольные разряды занимают позиции с номерами i = 2^j, j=0,1,2. . Значения контрольных разрядов равно сумме разрядов, номера которых больше номера контрольного разряда и таких, что двоичное представление номера содержит единицу в разряде j начиная с младших разрядов.

B2 = B3 + B6 + B7 + B10 + B11 (если длина исходного слова 7 бит)

Если слово полученное после подстановки контрольных разрядов передано правильно, то выражение полученное в результате сложения контрольных разрядов и суммы, вычисленной по вышеуказнному правилу, будет равно 0.

S2= B2 + B3 + B6 + B7 + B10 + B11 (если длина исходного слова 7 бит)

Если какой-то разряд исказился, некоторые значения выражений будут равны 1. Пусть исказился Bi, тогда первое значение (S1) станет равно 1, если двоичное представление i содержит 1 в младшем разряде. Второе значение (S2), если во втором и т.д. Величина . S3,S2,S1 — номер искажённого разряда.

entity Hamming is
port(Ic : in std_ulogic_vector(6 downto 0);
Id : in std_ulogic_vector(10 downto 0);
Oc : in std_ulogic_vector(10 downto 0);
Od : in std_ulogic_vector(6 downto 0);
end Hammaing;

Ic — вход для кодирования
Id — вход для декодирования
Oc — закодированное слово Ic
Od — декодированное слово Id

Илон Маск рекомендует:  Турне по c

Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим.

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.

Папиллярные узоры пальцев рук — маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни.

Шеннон кодирование информации. Коды шеннона — фано

При ответе на данный вопрос необходимо привести пример построения префиксного кода Шеннона-Фано для заданного начального алфавита и известных частот использования символов этого алфавита с помощью таблицы и графа.

В 1948-1949 гг. Клод Шеннон (Claude Elwood Shannon ) и Роберт Фано (Robert Mario Fano ) независимо друг от друга предложили префиксный код, названный в последствие в их честь. Алгоритм Шеннона — Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его первичного алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов — более длинными двоичными последовательностями.

Рассмотрим этот префиксный код на примере. Пусть имеется первичный алфавит, состоящий из шести символов: , также известны вероятности появления этих символов в сообщении соответственно <0,15; 0,2; 0,1; 0,3; 0,2; 0,05>. Расположим эти символы в таблице в порядке убывания их вероятностей.

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

Продолжим деление каждой группы. В первой группе два элемента, и деление на подгруппы здесь однозначно: в первой подгруппе будет символ D, а во второй — символ B. Во второй группе теоретически возможны три способа деления на подгруппы: и , и , и . Но в первом случае абсолютная разность суммарных вероятностей будет |0,2 — (0,15 + 0,1 + 0,05)| = 0,1. Во втором и третьем варианте деления аналогичные величины будут 0,2 и 0,4 соответственно. Согласно алгоритму необходимо выбрать тот способ деления, при котором суммы вероятностей в каждой подгруппе были примерно одинаковыми, а, следовательно, вычисленная разность минимальна. Соответственно наилучшим способом деления будет следующий вариант: в первой подгруппе и во второй. Далее по имеющемуся алгоритму распределим нули и единицы в соответствующие знаки кода каждой подгруппы.

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

Первичный алфавит Вероятности появления Знаки кода символа Код символа Длина кода
I II III IV
D 0,3 Х Х
B 0,2 Х Х
E 0,2 Х Х
A 0,15 Х
C 0,1
F 0,05

Данный код может быть построен и с помощью графа. Распределим символы алфавита в порядке убывания вероятностей — это будут концевые вершины (листья) будущего двоичного дерева (нижние индексы соответствуют вероятностям появления символов):

D 0,3 B 0,2 E 0,2 A 0,15 C 0,1 F 0,05

Согласно алгоритму построения кода Шеннона-Фано разобьем эти символы на две группы с приблизительно равными суммарными вероятностями появления и соединим первые символы каждой группы с корнем дерева:

D 0,3 B 0,2 E 0,2 A 0,15 C 0,1 F 0,05

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

D 0,3 B 0,2 E 0,2 A 0,15 C 0,1 F 0,05
D 0,3 B 0,2 E 0,2 A 0,15 C 0,1 F 0,05

Окончательно имеем следующий граф:

D 0,3 B 0,2 E 0,2 A 0,15 C 0,1 F 0,05

Теперь для каждого узла ветвления обозначим каждую левую исходящую дугу цифрой 0, а каждую правую исходящую дугу цифрой 1:

D 0,3 B 0,2 E 0,2 A 0,15 C 0,1 F 0,05

Для получения кода символа достаточно пройти по дугам полученного дерева от корня к соответствующей вершине и записать номера дуг, по которым осуществляется движение. Например, для символа A, двигаясь от корня дерева, проходим дуги с номерами 1, 1 и 0, следовательно код символа A — 110. Аналогично могут быть получены коды других символов.

Полученный код удовлетворяет условию Фано, следовательно он является префиксным. Средняя длина этого кода равна (см. формулу на стр.13):

К(Шеннона-Фано, А, Binary) = 0,3*2+0,2*2+0.2*2+0,15*3 +0,1*4+0.05*4 = 2,45 символа.

Теперь по известной нам формуле найдем избыточность кода Шеннона –Фано:

Q(Шеннона-Фано, A, Binary) = 2,45/2,41 – 1 = 0,01659751.

То есть избыточность кода Шеннона-Фано для нашего шестибуквенного алфавита составляет всего около 1,7 %. Для русского алфавита этот избыточность кодирования кодом Шеннона-Фано составила бы примерно 1,47%.

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

При ответе на данный вопрос необходимо привести пример построения префиксного кода Хаффмана для заданного начального алфавита и известных частот использования символов этого алфавита с помощью таблицы и графа.

В 1952 году Давид Хаффман показал, что предложенный им метод кодирования является оптимальным префиксным кодом для дискретных источников без памяти (у такого источника все сообщения независимы).

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

Рассмотрим алгоритм построения кода Хаффмана на примере. Пусть имеется первичный алфавит, состоящий из шести символов: , также известны вероятности появления этих символов в сообщении соответственно <0,15; 0,2; 0,1; 0,3; 0,2; 0,05>. Расположим эти символы в таблице в порядке убывания их вероятностей.

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

A 0 Код А 0 A 1 Код А 1 А 2 Код А 2 А 3 Код А 3 А 4 Код А 4
a 0 1 =D P = 0,3 a 1 1 P = 0,3 a 2 1 P = 0,3 a 3 1 P = 0,4 a 4 1 P = 0,6
a 0 2 =B P = 0,2 a 1 2 P = 0,2 a 2 2 P = 0,3 a 3 2 P = 0,3 a 4 2 P = 0,4
a 0 3 =E P = 0,2 a 1 3 P = 0,2 a 2 3 P = 0,2 a 3 3 P = 0,3
a 0 4 =A P = 0,15 a 1 4 P = 0,15 a 2 4 P = 0,2
a 0 5 =C P = 0,1 a 1 5 P = 0,15
a 0 6 =F P = 0,05

Теперь начинается второй этап алгоритма кодирования по Хаффману. Для формирования кода мы нумеруем символы всех промежуточных алфавитов, начиная с последнего. В нашем примере – с А 4 .

В А 4 всего два символа. Они получают соответственно номера 0 и 1. В алфавите А 3 уже три символа. Причем, один из символов алфавита А 4 , назовем этот символ «предок», был получен объединением двух символов алфавита А 3 , назовем первый из этих символов «дочкой», а второй «сыном». Коды этих двух символов формируются следующим образом. К номеру «предка» приписываются справа 0, чтобы получить номер «дочки», и 1 – чтобы получить номер «сына». Следующая итерация алгоритма по той же схеме формирует коды символов алфавита А 2 . В нем два первых символа будут иметь те же коды, что были у них в А 1 , а два последних символа изменят свой код, удлинив его на 1 символ («0» и «1» соответственно). Процесс останавливается при достижении первичного алфавита A 0 – коды для знаков первичного алфавита получены.

A 0 Код А 0 A 1 Код А 1 А 2 Код А 2 А 3 Код А 3 А 4 Код А 4
a 0 1 =D P = 0,3 a 1 1 P = 0,3 a 2 1 P = 0,3 a 3 1 P = 0,4 a 4 1 P = 0,6
a 0 2 =B P = 0,2 a 1 2 P = 0,2 a 2 2 P = 0,3 01 a 3 2 P = 0,3 a 4 2 P = 0,4
a 0 3 =E P = 0,2 a 1 3 P = 0,2 a 2 3 P = 0,2 a 3 3 P = 0,3
a 0 4 =A P = 0,15 a 1 4 P = 0,15 a 2 4 P = 0,2
a 0 5 =C P = 0,1 a 1 5 P = 0,15
a 0 6 =F P = 0,05

Данный алгоритм построения можно осуществить и с помощью графа. Расположим символы первичного алфавита в порядке убывания вероятностей их появления. Эти символы будут листьями будущего кодового дерева. Будем считать, что уровень этих концевых узлов равен N.

В получившемся промежуточном алфавите вновь выбираем два символа с наименьшей частотой использования. Это символ А с вероятностью 0,15 и новый символ, получившийся в результате объединения символов C и F на предыдущем этапе и имеющий ту же вероятность использования. Соединяем эти символы дугами, исходящими из одного узла N-2 уровня:

Посчитаем среднюю длину кодового слова для кода Хаффмана и нашего первичного алфавита А.

К(Хаффман, А, Binary) = = 0,3*2 + 0,2*2 + 0.2*2 + 0,15*3 + 0,1*4 + 0.05*4 = 2,45 символа

Среднее количество информации на один символ первичного алфавита равно:

I A = — (0,3* log 2 0,3 + 0,2* log 2 0,2 + 0,2* log 2 0,2 + 0,15* log 2 0,15 + + 0,1* log 2 0,1 + 0,05* log 2 0,05) = 2,41 бит.

Относительная избыточность кода Хаффмана в нашем случае:

Q(Хаффмана, A, Binary) = 2,45/2,41 – 1 = 0,01659751.

Таким образом, для нашего примера код Шеннона-Фано и код Хаффмана обладают одинаковой избыточностью. Однако, в тех случаях когда вероятности символов первичного алфавита сильно разнятся, ситуация меняется. Код Хаффмана обладает существенно меньшей избыточностью. Например, для русского языка избыточность кодирования кодом Хаффмана оказывается равной примерно 0,0090.

Для определенности будем рассматривать кодирование в двоичном алфавите (m = 2). Буквы (или любые сообщения, подлежащие кодированию) исходного алфавита записывают в порядке убывающей вероятности. Упорядоченное таким образом множество букв разбивают на две части так, чтобы суммарные вероятности этих подмножеств были примерно равны. Всем знакам (буквам) верхней половины в качестве первого символа присваивают кодовый элемент 1, а всем нижним — 0. Затем каждое подмножество снова разбивается на два подмножества с соблюдением того же условия равенства вероятностей и с тем же условием присваивания кодовых элементов в качестве второго символа. Такое разбиение продолжается до тех пор, пока в подмножестве не окажется только по одной букве кодируемого алфавита. При каждом разбиении буквам верхнего подмножества присваивается кодовый элемент 1, а буквам нижнего подмножества — 0.

Пример. Провести эффективное кодирование ансамбля из восьми знаков:

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL