Закодировать сообщение bbcbbc используя адаптивный алгоритм хаффмена с упорядоченным деревом

Обновлено: 18.05.2024

если (из следует ) - истинно, то ;

если - истинно, то ;

, т.е. независимости и .

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

Для измерения семантической информации также используется функция-мера . Ясно, что или .

Упражнение 17 Вычислить и предложения , про которое известно, что оно достоверно на 50%, и предложения , достоверность которого 25%.

4. Лекция: Сжатие информации

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

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

Кроме того, Доказано 2) утверждение о том, что существует такое кодирование (Шеннона-Фэно, Fano), что .

Рассмотрим д.с.в. и , независимые и одинаково распределенные. и , следовательно,

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

т.е. достаточно брать . Минимум по заданному может быть гораздо меньшим .

Пример. Пусть д.с.в. независимы, одинаково распределены и могут принимать только два значения и при от 1 до . Тогда

Все изложенное ранее подразумевало, что рассматриваемые д.с.в. кодируются только двумя значениями (обычно 0 и 1). Пусть д.с.в. кодируются значениями. Тогда для д.с.в. и любого ее кодирования верно, что и . Кроме того, существует кодирование такое, что и , где .

Простейшие алгоритмы сжатия информации

Метод Шеннона-Фэно состоит в следующем, значения д.с.в. располагают в порядке убывания их вероятностей, а затем последовательно делят на две части с приблизительно равными вероятностями, к коду первой части добавляют 0, а к коду второй - 1.

Для предшествующего примера получим

Еще один пример. Код составляется после сортировки, т.е. после перестановки значений B и C.

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

Построим коды Хаффмена для значений д.с.в. из двух предыдущих примеров.

Упражнение 18 Вычислить для блочного кода Хаффмена для . Длина блока - 2 бита. д.с.в. берется из последнего примера.

Упражнение 19 Вычислить и для кодов Хаффмена и Шеннона-Фэно для . д.с.в. задается следующим распределением вероятностей:

5. Лекция: Арифметическое кодирование

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

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

Пример арифметического кодирования. Пусть д.с.в. может принимать только два значения 0 и 1 с вероятностями 2/3 и 1/3 соответственно. Сопоставим значению 0 отрезок , а 1 - . Тогда для д.с.в. ,

таблица построения кодов -

Шаг 2. Из текущего кода вычитается нижняя граница содержащего его интервала, полученная разность делится на длину этого же интервала. Полученное число считается новым текущим значением кода. Переход к шагу 1.

Упражнение 22 Декодировить арифметический код 011 для последовательности значений д.с.в. из предыдущего упражнения. Остановиться, после декодирования третьего символа.

Упражнение 24 д.с.в. может принимать три различных значения. При построении блочного кода с длиной блока 4 для необходимо будет рассмотреть д.с.в. - выборку четырех значений . Сколько различных значений может иметь ? Если считать сложность построения кода пропорциональной количеству различных значений кодируемой д.с.в., то во сколько раз сложнее строить блочный код для по сравнению с неблочным?

Адаптивные алгоритмы сжатия. Кодирование Хаффмена

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

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

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

На рис. 5.1 приведен пример упорядоченного дерева Хаффмена.

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

Например, если в дереве на рис. 5.1 добавить еще две буквы A, то узлы A и D должны поменяться местами (См. рис. 5.2 ).

Если добавить еще две буквы A, то необходимо будет поменять местами сначала узел A и узел, родительский для узлов D и B, а затем узел E и узел-брат E (рис.6).

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

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

Основы теории информации и криптографии

Основы теории информации и криптографии Автор: В.В. Лидовский Информация о курсе В курсе излагаются основные понятия и факты теории информации. . 11. Лекция: Основы теории защиты информации лекции дается понятие криптографии, использование ее на .

Основы правовой информатики (юридические и математические вопросы информатики) введение

. и принятие юридических решений с помощью ЭВМ; основы теории информации применительно к правовой материи*(31). Особый . идентификации удаленного партнера. Несимметричная (асимметричная) криптография использует специальные математические методы. В .

Основы правовой информатики (юридические и математические вопросы информатики) введение

. среди других типов кодирования. В криптографии учитывается, что информация имеет смысл. Современные системы . и в других социальных науках. В самом деле, основу теории информации составляет одна из ветвей математики .

