RLE в чисто двоичной форме

[denny]

Возьмем число в двоичной форме, например $99\to1100011$.
Проведем стандартный run length encoding, с результатом сначала в произвольной форме,
скажем в виде вложенных массивов:

$$[[2, 1], [3, 0], [2, 1]]$$

Переведем все данные в двоичную форму:

$$[[10, 1], [11, 0], [10, 1]]$$

Теперь попробуем получить binary RLE минимальной длины.
Заметим, что блоки $1$ и $0$ в двоичном числе чередуются, а первый обязательно состоит из $1$.
Поэтому мы можем убрать сами $1$ и $0$, убрать скобки, соединив массивы:

$$10,11,10$$

Я думаю, что это кратчайшее binary RLE двоичного числа, которую можно потом декодировать обратно.
Если убрать разделители, то вся информация о числе сохранится
(и это первый вопрос, так ли это??),
но его нельзя будет восстановить.

Однако, если мы попытаемся представить разделители в двоичном виде
(чтобы получить чисто двоичное RLE), то видимо декодировать обратно также не получится.
Значит, в RLE двоичного числа обязательно должны присутствовать символы другого алфавита, не только $1$ и $0$.
Так ли это?

[mihaild]

denny в сообщении #1623509 писал(а):

это кратчайшее binary RLE

Чтобы говорить о "кратчайшем RLE", нужно определить, что в точности Вы понимаете под RLE - чтобы можно было искать в этом множестве.

denny в сообщении #1623509 писал(а):

то вся информация о числе сохранится (и это первый вопрос, так ли это??), но его нельзя будет восстановить

Что значит "информация сохранится, но восстановить нельзя"?
"Информация сохранится" - значит для двух разных чисел получатся, после убирания разделителей, разные последовательности? Это не так, легко строится контрпример.

[Dmitriy40]

denny
Нет, не так: можно просто выделить под число повторов фиксированное количество битов, в данном случае хватит двух. Но для представления любого числа от 0 до 254 включительно понадобится по 3 бита. Полей по 4 бита хватит для чисел до $2^{2^4}-2=65534$. Но для чисел с короткими цепочками одинаковых битов будет заметная избыточность, например число $85=1010101_2$ будет представлено как $001,001,001,001,001,001,001$. Но можно например договориться что первым числом будет идти длина поля минус 1 (в трёхбитовом виде её хватит для чисел до $2^{2^{7+1}}=2^{256}\approx10^{77}$), тогда для разных чисел длина поля будет разной, в зависимости от длиннейшей цепочки одинаковых битов в конкретном числе, и то же число $85=1010101_2$ будет представлено как $000,1,1,1,1,1,1,1$.
Кстати забавно у Вас ноль представляется: $0,1$ (ноль единичных битов и один нулевой бит).

-- 23.12.2023, 12:54 --

А ещё можно всегда ограничиться скажем двухбитовым полем длин, а для тех длин которые в два бита не помещаются кодировать их с нулевым количеством противоположных битов между двумя цепочками одинаковых битов. Например число $240=11110000_2$ закодируется в двухбитных полях как $11,00,01,11,00,01$.
Ну и вообще можно много разных форматов придумать.

[denny]

mihaild в сообщении #1623513 писал(а):

Что значит "информация сохранится, но восстановить нельзя"?
"Информация сохранится" - значит для двух разных чисел получатся, после убирания разделителей, разные последовательности? Это не так, легко строится контрпример.

К сожалению да, спасибо!

-- 23.12.2023, 14:30 --

Dmitriy40 в сообщении #1623515 писал(а):

denny
Ну и вообще можно много разных форматов придумать.

Да, но есть 2 момента. Нужно найти кратчайшее представление, потому собственно задача -
найти числа, которые длиннее своих RLE (и те, и другие в двоичной форме).
Ну и конечно хотелось бы иметь универсальный алгоритм для чисел любой длины!

-- 23.12.2023, 15:00 --

Ну в принципе, если сразу определять наибольшую длину идущих подряд одинаковых бит (а для этого существуют вполне определенные алгоритмы, и даже built-ins), то первый метод вполне подходит.
пусть избыточен, вопрос кратчайший ли он из возможных?

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

[Dmitriy40]

denny в сообщении #1623518 писал(а):

Ну и конечно хотелось бы иметь универсальный алгоритм для чисел любой длины!

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

denny в сообщении #1623518 писал(а):

Нужно найти кратчайшее представление,

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

denny в сообщении #1623518 писал(а):

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

Я для кого привёл кодирование числа 240 двухбитовыми полями? Ничего лишнего не нужно.

[denny]

Постараюсь поточнее сформулировать идею, но строго все равно не получится.
Итак у нас есть представление числа в двоичной системе.
Как вы сказали, это действительно хорошее бинарное (с помощью $0$ и $1$) представление:
чаще всего самое короткое, и с вполне определенным и несложным алгоритмом кодирования/декодирования.

