Question

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. {","(1)}
2. {"Н"(2)}
3. {"Д"(2)}
4. {"О"(2)}
5. {"Е"(2)}
6. {"Т"(2)}
7. {"В"(4)}
8. {"Р"(4)}
9. {" "(5)}
10. {"А"(6)}

Объединим узлы {","(1)} и {"Н"(2)} в узел 1 с весом 3 и запишем в порядке возрастания веса

Шаг 1

1. {"Д"(2)}
2. {"О"(2)}
3. {"Е"(2)}
4. {"Т"(2)}
5. {"1 (3)":[{","(1)},{"Н"(­<wbr />2)}]}
6. {"В"(4)}
7. {"Р"(4)}
8. {" "(5)}
9. {"А"(6)}

Шаг 2

1. {"Е"(2)}
2. {"Т"(2)}
3. {"1 (3)":[{","(1)},{"Н"(­<wbr />2)}]}
4. {{"2 (4)"[{"Д"(2)},{"О"(2­<wbr />)}]}
5. "В"(4)}
6. {"Р"(4)}
7. {" "(5)}
8. {"А"(6)}

Шаг 3

1. {"1 (3)":[{","(1)},{"Н"(­<wbr />2)}]}
2. {"3 (4)":[{"Е"(2)},{"Т"(­<wbr />2)}]}
3. {"2 (4)":[{"Д"(2)},{"О"(­<wbr />2)}]}
4. {"В"(4)}
5. {"Р"(4)}
6. {" "(5)}
7. {"А"(6)}

Шаг 4

1. {"2 (4)":[{"Д"(2)},{"О"(­<wbr />2)}]}
2. {"В"(4)}
3. {"Р"(4)}
4. {" "(5)}
5. {"А"(6)}
6. {"4 (7)":[{"1 (3)":[{","(1)},{"Н"(­<wbr />2)}]},{"3 (4)":[{"Е"(2)},{"Т"(­<wbr />2)}]}]}

Шаг 5

1. {"А"(6)}
2. {"4 (7)":[{"1 (3)":[{","(1)},{"Н"(­<wbr />2)}]},{"3 (4)":[{"Е"(2)},{"Т"(­<wbr />2)}]}]}
3. {"5 (8)":[{"2 (4)":[{"Д"(2)},{"О"(­<wbr />2)}]},{"В"(4)}]}
4. {"6 (9)":[{"Р"(4)},{" "(5)}]}

Шаг 6

1. {"А"(6)}
2. {"4 (7)":[{"1 (3)":[{","(1)},{"Н"(­<wbr />2)}]},{"3 (4)":[{"Е"(2)},{"Т"(­<wbr />2)}]}]}
3. {"5 (8)":[{"2 (4)":[{"Д"(2)},{"О"(­<wbr />2)}]},{"В"(4)}]}
4. {"6 (9)":[{"Р"(4)},{" "(5)}]}

Шаг 7

1. {"5 (8)":[{"2 (4)":[{"Д"(2)},{"О"(­<wbr />2)}]},{"В"(4)}]}
2. {"6 (9)":[{"Р"(4)},{" "(5)}]}
3. {"7 (13)":[{"А"(6)},{"4 (7)":[{"1 (3)":[{","(1)},{"Н"(­<wbr />2)}]},{"3 (4)":[{"Е"(2)},{"Т"(­<wbr />2)}]}]}]}

Шаг 8

1. {"7 (13)":[{"А"(6)},{"4 (7)":[{"1 (3)":[{","(1)},{"Н"(­<wbr />2)}]},{"3 (4)":[{"Е"(2)},{"Т"(­<wbr />2)}]}]}]}
2. {"8 (17)":[{"5 (8)":[{"2 (4)":[{"Д"(2)},{"О"(­<wbr />2)}]},{"В"(4)}]},{"6 (9)":[{"Р"(4)},{" "(5)}]}]}

После шага 9 получается полное кодовое дерево Хаффмана:

Код каждого символа определяется кодами ребер на пути от корня к листьям:

Символ "А" код равен 00

Символ " " код равен 111

Символ "Р" код равен 110

Символ "В" код равен 101

Символ "Т" код равен 0111

Символ "Е" код равен 0110

Символ "О" код равен 1001

Символ "Д" код равен 1000

Символ "Н" код равен 0101

Символ "," код равен 0100

Ни один символ не является началом другого символа, т.е. выполняется условие Фано.

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

2*4+6*2+5*3+2*4+4*3+­<wbr />2*4+4*3+2*4+1*4+2*4=9­<wbr />5 бит

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

01010011110001011001­<wbr />110011001001110111110­<wbr />001010011101010011101­<wbr />111100010101101111000­<wbr />11100110100

Длина исходного сообщения 30 байт или 240 бит в ASCII или 480 бит в Юникоде:

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

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

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

Коэффициэнт сжатия по отношению к восьмибитному коду равен 240/95 =~2.526

Коэффициэнт сжатия по отношению к равномерному коду равен 120/95 =~1.263