Для решения этой задачи, давайте сначала разберёмся с алгоритмом Хаффмана.
Алгоритм Хаффмана - это алгоритм сжатия данных, которым можно закодировать символы в сообщении таким образом, чтобы наиболее часто встречающиеся символы получили более короткое кодирование, а реже встречающиеся символы - более длинное кодирование. Таким образом, общая длина закодированного сообщения будет меньше, чем длина исходного сообщения.
Теперь приступим к кодированию исходного слова {aabbabcbdbbcaebdeebaeedb} по алгоритму Хаффмана.
1. Подсчитаем частоту встречаемости каждого символа в слове:
a - 6 раз
b - 7 раз
c - 2 раза
d - 4 раза
e - 5 раз
2. Строим дерево Хаффмана:
Построим дерево по нарастающей, объединяя символы с наименьшей частотой встречаемости:
1) Объединяем символы c и d суммируя их частоты: c+d = 2+4 = 6
Также объединяем символы c и d в один символ, чтобы понять какие буквы зашифрованы под каким кодом. Назовем символы их исходными значениями.
Итак, у нас остаются символы: a, b, c+d, e
2) Объединяем символы a и c+d: a+c+d = 6
Итак, теперь у нас остаются символы: a+c+d, b, e
3) Объединяем символы a+c+d и e: a+c+d+e = 6+5 = 11
Итоговое дерево имеет вид:
a+c+d+e
/ \
a+c+d b
/ \
a c+d
/ \
c d
3. Закодируем символы:
a - идем влево по дереву (левое поддерево от корня) - код будет "0"
b - идем вправо по дереву (правое поддерево от корня) - код будет "1"
c - идем влево, затем влево по поддереву - код будет "00"
d - идем влево, затем вправо по поддереву - код будет "01"
e - идем вправо по дереву - код будет "1"
4. Запишем код символов:
a = 0
b = 1
c = 00
d = 01
e = 1
Теперь перейдем к решению задачи:
Длина слова {aabbabcbdbbcaebdeebaeedb}, если закодировать его символы алгоритмом Хаффмана:
а = 0 (встречается 6 раз), значит длина кода символа а составляет 6 * 1 = 6
b = 1 (встречается 7 раз), значит длина кода символа b составляет 7 * 1 = 7
c = 00 (встречается 2 раза), значит длина кода символа c составляет 2 * 2 = 4
d = 01 (встречается 4 раза), значит длина кода символа d составляет 4 * 2 = 8
e = 1 (встречается 5 раз), значит длина кода символа e составляет 5 * 1 = 5
Длина сообщения, закодированного алгоритмом Хаффмана, будет суммой длин кодов символов, умноженных на их частоту встречаемости:
Длина сообщения = (6 * 1) + (7 * 1) + (2 * 2) + (4 * 2) + (5 * 1) = 6 + 7 + 4 + 8 + 5 = 30
Таким образом, длина закодированного сообщения будет равна 30.
