Пусть есть задача в начале некоторого большого файла произвольного содержания записывать одно целое число, тоже произвольное.

Проблема в том, что за записью этого числа (по условию задачи) идут какие-то не зависящие от него биты. Как указать, где оканчивается "тело" числа?

Очевидно, возможны разные нотации записи этого числа. Например, если бинарная запись этого числа состоит из К битов, сначала ставить К-1 единиц, потом "0", потом само число. То есть для числа 255 получаем вид: "1111111011111111тело_файла..."

Возможна ли более компактная нотация?

Akina,

запись числа 1 займёт 8 байт + 1 бит? Это компактно?

Dima T,

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

Код Левенштейна в Википекдии как-то муторно описан, а другое описание я искать поленился.

Реально размышляю про архиватор. По-дилетантски, конечно.

ptr128,

вопрос не в кодировании самом по себе, а в том ЕЩЁ, чтобы отделить запись числа от следующих непосредственно за ней произвольных битов.

"Префиксность" -- это про все подстроки строки. А здесь - только в одном месте, в начале строки.

Vladimir Baskakov,

одно число перед строкой - это упрощённая постановка задачи. А если нужно не одно число там разместить, а 100500?

Vladimir Baskakov,

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

Vladimir Baskakov,

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

Dima TОбъяви число 0 концом файла, а дальше так:


а какое битовое выражение для "запятой" использовать предлагаете?

И я ведь не сказал, что после 100500 чисел будет конец файла.

Dima T,

проблема в том, что вы, кажется, совсем не заботитесь о компактности формата. В то время как вопрос звучал "Возможна ли более компактная нотация?"

В той нотации, которая описана в корневом посте, для записи чисел 0 и 1 требуется 2 бита , для 2 и 3 требуется 4 бита , для 4-7 требуется 6 битов и т.д.
_____________________
Причём видно, что даже в рамках этого подхода можно расходовать биты более экономно: поскольку 0 и 1 записываются в 2-битной нотации, то в 4-битной 0 и 1 уже не появятся, и можно впихнуть в неё 2, 3, 4 и 5 .

То есть:
"0 0" это 0
"0 1" это 1

"10 00" это 2
"10 01" это 3
"10 10" это 4
"10 11" это 5

"110 NNN" это c 6 до 13 (по формуле 6+NNN)

"1110 NNNN" это c 14 до 29 (по формуле 14+NNN)

и т.д.

Любопытно, что если следовать Хаффману, то нужно инвертировать префиксы, объявляющие длину битовой записи "тела" числа. То есть, например:

"1111110 0" это 0
"1111110 1" это 1

"111110 00" это 2
"111110 01" это 3
"111110 10" это 4
"111110 11" это 5

"11110 NNN" это c 6 до 13 (по формуле 6+NNN)

"1110 NNNN" это c 14 до 29 (по формуле 14+NNNN)

"110 NNNNN" это c 30 до 61 (по формуле 14+NNNNN)

"10 NNNNNN" это c 62 до 125 (по формуле 61+NNNNNN)

"0 NNNNNNN" это c 126 до 253 (по формуле 125+NNNNNNN)

В сухом остатке: в начале записи (перед телом числа) идет "имя диапазона", обозначающее одновременно и число бит в теле числа, и "базу диапазона" -- константу, к которой нужно прибавить двоичное число, выраженное этими битами тела числа, чтобы получить окончательный результат.

То есть:

"однобитныйдиапазон 0" и "однобитныйдиапазон 1" - это запись двух чисел: База(1)+0 и База(1)+1;

"двухбитныйдиапазон NN" - это запись четырёх чисел: База(2)+0, База(2)+1, База(2)+2 и База(2)+3;

"трёхбитныйдиапазон NNN" - это запись 8 чисел - от База(3)+0 по База(3)+7;

"четырёхбитныйдиапазон NNNN" - это запись 16 чисел типа База(4)+NNN;

и так далее.

Словарь {"однобитныйдиапазон", "двухбитныйдиапазон", "трёхбитныйдиапазон","четырёхбитныйдиапазон", ... "М-битныйдиапазон"} должен обладать свойствами префиксности и оптимальности (для нашей задачи), то есть, например, битовые значения

0, 10, 110, 1110, ... (М_минус_одна_единица)0

-- должны быть распределены по нему в соответствии с нашими априорными ожиданиями частот записи нами разных чисел.

При этом для "хвоста" очень больших чисел, появление которых мы представляем совсем редким, должна работать дополнительная (к словарю) формальная нотация записи имён диапазонов:

(М_единиц)0

-- означающая "битовые тела" чисел, содержащие М+1 бит. Ну и базы, к которым нужно прибавлять двоичные числа, представленные этими битовыми телами, тоже будут рассчитываться по единой формуле ...

Как можно на запрос наиболее компактной нотации отвечать:
Dima TА какую нотацию ты решишь использовать - не имеет значения
?

Ваши заказчики такие ответы принимают?
____________________________
Dima Tесли добавить выкидывание старшей 1
то есть ваша нотация, как она была описана, уже сбойнула?

Dima T,

похоже на то. Там сдвиг будет зависеть от того, нужно ли нам -- по условию задачи -- иногда записывать число 0, или только натуральные числа.

Dima TВопрос 21097085 прозвучал так
Иван FXSА если нужно не одно число там разместить, а 100500?это было не о том, как записать одно число "сто тысяч пятьсот", а о том, что, возможно, нужно будет размещать "стопяцот" чисел.

Dima TТа тоже рабочая как ваша нотация справится с задачей записи числа

127213652436512428173512214698378623721714738352374 ?

я как раз знаю, как записать несколько чисел: сначала первое, потом вплотную к нему (без всяких запятых) второе и т.д.