Экономная запись числа

[Deynekin]

Вспомнилось по мотивам темы "Одометр".

Сравним представления чисел в системах счисления с различными основаниями b.

Те, кто застали механические калькуляторы "Феликс" (ещё во второй половине шестидесятых они совершенно всерьёз продавались в "Канцтоварах"; за совершенно серьёзные по тем временам 40 руб.) или же грудастые кассовые аппараты с рядами кнопок для каждого разряда, легко согласятся с записью числа в виде таблицы из b строк по количеству цифр в выбранной системе счисления: в каждом столбце-разряде отмечается одна позиция-цифра (в Феликсе это было положение соотв. рычажка, в кассовом аппарате - нажатая кнопка).

Будем считать, что нужно записывать числа, не превосходящие некое "достаточно большое" М. Тогда, при уменьшении b, такая таблица содержит меньше строк, но разрастается вширь, и наоборот.

-При каком основании счисления b таблица содержит минимальное количество клеток?

[vm__]

e (2.78 )? Т.е. 3?

[venco]

Ну это, я думаю, всем известно.
Даже компьюторы пытались такие делать.

А вот как насчёт такой задачи об экономной записи.
Нам надо в бинарном виде записывать целые числа, величина которых никак не ограничена. Начало записи известно, а конец - нет, т.е. его тоже надо как-то закодировать.
Ясно, что для больших чисел необходимо порядка log2(N) бит.
Соответственно, задача в том, чтобы минимизировать количество лишних бит.
Формально, минимизируем предел:
limit(N->infinity, average(k=1...N,bits(k)-log2(k)))
Где bits(k) - количество бит требуемых для кодирования натурального числа k.

[Deynekin]

e (2.78 )? Т.е. 3?

-Отгадайте загадку: "Два кольца, два конца, посередине ..."
-Ножницы!
-А-а-а, ты зна-а-ал...

[Deynekin]

Ой, venco, что-то ничего не понятно... Как это, к чему это: "Начало записи известно, а конец - нет, т.е. его тоже надо как-то закодировать."? И что такое "лишние биты"? ("...минимизировать количество лишних бит")
Пожалуйста, подмогните.

[mikeG]

b^b = M

[venco]

Вот пример такой кодировки.
К примеру, кодируем число k = 365.
Записываем его в двоичном виде:
101101101
Длина l1 = 9 бит, старший бит всегда 1, плюс ещё 8 бит двоичной мантиссы.
Записываем длину l1 опять же в двоичном виде:
1001
Длина l2 = 4.
Теперь кодируем длину l2 записью (l2-1) нулей, а затем - одна единица. После этого пишем мантиссу l1, и мантиссу k. В результате получаем:
0001 001 01101101 - 15 бит.
Следом можно кодировать следующее число.

Излишек: 15 - log2(365) = 6.5 бит.
При такой кодировке излишек ~= 2*log2(log2(k)), т.е. растёт до бесконечности с ростом k.
Можно ли придумать такую кодировку, чтобы излишек не превышал некоторую константу при больших k?
А затем надо минимизировать предел среднего излишка для всех k <= N.

[vm__]

Даже компьюторы пытались такие делать.

ЭВМ "Сетунь"

[PavelM]

Вот пример такой кодировки.
К примеру, кодируем число k = 365.
Записываем его в двоичном виде:
101101101
Длина l1 = 9 бит, старший бит всегда 1, плюс ещё 8 бит двоичной мантиссы.
Записываем длину l1 опять же в двоичном виде:
1001
Длина l2 = 4.
Теперь кодируем длину l2 записью (l2-1) нулей, а затем - одна единица. После этого пишем мантиссу l1, и мантиссу k. В результате получаем:
0001 001 01101101 - 15 бит.

Что-то непонятно, где экономия. Было 9 бит, стало 15.
Если вопрос об минимизации избыточной информации при кодировании в предположении о вероятностях разных символов, а проще говоря, компрессии, то все уже украдено до нас :

Алгоритм Хаффмана и др. префиксные коды

http://ru.wikipedia.org/wiki/%D0%9A%D0% ... 0%BD%D0%B0

[Deynekin]

Ещё страшней, ещё чуднее:
Вот рак верхом на пауке...

К примеру, кодируем число k = 365.
Записываем его в двоичном виде: 101101101 (...трах-тибидах...)
... В результате получаем: 0001 001 01101101 - 15 бит.

Излишек: 15 - log2(365) = 6.5 бит.
При такой кодировке излишек ~= 2*log2(log2(k)), т.е. растёт до бесконечности с ростом k.
Можно ли придумать такую кодировку, чтобы излишек не превышал некоторую константу при больших k?
А затем надо минимизировать предел среднего излишка для всех k <= N.