И все же есть числа, которые можно представить с помощью $0$ и $1$ короче, чем в двоичной форме,
т.е. как бы сжать информацию. Эти числа я и ищу.
Но теперь понял, что все непросто. Алгоритмов очень много, даже если ограничиться требованиями:
- Без потерь
- Без доп информации (хешей и т.д.)
- Универсально для любых чисел
то непонятно, как найти кратчайшее binary для данного числа.

UPD
Вот это серьезная инфа
https://cs.stackexchange.com/questions/ ... f-integers

[mihaild]

А причем тут RLE?
Просто вопросом "как покороче задать число" занимается раздел теории сложности - сложность описаний. Основной вариант - колмогоровская сложность, когда число задаётся программой на любом "хорошем" языке программирования. Но найти кратчайшую программу по числу нельзя, и более того, хотя для большинства чисел сложность примерна равна длине, существует мировая константа $C$ такая что ни для какого числа не получится доказать, что его сложность больше $C$.

[denny]

mihaild в сообщении #1623547 писал(а):

А причем тут RLE?
Просто вопросом "как покороче задать число" занимается раздел теории сложности - сложность описаний. Основной вариант - колмогоровская сложность, когда число задаётся программой на любом "хорошем" языке программирования. Но найти кратчайшую программу по числу нельзя, и более того, хотя для большинства чисел сложность примерна равна длине, существует мировая константа $C$ такая что ни для какого числа не получится доказать, что его сложность больше $C$.

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

(Оффтоп)

Я даже придумал вот что. Это алгоритм можно обернуть в простейшую if-конструкцию, и если результат получается длиннее двоичного представления, выводить его самого. А если получается сжать -- добавлять первым битом $0$ как признак того, что это код. Так фактически можно "сжать" весь натуральный ряд, имхо это довольно интересно. Я понимаю, что этим уже многие занимались. Идея была найти совсем простой, школьно-иллюстративный алгоритм

Я думал, что достаточно немного "допилить" RLE, и получится искомое. Но все, что получается,
эта хитрая игра с чанками бит, как то не очень. Проще признать поражение

[Dmitriy40]

denny в сообщении #1623544 писал(а):

непонятно, как найти кратчайшее binary для данного числа.

Если не использовать суббитные алгоритмы (типа арифметического сжатия), то минимально любое число (но только одно!) можно закодировать одним битом: если 1, то выдаём это вот число, если 0, то смотрим что там дальше и декодируем ещё как-то по другому.
Так что данный критерий (кратчайшее binary представление данного числа) совершенно не универсален.
Полезнее критерий сколько бит надо чтобы закодировать все числа в некотором диапазоне (сумма количества битов для каждого из чисел).
Что приводит к вопросу о вероятностях появления чисел, все ли они равновероятны или нет (и если нет, то коды Хаффмана и арифметического кодирования и ещё разные в помощь).
В принципе даже для равновероятного распределения арифметическое кодирование всё равно даст минимальное количество бит на число, но оно получится дробным (для не кратных степени двойки диапазонов) и потому придётся округлять вверх, что моментально ухудшит характеристику.

Если же ищете только числа которые можно закодировать короче бинарного представления, то главным становится вопрос как именно их кодировать - в зависимости от используемого кода множество чисел будет кардинально меняться. И никакого универсального способа нет и быть не может.

PS. Надеюсь помните что как бы ни изгаляться с кодированием произвольных чисел, всегда сжать любое число не получится в принципе. А то фразы про поиск сжимаемых чисел близки к построению универсального сжимателя, что невозможно.

-- 23.12.2023, 17:59 --

denny в сообщении #1623550 писал(а):

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

Дык это совсем несложно: числа вида $x=2^{k>4}$ кодируем в формате $0k_2$, все прочие числа $x$ кодируем в формате просто $x_2$ (в $x$ старшая всегда $1$). Чисел первого роде бесконечно много и все они кодируются короче своего бинарного представления. Вполне просто и однозначно. Делов-то.

-- 23.12.2023, 18:04 --

Если не нравится ведущий $0$, то можно и так: числа $x=2^{k>5} \to 10k_2$, все прочие числа $x \to 1x_2$ (в $x$ старшая всегда $1$).

[denny]

Dmitriy40 в сообщении #1623552 писал(а):

denny в сообщении #1623550 писал(а):

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

Дык это совсем несложно: числа вида $x=2^{k>4}$ кодируем в формате $1 k_2$, все прочие числа $x$ кодируем в формате $0 x_2$. Чисел первого роде бесконечно много и все они кодируются короче своего бинарного представления. Вполне просто и однозначно. Делов-то.

Спасибо вам за детальный анализ! Мда, я размышляю. Ну, с такой тривиальной идеи я и начал!
Но хотелось бы еще немного продвинуться (конечно не в сторону "универсального сжимателя" )
Еще как бы "прокультивировать" натуральный ряд в сторону сжатия, но без фанатизма.

