Течет речка печет печка дерево хаффмана

Как методом Хаффмана для сжать фразу на дворе трава, на траве дрова?

Как выглядит дерево Хаффмана для фразы НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА?

Как поэтапно создать кодовое двоичное дерево Хаффмана?

Как определить коды символов?

Отличается ли длина равномерного и неравномерного двоичного кода?

Как закодировать кодом Хаффмана фразу НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА?

Необходимо составить дерево, так, чтобы каждый узел с символом был окончанием ветки,

обычно такой узел называют листом, а количество повторений символа является весом этого узла.

Алгоритм построения дерева Хаффмана состоит в том, что на каждом шаге пары узлов с минимальнм весом соединяются

в общий узел, с весом равным сумме этих узлов, до тех пор пока не останется один узел, с весом равным длине сообщения.

При этом узлу с меньшим весом ставится в соответствие ребро с кодом 0,

а узлу с большим весом ставится в соответствие ребро с кодом 1.

Все коды рёбер по пути от корня до листа составляют код символа.

Построим двоичное дерево Хаффмана для фразы НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА

по частоте появления символов (по количеству повторений символа)

Считаем сколько раз в сообщении встречается каждый символ:

Символ «Н» встречается 2 раза

Символ «А» встречается 6 раз

Символ » » встречается 5 раз

Символ «Д» встречается 2 раза

Символ «В» встречается 4 раза

Символ «О» встречается 2 раза

Символ «Р» встречается 4 раза

Символ «,» встречается 1 раз

Символ «Е» встречается 2 раза

Расположим узлы, для построения дерева Хаффмана в порядке возрастания веса:

Объединим узлы и в узел 1 с весом 3 и запишем в порядке возрастания веса

Источник

Как найти коды Хаффмана для фразы прецедент с претендентом?

считаем количество появлений (вес) символов в сообщении и записываем список символов:

1. Символ «П» встречается 2 раза
2. Символ «Р» встречается 2 раза
3. Символ «Е» встречается 6 раз
4. Символ «Ц» встречается 1 раз
5. Символ «Д» встречается 2 раза
6. Символ «Н» встречается 3 раза
7. Символ «Т» встречается 3 раза
8. Символ » » встречается 2 раза
9. Символ «С» встречается 1 раз
10. Символ «О» встречается 1 раз
11. Символ «М» встречается 1 раз

Включаем все символы в список нераспределённых узлов в порядке возрастания веса символа:

Это последний (корневой) узел.

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

Коды символов определяем как пути от корня дерева до листа (конечного узла), соответствующего символу:

Длина кодированного сообщения равна сумме произведений количества повторений каждого символа на длину его кода: 2*4+2*4+6*2+1*4+2*4+­ 3*3+3*3+2*4+1*4+1*4+­ 1*4=78 бит

Длина кодированного сообщения равна 78 бит:

11001101010000011110­ 01100101111100011111­ 11001101011010110011­ 100110010100100011

Анализ сжатия фразы ПРЕЦЕДЕНТ С ПРЕТЕНДЕНТОМ:

Длина исходного сообщения 24 байт или 192 бит в ASCII.

сообщение содержит 11 различных символов. Длина кода одного символа при равномерном кодировании равна log₂(11)=4 бит

при равномерном кодировании длина текста равна 24*4=96 бит

Коэффициент сжатия к восьмибитному коду K= 192/78=2.46153846153­ 84617

Коэффициент сжатия к равномерному коду минимальной длинны K=96/78=1.2307692307­ 692308

Источник

Как найти коды Хаффмана для фразы не руби дрова на траве двора?

считаем количество появлений (вес) символов в сообщении и записываем список символов:

1. Символ «Н» встречается 2 раза
2. Символ «Е» встречается 2 раза
3. Символ » » встречается 5 раз
4. Символ «Р» встречается 4 раза
5. Символ «У» встречается 1 раз
6. Символ «Б» встречается 1 раз
7. Символ «И» встречается 1 раз
8. Символ «Д» встречается 2 раза
9. Символ «О» встречается 2 раза
10. Символ «В» встречается 3 раза
11. Символ «А» встречается 4 раза
12. Символ «Т» встречается 1 раз

Включаем все символы в список нераспределённых узлов в порядке возрастания веса символа:

Это последний (корневой) узел.

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

Коды символов определяем как пути от корня дерева до листа (конечного узла), соответствующего символу:

1. Код символа » » равен 00
2. Код символа «А» равен 100
3. Код символа «Р» равен 011
4. Код символа «В» равен 010
5. Код символа «О» равен 1101
6. Код символа «Д» равен 1100
7. Код символа «Е» равен 1011
8. Код символа «Н» равен 1010
9. Код символа «Т» равен 11111
10. Код символа «И» равен 11110
11. Код символа «Б» равен 11101
12. Код символа «У» равен 11100

