Минимальный префиксный код.

[sng1]

Какой префиксный код для кодирования целых чисел имеет минимальную (в битах) длину (как функцию от кодируемого числа).

[PAV]

Уточните, пожалуйста, постановку вопроса. Пусть $d(n)$ - длина слова, кодирующего число $n$. Как будет записываться величина длины всего кода, которую Вы хотите минимизировать?

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

[sng1]

Надо минимизировать $d(n)$ как функцию от $n$. Слышал, что есть код Левенштейна. Может быть он?

[PAV]

Я не понимаю. Пусть есть два кода: для одного длины $d_1(n)$, для другого - $d_2(n)$. Напишите, как определить, какой считается "короче". Для одних значений $n$ может быть выполнено $d_1(n)<d_2(n)$, а для других - наоборот. Сравнивать можно числа, но не функции.

[sng1]

Ассимптотически.

[PAV]

Подробнее. Формулу, пожалуйста.

[sng1]

Ограничим круг наших интересов неубывающими функциями $d_i(n)$. Если начиная с некоторого $N$ окажется, что $d_1(n)>d_2(n) $ для всех $n>N$, то будем считать код $d_1(n)$ плохим. Исключим из множества всех известных нам кодов плохие коды. Остальные коды назовем неплохими. Хотелось бы пример не очень сложного неплохого кода.