И еще напомню, что хотелось бы представить это на OEIS.
(Конечно, если последовательность будет принята, отмечу ссылки и персоналии всех, кто помог!!)
Типа "натуральные числа, двоичное представление которых длиннее, чем полученное данным алгоритмом".
Там редакторы демократичные, уже есть опыт публикаций.
Но алгоритм должен быть достаточно известным, вменяемым, коротким.
Но и не только для чисел вида $x=2^{k>4}$ (я уверен, там уже есть такие)

----

Возможно, не стоит вообще начинать с представления числа в двоичной системе, а переводить его в binary как-то по-другому, и только в случае большей длины использовать первое.

[Dmitriy40]

denny в сообщении #1623555 писал(а):

Но и не только для чисел вида $x=2^{k>4}$ (я уверен, там уже есть такие)

Да таких чисел можно нафорумлировать тонну. Например числа вида $1010\ldots101010_2$ ($k$ повторов комбинации $10_2$) (их тоже бесконечно много) кодировать как $1k_2$. Или вообще любые числа вида $yy\ldots y$ ($k$ повторов комбинации $y$) для достаточно длинных комбинаций или большого числа повторов как-то кодировать (если длина кода меньше бинарного представления).
И таких кодов можно придумать миллион. Или больше.
Так что Вы бы всё же сформулировали задачу более конкретно, а не просто "придумать алгоритм для OEIS". Там и так полно хлама, не стоит его ещё плодить.

[denny]

Dmitriy40 в сообщении #1623576 писал(а):

Так что Вы бы всё же сформулировали задачу более конкретно, а не просто "придумать алгоритм для OEIS". Там и так полно хлама, не стоит его ещё плодить.

Да, согласен ))
Пока пришла забавная идея, спрошу на seqfan, стоит ли правда "плодить хлам".
На OEIS уже есть maximal run length in base-2 representation of n.

Для кодирования мы берем из нее (или определяем сами), максимальное количество бит, необходимое для одного поля. Создаем RLE нашего числа, используя это количество бит для каждого поля, при необходимости дополняя нулями.
Без знания о том, какое это число, декодировать ее нельзя.
Но есть сильное подозрение, что в таком случае кодировка будет однозначна (разная для разных чисел).
То есть она все же содержит всю информацию о числе. Мы можем сравнить длину такого RLE с длиной обычного двоичного представления. Вот числа, для которых она строго меньше:

$$7, 15, 24, 28, 31, 56, 63, 64, 71, 96, 99, 103, 112, 113, 115, 119, 120, 124, 126, 127, 128, 192, 199, \ldots$$

Для декодирования нам нужно знать позицию числа в A043276. Это конечно читерство, но тем не менее...

[Dmitriy40]

denny в сообщении #1623764 писал(а):

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

Подозрения надо проверять. Тем более что это несложно: декодируйте $101010_2$. Это может быть как $10_2,10_2,10_2=110011_2=51$, так и $101_2,010_2=1111100_2=124$. Т.е. два разных числа кодируются одинаково.
Так что длину поля знать надо. Либо априори (выше приводил примеры как кодировать произвольные числа полями фиксированной длины), либо её тоже как-то кодировать в начале представления (способов много, например можно первое служебное поле заполнить числом вида $11\ldots10_2$, т.е. единицами с нулём на конце, это однозначно определяется и выдаёт длину поля: $10_2=2, 110_2=3, 1110_2=4, 11110_2=5, \ldots$).
С указанной кодировкой длины наименьшее число, кодируемое короче своего двоичного представления, будет $127=2^7-1=1111111_2=110_2,111_2$. Следующее $511=2^9-1=111111111_2=1110_2,1001_2$, потом $2^{10}-1, 2^{11}-1, 2^{12}-1$, потом $1110_2,0001_2,1100_2=1000000000000_2=2^{12}$, потом ещё 11шт чисел с заменой очередного левого нуля на единицу вплоть до числа $1110_2,1100_2,0001_2=1111111111110_2=2^{13}-2$. А следующее кодируется короче $1110_2,1101_2=2^{13}-1$. Вполне себе достаточно простая универсальная кодировка.

[Mihaylo]

Dmitriy40 в сообщении #1623552 писал(а):

PS. Надеюсь помните что как бы ни изгаляться с кодированием произвольных чисел, всегда сжать любое число не получится в принципе. А то фразы про поиск сжимаемых чисел близки к построению универсального сжимателя, что невозможно.

denny, обратите внимание на утверждение выше. Оно легко доказывается.
Любой архиватор работает хорошо на тех данных, на которые он "рассчитан". Но есть еще столько же видов данных, которые он антисжимает.
Любой архиватор сжимает одни данные и антисжимает другие данные, т.е. выдает архив бОльшего размера, чем сами данные.

Например, как правило, архиватор антисжимает свой собственный архив. Попробуйте убедиться на примере RLE.

[mihaild]

Mihaylo в сообщении #1624250 писал(а):

Но есть еще столько же видов данных, которые он антисжимает.

Вообще не совсем так. Бывают архиваторы, которые никогда не увеличивают размер больше чем на 1 бит, но иногда очень сильно уменьшают размер.