Длина кодированного сообщения равна сумме произведений количества повторений каждого символа на длину его кода: 2*4+2*4+5*2+4*3+1*5+­ 1*5+1*5+2*4+2*4+3*3+­ 4*3+1*5=95 бит

Кодированное сообщение длиной 95 бит:

10101011000111110011­ 10111110001100011110­ 10101000010101000011­ 11101110001010110011­ 000101101011100

Характеристики сжатия фразы НЕ РУБИ ДРОВА НА ТРАВЕ ДВОРА

Длина исходного сообщения 28 байт или 224 бит в ASCII:

сообщение содержит 12 различных символов. Длина кода одного символа при равномерном кодировании равна log₂(12)=4 бит

при равномерном кодировании длина текста равна 28*4=112 бит

Коэффициент сжатия к восьмибитному коду K= 224/95=2.35789473684­ 2105

Коэффициент сжатия к равномерному коду минимальной длинны K=112/95=1.178947368­ 4210525

Источник

Как найти коды Хаффмана для фразы течёт речка, печёт печка?

считаем количество появлений (вес) символов в сообщении и записываем список символов:

1. Символ «Т» встречается 3 раза
2. Символ «Е» встречается 4 раза
3. Символ «Ч» встречается 4 раза
4. Символ «Ё» встречается 2 раза
5. Символ » » встречается 3 раза
6. Символ «Р» встречается 1 раз
7. Символ «К» встречается 2 раза
8. Символ «А» встречается 2 раза
9. Символ «,» встречается 1 раз
10. Символ «П» встречается 2 раза

Включаем все символы в список нераспределённых узлов в порядке возрастания веса символа:

Это последний (корневой) узел.

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

Коды символов определяем как пути от корня дерева до листа (конечного узла), соответствующего символу:

1. Код символа «Ч» равен 110
2. Код символа «Е» равен 101
3. Код символа » » равен 100
4. Код символа «Т» равен 011
5. Код символа «П» равен 001
6. Код символа «А» равен 000
7. Код символа «К» равен 1111
8. Код символа «Ё» равен 1110
9. Код символа «,» равен 0101
10. Код символа «Р» равен 0100

Длина кодированного сообщения равна сумме произведений количества повторений каждого символа на длину его кода: 3*3+4*3+4*3+2*4+3*3+­ 1*4+2*4+2*3+1*4+2*3=­ 78 бит

Кодированное сообщение длиной 78 бит:

01110111011100111000­ 10010111011110000101­ 10000110111011100111­ 000011011101111000

Характеристики сжатия фразы ТЕЧЁТ РЕЧКА, ПЕЧЁТ ПЕЧКА

Длина исходного сообщения 24 байт или 192 бит в ASCII:

сообщение содержит 10 различных символов. Длина кода одного символа при равномерном кодировании равна log₂(10)=4 бит

при равномерном кодировании длина текста равна 24*4=96 бит

Коэффициент сжатия к восьмибитному коду K= 192/78=2.46153846153­ 84617

Коэффициент сжатия к равномерному коду минимальной длинны K=96/78=1.2307692307­ 692308

Источник

Как алгоритмом Хаффмана сжать фразу королева кавалеру подарила каравеллу?

Каждый символ помещаем в узел дерева с весом, равным числу повторений символа и сортируем по возрастанию весов:

Объединяем 2 узла с минимальным весом в промежуточный узел и помещаем этот узел в список в соответствии с весом.

в результате длина списка уменьшится на 1 узел, этот шаг повторяется до тех пор пока не осмтанется один корневой узел.

после выполнения шага 1 получим:

первый элемент списка соответствует левому ребру с кодом 0, а второй ребру с кодом 1

узел 11 является корневым узлом, строим дерево кодов начиная с узла 11.

по готовому дереву находим коды символов как путь от корня до листа

«В» двоичный код равен 1101

«Е» двоичный код равен 1100

«О» двоичный код равен 1111

«К» двоичный код равен 1110

«У» двоичный код равен 1000

«И» двоичный код равен 10010

«Д» двоичный код равен 100111

«П» двоичный код равен 100110

Длина кодированного сообщения равна сумме произведений количества повторений каждого символа на длину его кода:

3*4+3*4+4*3+5*3+3*4+­ 3*4+7*2+3*3+2*4+1*6+1­ *6+1*5=123 бит

Длина кодированного сообщения равна 123 бит:

11101111001111110111­ 001101010001110011101­ 0110111000011000000

10011011111001110100­ 110010101010001110010­ 010111011100101101100­ 0

Анализ сжатия фразы:КОРОЛЕВА КАВАЛЕРУ ПОДАРИЛА КАРАВЕЛЛУ

Длина исходного сообщения 36 байт или 288 бит в ASCII:

сообщение содержит 12 различных символов.

Длина кода одного символа при равномерном кодировании равна log₂(12)=4 бит

при равномерном кодировании длина текста равна 36*4=144 бит

по отношению к восьмибитному коду К=288/123=~2.34

по отношению к равномерному коду минимальной длинны К=144/123=~1.17

Источник