Основы алгоритмизации и программирования (2)

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

На рис. 5.1 приведен пример упорядоченного дерева Хаффмена.

Например, если в дереве на рис. 5.1 добавить еще две буквы A, то узлы A и D должны поменяться местами (См. рис. 5.2).

Если добавить еще две буквы A, то необходимо будет поменять местами сначала узел A и узел, родительский для узлов D и B, а затем узел E и узел-брат E (рис.5.3).

Дерево нужно перестраивать только при появлении в нем нового узла-листа. Вместо полной перестройки можно добавлять новый лист справа к листу ESC > и упорядочивать, если необходимо, полученное таким образом дерево .

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

В зависимости от поступающих на вход символов алгоритм перестраивает кодовое дерево, корректируя его в соответствии с изменением статистики входного потока. При декодировании происходит аналогичный процесс.

Для обеспечения возможности правильного кодирования/ декодирования используется упорядоченная структура кодового дерева.

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

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

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

Способ построения полиномиальных кодов, минимальное расстояние между кодовыми словами которых равно заданному числу, был открыт:

(2) раздел кибернетики, в котором изучаются и разрабатываются системы изменения письма с целью сделать его более понятным

(3) раздел математики, в котором изучаются и разрабатываются системы изменения письма с целью сделать его непонятным для непосвященных лиц

(3) нематериальная сущность, при помощи которой с любой точностью можно описывать реальные, виртуальные и понятийные сущности

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

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

(3) минимум среднего количества бит, которое нужно передавать по каналу связи о текущем значении данной дискретной случайной величины

(1) изменении(как в увеличении, так и в сжатии) количества бит, необходимых для хранения или передачи информации

(3) его узлы могут быть перечислены в порядке неубывания веса и в этом перечне узлы, имеющие общего родителя, должны находиться рядом, на одном ярусе

(1) исходная информация - сжатие - шумозащитное кодирование - канал связи - декодирование шумозащитных кодов - дешифровка - полученная информация

(2) исходная информация - сжатие - шифрование - шумозащитное кодирование - канал связи(проявляется действие шумов) - декодирование шумозащитных кодов - распаковка - дешифровка - полученная информация

(3) исходная информация - шифровка - сжатие - шумозащитное кодирование - канал связи(проявляется действие шумов) - декодирование шумозащитных кодов - распаковка - дешифровка - полученная информация

(4) исходная информация - шифровка - сжатие - канал связи - распаковка - дешифровка - полученная информация

(5) исходная информация - шифровка - сжатие - шумозащитное кодирование - канал связи - декодирование шумозащитных кодов - дешифровка - распаковка - полученная информация

Перед испытуемым человеком зажигается одна из N лампочек, которую он должен указать. Проводится большая серия испытаний, в которых каждая лампочка зажигается с определенной вероятностью p_i , где i - это номер лампочки. Среднее время, необходимое для правильного ответа испытуемого, пропорционально:

(1)

(3) величине энтропии

(1)

(2)

(3) для любой дискретной случайной величины и любого ее кода

(4) для любой дискретной случайной величины и любого ее кода

(3) каждая точка в картинке характеризуется тремя равноважными атрибутами: яркостью, цветом и насыщенностью

(1) для совершенного (m,n) -кода, исправляющего все ошибки веса, не большего k , выполняется соотношение . Верно и обратное утверждение

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

(3) таблица декодирования совершенного кода, исправляющего все ошибки в не более чем k позициях, имеет в качестве лидеров все строки, содержащие не более k единиц. Верно и обратное утверждение

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

(3) математическую теорию, посвященную измерению информации, ее потока, "размеров" канала связи и т.п.

Если задана функция , где s -это предложение, смысловое содержание которого измеряется, p(s) - вероятность истинности s , то эта функция обладает свойствами:

(1) если s -истинно, то

(2)

(3) если - истинно, то

(4)

(5) если - истинно, то

Дискретная случайная величина X может принимать три различных значения. При построении блочного кода с длиной блока 4 для X необходимо будет рассмотреть дискретную случайную величину X - выборку четырех значений X . X может иметь:

Для кодирующей матрицы построить (2,5)-код:

(1)

(2)

(3)