-Да, вроде бы, можно придумать: обычная двоичная, чем она плоха, какие в ней излишки!? - Стоит ли раздувать 9-битовую запись до 15-битовой (да ещё всего лишь ради того только, чтобы хитромудро представить лидирующую единицу, а потом подсчитывать излишки?
Не, я, наверное, - пасс

[venco]

Что-то непонятно, где экономия. Было 9 бит, стало 15.

А откуда вы узнали что было 9 бит? Принимающая сторона этого не знает.
Т.е., если вы просто будете передавать биты числа - 101101101, то как отличить их от 5, переданной три раза?

Алгоритм Хаффмана и др. префиксные коды

Все они рассчитаны на ограниченный алфавит.
А меня интересует возможность передавать неограниченно большие числа.

На самом деле, похоже, добиться потерь, ограниченных костантой, невозможно. В лучшем случае это будет что-то типа log2(log2(k))+log2(log2(log2(k)))+...

[Deynekin]

А откуда вы узнали что было 9 бит? Принимающая сторона этого не знает.
Т.е., если вы просто будете передавать биты числа - 101101101, то как отличить их от 5, переданной три раза?

Да, примерно, оттуда же, откуда смогли узнать, что 0001 001 01101101 - это было 15 бит, причём вся цепочка - это не 0,4,5,5,5

[PavelM]

Алгоритм Хаффмана и др. префиксные коды

Все они рассчитаны на ограниченный алфавит.
А меня интересует возможность передавать неограниченно большие числа.

Можно разбить бесконечное число на числа конечной длины и взять адаптивный алгоритм Хаффмана который кодирует в реальном времени без знания вероятностей заранее. В принципе без предположения о распределении символов в числе построить что-то оптимальное невозможно. Числа могут быть такими, что сжатие может быть просто невозможно.

Пример - разбейте сжатый по максимуму архив RAR на числа произвольной длины и попробуйте сэкономить еще малость.

Статья по теме:

http://en.wikipedia.org/wiki/Universal_ ... ression%29

[venco]

откуда смогли узнать, что 0001 001 01101101 - это было 15 бит, причём вся цепочка - это не 0,4,5,5,5

Смотрим сколько нулей сначала, до первой единицы - 3, значит l2 = 4. Читаем следующие, после начальных нулей, 4 бита, получаем l1 = 9. Читаем следующие l1-1 = 8 бит, приписываем единицу старшим разрядом и получаем 101101101 = 365. Никакой неоднозначности.

[venco]

Можно разбить бесконечное число на числа конечной длины

Число бесконечной длины можно разбить только на бесконечное число (X) конечных чисел. Придётся ещё передавать это бесконечное число X. Задача свелась к предыдущей.

Числа могут быть такими, что сжатие может быть просто невозможно.

Откуда взялось сжатие? Я про него ничего не говорил.

http://en.wikipedia.org/wiki/Universal_code_%28data_compression%29

А тут как раз примерно то, о чём я и толкую.
Elias delta coding - это в точности кодировка, которую я описал.

[PavelM]

Число бесконечной длины можно разбить только на бесконечное число (X) конечных чисел. Придётся ещё передавать это бесконечное число X. Задача свелась к предыдущей.

Нет число чисел передавать не надо. Разбив бесконечное число на блоки равной длины, получим конечный алфавит. Далее, применяем, например, адаптивный алгоритм Хаффмана. Он адаптируется к потоку.

Откуда взялось сжатие? Я про него ничего не говорил.

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

[venco]

Нет число чисел передавать не надо.

Как вы восстановите число из блоков, если не знаете из какого количества блоков число состоит?

Далее, применяем, например, адаптивный алгоритм Хаффмана.

Кодировать по Хаффману младшие биты нет смысла. Например, во многих, если не всех, архиваторах, основанных на LZW (zip, rar), только несколько старших битов потенциально большого смещения строки, а также его длина, кодируются со сжатием. Младшие же биты передаются как есть.

[O.K.]

откуда смогли узнать, что 0001 001 01101101 - это было 15 бит, причём вся цепочка - это не 0,4,5,5,5

Смотрим сколько нулей сначала, до первой единицы - 3, значит l2 = 4. Читаем следующие, после начальных нулей, 4 бита, получаем l1 = 9. Читаем следующие l1-1 = 8 бит, приписываем единицу старшим разрядом и получаем 101101101 = 365. Никакой неоднозначности.

venco, а откуда мы знаем, что последняя прочитанная мантисса это и есть наше число, а не новая длина l0?

[venco]

venco, а откуда мы знаем, что последняя прочитанная мантисса это и есть наше число, а не новая длина l0?

В данном формате всегда пишется две мантиссы.