Question

Как построить дерево Хаффмана, найти коды и сжать слово department?

• Как создать двоичное кодовое дерево Хаффмана для слова DEPARTMENT?
• Как определить двоичные коды символов для слова DEPARTMENT?
• Как выглядит двоичное дерево Хаффмана для слова DEPARTMENT?
• Как отличаются размеры равномерного и неравномерного двоичных кодов?
• Как закодировать методом Хаффмана слово DEPARTMENT?
• Как применить алгоритм Хаффмана для сжатия слова DEPARTMENT?

Answer 1

Записываем фразу:DEPARTMENT

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

1. Символ "D" встречается 1 раз
2. Символ "E" встречается 2 раза
3. Символ "P" встречается 1 раз
4. Символ "A" встречается 1 раз
5. Символ "R" встречается 1 раз
6. Символ "T" встречается 2 раза
7. Символ "M" встречается 1 раз
8. Символ "N" встречается 1 раз

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

1. {"D"(1)}
2. {"P"(1)}
3. {"A"(1)}
4. {"R"(1)}
5. {"M"(1)}
6. {"N"(1)}
7. {"E"(2)}
8. {"T"(2)}

Шаг 1

Объединяем {"D"(1)}+{"P"(1)} в узел {1 (2)}

1. {"A"(1)}
2. {"R"(1)}
3. {"M"(1)}
4. {"N"(1)}
5. {"E"(2)}
6. {"T"(2)}
7. {1(2)}

Шаг 2

Объединяем {"A"(1)}+{"R"(1)} в узел {2 (2)}

1. {"M"(1)}
2. {"N"(1)}
3. {"E"(2)}
4. {"T"(2)}
5. {1(2)}
6. {2(2)}

Шаг 3

Объединяем {"M"(1)}+{"N"(1)} в узел {3 (2)}

1. {"E"(2)}
2. {"T"(2)}
3. {1(2)}
4. {2(2)}
5. {3(2)}

Шаг 4

Объединяем {"E"(2)}+{"T"(2)} в узел {4 (4)}

1. {1(2)}
2. {2(2)}
3. {3(2)}
4. {4(4)}

Шаг 5

Объединяем {1(2)}+{2(2)} в узел {5 (4)}

1. {3(2)}
2. {4(4)}
3. {5(4)}

Шаг 6

Объединяем {3(2)}+{4(4)} в узел {6 (6)}

1. {5(4)}
2. {6(6)}

Шаг 7

Объединяем {5(4)}+{6(6)} в узел {7 (10)}

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

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

корневой узел {7 (10)} содержит узлы {5(4)} и {6(6)} (шаг 7)

узел {5(4)} содержит узлы {1(2)}+{2(2)} (шаг 5)

узел {6(6)} содержит узлы {3(2)}+{4(4)} (шаг 6)

и так далее.

В результате получим дерево кодов Хаффмана:

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

1. Код символа "T" равен "111"
2. Код символа "E" равен "110"
3. Код символа "N" равен "101"
4. Код символа "M" равен "100"
5. Код символа "R" равен "011"
6. Код символа "A" равен "010"
7. Код символа "P" равен "001"
8. Код символа "D" равен "000"

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

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

00011000101001111110­<wbr />0110101111

Характеристики сжатия слова DEPARTMENT:

Длина исходного слова 10 байт или 80 бит в ASCII:

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

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

Коэффициент сжатия к восьмибитному коду K= 80/30=2.666666666666­<wbr />6665

Коэффициент сжатия к равномерному коду минимальной длинны K=30/30=1