(1) ряду однородных объектов ставится в соответствие некий код, позволяющий индентифицировать любой объект из данных однородных объектов по этому коду

(2)

(3) I(X,Y) = HX + HY - H(X,Y) , где

(5) I(X,Y) = 0 только если

Найти среднюю длину code1 для дискретной случайной величины X :

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

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

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

(1) устройство, определяющее интервал времени от отправки сигнала передатчиком до его приема приемником

(2) совокупность устройств, объединенных линиями связи, предназначенных для передачи информации от источника информации до ее приемника

(2)

Для кодирующей матрицы найти минимальное расстояние между словами кода:

Найти энтропию дискретной случайной величины X , заданной распределением

(1)

(2)

(3)

Найти среднюю длину code4 для дискретной случайной величины X :

Имеется (8,9)-код с проверкой четности. Вычислить вероятность ошибочной передачи без использования кода, если вероятность ошибки при передаче каждого бита равна 1%:

(1)

(2)

(3)

Для кодирующей матрицы найти вероятность правильной передачи:

(2) описательные конструкции компонент документа в их структурной взаимосвязи - они не входят в HTML, но определяют его

(3) описательные маркеры - определяют структуру документа - им соответствуют элементы разметки HTML типа H1, P, A, IMG и т.п.

Определить HZ , если задана дискретная случайная величина Z=(X₁+1) 2 -X₂ , где независимые дискретные случайные величины X₁ , X₂ могут с равной вероятностью принимать значение либо 0, либо 1:

Вычислить ML₁( X ) для блочного кода Хаффмена для X . Длина блока - 2 бита:

Передатчик задается случайной величиной со следующими законами распределениями вероятностей: P(X₁=-1)=1/4 , P(X₁=0)=1/2 , P(X₁=1)=1/4 . Емкость канала связи с шумом равна 4000 бод. Вычислить максимальную скорость передачи данных по этому каналу передатчиком, обеспечивающую сколь угодно высокую надежность передачи:

(2) для точной дискретизации ее частота должна быть не менее чем в три раза выше наибольшей частоты гармоники, входящей в дискретизируемую величину

(3) для точной дискретизации ее частота должна быть не менее чем в два раза выше наибольшей частоты гармоники, входящей в дискретизируемую величину

Дискретные случайные величины X₁ и X₂ определяются подбрасыванием двух идеальных тетраэдров, грани которых помечены числами от 1 до 4. Дискретная случайная величина Y равна сумме чисел, выпавших при подбрасывании этих тетраэдров, т.е. Y=X₁+X₂ . Вычислить I(X₁,Y) :

(1)

(2)

(3)

(1) длина 10 * 9 = 90 бит

(2) 0'К'0'И'0'Б'0'Е'0'Р'0'Н' 1 \langle 9,1 \rangle 0'Т'1 \langle 5,1 \rangle 1 \langle 5,2 \rangle, длина 3 * 7 + 7 * 9 = 84 бит

(3) длина 10 * 9 = 90 бит

(1) наибольшее расстояние между двумя кодовыми словами меньше либо равно наибольшему весу нулевого слова

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

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

(3) движение и действие малых масс или передача и преобразование малых количеств энергии направляется и контролируется при помощи больших количеств энергии

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

(2) структурный смысл выбранного фрагмента: примечание, начало раздела, конец подраздела, ссылка на другой фрагмент и т.п.

(1) исходная информация - шифровка - сжатие - шумозащитное кодирование - канал связи - декодирование шумозащитных кодов - дешифровка - распаковка - полученная информация

(3) исходная информация - шифровка - сжатие - канал связи - распаковка - дешифровка - полученная информация

(4) исходная информация - шифровка - сжатие - шумозащитное кодирование - канал связи(проявляется действие шумов) - декодирование шумозащитных кодов - распаковка - дешифровка - полученная информация

(5) исходная информация - сжатие - шумозащитное кодирование - канал связи - декодирование шумозащитных кодов - дешифровка - полученная информация

Вычислить предложения , про которое известно, что оно достоверно на 50%, и предложения , достоверность которого 25%:

(1)

(2)

(3)

(1)

(2) для любой дискретной случайной величины и любого ее кода

(3) для любой дискретной случайной величины и любого ее кода

(4)

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

