Как найти коды Хаффмана и сжать фразу шла саша по шоссе и сосала сушку?
Как создать кодовое двоичное дерево Хаффмана для сообщения ШЛА САША ПО ШОССЕ И СОСАЛА СУШКУ?
Как определить двоичные коды символов?
Как выглядит двоичное дерево Хаффмана для сообщения ШЛА САША ПО ШОССЕ И СОСАЛА СУШКУ?
Отличается ли длина равномерного и неравномерного двоичного кода?
Как закодировать кодом Хаффмана фразу ШЛА САША ПО ШОССЕ И СОСАЛА СУШКУ?
Строим двоичное дерево кодов динамически, по частоте появления каждого символа в сообщении (можно и по готовой таблице вероятностей появления символов).
Определим частоты появления символов
- Символ «Ш» встречается 4 раза
- Символ «Л» встречается 2 раза
- Символ «А» встречается 5 раз
- Символ » » встречается 6 раз
- Символ «С» встречается 6 раз
- Символ «П» встречается 1 раз
- Символ «О» встречается 3 раза
- Символ «Е» встречается 1 раз
- Символ «И» встречается 1 раз
- Символ «У» встречается 2 раз
- Символ «К» встречается 1 раз
каждый символ является конечным узлом дерева, а частота появления является весом этого узла.
составим список нераспределённых узлов по возрастанию весов.
- «П» (1)
- «Е» (1)
- «И» (1)
- «К» (1)
- «Л» (2)
- «У» (2)
- «О» (3)
- «Ш» (4)
- «А» (5)
- «_» (6)
- «С» (6)
объединяем узлы с минимальными весами в один родительский узел с суммарным весом
и помещаем его в список вместо этих узлов в соответствии с весом этого узла
в результате список нераспределённых узлов сокращается на 1 узел.
Эту операцию повторяем до тех пор пока не останется один корневой узел.
Узлы «П» и «Е» объединяем в узел 1
после первого шага список примет вид:
после шага 10 останется один корневой узел с весом 32
строим кодовое дерево: узел с меньшим весом помещаем в левую ветвь, а с большим в правую.
При обходе дерева левое ребро добавляет к коду бит 0, а правое бит 1
получаем следующую таблицу кодов символов
- Код символа «С» равен 00
- Код символа » » равен 111
- Код символа «А» равен 110
- Код символа «Ш» равен 101
- Код символа «О» равен 010
- Код символа «У» равен 0111
- Код символа «Л» равен 0110
- Код символа «К» равен 10001
- Код символа «И» равен 10000
- Код символа «Е» равен 10011
- Код символа «П» равен 10010
Заметим , что получились префиксные коды: код любого символа не является началом кода другого символа, т.е. соблюдается условие Фано.
Длина кодированного сообщения равна сумме произведений количества повторений каждого символа на длину его кода:
4*3+2*4+5*3+6*3+6*2+ 1*5+3*3+1*5+1*5+2*4+1 *5=102 бит
Кодирование осуществляется по таблице кодов, заменой каждого символа его кодом
Кодированное сообщение имеет вид:
10101101101110011010 111011110010010111101 010000010011111100001 110001000110011011011 1000111101100010111
Чтобы раскодировать сообщение необходимо последовательно считать первый бит и пройти от корня соответствующее ребро дерева, далее следующий бит и так до тех пор до тех пор, пока узел не является листом (конечным узлом ветви), затем повторить эту операцию от корня снова, до тех пор, пока не кончится сообщение.
Фраза «ШЛА САША ПО ШОССЕ И СОСАЛА СУШКУ» имеет длину 32 байт или 256 бит в восьмибитном коде (например ASCII) или 512 бит в юникоде.
Это сообщение содержит 11 различных символов. Длина кода одного символа при равномерном кодировании равна log₂(11)=4 бит
при равномерном кодировании длина текста равна 32*4=128 бит
Коэффициент сжатия по сравнению с равномерным кодированием равен 128/102=~1,25
Коэффициент сжатия по сравнению с кодом ASCII кодированием равен 256/102=~2,5
Коэффициент сжатия по сравнению с кодированием в юникоде равен 512/102=~5
Источник
Егэ дерево хаффмана
Сжатие информации Сжатие данных – сокращение объема данных при сохранении закодированного в них содержания.
Сжатие информации Сжатие происходит за счет устранения избыточности кода, например, за счет упрощения кодов, исключения из них постоянных битов или представления повторяющихся символов в виде коэффициента повторения. Важнейшая характеристика процесса сжатия – коэффициент сжатия. Коэффициент сжатия – отношение объема исходного сообщения к объему сжатого.
Алгоритмы сжатия 1. Равномерное сжатие с использованием кодов одной длины. Этот метод используется, если в записи сообщения присутствует небольшая часть алфавита. 2. Сжатие с использованием кодов переменной длины. Сокращение объёма данных достигается за счёт замены часто встречающихся данных короткими кодовыми словами, а редких — длинными.
Сжатие с использованием кодов переменной длины В этом случае возникает проблема отделения кодов символов друг от друга. Решить эту проблему позволяет условие, достаточное для однозначного декодирования сообщений с переменной длиной кодовых слов, условие Фано : Никакое кодовое слово не является началом другого кодового слова. По-другому условие Фано называют свойством префиксности , а код, удовлетворяющий этому условию, называют префиксным кодом .
Префиксные коды Чтобы понять, как строятся префиксные коды, рассмотрим, как построить ориентированный граф, определяющий этот код. Например, кодовые слова 00, 01, 10, 011, 100, 101, 1001, 1010, 1111, кодируют соответственно буквы: a , b , c , d , e , f , g , h , i .
Префиксные коды Построим граф этого кода. Из начальной вершины выходят две дуги, помеченные 0 и 1. Затем из конца каждой такой дуги входят новые дуги, помеченные 0 и 1 так, чтобы, идя по этим дугам от корня, читалось начало какого-либо кодового слова.
Префиксные коды Если при этом какое-то последовательность оказывается прочитанным полностью, то у конца последней дуги пишется кодируемый символ. Из получившихся вершин снова проводятся дуги — и так далее, до тех пор, пока не будут исчерпаны все коды.
Префиксные коды Если известен граф, созданный по префиксному коду, то по этому графу легко восстанавливается код каждого символа — надо просто, идя от корня к листу, помеченному данным символом, выписать 0 и 1 в порядке их прочтения. Идея префиксного кодирования была использована американским ученым Д.Хаффманом для создания эффективного алгоритма сжатия символьной информации.
Алгоритм Хаффмана Алгоритм Хаффмана — адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.
1. Символы исходного алфавита образуют вершины. Вес каждой вершины вес равен количеству вхождений данного символа в сжимаемое сообщение. 2. Среди вершин выбираются две с наименьшими весами (если таких пар несколько, выбирается любая из них). 3. Создается следующая вершина графа, из которой выходят две дуги к выбранным вершинам; одна дуга помечается цифрой 0, другая — символом 1. Вес созданной вершины равен сумме весов, выбранных на втором шаге вершин. 4. К новым вершинам применяются шаги 2 и 3 до тех пор, пока не останется одна вершина с весом, равным сумме весов исходных символов.
НА_ДВОРЕ_ТРАВА,_НА_ТРАВЕ_ДРОВА а в д , е н р о т _ 6 4 2 1 2 2 4 2 2 5 Составим таблицу кодов символов:
Найдем объем сообщения после кодирования кодом Хаффмана: 2·6 + 3·4 + 4·2 + 4·1 + 4·2 + 4·2 + 3·4 + 4·2 + 4·2 + 3·5 = 95 бит. Теперь подсчитаем объем этого сообщения, если каждый его символ кодировать цепочкой из 0 и 1 равной длины. Т.к. в сообщении 10 различных символов вес одного символа 4 бита. Поэтому после кодирования получится сообщение объемом 4·3 = 120 бит. Коэффициент сжатия равен 120/95 =1,26. Сообщение в памяти компьютера закодировано с помощью ASCII-кодов, каждый символ весит 8 бит. Значит, объем исходного сообщения 240 бит. Коэффициент сжатия равен 240/95 = 2,53.
Математики доказали, что среди алгоритмов, кодирующих каждый символ по отдельности и целым количеством бит, алгоритм Хаффмана обеспечивает наилучшее сжатие.
Для кодирования сообщения, состоящего из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. А–00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Выберите правильный вариант ответа. 1) для буквы Б – 01 2) это невозможно 3) для буквы В – 01 4) для буквы Г – 01 Задача А9
0 0 0 0 0 1 0 1 1 1 1 0 1 1 корень Задача А9. Решение. Построим двоичное дерево, в котором от каждого узла отходит две ветки: 0 или 1. Разместим на дереве буквы А, Б, В, Г и Д так, чтобы их код получался как последовательность чисел на рёбрах: А Б В Г Д
Задача А9. Решение. По дереву определим, что для букв Г и Д код можно сократить. Выберем ответ из предложенных вариантов: 1) для буквы Б – 01 2) это невозможно 3) для буквы В – 01 4) для буквы Г – 01 0 0 0 0 0 1 0 1 1 1 1 0 1 1 А Б В Г Д Ответ: 4.
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? 1) 1 2) 1110 3) 111 4) 11 Для самостоятельной работы
Для 5 букв латинского алфавита заданы их двоичные коды. Эти коды представлены в таблице: Задача А9 A B C D E 000 01 100 10 011 Определить, какой набор букв закодирован двоичной строкой 0110100011000
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? Задача А9
Источник
Как использовать алгоритм Хаффмана для кодирования фразы мама мыла раму?
Как сравнить длину равномерного и неравномерного двоичного кода?
Как закодировать неравномерным двоичным кодом фразу МАМА МЫЛА РАМУ?
Для кодирования и декодирования фразы или сообщения сначала необходимо построить двоичное дерево по которому определяются коды символов.
Двоичное дерево строится по таблице вероятностей распределения символов или по таблице частот распределения символов.
Составляем таблицу частот, для этого надо просто посчитать сколько раз каждый символ встречается в тексе сообщения: МАМА_МЫЛА_РАМУ
- М встречается 4 раза
- А встречается 4 раза
- _ встречается 2 раза
- Ы встречается 1 раз
- Л встречается 1 раз
- Р встречается 1 раз
- У встречается 1 раза
Каждый символ является листом (конечным узлом) двоичного дерева
добавим каждый лист в список нераспределенных узлов назначив ему вес, равный его частоте и запишем в порядке возрастания весов:
попарно объединяем узлы с наименьшим весом в один родительский узел, вес которого равен сумме весов этих узлов и добавляем в список нераспределенных узлов вместо объединенных узлов в соответствии с весом нового узла.
Левому узлу ставим ребро, добавляющее к к коду символа 0, а правому ребро, добавляющее к коду символа 1, поскольку дерево строится снизу код образуется с конца, сначала добавляется последний символ,потом предпоследний и так далее.
После объединения узлов «Ы» и «Л» в узел 1 список нераспределенных узлов примет вид:
на шаге 2 объединения узлов «Р» и «У» в узел 2 получим
на шаге 3 объединяем узлы 1 и 2 в узел 3 и получаем
на шаге 4 объединяем узлы «_» и 3 в узел 4
Теперь на шаге 6 объединяем узлы «М» и «А» в узел 5
На шаге 7 объединяем узлы 4 и 5 в узел 6 и дерево готово
проходя по дереву от корня до каждого листа получаем коды символов:
Чем чаще встречается символ, тем короче его код, это позволяет увеличить сжатие, по сравнению с равномерным кодированием.
Каждый код не является началом другого кода т.е. выполняется условие Фано.
Длина закодированного сообщения равна сумме произведений длины кода на частоту символа в сообщении:
Длина кодированного сообщения 36 бит:
Длина исходного сообщения 14 символов или 14 байт (112 бит) в ASCII:
при использовании сжатия по алгоритму Хаффмана коэффициэнт сжатия равен 112/36=3.11
сообщение содержит 7 различных символов. Длина кода одного символа при равна log₂(7)=3 бит
длина кодированного текста равна 14*3=42 бит
коэффициэнт сжатия равен по сравнению с несжатым текстом 112/36=2.66
коэффициэнт сжатия по сравнению с равномерно сжатым текстом равен 42/36=1.17
Источник