Каков оптимальный код Хаффмана для следующих символов, частоты которых являются первыми 8 числами Фибоначчи: a : 1, b : 1, c : 2, d : 3, e : 5, f : 8, g : 13, h : 21 ? Обобщите случай, чтобы найти оптимальный код, когда частоты являются первыми n числами Фибоначчи.
Это одна из проблем с назначением, которые у меня есть. Я не прошу прямого ответа, просто для некоторых ресурсов.
Где я должен искать, чтобы собрать воедино ответы на вопросы?
Прочтите — http://en.wikipedia.org/wiki/Huffman_coding — особенно обратите внимание к фразе «Двоичное дерево генерируется слева направо, беря два наименее вероятных символа и соединяя их вместе, чтобы сформировать другой эквивалентный символ, вероятность которого равна сумме двух символов. Процесс повторяется до тех пор, пока не останется только один символ. ".
Как вышеизложенное относится к ряду Фибоначчи?
Алгоритм кодирования Хаффмана берет два узла с наименьшей частотой и соединяет их, чтобы сформировать родителя, который имеет равную по частоте сумму дочерних узлов. При случайной частоте символов нам нужно вычислять как минимум два узла для объединения каждый раз, но в случае последовательности частот Фибоначчи последовательность в ряду Фибоначчи такая же, как последовательность в кодировании Хаффмана.
Пример: - а : 1, б : 1, в : 2, г : 3, д : 5, е : 8, г : 13, ч : 21
он сформирует дерево с наклоном влево или вправо, где кодирование каждого символа может быть получено с использованием простой формулы
если n не является символом
a = (n-2)*0 + 0
b = (n-2)*0 + 1
c = (n-3)*0 + 1
d = (n-4)*0 + 1
e = (n-5)*0 + 1
. . . последний = 1
так для приведенного выше примера
a = (n-2)*0 + 0 = (6)*0 + 0 = 0000000
b = (6)*0 + 1 = 0000001
c = (5)*0 + 1 = 000001
.......
Я надеюсь, ты понял шаблон
интересная вещь - вычисление средней длины бита
avg = ((n-1)*2 + sumof((n-i+1)*fib(i)) где i в (3,n))/(sumof(fib(i)) где i в (1, п))
вышеизложенное можно упростить до прямой формулы.
