Метод Фано

[maxmatem]

Вот изучаю метод Фано, для сжатия, при таком распределении вероятностей.
$\[A = \{ a_i \} _{i = 1}^{12} \]$, $B={0;1}$

$\[ p = {\text{\{ 0}}{\text{.145;0}}{\text{.137;0}}{\text{.133;0}}{\text{.111;0}}{\text{.098;0}}{\text{.09;0}}{\text{.088;0}}{\text{.054;0}}{\text{.027;0}}{\text{.021;0}}{\text{.001\} }} \] $
У меня получилось следующее:

$\[ \begin{gathered} a_1 - 0000 \hfill \\ a_2 - 0001 \hfill \\ a_3 - 001 \hfill \\ a_4 - 010 \hfill \\ a_5 - 011 \hfill \\ a_6 - 1000 \hfill \\ a_7 - 1001 \hfill \\ a_8 - 101 \hfill \\ a_9 - 1100 \hfill \\ a_{10} - 1101 \hfill \\ a_{11} - 1110 \hfill \\ a_{12} - 1111 \hfill \\ \end{gathered} \] $
Просто интересно верно ли я применил метод, может можно как-нибудь в какой-нибудь программе проверить?

[lim0n]

Если речь идет о алгоритме Шеннона-Фано, результат не похож на правду. Получившийся код слишком равномерен для такого неравномерного распределения вероятностей. Проверьте, коды должны быть длиной от 3 до 6.

Кстати, Вы что-то пропустили: $\sum p_i=0.905$?

[maxmatem]

да там ещё 0.095. я вот немного пересчитал и получил следующее
$\[ \begin{gathered} a_1 - 000 \hfill \\ a_2 - 001 \hfill \\ a_3 - 010 \hfill \\ a_4 - 011 \hfill \\ a_5 - 100 \hfill \\ a_6 - 101 \hfill \\ a_7 - 1100 \hfill \\ a_8 - 1101 \hfill \\ a_9 - 1110 \hfill \\ a_{10} - 11110 \hfill \\ a_{11} - 111110 \hfill \\ a_{12} - 111111 \hfill \\ \end{gathered} \] $
и средняя длина кода $\[ \lambda = 3.352 \]$
Кстати я ещё к тому же распределению вероятностей применил метод Хаффмана и получилось, что средняя длина в методе Фано, и методе Хаффмана совпали. Это нормально???

[lim0n]

maxmatem в сообщении #360628 писал(а):

Это нормально???

Нормально, хотя в общем случае кодирование по Хаффману оптимально.