как правильно применить метод кодирования Шеннона-Фано

[eugrita]

Пусть задан алфавит с частотами
\begin{pmatrix} a & b & c & d & e\\ 37 & 22 & 16 & 14 & 11 \end{pmatrix},
Какое правильное 1-е разбиение на группы по методу Шеннона-Фано ?
\begin{pmatrix} a & b \\ 37 & 22 \end{pmatrix},\begin{pmatrix} c & d & e\\ 16 & 14 & 11 \end{pmatrix},
или
\begin{pmatrix} a & d \\ 37 & 14 \end{pmatrix},\begin{pmatrix} b & c & e\\ 22 & 16 & 11 \end{pmatrix},
другими словами, разбиения на подмножества делаем только 1 сечением или произвольным выбором (с сохранением упорядоченности) с целью мах близости к 0.5 ?

[cyb12]

Первое разбиение обычно выбирается так, чтобы суммарная частота встречаемости была примерно одинаковой. Тем самым второй вариант гораздно лучше. Но вообще разбивать можно как угодно, так как все равно получится префиксный код. Выбор разбиения с минимальным отличием в вероятности обусловлен стремлением сделать код оптимальнее. Но в любом случае минимальность не гарантируется. Среди всех кодов, построенных для всех разбиений, оптимальный будет. Но не всегда он получится сразу. Ну а если формально, то правильно (именно по Шеннону-Фано) выбрать второй вариант.

[eugrita]

т.е другими словами перебор всех подмножеств данного с целью мах приближения к 0.5 в 1 случае или к $0.5p_i_-_1$
в общем случае ??

[sup]

Так можно и на задачу о рюкзаке напороться. Судя по всему, сначала все частоты сортируем по убыванию (ну или возрастанию) а потом массив "разрезаем" на две части. Никакого перебора. Да оно и по логике так. Нет особого смысла добиваться идеального деления пополам. Поскольку в дальнейшем из за этого могут возникнуть большие перекосы. Чтобы таких перекосов избежать, в группы объединяются "близкие" частоты ... примерно одного порядка. Для примера, пусть частоты 13,8,4,2,1. "Простой" разрез приводит к двум группам (13) и (8,4,2,1). Перекос (13 -- 15) небольшой. Это в конце концов дает
13- 1бит, 8- 2бит, 4- 3бит, 2- 4бит, 1- 4бит. Результат 13+2*8+3*4+4*(2+1)=53.
Если же использовать на первом шаге идеальное разбиение (13,1) и (8,4,2), то получим
13- 2бит, 1- 2бит, 8- 2бит, 4- 3бит, 2- 3бит. Результат 2*(13+8+1) +3*(4+2)=62.
Это случилось потому, что в одну группу попали "очень разные" частоты 13 и 1.
А вообще, лучше всего использовать коды Хаффмана. Время их построения такое же, но они зато гарантируют оптимальность.

[eugrita]

парадокс. Добивались оптимальности за счет более точного деления пополам по частотам - получили хуже,чем если упорядоченный по сечениям.
Что же тогда считать стандартным вариантом алг Шеннона?

[sup]

Судя по википедии - простой разрез. В общем то ... это достаточно логично. А кроме того, поиск наилучшего разбиения - это еще та головная боль. Причем результат не гарантирован. С другой стороны, все это имело какой-то смысл лишь до того, как Хаффман предъявил эффективный алгоритм построения оптимальных кодов. Поэтому сейчас, данный метод присутствует лишь в справочниках.