Question

Как найти коды Хаффмана для фразы Карл украл у Клары кораллы, . . .?

• Как применить алгоритм Хаффмана для фразы КАРЛ УКРАЛ У КЛАРЫ КОРАЛЛЫ, КЛАРА УКРАЛА У КАРЛА КЛАРНЕТ?
• Как создать кодовое двоичное дерево Хаффмана для сообщения КАРЛ УКРАЛ У КЛАРЫ КОРАЛЛЫ, КЛАРА УКРАЛА У КАРЛА КЛАРНЕТ?
• Как определить двоичные коды символов?
• Как выглядит двоичное дерево Хаффмана для сообщения КАРЛ УКРАЛ У КЛАРЫ КОРАЛЛЫ, КЛАРА УКРАЛА У КАРЛА КЛАРНЕТ?
• Отличается ли длина равномерного и неравномерного двоичного кода?
• Как закодировать кодом Хаффмана фразу КАРЛ УКРАЛ У КЛАРЫ КОРАЛЛЫ, КЛАРА УКРАЛА У КАРЛА КЛАРНЕТ?

Answer 1

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

КАРЛ УКРАЛ У КЛАРЫ КОРАЛЛЫ, КЛАРА УКРАЛА У КАРЛА КЛАРНЕТ

считаем количество появлений символов:

1. Символ "К" встречается 8 раз
2. Символ "А" встречается 11 раз
3. Символ "Р" встречается 8 раз
4. Символ "Л" встречается 9 раз
5. Символ " " встречается 9 раз
6. Символ "У" встречается 4 раза
7. Символ "Ы" встречается 2 раза
8. Символ "О" встречается 1 раз
9. Символ "," встречается раз
10. Символ "Н" встречается 1 раз
11. Символ "Е" встречается 1 раз
12. Символ "Т" встречается 1 раз

Сортируем и получаем список нераспределенных узлов

1. {"О" (1)}
2. {"," (1)}
3. {"Н" (1)}
4. {"Е" (1)}
5. {"Т" (1)}
6. {"Ы" (2)}
7. {"У" (4)}
8. {"К" (8)}
9. {"Р" (8)}
10. {"Л" (9)}
11. {" " (9)}
12. {"А" (11)}

Объединяем {"О" (1)} и {"," (1)} в узел {1 (2)} и добавляем в список вместо этих узлов с учетом веса.

1. {"Н" (1)}
2. {"Е" (1)}
3. {"Т" (1)}
4. {1 (2)}
5. {"Ы" (2)}
6. {"У" (4)}
7. {"К" (8)}
8. {"Р" (8)}
9. {"Л" (9)}
10. {" " (9)}
11. {"А" (11)}

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

1. {"Т" (1)}
2. {2 (2)}
3. {1 (2)}
4. {"Ы" (2)}
5. {"У" (4)}
6. {"К" (8)}
7. {"Р" (8)}
8. {"Л" (9)}
9. {" " (9)}
10. {"А" (11)}

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

1. {1 (2)}
2. {"Ы" (2)}
3. {3 (3)}
4. {"У" (4)}
5. {"К" (8)}
6. {"Р" (8)}
7. {"Л" (9)}
8. {" " (9)}
9. {"А" (11)}

Объединяем {1 (2)} и {"Ы" (2)} в узел {4 (4)} и повторяем добавление в список.

1. {3 (3)}
2. {4 (4)}
3. {"У" (4)}
4. {"К" (8)}
5. {"Р" (8)}
6. {"Л" (9)}
7. {" " (9)}
8. {"А" (11)}

Объединяем {3 (3)} и {4 (4)} в узел {5 (7)} и повторяем добавление в список.

1. {"У" (4)}
2. {5 (7)}
3. {"К" (8)}
4. {"Р" (8)}
5. {"Л" (9)}
6. {" " (9)}
7. {"А" (11)}

Объединяем {"У" (4)} и {5 (7)} в узел {6 (11)} и повторяем добавление в список.

1. {"К" (8)}
2. {"Р" (8)}
3. {"Л" (9)}
4. {" " (9)}
5. {6 (11)}
6. {"А" (11)}

Объединяем {"К" (8)} и {"Р" (8)} в узел {7 (16)} и повторяем добавление в список.

1. {"Л" (9)}
2. {" " (9)}
3. {6 (11)}
4. {"А" (11)}
5. {7 (16)}

Объединяем {"Л" (9)} и {" " (9)} в узел {8 (18)} и повторяем добавление в список.

1. {6 (11)}
2. {"А" (11)}
3. {7 (16)}
4. {8 (18)}

Объединяем {6 (11)} и {"А" (11)} в узел {9 (22)} и повторяем добавление в список.

1. {7 (16)}
2. {8 (18)}
3. {9 (22)}

Объединяем {7 (16)} и {8 (18)} в узел {10 (34)} и повторяем добавление в список.

1. {9 (22)}
2. {10 (34)}

Объединяем {9 (22)} и {10 (34)} в корневой узел {11 (56)} и дерево готово.

Графическое изображение дерева строим начиная с корневого узла, в который входят узлы {9 (10)} и {10 (34)}

Каждый узел изображаем в виде прямоугольника из которого выходят 2 ребра ведущие к входящим в него узлам.

Левому ребру соответствует код 0, а правому код 1

Концевые узлы (листья дерева), содержащие символы текста, выделяем цветом.

Графически двоичное дерево кодов выглядит так:

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

1. "А" код символа 01
2. " " код символа 111
3. "Л" код символа 110
4. "Р" код символа 101
5. "К" код символа 100
6. "У" код символа 000
7. "Ы" код символа 00111
8. "Т" код символа 00100
9. "Е" код символа 001011
10. "Н" код символа 001010
11. "," код символа 001101
12. "О" код символа 001100

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

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

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

10001101110111000100­<wbr />101011101110001111001­<wbr />100110100111111100001­<wbr />100101011101100011100­<wbr />1101

11110011001101011110­<wbr />001001010111001111000­<wbr />111100011011100111110­<wbr />011001101001010001011­<wbr />00100

Анализ сжатия фразы КАРЛ УКРАЛ У КЛАРЫ КОРАЛЛЫ, КЛАРА УКРАЛА У КАРЛА КЛАРНЕТ

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

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

при равномерном кодировании минимальной длинны, длинна текста равна 56*4=224 бит

Коэффициэнт сжатия к восьмибитному коду K=448/175=2.56

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