Да-да, об этом уже была статья на Хабре, но без практической реализации. Здесь же мы сфокусируемся как на теоретической части, так и на программерской. Итак, все под кат!

Немного размышлений

Кодирование

Ни один код не должен быть префиксом другого

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

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

Код каждого символа я разделил пробелом. По-настоящему в сжатом файле такого не будет!
Вытекает вопрос: ~~как этот салага придумал код~~ как создать таблицу кодов? Об этом пойдет речь ниже.

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

Здесь приходят на выручку бинарные деревья поиска. Не волнуйтесь, здесь методы поиска, вставки и удаления не потребуются. Вот структура дерева на java:

Это не полный код, полный код будет ниже.

Вот сам алгоритм построения дерева:

Извлечь два дерева из приоритетной очереди и сделать их потомками нового узла (только что созданного узла без буквы). Частота нового узла равна сумме частот двух деревьев-потомков.
Для этого узла создать дерево с корнем в данном узле. Вставить это дерево обратно в приоритетную очередь. (Так как у дерева новая частота, то скорее всего она встанет на новое место в очереди)
Продолжать выполнение шагов 1 и 2, пока в очереди не останется одно дерево — дерево Хаффмана

А что дальше?

Мы получили дерево Хаффмана. Ну окей. И что с ним делать? ~~Его и за бесплатно не возьмут~~ А далее, нужно отследить все возможные пути от корня до листов дерева. Условимся обозначить ребро 0, если оно ведет к левому потомку и 1 — если к правому. Строго говоря, в данных обозначениях, код символа — это путь от корня дерева до листа, содержащего этот самый символ.

Декодирование

Ну, пожалуй, осталось самое простое — декодирование. Я думаю, многие из вас догадались, что просто создать сжатый файл без каких-либо намеков на то, как он был закодирован, нельзя — мы не сможем его декодировать! Да-да, мне было тяжело это осознать, но придется создать текстовый файл table.txt с таблицей сжатия:

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

Ни один код не должен являться префиксом другого

Реализация

Пришло время ~~унижать мой код~~ писать архиватор. Назовем его Compressor.

Начнем с начала. Первым делом пишем класс Node:

Класс, создающий дерево Хаффмана:

Класс, облегчающий чтение из файла:

Ну, и главный класс:

Файл с инструкциями readme.txt предстоит вам написать самим :-)

Заключение

Наверное, это все что я хотел сказать. Если у вас есть что сказать по поводу ~~моей некомпетентности~~ улучшений в коде, алгоритме, вообще любой оптимизации, то смело пишите. Если я что-то недообъяснил, тоже пишите. Буду рад услышать вас в комментариях!

Да-да, я все еще здесь, ведь я не забыл про коэффициент. Для строки s1 кодировочная таблица весит 48 байт — намного больше исходного файла, да и про добавочные нули не забыли(количество добавленных нулей равно 7)=> коэффициент сжатия будет меньше единицы: 176/(65 + 48*8 + 7)=0.38. Если вы тоже это заметили, то ~~только не по лицу~~ вы молодец. Да, эта реализация будет крайне неэффективной для малых файлов. Но что же происходит с большими файлами? Размеры файла намного превышают размер кодировочной таблицы. Вот здесь-то алгоритм работает как-надо! Например, для монолога Фауста архиватор выдает реальный (не идеализированный) коэффициент, равный 1.46 — почти в полтора раза! И да, предполагалось, что файл будет на английском языке.

Выпустил upgrade: добавил GUI + изменил алгоритм обработки исходного текста так, чтобы не читать весь файл в память. Короче, кидаю ссылку на git для любознательных: сами всё увидите.

Благодарности

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

Читайте также:

Закодировать сообщение bbcbbc используя адаптивный алгоритм хаффмена с упорядоченным деревом

Простейшие алгоритмы сжатия информации

Адаптивные алгоритмы сжатия. Кодирование Хаффмена

Похожие документы:

Основы теории информации и криптографии

Основы правовой информатики (юридические и математические вопросы информатики) введение

Основы правовой информатики (юридические и математические вопросы информатики) введение

Основы алгоритмизации и программирования (2)

Немного размышлений

Кодирование

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

А что дальше?

Декодирование

Реализация

Заключение

Благодарности