Кратчайшее представление натуральных чисел и способы разложения их.
Аноним
11/12/19 Срд 03:24:12
№
1
произвольных натуральных чисел,
и попытаемся выбрать оптимальную и кратчайшую запись этих чисел.
Тема может быть полезна для реализации обратимого "сжатия без потерь" - несжимаемых данных,
но инфа о разложении чисел - разбросана по сети, фрагментами.
Давайте же стянем её сюда, и переварим.
Итак, начну...
На данный момент, оптимальнейшим способом записи произвольного натурального числа,
является ничто иное как запись его в виде двоичном виде - в виде бит.
Число можно разложить на степени двойки,
можно факторизовать число и разложить на простые множители,
можно разложить на сумму трех квадратов (исключив числа определённого вида): https://ru.wikipedia.org/wiki/Теорема_Лагранжа_о_сумме_четырёх_квадратов
можно также разложить на сумму двух-трех простых чисел: https://ru.wikipedia.org/wiki/Проблема_Гольдбаха
Как ещё можно разложить произвольное натуральное число?
Как можно было бы сжать зеттабайт несжимаемых данных (случайных, зашифрованных)?
Пока, наилучшим обратимым преобразованием, которое мне удалось найти является "Преобразование Барроуза-Уилера".
Оно снижает информационную энтропию данных, позволяя их сжать:
https://ru.wikipedia.org/wiki/Преобразование_Барроуза_—_Уилера
Однако, файл данных, состоящий из 256 байт, содержащий все комбинации этих байт,
сжался в 422 байта программой bzip2.
Очевидно, что сжать последовательно идущие байты, можно было бы - вот так: 00-FF, указав диапазон их.
Чтобы не писать все эти байты.
При этом, строка занимает - всего 5 символов, включая символ-разделитель '-';
Также, любое натуральное число можно представить в виде суммы нескольких последовательных натуральных чисел.
Например, число 25 можно представить в виде суммы из одного (25), двух (12+13) и пяти чисел (3+4+5+6+7).
Поэтому, можно было бы указать стартовое число, и количество членов длиннейшей последовательности...
Ещё одной идеей, было следующее:
взять целый сектор, скажем 512 байт, каким-то невъебенным образом,
разложить его на сумму двух-трех простых чисел,
согласно бинарной и тернарной проблеме Гольдбаха,
затем записать эти простые числа в виде коротком, как на primeGrid: http://primegrid.com/primes/mega_primes.php
И действительно, к чему писать 9,383,761 (decimal digits), если можно просто записать число - так: 10223×2^31172165+1 ???
Осталось только надыбать/создать/воссоздать - алгоритмы!
Любое натуральное число можно представить в виде СУММЫ КУБОВ пяти целых чисел:
Доказательство:
6n - 2 = n^3 +(n+2)^3 - (n+1)^3 - (n+1)^3 - 2^3
6n - 1 = (n+1)^3 + (n-1)^3 - n^3 - n^3 - 1^3
6n = (n+1)^3 + (n-1)^3 - n^3 - n^3 + 0^3
6n+1 = (n+1)^3 + (n-1)^3 - n^3 - n^3 + 1^3
6n + 2 = n^3 +(n-2)^3 - (n-1)^3 - (n-1)^3 + 2^3
6n + 3 = (n-3)^3 +(n-5)^3 - (n-4)^3 - (n-4)^3 + 3^3
Поэтому, можно было бы сохранить только n и остаток. Это дело на любителя.
>Преобразование Барроуза-Уилера
>снижает информационную энтропию данных, позволяя их сжать
похоже на обратимую сортировку, но на выходе не совсем отсортированные данные.
Какие существуют алгоритмы обратимой сортровки, с наименьшей избыточностью инфы?
>действительно, к чему писать 9,383,761 (decimal digits), если можно просто записать число - так: 10223×2^31172165+1
Проблема в том, что на primegrid ищут только простые числа специального вида: https://ru.wikipedia.org/wiki/PrimeGrid#Список_подпроектов
Сразу пришла в голову мысль,
алгоритмом Миллера-Рабина - найти от большого числа x
(а это может быть целый сектор),
найти рядом с ним - ближайше простое число,
из таких чисел как 321-числа,
то есть простое число p, вида (3 × 2^n±1)..
Затем, представить x так:
x = c×d + r, где c - частное, d - делитель, r - остаток.
В качестве делителя - взять p, а в качестве остатка - (x mod p),
таким образом:
x = k*p + (x mod p), где k = ((x - (x mod p)) / p)) - частное,
p - простое 321-число, x - само число.
Как сжать всю эту хуйню?
k, по идее, должно быть небольшим, так как p - находится близко к x.
p - можно записать лишь степенью, так как это 321 число, и оно может быть получено из неё,
А вот остаток, r = (x mod p), может быть довольно пиздатым,
поэтому, идея пошла по пизде, возможно потому, что я не смог в рекурсивное разложение.
Наверняка, любое натуральное число можно представить в виде:
(множитель × основание^показатель_степени ± слагаемое)
и я думаю, было бы годно, составить, каким-то образом невъебенным,
огромную таблицу оптимальнейших представлений всех натуральных чисел от 0 до лярдиллиарда.
Чё-т, глядя на это: https://ru.wikipedia.org/wiki/Проблема_196
взбрела в голову идея...
Взять произвольное натуральное число,
найти ближайший палиндром к нему,
записать половину палиндрома,
отнять число от палиндрома или палиндром от числа,
записать остаток.
Битовая длина палиндрома должна быть равна половине битовой длины числа, а вместе с остатком - почти как число.
Но, в большинстве случаем, остаток может иметь меньшую битовую длину.
Быть может, можно было бы использовать не палиндромы, а числа вида:
123456123456123456123456123456
записав только 123456 и количество повторов.
Тогда, битовая длина такого числа - была бы ещё меньше.
Некоторые числа можно было бы представить факториалом, или нотацией кнута,
чтобы они имели короткую запись, но не все...
Если раскладывать на простые, множители, то битовая длина простых чисел равна их битовой длине,
однако, простое число плюс-минус 1 - уже не простое, и может быть факторизовано.
Надо бы, наверное, создать какую-нибудь гугл-таблицу, которую можно редактировать совместно,
расположить в ней натуральные числа по порядку,
и совместными усилиями представить эти числа в кратчайшем виде.
Возможно эта таблица позволит кодировать числа намного оптимальнее, нежели двоичная система,
а быть может, будут найдены какие-либо новые закономерности для представления натуральных чисел,
а возможно даже появятся и новые теоремы.
Ещё одну идею подвалю.
Пи - число иррациональное.
То есть оно бесконечно, и главное - не имеет периода повтора десятичных (шестнадцатиричных, двоичных) цифр.
Вот что из этого вытекает: http://philosophystorm.org/filosofiya-chisla-pi
Существует алгоритм вычисления N-ного знака числа пи: https://habr.com/ru/post/179829/
Так вот, можно взять число пи, указать стартовый оффсет, и длину данных,
и при помощи этого алгоритма, закодировать неебически длинное значение - лишь двумя числами.
А это, существенно позволило бы сжать данные любого размера.
Только вот стартовый оффсет может занять лярд длин данных.
Но что если их сначала сжать, а потом уже в числе пи отыскать?
Если сжатие без потерь хочешь, то по идее можно его добиться если работать относительно каких-нибудь генераторных схем с особо сложным устройством. Смысл оно будет иметь только для объёмных штук, к примеру от 1Мб, а иначе получим твои же 256->256+ вместо сжатия.
У меня были прикидки использовать комбинацию LFSR, популярных алгоритмов и перераспределение адресации в пределах произвольных блоков байт чтобы вычленять ставшие регулярными последовательности.
Грубо говоря, блок:
...12341234123421345373745625130423...
При преобразовании к квадратному n колоночному (само перераспределение адресов можно самыми разными хэшами делать, и любым другим дремучим ужасом) может дать например колонку:
[01234567890123456789012345678901234567890123456789...]
Соответственно если мы можем опознать в этом последовательность и дать ей более компактную запить чем сама последовательность, то можно сделать нечто вида:
f(Bytes) -> [used_f] + newBytes + [record]
И если данное нечто оказывается короче оригинала, то мы достигли успеха. Далее можно продолжать тоже самое для новополученного массива либо вообще для всего выражения.
Естественно у происходящего должны быть определены и обратные операции, полностью выводимые из выходной записи. Соответственно, все трансформации должны быть грамотно закодированы.
В самом конце в идеале должно получаться выражение которое пускается в обратный генератор и он будет как хорошая тьюринг-машина бегать туда-сюда по инструкциям пока не получит в нужном месте сигнал остановки.
Логических изъянов при условии "как минимум крупных объёмов" обнаружить пока не удалось (но контекстная схема для такой упаковки должна быть в самом деле изощрённой), но для выстраивания в общем и рабочем виде ещё очень далеко, понятное дело. Насчёт эффективности по скорости вычислений не уверен.
>Если сжатие без потерь хочешь, то по идее можно его добиться
>если работать относительно каких-нибудь генераторных схем с особо сложным устройством.
Именно.
Изначально, я себе в голове, вообще рисовал некое устройство, алгоритм, функцию, то есть - некий порождатель инфы,
а именно - порождатель любого натурального числа (большой длины).
Что-то вроде вот этих чисел: https://ru.wikipedia.org/wiki/Большие_числа
В частности, какая-то такая вот функция:
>1928 год — Вильгельм Аккерман опубликовал свою функцию.
То есть, некая функция, которая принимает короткие (битовая длина) параметры,
множит их, возводит в степень там, вычисляет факториалы, и прочие нотации Кнута,
и выдаёт конкретное уникальное, но - натуральное число, из всего множества натуральных N.
И, как я понял, все эти "большие числа" - могут иметь только "определённый вид",
как впрочем и "простые числа", которые с "короткой записью", на "primeGrid".
Поэтому, выдать произвольное натуральное число, размером в сектор (512 байт, например) - такие функции-алгоритмы не могут.
"Сжатие без потерь" - подразумевает кодирование повторяющихся последовательностей,
и предварительную пре-обработку,
то есть, обратимое снижение информационной энтропии "произвольных входных данных",
какую-то "обратимую оптимизацию" этих данных (как это делает всё то же - Преобразование Барроуза-Уилера),
Однако, по Шеннону, энтропия - это и есть сама информация,
и если её снизить - то надо просто выкинуть кусок инфы (реализуя сжатие с потерями),
и выкинов это говно - снизить колгоморовскую сложность этих данных: https://ru.wikipedia.org/wiki/Колмогоровская_сложность
Здесь, http://kodpi.net/13/13.htm , я нашёл некий пример "сжатия - несжимаемых данных",
они просто "выкинули байт", а потом "подобрали его", хэххэх.
Можно было бы "выкинуть" и "много байт", а потом - "подобрать их".
Такой многораундовый алгоритм я тоже искал - чтобы с помощью него, можно было бы,
вычислительные мощности приложить, порождая из короткой инфы, более громоздкую, но однозначную.
>Смысл оно будет иметь только для объёмных штук, к примеру от 1Мб, а иначе получим твои же 256->256+ вместо сжатия.
256 последовательных байт - это просто был пример "несжимаемых данных"
(то есть данных, содержащих "все возможные комбинации" всех байт).
Конечно, в качестве "несжимаемых данных", можно взять и другие "мегабайтные комбинации",
в частности "зашифрованные данные", или "случайные данные",
то есть данные, с максимальной "информационной энтропией",
данные, в которых количества единиц/нулей, и количества блоков более длинных чем бит - (00, 01, 10, 11), (0...0, ..., 1...1)
- распределены равномерно, по всем этим данным.
>само перераспределение адресов можно самыми разными хэшами делать, и любым другим дремучим ужасом
А как обратить потом?
Хэши имеют коллизии, поэтому они считаются необратимыми односторонними функциями. В этом проблема.
Поначалу, у меня тоже была идея использовать хэши, и она была простой:
вычислить хэш, и потом, просто - несмотря на ресурсы, подобрать сами данные по нему.
Но тогда, нужно указать номер коллизии (для пропуска инвалидных коллизий, при подборе),
а с этим номером (плюс сам хэш) - размер данных уже равен битовой длине самих данных.
Просто подумай, сколько коллизий будет иметь четырехбайтная контрольная сумма восьмибайтного блока данных,
если попытаться этот блок подобрать? Да, максимальное число этих коллизий может быть представлено ещё четырьмя байтами...
Поэтому, в итоге, думается мне, что лучше было бы преобразовывать инфу вентилями,
производящими "обратимые вычисления", а именно:
https://ru.wikipedia.org/wiki/Вентиль_Тоффоли
https://ru.wikipedia.org/wiki/Вентиль_Фредкина
https://ru.wikipedia.org/wiki/CNOT
Обратимые вычисления, они не херят инфу, а просто меняют данные местами.
Тогда, можно было бы, замкнуть цикличное преобразование на много раундов, не теряя инфы, а адреса - сдвигать,
и таким образом, добиться через N-циклов - более упорядоченных данных, с меньшей энтропией,
и возможностью обратить выходные данные.
>И если данное нечто оказывается короче оригинала, то мы достигли успеха.
Но, вот-вот! Тут то и трабла.
Я рассматривал также вариант обратимой сортировки, последовательностью XOR-обменов,
но если записывать последовательность индексов элементов, где производится обмен,
то инфа (энтропия информационная), она - перемещается в них, в эти индексы,
и эта последовательность, в итоге - ещё длинее чем сама инфа.
То же самое и с числом пи. В пи, может содержаться нужная инфа, но инфа о том как добраться к ней внутри числа пи - может занимать эксабайты.
Поэтому, после всего этого, хотелось бы просто составить некую таблицу глобальную,
кратчайших представлений всех натуральных чисел от 0 до 2^N (где N, скажем 64),
или, ещё лучше - так это найти формулу разложения произвольных больших натуральных чисел,
и представления их в виде более оптимальном, нежели в виде - бинарном.
Тогда, можно было бы сделать JSON-объект с таблицей замен, и пускай архиватор-деархиватор занимал бы терабайт,
но зато без проблем, жал бы гигабайты в килобайты, обратимо, и расжимал бы.
И чё-то сдаётся мне, что есть в математике - куча теорем, позволяющих представить любое натуральное число,
в виде намного более коротком, нежели в виде бинарном.
Как хорошо известно многим учёным,
синергетические процессы самоорганизации в кибернетических суперсистемах,
порождают негэнтропийные процессы упорядочивания информации,
снижая тем самым информационную энтропию.
В связи с этим, существуют два понятия - негэнтропия и экстропия.
https://ru.wikipedia.org/wiki/Негэнтропия
https://ru.wikipedia.org/wiki/Экстропианство
Внимание, вопрос: вывели ли уже универсальную формулу самоорганизации информации,
которая обратимо снижает информационную энтропию для произвольных входных данных,
позволяя их впоследствии - восстановить однозначно,
в результате эволюции самоорганизовавшейся системы?
Зачем спрашиваю...
Не, ну рили, как сжать без потерь - несжимаемые данные?
Там же, почти, равномерное распределение всех возможных байт!
На вид они, как рандом, информационная энтропия данных - на высоте.
В общем, надо, всю эту инфу, как-то упорядочить, но обратимо, чтобы потом восстановить.
Если просто отсортировать их (необратимо), то данные будут испорчены.
Поэтому, обращаюсь к специалистам по синергетике.
Универсальная формула самоорганизации, согла бы подарить человечеству универсальный алгоритм суперсжатия,
поскольку информацинная энтропия данных - снижалась бы, в результате синегретической самоорганизации.
Но обратимо, потому что процессы самоорганизации протекают при наличии притока энергии,
а без энергии, происходит эволюция самоорганизовавшейся системы.
Так вот, полагаю, что по причине детерминистичности процесса развития самоорганизовавшейся системы,
сжатая инфа, с более низкой энтропией, могла бы однозначно декодироваться в изначальную инфу, с более высокой энтропией,
на определённом этапе развития этой, самоорганизовавшейся системы.
Ну с натуральным числом всё сравнительно просто - бинарное представление, как и любое другое - всего лишь укороченная запись полинома с плавным ростом степеней где все члены суммируются, а коэффициенты априори целые и от 0 до (основание_полинома - 1).
Даже без модификаций подобного ты можешь банально находить более удачные разложения чем в десятичной системе и получать укороченную запись (но прочтение и алгебраические операции станут усложнёнными).
Если брать гибридные системы счисления, то можно например сделать так:
[основание](коэффициент_степерь) + ...
Соответственно:
[10](3_5) + [10](1_0) = 300001
Очевидно, что таких разложений можно придумать очень много (особенно если шарить за системы счисления и спокойно конструировать маргинальные их виды), но почти все они будут более громоздкими.
Это всё вертится вокруг понятия о нормальной форме. Т.е. такому шаблону к которому можно любое число привести однозначным образом, что позволяет далее сравнивать величины. Но если сравнивать - не главная задача, то мы можем делать что угодно.
В случае записи подобными полиномами очевидно что наикратчайшая запись будет как раз-таки в 1-3 члена, что собственно ехидно отсылает нас к проблеме Гольдбаха. Но при этом и сами основания, коэффициенты и степени могут быть столь огромными, что и к ним можно будет какую сокращённую нотацию прицепить.
>снизить колгоморовскую сложность
На мой взгляд у этого определения есть ключевая беда - оно оценивает структурную сложность в вакууме, вне всякого контекста.
Если отбросить тезис про универсальность и смотреть по существу, то мы изначально окажемся в ситуации когда мы крайне огромное понятие пытаемся описать в рамках какого-то контекста.
А раз всё так, то кто мешает работать с ситуативными таблицами и прочими вспомогательными вещами? Вне полного перечисления последовательностей любую последовательность всегда легко представить в виде ситуативной ссылки в краткой форме. А как оно относится к структуре? Да весьма просто - ссылкой мы утверждаем, что поэлементные отличия последовательности от того что представлено по ссылке нулевые.
Для единичных элементов и чисел мы в целом используем ту же самую логику, поэтому игнорировать её для более крупных вещей при практических задачах - это самокастрация.
У беспредельного сжатия есть однако очевидные дикие последствия.
Во-первых, при полном перечислении совершенно точно нельзя меньшим числом записать каждое большее - коллизии будут появляться априори.
Во-вторых, если ты всё-таки находишь удачные способы краткого представления, то это порождает совершенно магическую ситуацию, когда сжатие технически ничем не ограничено. И это уже по-своему страшная ситуация, т.к. грань между 100Гб и 100Тб оказывается только во времени распаковки. И если данная схема начинает работать, то это моментально начнёт влиять на всю информационную сферу и всё что с ней связано. Если весь архив порнолаба за все года можно уместить в микрофайлик весом не больше mp3, то это чудесно.
Но точно также мы, значит, можем через стеганографию захуярить альбом Металлики в картинку с обложкой этого альбома, нисколько не увеличив размер картинки. А в каждую вложенную песню в свою очередь мы можем вложить дискографию Мегадэт. А туда ещё чего. А потом ещё. И ещё.
В итоге при передаче одной-единственной картинки может оказаться вся библиотека всех файлов мира. Но и она же самая при передаче любой другой картинки с вложенными данными.
И концептуально это таки тотальная ебатория и натуральная магия: в любом произвольном файле содержатся вообще все возможные файлы, нужно лишь иметь грамотно настроенные управляющие структуры чтобы это всё доставать.
И этого в общем-то достаточно, чтобы утверждать, что в общем случае такой алгоритм - астальная хуита.
Но вот доказать что такой подход не взлетит ни в одной частной ситуации, или даже целом классе таких ситуаций...
>Ну с натуральным числом всё сравнительно просто - бинарное представление,
>как и любое другое - всего лишь укороченная запись полинома
>с плавным ростом степеней где все члены суммируются,
>а коэффициенты априори целые и от 0 до (основание_полинома - 1).
Да. Взять какое-нибудь число:
168(10) = 10101000(2)
76543210 (номера разрядов)
10101000 = 1×2^7 + 0×2^6 + 1×2^5 + 0×2^4 + 1×2^3 + 0×2^2 + 0×2^1 + 0×2^0.
Видно, что множителями являются биты числа в соответствующих разрядах.
То есть сам полином содержит эти биты,
и он по определению не может быть оптимальнее,
не может содержать меньше инфы, чем сама двоичная запись.
В десятичной системе счисления - та же фигня:
210 (номера разрядов)
168 = 1×10^2 + 6×10^1 + 8×10^0. Те же цифры - но во вножителях полинома.
Как и в шестрадцатиричной:
168(10) = A8(16)
10 (номера разрядов)
A8 = A×16^1 + 8×16^0. Те же цифры - но во множителях полинома.
Если расписать так:
168 = 1×10^2 + (6×10^1 + 8×10^0), то очевидно, откуда берётся слагаемое (6×10^1 + 8×10^0)
Это просто - остаток: 168 mod 10^2 = 168 mod 100 = 68.
Я знаю, что любое натуральное число x представимо в виде:
x = c×d + r, где x - число, с - частное, d - делитель, r - остаток.
Так вот, наверняка, всё-таки, для любого натурального числа, можно было бы подобрать такой делитель,
при котором остаток занимал бы наименьшее количество бит, а его - представить короче.
Например: 168 = 21×2^3 + 0; 168 -> {21, 2, 3, 0}.
Тут очевидно, что битовая длина четырёх чисел на выходе - больше нежели 8 бит самого числа,
но если брать большие числа (как вот те, простые megaprimes, на primeGrid),
то в подобном разложении, на показатель степени - может быть существенный профит.
>Даже без модификаций подобного ты можешь банально находить более удачные разложения
Как? Есть алгоритмы, формулы, методы, функции?
>чем в десятичной системе и получать укороченную запись
>(но прочтение и алгебраические операции станут усложнёнными).
Так их можно закодировать определённой комбинацией бит. Сколько их там, этих операций?
Например, какое-нибудь число "7×5^(5^(3!))" - нахуя писать десятичными цифрами,
если можно куда уж проще, но с дополнительными операциями?
А оно уже, в развёрнутом в памяти виде - может содержать в себе, часто повторяющиеся байты,
и тем же кодом Хаффмана, можно было бы ссылаться на эти байты и их комбинации, их - в этом числе.
>почти все они будут более громоздкими
Вот именно. Двоичная, скорее всего, самая универсальная и оптимальная.
А если и нет, то оптимальнейшей была бы какая-нибудь система из "систем счисления",
где разные числа представлены в совершенно разных системах счисления.
>Это всё вертится вокруг понятия о нормальной форме.
>Т.е. такому шаблону к которому можно любое число привести однозначным образом,
>что позволяет далее сравнивать величины. Но если сравнивать - не главная задача, то мы можем делать что угодно.
Сравнивать можно и в двоичной. Задача состоит в том, чтобы хранить числа.
Почему натуральные? Да потому что:
00000000 - 0
00000001 - 1
00000010 - 2
...
11111111 - 255
...
11111111 11111111 - 65535
...и так далее, и по экспоненте... Всё это - натуральные числа,
которые уже потом могут быть проинтерпретированы как угодно,
в том числе и как целые, отрицательные, и как дробные - с плавающей точкой.
>В случае записи подобными полиномами очевидно что наикратчайшая запись будет как раз-таки в 1-3 члена,
Как это ты так, от нормальной формы пришёл к 1-3 членам?
Я знаю, что есть конъюнктивная нормальная форма: https://ru.wikipedia.org/wiki/Конъюнктивная_нормальная_форма
дизъюнктивная нормальная форма: https://ru.wikipedia.org/wiki/Дизъюнктивная_нормальная_форма
и совершенная дизъюнктивная нормальная форма: https://ru.wikipedia.org/wiki/Совершенная_дизъюнктивная_нормальная_форма
Все они позволяют сводить к ним и записывать - булевы формулы.
Хочешь сказать, что упрощая и оптимизируя сами эти булевы формулы, можно прийти к 1-3 членам всего, для любой формулы? КАААКК???
>что собственно ехидно отсылает нас к проблеме Гольдбаха.
А причём тут проблема Гольдбаха?
>Но при этом и сами основания, коэффициенты и степени могут быть столь огромными,
>что и к ним можно будет какую сокращённую нотацию прицепить.
Ну так и их можно было бы рекурсивно разложить...
>оно оценивает структурную сложность в вакууме, вне всякого контекста.
По-моему, оно оценивает саму энтропию, потому что связано с ней: https://ru.wikipedia.org/wiki/Колмогоровская_сложность#Связь_с_энтропией
А энтропия - зависит от непредсказуемости инфы.
>кто мешает работать с ситуативными таблицами
>Вне полного перечисления последовательностей любую последовательность
>всегда легко представить в виде ситуативной ссылки в краткой форме.
Опять же, если в таблице будут перечислены все последовательности,
то размер адреса последовательности в ней - будет равен размеру самой последовательности.
А если нет, и если таблица неполная, значит исходные данные,
представляемые ссылками на неполные данные из неё - сжимаемы,
и частоты нахождения ВСЕХ ВОЗМОЖНЫХ последовательностей -
не распределены равномерно, а существенно сдвинуты
в пользу повторов именно этих последовательностей, из неполной таблицы.
>А как оно относится к структуре? Да весьма просто - ссылкой мы утверждаем,
>что поэлементные отличия последовательности от того что представлено по ссылке нулевые.
А если отличия от данных, содержащихся в таблице неполных последовательностей - существенны,
то представление самих отличий этих, может быть длиной в саму последовательность.
>Во-первых, при полном перечислении совершенно точно
>нельзя меньшим числом записать каждое большее - коллизии будут появляться априори.
В том-то и весь прикол несжимаемых данных, они же - непредсказуемы, блядь.
Грубо говоря, все возможные последовательности из полного перечисления - распределены равномерно в этих данных.
>страшная ситуация,
>т.к. грань между 100Гб и 100Тб оказывается только во времени распаковки.
А чё тут страшного, если у тебя 100 гигабайтный ключ от PRNG,
позволяющий нагенерировать 100 ТБ нужной тебе инфы, в некоем генераторе-порождателе инфы?
Попробуй подбери перебором этот ключ длиной в 100 гигабайт - для получения именно этих уникальнейших данных.
Даже ключ длиной 256 бит, хакер будет перебирать аж до тепловой смерти Вселенной.
>И если данная схема начинает работать, то это моментально начнёт влиять на всю информационную сферу и всё что с ней связано.
Просто, для хранения зашифрованных бекапов, систем, можно было бы использовать немного места, а не сотни гигабайт.
Для передачи bigdata, не нужно было бы использовать огромные грузовики с жесткими дисками (как на картинке).
>Если весь архив порнолаба за все года можно уместить в микрофайлик весом не больше mp3, то это чудесно.
Да, можно было бы порнлаб слить.
Но, ещё более годной - была бы возможность перемещаться по данным, не распаковывая их.
Представь себе PRNG, куда ты пхаешь некий уникальный 100-килобайтный ключ, и он выдаёт тебе последовательные байты.
А в этих байтах содержится - модель всей Вселенной.
Но для перемещения по этой виртуальной Вселенной, тебе не нужно распаковывать все данные,
а достаточно изменить оффсет (конкретное планковское время и планковский объем),
и начать читать данные с другой позиции.
То есть, тебе не нужно, 100КБ, распаковывать в 100 гигабайт, затем в 100 Терабайт, и так далее.
Может такая шняга была бы для кого-то и страшной, ведь диверсификация такого уникального ключа,
нивелировала бы уникальность - абсолютно любой инфы.
>В итоге при передаче одной-единственной картинки может оказаться вся библиотека всех файлов мира.
Охуенно же. Можно было бы вложить даже - ещё не вышедшие фильмы!
Зато, любую инфу можно было бы восстановить, и снова по сети, в торрентах, раздать.
Не обязательно даже снимать какие-либо фильмы.
Но опять же, в таких пиздатых массивах инфы, надо бы точно знать - откуда начать читать данные,
и этот оффсет может быть длиной в сами данные, если не больше.
То есть, если их продолжать генерить, генерить и генерить, (затрачивая время и циклы на генерацию),
а не просто упаковать изначально и выдать - совсем другой ключ для их быстрой генерации.
>И этого в общем-то достаточно, чтобы утверждать, что в общем случае такой алгоритм - астальная хуита.
>Но вот доказать что такой подход не взлетит ни в одной частной ситуации, или даже целом классе таких ситуаций...
Все быть может, все быть может,
Все быть может, может быть.
Но одно лишь быть не может —
То, чего не может быть.
>Как это ты так, от нормальной формы пришёл к 1-3 членам?
Под "нормальной формой" имеется в виду любая схема записи, которая позволяет записывать однородные сущности единственным образом.
>Двоичная, скорее всего, самая универсальная и оптимальная
> скорее всего
Oh, my... Почитай дискретку, там обычно в начале этот разбор полётов даётся. Разве что надо помнить что итоговая доминация двоичной вызвана сугубо техническими причинами.
>энтропия - зависит от непредсказуемости инфы
Опять же, в вакууме. Степень измеренной охуительности данных может разительно разниться в зависимости от того что мы знаем о системе и собственно входных данных.
А если мы производим сверху какие-либо манипуляции, то уж тем более.
>если в таблице будут перечислены все последовательности...
Вот тут ты начинаешь повторять стандартную выкладку теории сжатия, а там всё совершенно однозначно уже расписали и разработали.
>А чё тут страшного?
Если подобное будет обнаружено и поставлено на широкие рельсы, то это полностью изменит окружающий тебя цифровой мир.
>возможность перемещаться по данным, не распаковывая их
Это уже совсем фантастично выглядит, т.к. для перемещения тебе всё равно необходимо как-то вычислить предыдущие блоки.
Впрочем, если таки отбросить скептизцм, то единственное о чём мы тут можем более-менее реально говорить - очень упоротая файловая система, где реальным носителем является астральная сущность, а все записанные данные по факту лишь инструкции и указатели.
Если, например, мы рассмотрим текущий компьютер в отрыве от HDD, то процессор с оперативкой собственно то и делают: откуда-то волшебным образом появляются команды и данные.
Собственно в нашем случае речь идёт о том, чтобы вместо i/o происходила калькуляция внутри самого процессора по, опять же, крайне изощрённой схеме. И тут надо какой-то proof-of-concept выкатывать, т.к. иначе вопрос о хуите и признании несжимаемости ну просто нельзя не поднять.
Но чтобы ещё позадориться надо б вспомнить, что количество состояний крупного компьютера давно уже вышло на астрономические масштабы. И если можно ещё пару раз удвоить-утроить битность адресации то получится машина чьих состояний больше чем учёные атомов во Вселенной насчитали. Для таких рассуждений ментальная лазейка, чтобы продолжать пытаться, очевидно остаётся.
> специалистам по синергетике.
> куча псевдонаучного шизоидного бреда
И почему я не удивлен.
Ух, что надыбал: https://ru.wikipedia.org/wiki/Фибоначчиева_система_счисления
>смешанная система счисления для целых чисел
И внизу:
>Категории: Системы счисления Золотое сечение Сжатие данных
Как думаете, она оптималнее двоичной? Есть моар таких смешанных систем?
Вот, ебать: https://ru.wikipedia.org/wiki/Система_счисления#Факториальная_система_счисления
Ну всё, я пошёл кодить сверхсжатие BigData.
>Есть моар таких смешанных систем?
Крайне много, в 60-70х их активно информатики перебирали, там один только Кнут более 10 штук наклепал.
Но не понимаю твоего энтузиазма вокруг них. Как и про бигдату. Последняя вообще не нужна в сжатом виде, там вся писька в обработке объёмной хуйни.
Ну смотри. Всё просто. Есть четырёхтерабайтный HDD... Он забит порнухой и играми. Для файла подкачки - места уже нет.
Ось вот-вот слетит нахуй, из-за эрроров и багов от нехватки RAM.
Значит... Надо сделать бекап! Берёшь другой четырёхтерабайтник...
И туда сливаешь бекап, каким-нибудь memcpy чтобы вооще по хардкору.
Ой... Бля... Да там же данные открыты! Ну там пароли всякие и т. д., они же прямо hex'ом и прописаны, блядь, в секторах...
Их же могут спиздить?!!
Значит... Надо зашифровать!.. Шифруешь их... А теперь... Надо же всю эту хуйню сжать!..
А зашифрованные данные-то несжимаемы! FFFFUUUUU!
Это чё теперь, для каждого бекапа по четырехтерабайтнику покупать?
Да ну нахуй!
Проще запилить универсальный порождатель натуральных чисел, на смешанной системе счисления,
который кодировал бы все натуральные числа оптимальнее чем двоичня система,
и если достигнуть прорыва во всей этой хуете, то ещё и в довесок - слить в килобайты весь прон с порнлаба.
>Но не понимаю твоего энтузиазма вокруг них.
Да всё просто. Вот есть четырёхтерабайтник. Забит он порнухой и играми.
Для файла подкачки уже места нет. Лезут сраные окна: "Недостаточно памяти... Недостаточно памяти!!!"
Система вот-вот пойдёт по пизде. Значит... Надо сделать бекап!
Берёшь, такой, другой четырёхтерабайтник, и сливаешь туда бекап, каким-нибудь memcpy, в tar-архив, чтобы вообще по хардкору.
Но... Стоп... Там же данные открыты. Ну, там пароли всякие, они же HEX'ом прямо в секторах прописаны.
Их могут спиздить! Значит... Надо... Зашифровать всё это нахуй.
Шифруешь... А теперь... Надо всю эту хуйню как-то сжать. Авотхуй! Данные-то несжимаемы, блядь!
Это что получается? Для каждого бекапа по 4-х терабайтнику покупать?
Неее, проще же, наверное, запилить универсальный порождатель инфы, работающий на принципах смешанных систем счисления,
на всяких фрактально-факториальных негафибоначчиевых хуйнях, и в качестве бонуса ещё - слить весь порнохаб - в килобайтики. Лол.
Макаба глючит пиздец. Отправил один пост. Каптча невалидна. Отправил второй пост - появилось два.
>смешанной системе счисления,
который кодировал бы все натуральные числа оптимальнее чем двоичня система
Это всё прекрасно, но на физическом уровне у тебя всё равно двоичная система. Любое кодирование с использованием современного компьютера означает, что итоговый результат должен быть в конце переведён в двоичный вид.
>для каждого бекапа по четырехтерабайтнику покупать?
Серьёзные системы бекапов обычно посложнее устроены чем чистое копирование диска. Алсо, даже при копировании топа современные методы позволяют шифровку и сжатие наложить.
>Это всё прекрасно, но на физическом уровне у тебя всё равно двоичная система.
>Любое кодирование с использованием современного компьютера означает, что итоговый результат должен быть в конце переведён в двоичный вид.
Я думал так сделать. Есть какое-нибудь число 121448(10) = 11101101001101000(2) - 17 бит.
Разложу по фибоначчи: 121448 = 121393 + 55. Беру только индексы их: {10, 26} => в биты {1010, 11010}. 4 бита + 5 бит = 9 бит, а не 17.
Понял суть?
>>62934
Нашёл тут 2000 чисел фибоначчи: https://oeis.org/A000045/b000045.txt
Обрадовался, как дитя. Думал, ну щас пронумерую по порядку их, запхну в массив,
и начну раскладывать сектора, и ужимать всё числами.
Не тут-то было. Длина этих индексов, вместе взятых - превышает битовую длину числа.
Эти числа фибоначчи, просто как двоичные цифры вида 256^N, а каждый индекс - как байт. В итоге - та же длина почти.
ЧЯДНТ?
>>62935
Думал начну факторизовать и всё будет заебись. Автохуй! Множители больше, чем цифры числа. Битовая длина тоже. Бле...
>>62947
>Серьёзные системы бекапов обычно посложнее устроены чем чистое копирование диска.
>Алсо, даже при копировании топа современные методы позволяют шифровку и сжатие наложить.
Ты не учитываешь то, что многие видео уже пожаты, и они несжимаемы.
>Бле
Пиздец ты наплодил, че такой буйный? Тебе ж сказали, нельзя сжать несжимаемое, если нет алгоритма, который описывает число и который короче записи этого числа, то ничего ты не сделаешь. 100000 единиц сжать можно, рандомное число нельзя.
>Беру только индексы их: {10, 26} => в биты {1010, 11010}. 4 бита + 5 бит = 9 бит, а не 17.
>Понял суть?
Понял, ты не знаешь устройство компьютера.
1. Ячейка памяти представляет собой фиксированное число даже не бит, а байт.
2. Хранить биты между несколькими словами совершенно бессмысленный номер.
3. Компьютер при побайтной работе довольно глупый - всё что он наблюдает это бесконечные байтовые последовательности. Без алгоритмизированного шаблона по вычленению оттуда собственно чисел, или ещё каких данных, хуй он тебе что сделает. А теперь прикить как ты твоит 4 + 5 уложишь, чтобы получилось 9 которые поймёт и считает компьютер.
>1. Ячейка памяти представляет собой фиксированное число даже не бит, а байт.
>2. Хранить биты между несколькими словами совершенно бессмысленный номер.
>3. Компьютер при побайтной работе довольно глупый - всё что он наблюдает это бесконечные байтовые последовательности.
>Без алгоритмизированного шаблона по вычленению оттуда собственно чисел, или ещё каких данных,
>хуй он тебе что сделает.
>А теперь прикить как ты твоит 4 + 5 уложишь, чтобы получилось 9 которые поймёт и считает компьютер.
Биты, то я для наглядности показал.
Если реально можно было бы так сжать, то понятно что с ростом числа, в среднем 17 байт могло бы быть сжато в 9 байт.
Ну да пофиг.
>>62956
Терь у меня немного другая идея, с этими числами Фибоначчи.
Короче, взял я последнее число Фибоначчи, и вижу:
>>> str('bitlength 2000-th Fibonacci number = ')+str(len(bin(4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125)[2::]))+str(' bits')
'bitlength 2000-th Fibonacci number = 1388 bits'
То есть его длина 1388 бит, в бинарном виде.
Можно взять 2000 чисел, пронумеровать их индексы от 0 до 2000,
и закодировать наличие или отсутствие чисел - битами.
Например, число:
27(10) = 11011(2)
Разложу по Фибоначчи:
27 = 21 + 5 + 1
0 1 2 3 4 5 6 7 8 <- индекс числа Фибоначчи
0 1 1 2 3 5 8 13 21 <- само число
0 0 1 0 0 1 0 0 1 < - и как-то так представить число 27.
Тут уже 3 единичных бита, но длина числа в битах - 9 бит, а не 5.
Упор можно сделать на то, что с ростом длины, падает количество единиц,
а значит - информационная энтропия данных, представляющих число.
Дальше уже, эти данные можно пожать архиватором, они должны быть более сжимаемы.
Ведь множество чисел может быть представлено двумя-тремя числами Фибоначчи,
а значит будут два-три единичных бита - остальное биты нулевые.
>с ростом длины, падает количество единиц,
>а значит - информационная энтропия данных, представляющих число.
>Дальше уже, эти данные можно пожать архиватором, они должны быть более сжимаемы.
Хм, в таком случае тебе необходимо заранее сообразить разумные пределы длины перекодируемых байтов, а также выяснить эффективное количество последовательных нулей-единиц для сжатия.
Однако у Фибоначчи очень знатный рост происходит и чтобы ими любое число описывать необходимы также и отрицательные индексы.
>Хм, в таком случае тебе необходимо заранее сообразить разумные пределы длины перекодируемых байтов, а также выяснить эффективное количество последовательных нулей-единиц для сжатия.
Да там всё просто. Берётся максимальное число 2^(n+1)-1,
затем ищется ближайшее к нему число Фибоначчи, и его индекс - максимальное количество бит для кодирования.
Вот, если хочешь, потыкай пример на питоне: https://rextester.com/YLFZS33456
Нулей действительно дофига, и ещё одно свойство я вижу - вполне закономеро, нет комбинации 11.
Но могут быть 01 и 10, где какая - неясно, и если жать кодом Хаффмана, всё-равно по битовой длине как двоичное представление получается, даже больше.
>Однако у Фибоначчи очень знатный рост происходит
Кстати, насчёт роста. Я вижу, что график чисел Фибоначчи растёт быстрее чем x^2 и даже x^3, но медленее чем 2^x.
В двоичной системе аналогом чисел Фибоначчи являются числа вида 2^x, которые и кодируются битами,
а их сумма - представляет собой число.
Так вот график 2^x растёт быстрее, поэтому двоичная система счисления - оптимальнее фибоначчиевой.
>и чтобы ими любое число описывать необходимы также и отрицательные индексы.
Я не собирался производить операции над числами в фибоначчиевой системе,
я хотел в ней просто выразить числа и хранить, так как думал что запись числа в ней может быть оптимальнее.
А значит, многократным переводом из двоичной в фибоначчиевую, типа можно было бы сжать число.
Но как видишь, это не так...
Остаётся смотреть в сторону разложений чисел на всякие там, к примеру - додекаэдральные числа: https://ru.wikipedia.org/wiki/Гипотезы_Поллока
>нет комбинации 11
А вот это очень полезное дело. Т.к. про байты отчего и говорю - всей схеме необходимы разделители. Если уж решил, что будут произвольная длина кодов, то без разделителей не обойтись. И если разделитель такой ёмкий и характерный, это таки победа.
Правда остаётся вопрос как им отбивать числа имеющие в оконцовках единицы. Однако, если максимум подряд идущих единиц - две, то разделителем может стать, например 1110111. Тоже вполне неплохо.
>всё-равно по битовой длине как двоичное представление получается, даже больше
Ну так в чистом виде по идее у тебя должна появляться более громоздкая запись. Вся писька в том, чтобы в этой громоздкой выделить некий инвариант, который можно вынести за рамки, тем самым получая хотя бы 1% сжатия.
>Так вот график 2^x растёт быстрее, поэтому двоичная система счисления - оптимальнее фибоначчиевой
Опять же, это дискретка известная, там "оптимальным" считается нечто между 2 и 3. Тернарная система не взлетела по сугубо инженерным причинам, ну и плюс к ней алгебру логики сложнее прикручивать.
>думал что запись числа в ней может быть оптимальнее
Ну вот это совершенно точно нет, опять же с пруфами. Впрочем только для целых чисел. Никто на самом деле не мешает считать полторашками, например.
>А вот это очень полезное дело. Т.к. про байты отчего и говорю - всей схеме необходимы разделители.
>Если уж решил, что будут произвольная длина кодов, то без разделителей не обойтись.
>И если разделитель такой ёмкий и характерный, это таки победа.
>Правда остаётся вопрос как им отбивать числа имеющие в оконцовках единицы.
>Однако, если максимум подряд идущих единиц - две,
>то разделителем может стать, например 1110111. Тоже вполне неплохо.
А причём тут байты? Разделитель можно юзать и в бинарных данных.
С разделителем '11', такое уже не прокатит, потому что появляется многозначность:
100100001111010011101001010
10010000[11][11]0100[11]101001010
100100001[11]101001[11]01001010
А вот с разделителем '011', данные вида:
10010000101110100101101001010
могут быть однозначно разбиты на три числа:
100100001[011]101001[011]01001010
>Ну так в чистом виде по идее у тебя должна появляться более громоздкая запись.
>Вся писька в том, чтобы в этой громоздкой выделить некий инвариант,
>который можно вынести за рамки, тем самым получая хотя бы 1% сжатия.
Я же писал выше, что даже, если подсчитать частоты нахождения комбинаций '01' и '10', и сжать их тем же кодом Хаффмана,
длина сжатого представления числа в фибоначчиевой системе - получается примерно равной,
длине представления этого числа в двоичной системе, а то и больше.
Поэтому, и сжать не получается.
Кстати, хотя функция f(x) = x! растёт быстрее, чем f(x) = 2^x,
факториальная система счисления - ещё больше цифр выдаёт на выходе: https://rextester.com/OQP66610
Поэтому данные представления числа в этой системе - тоже избыточны.
Но я не знаю как насчёт энтропии этих данных, возможно они будут более сжимаемы.
>Опять же, это дискретка известная, там "оптимальным" считается нечто между 2 и 3.
>Тернарная система не взлетела по сугубо инженерным причинам, ну и плюс к ней алгебру логики сложнее прикручивать.
Троичная система счисления, считается оптимальной, потому что ln(x)/x,
где x - основание системы счисления, имеет максимум при e.
Если проще, можно рассмотреть пример: у нас есть 60 дощечек, на которых можно написать повторяющиеся цифры - как нужно поступить, какую позиционную систему выбрать, чтобы при помощи этого набора выразить максимальное количество чисел? Можно сделать по 30 нулей и единиц, тогда в двоичной системе можно будет записать 2^30 - чуть более миллиарда различных чисел. Если сделать по 20 штук "0", "1" и "2" - то 3^20 - почти 3,5 миллиарда чисел в троичной системе. 4 цифры на 15 разрядов: 4^15=2^30, максимум функции пройден, дальше на убыль: 5^12 - менее четверти миллиарда, 6^10 - 60 миллионов, наконец 10^6 (привычная нам десятичная система) - миллион, совсем смех. 12^5 - вчетверо меньше... А можно просто 60 разных цифр и один разряд, как вавилоняне - вот и будут лишь числа от 0 до 59.
В непрерывном случае максимум приходится на число e=2,718...,
так что основание 3 выглядит лучше всех, 2 и 4 - одинаково чуть похуже: http://phg.su/basis2/X51.HTM - наглядно.
Вот в этой "википедии": https://ru.wikibooks.org/wiki/Системы_счисления ,
расписано про "зависимость плотности записи информации от основания системы счисления"
и вот тут ещё: http://igorypimenov.narod.ru/Psichophisical_model.pdf
В конце 3 страницы и в начале 4.
>Ну вот это совершенно точно нет, опять же с пруфами.
>Впрочем только для целых чисел. Никто на самом деле не мешает считать полторашками, например.
Поэтому и фигово.
Глянул я, в общем, последовательность из 1000 додекаэдральных чисел: https://oeis.org/A006566/b006566.txt
Растёт она не очень быстро, но быстрее чем кубы.
Корень кубический, в три раза короче по битовой длине, чем сам куб, но по первой гипотезе Поллока,
их 9, надо, этих кубов: https://ru.wikipedia.org/wiki/Гипотезы_Поллока
а значит длина двоичного представления разложенного числа - должна быть ещё длинее чем само число.
Фак.
>у нас есть 60 дощечек, на которых можно написать повторяющиеся цифры - как нужно поступить, какую позиционную систему выбрать, чтобы при помощи этого набора выразить максимальное количество чисел?
Ты опять перечислимостью занимаешься. На перечислимости совершенно однозначно уже всё исследовано.
Где можно выйти куда-либо - это на записи отдельных случаев, возможно с промежуточным преобразованием. Одна беда - как это сделать статистически равномерным, чтобы гарантировать сжатие.
Даже на дощечках ты можешь пожертвовать частью "бит", например среди нижнего регистра, чтобы иметь возможность выразить совсем специальные числа заданными кодами. Да, так ты нарушишь монотонность - сверху будет заполнение с пробелами. Однако там где оно нужно ты сможешь таки выразить большие величины чем позволит полное перечисление.
Также можно попробовать итеративно разбивать весь набор на разные кодировки лишь бы сохранялась обратимость. Можно вычленить каждые вторые 4 бита, можно вычленять на основе последовательности. Таких разбиений может быть условно дохуя. Но если хоть одно из них в итоге обнаружит сжимаемые данные, то мы можем онные сжать и положить рядом с оригиналом, указав лишь по какому алгоритму произошло вычленение.
Решил отпердолить троичную систему счисления, чтобы вконец разочароваться в этой идее...
Нашёл вот эту многообещающую статью: https://arxiv.org/ftp/arxiv/papers/1201/1201.5603.pdf
Выдернул с неё основание 3, префиксный код, и запилил это: https://rextester.com/YPFE4643
Заодно уж заделал функцию для конвертации числа в b-ричную систему счислени и из b-ричной - в десятичную.
Добавил функцию для кодирования-декодирования, при помощи префиксного кода:
https://ru.wikipedia.org/wiki/Префиксный_код
https://ru.wikipedia.org/wiki/Код_Хаффмана
и функцию для подсчёта нулевых и единичных бит, а также их комбинаций.
Можешь ткнуть в код и нажать F8, чтобы запустить.
Видно, что нихуя не работает, сжатие, как описано в статье выше,
кроме как для случая с числом 1358, указанном в статье.
Попытался найти закономерность, и стало очевидно,
что количество бит закодированного префиксным кодом троичного представления числа,
падает тогда, когда троичное представление этого числа - содержит много двоек.
В любом случае, закодированное префиксным кодом - троичное представление рандомного числа,
хоть и избыточно (длина строки и объем данных больше, чем у двоичного представления),
но тем не менее, оно содержит больше нулей, чем двоичное представление этого числа,
а значит меньше грузит линию при передаче данных.
Разве что в этом и профит, блеать.
А вот как сжать рандом ёбанный, или крипторандом - хз.
Чё-то вертится на уме, опять же, какой-то закольцованный йоба-LSFR, с динамической адресацией, снижающий энтропию входных данных...
Его, кстати, можно было бы и закодить в виде таблицы замен, но не думаю, что оно что-то даст.
Раз уж про системы счисления речь зашла, чё бы не колупнуть вот это: https://ru.wikipedia.org/wiki/Asymmetric_numeral_systems
Выглядит привлекательно, но чё-то сорцов не вижу.
>Чё-то вертится на уме, опять же, какой-то закольцованный йоба-LSFR, с динамической адресацией, снижающий энтропию входных данных
Опять же это надо как-то изящно обосновать.
Я интересу ради попробовал несколько тысяч генераторов рандомных (в принципе любой рандомайзер по сиду подойдёт - тупо делаешь их множество и собираешь в списки\массивы выдачу) настроить под поиск в них удачной комбинации бит - увы и ах, попаданий было ноль на миллионы проверок, а времени на одном потоке ушло овердохуя.
Вообще, если задачу формулировать в таком варианте, то у нас есть целая гора очень хороших и работающих повсеместно алгоритмов сжатия. Не доверять им я смысла не вижу. Соответственно всю первичную работу можно поручать данной группе алгоритмов (например в zip запаковать с максимальным уровнем сжатия).
Далее мы сталкиваемся с обилием энтропии.
И тут мы можем постулировать два случая:
1) Всевозможные рандомайзеры с сидом совершенно явным образом задают огромное количество информации.
Нужен буквально следующий набор:
<код типа рандомайзера> <сид> <оффсет байт/бит от начала выданной последовательности> <собираемое число байт/бит начиная с оффсета>
Если брать сдвиг по битам и ещё, например, добавить пару флагов вроде реверсивного взятия, инверсии и каких-нибудь перетасовок, то такая схема очевидно позволит записать довольно много данных буквально несколькими байтами (для пущего эффекта это всё можно вырезать из общей последовательности и записать позицию с которой вырезание произошло, чтобы при декодировании вклеивать), которые ещё и отдельно хранить можно.
Но насколько ничтожна вероятность что для рандомного куска байт будет выгодное нам попадание? С виду проверять чистые байты/биты - гиблое дело. Но можно попробовать что-то типа регексов по типу: "идём от текущей позиции, делая приращение по условной единице, если среди всех генераторных схем случилось попадание позволяющее после всех манипуляций сэкономить хотя бы один байт - попробовать движение дальше покуда есть приращение сэкономпленного, как только матчинг пропадает то откатываемся на шаг назад и делаем вырезку данных, после чего продолжаем опять".
Это заведомо не будет иметь большой вычислительной эффективности, но в случае попаданий очевидно будет иметь эффективность сжатия.
2) Можно устроить вишмастер для уже сжатых данных, по какой-либо схеме рандомности разбросав байты. Если мы можем это преобразование записать конкретным образом и оно обратимо, то можно просто перебирать шатание байтов: ушатать и проверить происходит ли сжатие с указанной эффективностью не ниже минимальной.
Тут достаточно:
<список ранее применённых схем шатания байт <код такой схемы>> <было ли сжатие>.
В данном случае мы уже точно имеем очень медленное приращение побочных данных, плюс можем обеспечить рекурсивность. Опять же, вероятность того что цепочка рандомизаций выдаст результат который подарит новые грани сжатия явно ненулевая, но и едва ли великая. Вычислительная сложность также может быть пиздецовой. Впрочем люди и софт крупный могут компилить вручную, если можно будет распечатать крупный файл из нихуя, то энтузиасты подождут обработку.
Сам ещё не пробовал, на выходных может будет окно - запущу в каком-нибудь примитивном виде поглазеть.
Ну и в общем, если мы по обоим случаям можем обнаружить и обосновать ненулевую вероятность сжатия, да ещё и которую можно на простом ПеКа выявить менее чем за час работы - бинго. Далее опять же рекурсивность можно будет врубать и жать до посинения.
----
Сейчас ещё прикинул - можно покопать в сторону лосслесс, но хитрым образом. Например, есть схема сжатие джипегов через косинусоиды. Выигрыш там огромный в том числе для особо сложных данных. При этом при правильной кодировке можно воспроизводить цельный битмап каждый раз, пусть и с потерей ряда данных.
Однако, можно сделать подобное, а те самые теряемые данные банально заинвёртить относительно восстанавливаемого массива. Тогда мы получим:
<пережатое косинусоидами или чем подобным> + <массив дополнений до лосслесс>
Последний можно попробовать повторно пожать традиционным сжатием, разбить на куски и повторить текущую процедуру итд.
>Чё-то вертится на уме, опять же,
>какой-то закольцованный йоба-LSFR,
>с динамической адресацией,
>снижающий энтропию входных данных.
>Опять же это надо как-то изящно обосновать.
За LSFR, сказал вот этот анон: >>62877, и наверное он - это ты.
Я, конечно же, мало что понял, но пошёл на википедию: https://ru.wikipedia.org/wiki/Регистр_сдвига_с_линейной_обратной_связью
и вижу там пикрил.
Вижу, что полубайты (4 бита), изменяются им, циклично,
и это натолкнуло на мысль, что изменение полубайт может изменить информационную энтропию несжимаемых данных,
потому как если изменять полубайты в данных, где частоты встречаемости,
у всех возможных значений полубайт - распределены равномерно,
то может изменяться частота встречаемости одних символов по сравнению с другими,
а следовательно и пожать эти данные можно будет, впоследствии, после такого преобразования.
Но LSFR - это очень грубо и непонятно, поэтому я предложил - таблицу замен, чтобы жестко захардкодить замены эти.
Далее, тот анон сказал, в своём посте, что блуждание этого LSFR (или любого другого заменителя байт),
можно замкнуть на перераспределение адресации, как-бы генерируемой, им же.
Ну, чтобы он блуждал, блуждал, внутри блока данных, менял байты там, получал новые,
интерпретировал их как адреса, шёл в нужный адрес, и там изменял,
и так - аж пока он либо не сгенерит нужные данные,
либо через N итераций не получит сигнал стоп, сгенерив-таки эти данные.
Дальше, у меня до этого, была мысль о некоей обратимой сортировке.
Если кратко, то это просто последовательность XOR-обменов...
Пусть есть строка 'helloworld'.
В массив её: -> ['h', 'e', 'l', 'l', 'o','w','o','r','l','d'].
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'] индексы - для наглядности.
['h', 'e', 'l', 'l', 'o', 'w', 'o', 'r', 'l', 'd']
Меняем нулевой и первый символ, тройным XOR https://ru.wikipedia.org/wiki/XOR-обмен ,
и записываем по два индекса, где производится этот обмен символов:
['d', 'e', 'l', 'l', 'o', 'w', 'o', 'r', 'l', 'h'] - [0, 9]
И так, пока строка не будет отсортирована.
['d', 'e', 'h', 'l', 'o', 'w', 'o', 'r', 'l', 'l'] - [2, 9]
['d', 'e', 'h', 'l', 'l', 'w', 'o', 'r', 'l', 'o'] - [4, 9]
['d', 'e', 'h', 'l', 'l', 'l', 'o', 'r', 'w', 'o'] - [5, 8]
['d', 'e', 'h', 'l', 'l', 'l', 'o', 'o', 'w', 'r'] - [7, 9]
['d', 'e', 'h', 'l', 'l', 'l', 'o', 'o', 'r', 'w'] - [8, 9]
Итак, получаем полностью отсортированный массив, и строку из него: 'dehllloorw'. Все буквы - в алфавитном порядке.
Cимволы здесь, повторяются чаще, а значит то же арифметическое кодирование может быть уже применено к этим данным.
Но главное то, что эти данные можно обратить в исходную строку,
если произвести XOR-обмены - в обратном порядке, в соответствии с приложенной последовательностью индексов.
Каждый индекс, имеет значения от 0 до значения (длина массива-1).
НО!.. В то время как отсортированная строка, в результате сортировки - теряет энтропию,
сами эти индексы в общем-то, перенимают всю инфу от строки (её информационную энтропию).
И если строка содержала в себе 9 символов, то после 6-ти XOR-обменов, имеем +12 чисел сверхуй, в этих индексах.
И поскольку в этих символах вся энтропия и инфа, то это информационная избыточность...
Так вот, наверняка, этими индексами могли бы данные внутри блока самих же данных,
и данные - образующиеся в процессе замены (адреса).
То есть пофиг, какой длины последовательность этих индексов, она всё-равно внутри блока.
Однако из соображения о том, что сами индексы перенимают информационную энтропию, и что она никуда не девается,
следует то, что сколько не бегай внутри блока, сколько данные с адресами не меняй, а энтропия блока данных - не снизится, блядь.
Исходя из вышеописанного, строго следует то, что как тут всё это изящно обосновать - хуй знает.
>Я интересу ради попробовал несколько тысяч генераторов рандомных
>(в принципе любой рандомайзер по сиду подойдёт - тупо делаешь их множество и собираешь в списки\массивы выдачу)
>настроить под поиск в них удачной комбинации бит - увы и ах,
>попаданий было ноль на миллионы проверок, а времени на одном потоке ушло овердохуя.
Ну, если это CSPRNG какой-нибудь, то смотри какая фигня...
У меня тоже была идея, взять какой-нибудь шифр, блочный,
и по блокам пытатся шифровать, с разными ключами,
перебирая все возможные ключи так,
чтобы на выходе зашифрованные данные имели минимальное количество единиц, и максимальное количество нулей.
Так вот, как думаешь, какой длины примерно будет seed для CSPRNG, (или ключ для блочного шифра),
чтобы следующий блок данных гарантированно имел минимальное количество единиц?
Наверняка, этот seed (ключ), будет длиной в блок, верно? И наверняка, его значение - будет представлять из себя,
внезапно, опять же - несжимаемые данные. И следующий блок, уже, по-любому - будет пиздецки радомным.
>Вообще, если задачу формулировать в таком варианте,
>то у нас есть целая гора очень хороших и работающих повсеместно алгоритмов сжатия.
>Не доверять им я смысла не вижу.
>Соответственно всю первичную работу можно поручать данной группе алгоритмов
>(например в zip запаковать с максимальным уровнем сжатия).
Они уже научились сжимать несжимаемые данные? В этом-то и вся пиписька!
Я почему смотрю именно в сторону разложения чисел?
Да потому что, если какие-либо числа, специльного вида, можно записать короче,
то так можно будет сжать любое натуральное число, любой длины: https://username1565.github.io/BigInteger.js/cube_root.html
будь то сектор на диске, будь то бинарная строка, текст или hex.
Разложение в сумму степеней - отпадает... https://ru.wikipedia.org/wiki/Проблема_Варинга
Там даже минимальное количество слагаемых больше, чем степень.
То есть, если двоичное представление корня кубического,
оно хоть и в три раза меньше куба, но зато четыре корня вряд - вот тебе и избыточность инфы уже.
А вот числа, вроде тех же простых чисел Прота, если можно представить в виде k×2^n+1,
то достаточно записать лишь множитель и степень, вместо того, чтобы писать само длиннющее число,
какое-нибудь 10223×2^31172165+1? Понимаешь?
И если, внезапно, окажется, что какими-то древними математиками, в каком-то веке до нашей эры,
доказана какая-то теорема о разложении любого, произвольного, натурального числа,
на два-три, да пофиг, пусть даже на стопицот чисел Прота,
и если можно будет с лёгкостью их подобрать,
то вот тебе и сверхсжатие, да ещё и рекурсивное.
>можно просто перебирать шатание байтов: ушатать и проверить происходит ли сжатие с указанной эффективностью не ниже минимальной.
Кстати, насчёт шатания. Я где-то слышал, что встряска, может способствовать организационным и самоорганизационным процессам.
Выше, здесь >>62906, был пост про самоорганизацию.
И если применить законы самоорганизации для упрощения инфы (с возможностью её восстановления при развёртке),
то встряска и шатание байт могли бы ещё и ускорить процесс самоорганизации инфы.
Эдакое негэнтропийное, или не, даже экстропийное кодирование, по аналогии с энтропийным кодированием:
https://ru.wikipedia.org/wiki/Энтропийное_кодирование
Кстати, там же, две строчки, которые чётко описывают проблематику этого треда:
>Согласно теореме Шеннона, существует предел сжатия без потерь, зависящий от энтропии источника.
>Чем более предсказуемы получаемые данные, тем лучше их можно сжать.
>Случайная независимая равновероятная последовательность сжатию без потерь не поддаётся.
>Как ещё можно разложить произвольное натуральное число?
>Как можно было бы сжать зеттабайт несжимаемых данных (случайных, зашифрованных)?
А как насчёт разложения длинных чисел - на сумму трех полнократных чисел?https://ru.wikipedia.org/wiki/Полнократное_число#Суммы_и_разности_полнократных_чисел
>Эрдёш высказал гипотезу, что любое достаточно большое целое число
>является суммой максимум трёх полнократных чисел.
>Гипотеза была доказана Роджером Хит-Брауном.
Их запись, походу короче (из-за показателя степени),
и даже если три числа вместе записать,
то для больших чисел, представление числа тоже должно бы быть короче, не?
Тогда, надо будет писать максимум - шесть чисел (и показатели степени ещё),
и если показатели степеи двойка и тройка,
то основания степеней полнократных чисел - могут быть настолько длинными,
что в сумме они, по длине двоичной, могут превышать само число - в двоичном виде.
>LSFR
Просто к слову пришёлся как один из наиболее понятных мне алгоритмов для псевдорандома. Там схема явным образом задаётся полиномом и сидом, что собственно и позволяет сколько-то компактно описать рандомизатор.
Сегодня вероятности подрочил немного - словарные схемы в чистом виде выглядят совершенно гиблым делом.
Однако, если "словарь" будет каким-то образом генерироваться на основе поданного на него блока байтов, где из поданного блока словарь в компактном виде будет записывать от 30% блока - собственно бинго. Осталось только структуру подобрать какую-нибудь и чтобы граф её трансформаций можно было в один-два байта уместить.
Хз, наверное в течение недели напишу на чём-нибудь.
Опять же, всё упирается в мат.ожидание:
- словарь может содержать лишь ничтожную часть от возможных комбинаций байтов заданной длины
- тем не менее в пределах блока (5, 7, 15 и более байт) реальная комбинация будет на порядок более ничтожной от всего пространства возможных комбинаций по столько же байт
- соответственно, если мы можем соорудить словарь чьё "адресное пространство" сколько-то больше поданных на него блоков, а сам подготовленный словарь вместе с трансформациями будет иметь в себе критически выигрышный процент от взятых для текущей итерации блоков, то будет хорошо
Общая схема примерно так:
<полученный сид словаря> <настроечная структура> <список блоков фиксированного размера <блок байтов>>
Настроечная структура в общем виде должна иметь один-два бита для типа используемых словарей, и далее набор бит соответствующий каждому блоку: единица означает что данный блок должен быть декодирован по словарю, ноль - что должен восприниматься как есть.
В данном случае мы должны получить гонку между приращением настроечной информации на список блоков против выигрыша от скольки-то сокращённых блоков.
Алгоритм должен априори гарантировать что n-% и 100% попадание блоков в словарь даст меньший объём чем исходный список. А раз так то нужно лишь убедиться что общая вероятность попадания не меньше собственно n%.
Фух, хоть сформулировал чего ищу вообще.
В любом случае это вполне благородная почва чтобы зубы пообламывать. Вреда никому не наносится, в процессе узнаёшь много нового и лучше осваиваешь фундамент, а если всё-таки взлетит то тебя полпланеты няшей-писей назовут.
Хотя вообще такие задачки должны преподаватели студентоте подкидывать - нате мол, в течение семестра поразвлекайтесь, кто сможет тому пятёрку автоматом
>>63122
>>63124
Короче, посоны!
Думал, я, думал насчёт негэнтропии... И не придумал ничего лучше...
Кроме как... ВНЕЗАПНО... НЕГАЦИИ ЭНТРОПИИ!
Опишу алгоритм "негэнтропийного сжатия" так, как я его вижу.
Идея следующая...
Пусть у нас будут - несжимаемые данные, в которых количество единиц и нулей - одинаково, а их распределение - равномерно.
И пусть этими данными - будет некая 32-битная строка:
00011011111001000001101111100100 (длина 32 бит, в ней 16 единиц и 16 нулей, хуй пойми где).
Проводить негацию будем там, где обнаружено - наибольшее количество единичных бит.
Для этого, придётся производить подсчёт единичных бит, затрачивая время и вычислительные мощности,
но нам на это похуй, ведь мы хотим сжать НЕСЖИМАЕМЫЕ ДАННЫЕ,
и профит свистящих куллеров на проце, в том,
что "НЕСЖИМАЕМЫЕ, БЛЯДЬ, ДАННЫЕ",
в итоге, должны превратиться в СЖИМАЕМЫЕ.
Итак...
Для начала, определим максимальное значение блока данных, по формуле:
n = 2^⌊ln(bitlength)/ln(2)⌋;
где
n - длина блока в битах,
^ - возведение в степень,
⌊x⌋ - округление x к меншему (floor),
ln - логарифм по основанию e,
bitlength - длина блока данных.
КОД (Python3):
>LEN = 32
>import math;
>n = int(math.pow(2, (math.floor((math.log(LEN)/math.log(2)))))); #максимальное число блока бит, для данных длиной LEN бит.
>print(n); #32
Вроде, работает правильно.
Дальше...
Включаем алгоритм подсчёта единиц в блоках данных разной длины,
со сдвигами, половиня длину блока каждый раз, на каждой итерации,
и либо производим негации, отмечая биты, либо не производим, отмечая ноль.
TL;DR
ОПИСАНИЕ АЛГОРИТМА:
Шаг 1.
Считаем единичные биты в блоке размер которого определён выше (32 байт). Стартовый оффсет - 0;
Если количество этих единиц больше половины блока - то отмечаем бит негации блока, и производим негацию ВСЕГО БЛОКА.
Тогда, количество единиц должно уменьшиться, а информационная энтропия - сместиться.
Если количество единиц меньше либо равно значению половины блока - то не трогаем его и оставляем как есть.
Шаг 2.
Ещё один момент... Рассмотрим пример: пусть есть 16 бит данных, и блок по 8 бит.
00001111 11110000 (два блока по 8 бит)
4 4 (количество единиц в каждом блоке - по половине блока, и как-бы пропускаем, и не трогаем)
1111 1111
8 (но здесь их - намного больше, стартовый оффсет 4-й бит, длина блока 8 бит)
Поэтому, на шаге 2 - расширяем Шаг 1.
Производим сдвиг блока (32 байт) на половину (16 байт). Стартовый оффсет не 0 уже, а 16.
И ещё в одном блоке (32 минус 16, то есть, до конца данных) просчитываем количество единиц.
Дальше - аналогично. Либо негация, либо нет. И бит один отметить.
Однако даже если там, в этом урезанном недоблоке 32-битном,
будут все 16 единиц, количество их будет равно половине полного блока (32/16 бит),
и негацию можно не проводить, по условию,
как и можно не проводить эту итерацию вовсе,
ибо ноль 32-битных блоков здесь, всего.
Шаг 3. Половиним длину блока. Было 32, стало 16.
Теперь, как и в Шаге 1 - считаем единицы в двух блоках по 16 бит. Стартовый оффсет 0-й бит:
0001101111100100 0001101111100100 (их по 8, этих единиц, в каждом). Следовательно - никаких негаций. Бит негаций - 0.
Шаг 4. Аналогично шагу 2. Сдвигаем блок на половину (было 16 бит), теперь (с стартового оффсета 8, и по 16 бит на блок) получаем:
00011011 1110010000011011 11100100
Как и в Шаге 1 - считаем биты для каждого 16-ти битного блока (их всего один, он посередине).
Единиц в нём - 8 и менее (где по бокам, в недоблоках). Поэтому - никаких негаций, по условию. Бит негаций - 0 и здесь.
Шаг 5. Снова половиним длину блока. Было 16 бит, стало 8. Стартовый оффсет - 0;
По 8 бит блок:
00011011 11100100 00011011 11100100
Как в шаге 1, считаем биты в этих 8-ми битных блоках. Единиц этих по 4, в каждом блоке, и это ровно половина блока.
Значит - никаких негаций. Бит негаций - 0. Ебать-копать, да эти данные, блядь, внатуре - какие-то несжимаемые!
Шаг 6. Сдвиг на половину блока. Был блок длиной в 8 бит, стартовый оффсет теперь 4-й бит, а не 0-й, и 8 бит - длина блока, прежняя.
0001 10111110 01000001 10111110 0100
Теперь, как и в шаге 1, считаем биты для каждого 8-ми битного блока.
1 6 2 6 1 - и вот здесь, можно провести негацию двух блоков из трех (не считая недоблоки)! Биты негаций: (1) 1 0 1.
Первый бит означает, что будут негации, дальше бит, негации или не негации каждого последующего блока из 8-ми бит.
Теперь, производим саму негацию:
0001 01000001 01000001 01000001 0100
Почему негации? А по условию, потому что количество единиц в двух блоках зашкаливает.
При длине блока в 8 бит, и половине допустимых единиц (4), там их по 6, этих единиц.
На выходе - более сжимаемые данные, так как после негаций имеем нарушение равномерного распределения бит.
_____________
Как и в шаге 3, можно было бы продолжать половинить блок, углубляясь, и просчитывая единички в более мелких блоках (со сдвигом),
но здесь уже смысла негировать - нет,
и очевидно, что мы получили строку с наименьшей информационной энтропией
(в ней - много нулей, и мало единиц).
Если повторять Шаг 3, в отсутствие негаций, то бит негаций каждого раунда - будет 0.
Шаг 7. Теперь... Пишем дополнительные данные, в конец этих уже "сжимаемых данных":
Приведу таблицу проведённых выше операций:
Старт длина блока биты
0 32 (0)
16 32 (0)
0 16 (0)
8 16 (0)
0 8 (0)
4 8 (1)101(биты негаций или не негаций последующих блоков по 8 бит, следующих со старта)
0 4 (0)
2 0 (0)
и т. д.
Промежуточный результат:
00000110100 - это дополнительные данные (информационная избыточность).
После всего этого, следовало бы добавить ещё и длину самих этих вот - дополнительных данных.
Идеальным вариантом, я вижу гамма-код Элиаса,
позволяющий закодировать любое число неопределённой длины:
https://ru.wikipedia.org/wiki/Гамма-код_Элиаса
но так как длина их неопределена, как и длина числа этого, то код - реверсивный.
То есть: 00000110100 (11 бит); 11 -> 000 1 011 (Код эллиаса) -> реверс кода: (1101000) -> в конец строки.
Результат:
0001 01000001 01000001 01000001 0100+
00000110100+
1101000 =
00010100000101000001010000010100000001101001101000 (окончательный результат преобразования).
Теперь, рассмотрим их...
Эти данные хоть и избыточны (длина их более 32 бит), но они уже не "несжимаемы",
напротив, они уже выглядят "более сжимаемыми", поскольку единиц меньше чем нулей.
При больших длинах блока, относительный прирост дополнительных данных может быть минимален.
Восстановление данных - обратной операцией:
сначала читаем реверсный код Элиаса, реверсируем его, получаем число,
определяем длину дополнительных данных, а также длину самих данных, без них и кода Элиаса,
считаем максимальную длину блока для данных уже известной длины,
дальше согласно битам дополнительных данных - производим или не производим негации,
и получаем сами данные.
Вроде, должно работать, совместно с сжатием, и вроде как ещё, должно давать возможность - многораундового сжатия.
Алсо, на базе развёртки данных из зажатой инфы, ИМХО, можно было бы замутить и некий - порождатель инфы.
Но я чё-т ебу, как всё это закодить... Это же не проект не на один день, и меня уже заебало.
В общем, кто допилит - шнобелевку получите. Дерзайте. Авось модель Вселенной на флешках будем носить.
Всё бы ничего, и энтропия от таких углубляющихся негаций - должна бы нижаться,
но по условию:
>Если количество этих единиц больше половины блока - то отмечаем бит негации блока, и производим негацию ВСЕГО БЛОКА.
блок данных содержащий половину единиц от длины блока останется с таким же количеством единиц даже после негации.
То есть срока, вида:
0101010101010101
Даже при длине блока в 2 бита (а это уже ебать кака избыточность в виде бит дополнительных данных):
будет разбит так:
01 01 01 01 01 01 01 01
Казалось бы, такие данные таки должны быть "сжимаемы",
так как в них четыре раза повторяется полубайт '0101' и дважды - байт '01010101'.
Однако, для всех полубайт (2^4),
из 16-ти возможных значений - 6 содержат два единичных и два нулевых бита,
а из всех возможных 256-ти значений байта (2^8) - 70 значений содержат такое же количество единиц,
как и количество нулей внутри них (несжимаемые данные).
И с ростом количества разрядов (степень у двойки) - растёт и количество этих значений,
пожирая где-то около трети всех возможных значений.
Это значит, что если данные будут какими-то вот такими:
01 10 01 01 10 01 01 10, то они не будут пронегированы алгоритмом,
и останутся по-прежнему - несжимаемыми.
Хотя, в 70 значений для байта, я включил также значения вида:
00001111 (4 нуля, 4 единицы)
00110011 (4 нуля, 4 единицы)
10111000 (4 нуля, 4 единицы)
и если такие данные будут в бинарной строке, то при длине блока в 2 бита, они конечно же могут быть пронегированы,
а следовательно байты эти - исключены.
Тогда, вполне возможно, что количество байт для кодирования строки-результата,
может быть значительно снижено - вышеописанным алгоритмом.
Остаётся терь как-то закодить всю эту шнягу и проверить.
Попытался подсчитать, сколько значений четырехбитного числа содержит 2 единичных и 2 нулевых бита.
Получил число 6.
Просчитал последовательность этих чисел для разной длины бит.
Попытался найти её и нашёл это:
https://oeis.org/A210736
>Expansion of (1 + sqrt( (1 + 2x) / (1 - 2x))) / 2 in powers of x.
binomial: https://ru.wikipedia.org/wiki/Биномиальное_распределение
Здесь полная последовательность: https://oeis.org/A210736/b210736.txt
При этом, код префиксный код длиной в n бит может закодировать максимум (2^(n-1) + 1) уникальных значений.
В общем, это те самые несжимаемые данные, количество единиц в которых, ни негацией, ни XOR'ом не изменить.
Единички и нули - там могут быть где угодно,
и кратчайший способ представить их посредовательность - это, походу - записать её битами, так как оно записано.
Что с ними делать-то? Можно как-то в число конвертнуть, а его разложить?
Первое что приходит в голову, это сделать нечто вроде:
01010101 (4 единицы)
XOR
01111111 =
00101010 (уже 3 единицы) XOR
00111111 =
00010101 (три, число перевёрнуто) XOR
00011111 =
00001010 (две единицы).
И как-то так, рекурсивно, при помощи XOR уменьшить количество единичных бит,
порождая негентропийные тенденции в глобальных переменных,
а потом - пожать нули, префиксным кодом. Разумеется, с возможность развёртки изначального числа...
И вообще, можно ли как-то из байта несжимаемых данных - получить два байта данных,
но данных с большей сжимаемостью, разве это не профит?
Можно было бы зациклить же сжатие!
И одним из таких способов, я вижу следующее преобразование...
Пусть x = c × d +- r, где c = d = k - floor(sqrt(x)); r - остаток (число от 0 до k).
Так как c = d, то x = d^2 +- r; где d - число до корня (или +1), r - от (0 до d).
Так как корень от числа в два раза короче числа по битности,
то запись чисел d и r рядом, даст битность такую же как и у x,
плюс ещё один бит для знака (плюс-минус).
Профит же, должен бы быть в том, что при разных значениях x в разных блоках,
k и r могут повторяться не один раз, в разных блоках,
а это должно бы повышать сжимаемость данных после преобразования.
>>63189
Сделал скрипт на питоне, но немного с другим подходом.
Он считает единицы в битовом потоке, и как только их количество начинает расти - пишет стартовый оффсет в массив,
а как только начинает падать - пишет длину для негации.
Затем проводится негация, и добавляется дополнительный код в виде индексов и длин для негации, закодированных Гамма-кодом Элиаса.
Если кому интересно, могу скинуть скрипт по запросу, поколупаетесь,
но сейчас не дам - там много говнокода и комментариев нахуй не нужных, и лень вилкой их чистить.
Данные на выходе содержат мало единиц, но с гамма-кодом этим, дополнительным,
длина данных получается в два раза больше почти, для коротких битовых строк.
Как не химичь с информационной энтропией, пытаясь её занизить,
и как не пытайся представить ВСЕ числа короче,
но сжать всё множество всех случайных данных, с максимальной энтропией (несжимаемые данные)
- не получится никак.
Представь себе, что тебе удалось сжать данные с битностью n-бит, хотя-бы на один бит ("n-1" бит).
А теперь, сравни число всех возможных файлов длиной n бит,
с числом всех возможных файлов длиной "n-1" бит. Их будет - в два раза больше.
Обратное восстановление - порождает коллизию, которую можно разрешить, указав один бит.
Без него, двухбитное число 10 может быть развёрнуто в трёхбитное - двумя способами: 010 и 110,
и появляется многозначность. А вместе с ним, три бита сжать в два - нельзя.
И если писать рядом со сжатыми данными номер коллизии, для однозначного их восстановления по хэшу, и хэш,
то для разных хэш-функций, максимальное количество всех возможных коллизий может быть настолько велико,
что их число может быть выражено числом,
дополняющим данные до изначальной их битности.
А чё бы их тогда не расжать, а потом сжать?
Для представления достаточно больших блоков данных, в фибоначчиевой системе счисления,
из-за отсутствия комбинации 11 внутри этого представления,
преобразование Барроуза-Уиллера должно бы дать дохрена нулей на выходе преобразования,
и эти нули можно было бы пожать при помощи кодирования длин серий:
https://ru.wikipedia.org/wiki/Кодирование_длин_серий
И пофиг на длину данных, ведь данные в результате они были бы сжимаемы.
Вот тут, в главе 4 нашёл ещё один способ занизить энтропию данных (отношение количества единичных бит к количеству нулевых): http://ders.stml.net/cmpr/cpt/cpt.html#4
Даже когда все 4 комбинации 00, 01, 10, 11 повторяются с одной и той же частотой,
количество нулевых бит возрастает после этого преобразования.
И несмотря на то, что длина данных растёт, сами данные из-за этого становятся более сжимаемы.
Есть ещё моар подобных алгоритмов?
Можно было бы разбить данные на блоки по x-бит, например по 5 бит, а затем XOR'ить эти блоки на x-битные значения вида:
11111
01111
00111
00011
00001
11110
11100
11000
10000
00000
После этого, считать количество единичных бит результата,
и писать результат с наименьшим количеством единичек,
а также индекс поскоренного значения, а не само это значение.
Их не так много, среди 2^5, и если их, эти значения, предварительно положить в массив,
то их количество может быть ещё в два раза меньше,
так как половина из них это негации другой половины.
Зато, даже если данные будут несжимаемые,
количество единиц после XOR'а на 01111 или 11110 будет уменьшено на 1,
и после нескольких прогонов, эти данные могут стать сжимаемыми,
так как дохрена значений в них - могут повторятся.
Если, при помощи XOR,
различных рандомных значений,
на ограниченное число значений n-ной битности и их инверсий,
можно гарантированно снизить количество единичных бит,
в n-битном двоичном представлении,
любого произвольного натурального числа,
где бы не находились его биты,
то по причине реверсивности операции XOR,
можно будет и породить любое произвольное натуральное число n-ной битности,
за ограниченное количество шагов,
если записать эти значения последовательно, как цифры.
Только это не совсем цифры.
В двоичной системе, цифрами являются числа:
10000000
01000000
00100000
...
00000001
И биты в числе 01010101 - как-бы символизируют либо наличие, либо отсутствие этих цифр,
которые прибавляют по биту к числу:
01010101 = 0 x 1000000 + 1 x 01000000 + 0 x 00100000 + ... + 1 x 00000001
Только вот, исключая эти числа из рандомного числа, придётся указать их столько,
сколько единичных бит в числе, при этом, надо знать ещё и позицию бита.
А тут, одним махом, независимо от расположения бит, можно отнять - сразу по несколько единичек,
за одну операцию, получив нужное число из числа с минимальным количеством единичек:
01011101 (5 единичек, изначальное число) XOR 00011111 (подбирается перебором) =
01000010 (число-результат, 2 единички, минимальное количество единичных бит, низкая энтропия)
и наоборот - получить изначальное число, из числа с низкой энтропией и одной "цифры"- за одну опять-таки операцию:
01000010 (2 единички - предыдущее число-результат) XOR 00011111 (лишь одно из 8-ми битных чисел, подобных числам в предыдущем посте, цифра)
= 01011101 (5 единичек, изнаальное число).
Если эту хуйню хорошенько продумать, можно было бы её оптимизировать,
и сделать нечто вроде пиздатого Кубика-Рубика,
собираемого за минимальное количество шагов и операций.
Тогда и сверхсжатие рекурсивное было бы, и одновременно с этим - порождатель инфы заебатый.
Ну и конечно же, после всего этого, свёртку-развёртку инфы можно было бы и автоматизировать,
как тут: https://www.youtube.com/watch?v=nt00QzKuNVY&feature=emb_title
https://habr.com/ru/post/410945/
>за одну операцию, получив нужное число из числа с минимальным количеством единичек
получив нужное число с минимальным количеством единичек (сжимаемые данные), из изначального числа, хотел написать.
>>63437
>>63438
Попучкал, пучкал по гуглу Кубик-Рубика, и напучкал это:
>https://pikabu.ru/story/prosto_interesno_chislo_kombinatsiya_kubika_rubika_71745
>Число возможных различных состояний кубика Рубика равно (8! 38-1) (12! 212-1) 2 = 43 252 003 274 489 856 000,
>то есть более 43 квинтиллионов комбинаций.
>Несмотря на это, доказано, что из любого состояния кубик можно собрать не более чем за 20 ходов.
>Иными словами, так называемый «алгоритм Бога» будет давать решения не длиннее 20 ходов.
Так что, если цифрами писать ходы сборки конкретного состояния,
то одно из чисел от 0 до 43252003274489856000 будет записано не более чем 20-ю ходами-цифрами,
а наибольшее число - оно и так 20-ю цифрами записано, десятичными, и хуй сожмёшь его сильнее.
Для некоторых состояний-цифр, десятичная запись может быть даже короче, чем запись цифрами-ходами.
Хотя... Если в случае записи цифрами-ходами, в итоге будут выданы таки-сжимаемые данные,
то после сжатия их, возможно, запись будет короче, возможно намного, и возможно даже, можно будет применить - рекурсивное сжатие.
В любом случае, охуенно было бы иметь возможность породить произвольное натуральное n-битное число,
за количество шагов меньшее,
нежели добавление каждого бита, в нужной позиции - к его двоичному представлению.
И быть может, теория групп - в состоянии решить подобную задачу.
Каково для определённой заданной битности - минимально-возможное число чисел,
которые используясь как цифры, могли бы, в минимальной комбинации,
выдавать любое произвольное n-битное натуральное число для этой заданной битности?
То есть, каково число чисел, чтобы комбинация из них была именно минимальна
для каждого натурального числа, выражающегося комбинацией этих числел,
как и его десятичное и/или двоичное представление - комбинацией десятичых и/или двоичных цифр?
Ведь чем меньше цифр в записи числа, тем меньше и запись самого числа,
тем более, с учётом того, что и другие числа могут быть этими цифрами, если изменить операцию
из сложения на какой-нибудь XOR.
Можно было бы, каким-то алгоритмом, длинные бинарные палиндромы в двоичных данных выискивать,
и как нашли его - оставить в данных, половину палиндрома, приписать стартовый индекс его начала и индекс конца, или длину,
а другую половину палиндрома - не писать и вырезать с данных, потому что она повторяется.
При нахождени достаточно длинного палиндрома, в случайных данных, длина данных при таком кодировании,
упала бы сразу, на половину длины палиндрома этого.
Но это - не то. И интересно, а вот эта проблема уже решена?
https://en.wikipedia.org/wiki/Longest_repeated_substring_problem
Можно было бы в куче бинарного рандома найти длиннейший блок повторяющихся значений,
записать его один раз, а дальше - индексы. И вырезать нафиг все эти повторы,
и так вот - сжать данные, возможно даже - существенно.
А дальше уже - это дело зациклить. Индексы можно было бы писать кодом Эллиаса.
Развёртка данных была бы быстрее, нежели поиск длиннейшей повторящейся подстроки...
С Новым Годом!
Тут, скорее надо бы найти не длиннейшую повторяющуюся подстроку, а длиннейшую подстроку, частота повторов которой внутри данных - максимальна.
Например, в несжимаемых данных:
000110110000110111000110110000110111 (36 бит, ровно половина из которых, 18 бит - единичных)
этой подстрокой является подстрока 00011011
содержащая все возможные комбинации двухбитных значений:
00011011 0 00011011 1 00011011 0 00011011 1
А что если тупо, по какой-то формуле, нагенерировать список значений,
которые будут иметь разную информационную энтропию,
и которая будет плавно повышаться в этих значениях.
А потом поксорить входные данные на каждое из этих чисел - но с разными сдвигами,
и так до тех пор, пока не будет получен результат с минимальной энтропией.
Затем записать его, этот результат, номер числа в массиве, и сдвиг.
При длинных числах существенное снижение энтропии результата - даст кучу нулевых бит и даже байт в результате,
и этот результат можно будет пожать.
Снизить отношение количества единичных бит к количеству нулевых бит, можно было бы, просто заменяя один нулевой бит на два нулевых.
Но, тогда, ебически растёт размер данных.
Зато в результате, данные содержат много нулевых бит,
и повышается вероятность формирования ими большего числа нулевых байт.
Таким образом, количество нулевых байт в длинны данных растёт,
а значит повышается частота появления нулевого байта в потоке,
что должно бы делать данные сжимаемыми.
Но постойте... А что если эти сжимаемые данные, до сжатия их, пропустить ещё и через преобразование Барроуза-Уиллера?
Заебись же должно быть, не?
Короче, вываливаю годноту - рекурсивная компрессия случайных данных:
раз: https://www.researchgate.net/publication/325070038_A_Method_for_Recursive_Data_Compression
два: http://vixra.org/pdf/1807.0507v1.pdf
И ещё, изменение интерпретации типов данных, может способствовать свёртке всего натурального ряда,
при помощи аксиом Пеано,
а также развёртке любого натурального числа из множества натуральных, не только в режиме списков, но ещё и в поточном режиме:
https://anton-k.github.io/ru-haskell-book/book/12.html#натуральные-числа-1
Рекурсивная свёртка-развёртка данных. Всё просто.
Надо только закодить это. И чтобы понять всё это - гуглите определение N.
Заебало тут семёнить, запхнул свой опус в программач: https://2ch.hk/pr/res/1008826.html#1564379
Может там найдутся спецы, которые помогут закодить всё это кодирование кодировационное.
Хотя, постойте. Скопипащу-таки эту идею ITT, для истории, потомкам.
Может кто-нибудь из пучканов разовьет и оптимизирует всю эту шнягу, сведя её - в глобальный гипер-оптимум.
____________________________________________________________
Если данные - это файл, то я полагаю,
что стоит попытаться занизить информационную энтропию Шеннона, снизив количество инфы в файле,
а именно - для начала, подсчитать количество единичных битов в файле,
и если их больше 50% - то сделать негацию всего файла,
приписав один лишь бит дополнительных данных к изменённым двоичным данным файла.
То же самое, можно проделать и с блоками данных поменьше,
например в каждой половине файла подсчитать единички, и если больше 50% - негация,
в каждой четверти... И так далее... Тогда, соответсвенно +2 бита и +4 бита дополнительных данных.
С уменьшением блока - длина дополнительных данных растёт в геометрической прогрессии, и надо бы найти компромисс...
Наличие дополнительных данных требует указание их длины, и её можно указать - используя универсальный код, например - код Элиаса.
И самое главное - наличие этих дополнительных данных, в файле, оправдывалось бы тем,
что их мало, а длина блоков, подвергнутых негации - велика,
и если изначально, файл был несжимаемым
(зашифрованный файл, файл содержащий случайные данные),
и вероятность распределения всех байт была равномерной в нём,
то после негации блоков, содержащих много FE-FF-... байт,
частота их появления падает в ноль, и взамен - увеличивается частота повления байт 00-01-...,
которых было меньше в негируемом блоке, так как негация производится по условию наличия более 50% единичных бит.
Однако существуют реально несжимаемые данные, это данные с биномиальным распределением бит!
Их негацией уже никак не взять!
https://ru.wikipedia.org/wiki/Биномиальное_распределение
Вот так растёт их число: https://oeis.org/A210736
А вот полный список: https://oeis.org/A210736/b210736.txt
Это данные вида:
00110011
01011001
11000101
01101010
(по 4 единичных бита в каждом, из 8 бит в байте).
После негации они дадут снова 4 бита, превращаясь в такие же несжимаемые данные, но меняя свой старший бит.
Что с ними делать - хуй знает.
Но, первое, что приходит в глову, так это сделать одну хитрожопую операцию с ними:
либо XOR на 01111111 (для тех, где ноль - старший бит),
либо XOR на 10000000 (для тех, где единица - старший бит).
После этой операции, количество единиц в этих несжимаемых данных, должно гарантированно упасть на 1,
то есть с 4 до 3 единички, в случае с данными выше.
И вообще, так как несжимаемые данные переходят в такие же, после негации,
и так как 10000000 = NOT 01111111, то можно сделать и по-другому:
если старший бит 1 - NOT для данных, и XOR на 01111111, если несжимаемые.
иначе - XOR на 01111111, если несжимаемые,
так как ровно половину из этих несжимаемых данных, можно XOR-ить на 01111111, снижая гарантированно количество единиц на 1.
Если эту схему обобщить, на все возможные значения N-ной битности, из диапазона [0, (2^N)-1],
то можно сделать ещё проще:
1. Если старший бит 1 - сразу же негация, либо нет и пишем как есть + 1 бит дополнительных данных (1 - если негация, 0 - если нет).
2. Считаем единичные биты.
Если их ровно 50% в блоке данных чётной битности, то данные несжимаемы - сразу же XOR на 0111...1111,
уменьшение после этого количества единиц на одну единичку, и + ещё 1 бит со значением 1 - в дополнительных данных.
Если же единичных бит в блоке меньше 50%, то данные блока считаем сжимаемыми,
оставляем этот блок как он есть, и +1 бит со значением 0 - в дополнительные данные.
Возможно, можно было бы рекурсивно как-то занизить количество единичек в блоке данных, убирая их по одной,
но так, чтобы писать как можно меньше бит дополнительных данных.
Таким образом, преобразуя поблочно двоичный код файла, содержащего несжимаемые данные,
можно было бы снизить информационную энтропию Шеннона,
то есть снизить количество единиц и увеличить количество нулей,
снизить частоту встречаемости 1 среди этих нулей, как-бы - разрежая данные.
А дальше уже, так как по Шеннону, энтропия - это и есть информация,
то при низкой информационной энтропии,
голой инфы, в файле - содержалось бы меньше, остальное всё - это вода ёбанная, нолики, блядь,
а значит всю эту хуйню можно пожать каким-нибудь арифметическим кодированием,
кодом Хаффмана, архиватором Бабушкина с бенчмарком Дедушкина.
Но, в общем, хуй знает как это всё оптимизировать.
В рунете нихуя не нашёл, поэтому, на английском - пара ключевых слов,
для поиска более эффективных алгоритмов минимизации энтропии Шеннона:
https://www.google.com/search?q=shannon+entropy+minimization
https://www.google.com/search?q=shannon+entropy+oprimization
Как будет время, надо будет глянуть ещё, подробно - про квантовые диагональные матрицы:
>The Shannon entropy optimization problem can be viewed as a special case
>of the quantum entropy optimization problem with diagonal matrices.
>квантовые диагональные матрицы:
У тебя с английским хуёво или у тебя дизлексия? Что за испорченный телефон?
Я прочитал про квантовую энтропию, а дальше не читал, и подумал что раз ихний алго с квантами работает, то и матрицы квантовые.
>>63581
Можно, ещё, походу, как-то разделить множество данных с высокой энтропией -
на несколько множеств с энтропией низкой, но инверсной.
Пикрил - отсюда:
https://www.dataversity.net/from-a-single-decision-tree-to-a-random-forest/#
Но тогда, походу, длина данных будет расти вдвое. Но на пикчах - она не растёт.
Видно, что для одного из множеств - можно провести негацию, а потом склеить их и сразу же пожать обоих.
Подобные задачи, походу, решают - алгоритмы оптимальной негэнтропийной кластеризации данных,
и решают их при помощи нейросетей, обучая их - алгоритмами обучения без учителя:
http://neerc.ifmo.ru/wiki/index.php?title=Кластеризация
так как без нейросетевого параллелизма,
попытка достичь максимальной экстропии - порождением негэнтропийных процессов на машине Тьюринга,
за полиномиальное время - ресурсозатратна и временезатратна.
Ведь именно мозг позолил живым системам эволюционировать эффективно,
за счёт нейросетевого ускорения параллелизма когнитивных вычислений.
Годнота от Роджера Пенроуза, особенно вот тут: https://youtu.be/la1IHh_9r9M?t=2637
Цитата:
>У нас есть два типа сингулярностей, теперь. У нас имеется сингулярность в Большом Взрыве, и имеется сингулярность в чёрных дырах.
>В первоначальный период, когда люди беспокоились об этом, они говорили, ну, прошлое и будущее, более мнение одинаково,
>и имеется колоссальная, колоссальная разница, на самом деле.
>Она состоит в том, что Большой Взрыв, в некотором смысле - низкоэнтропийная сингулярность,
>сингулярность, с очень-очень низкой энтропией,
>в то время как сингулярности в чёрной дыре - это сингулярность с очень-очень высокой энтропией.
>...
Судя по этому тексту: https://ru.wikipedia.org/wiki/Исчезновение_информации_в_чёрной_дыре#Доклад_Стивена_Хокинга
речь о топологической сингулярности.
Сходу вопрос, как именно могут помочь топологии - сжать несжимаемые данные в парочку бит, снизив информационную энтропию?
Будет время - загугли всерьёз "Многомерное сжатие данных". Там что-то есть.
Сходу нашёл какое-то многомерное шкалирование и кластеризацию: https://ru.wikipedia.org/wiki/Многомерное_шкалирование
Может быть, это как-то поможет...
>Может быть, это как-то поможет...
Тут скорее таблетки помогут.
Быть может, любое натуральное число можно представить в виде суммы каких-то прогрессий,
которые можно было бы записать в виде более кратком,
нежели двоичное представление числа?
Я понел! Чтобы сжать данные - надо сделать так:
1. взять двоичное представление рандомного числа.
2. Заменить один нолевой бит на два нулевых, получив тем самым - более длинный кусок двоичных данных,
но с меньшим количеством единиц по отношению к нулям (более низкая энтропия).
3. Затем пропустить эту хуету через преобразование Барроуза-Уилера.
4. Сжать эту фигню, нахуй.
Обратное преобразование - реверсивнейшим образом обратимо.
Вообще-то это сжатие с потерями.
Алгоритм под названием Taco, ускоряющий обработку больших данных в 100 раз,
автоматизирует компрессию тензорных разрежённых матриц:
http://tensor-compiler.org/taco-tools.pdf
>преобразование Барроуза-Уилера
Есть какие-либо аналоги у этого алгоритма, которые ещё охуеннее сортируют?
Пишут, что это целый класс алгоритмов, под названием "блочно-сортирующее сжатие",
но поиск выдаёт только этот алгоритм - BWT.
Может ли он быть многомерным, например для сортировки матриц двумерных матриц?
Представляю себе что-то воде кубика на пикрил >>63437, где каждая грань - это двумерная ёба-тензорная матрица.
>Представляю себе что-то воде кубика на пикрил >>63437
Не, ещё пижже - многомерный гиперкубик-гиперрубика. Пикрелейтед.
>двумерная ёба-тензорная матрица
Многомерная сверхтензорная ёба-матрица.
Хотелось бы предложить, в качестве метода снижения энтропии - следующий алгоритм:
Берём и принимаем на вход - исходную битовую строку,
читаем её побитово,
и пишем вторую строку - выходную:
если бит исходной строки изменился, то бит выходной - 1,
иначе, если не изменился то 0.
На выходе - образуется другая бинарная строка.
Преобразование может быть поточным.
Обратное восстановление исходной стрки - обратно: если на входе бит 1, то бит изменился, иначе - не изменился, и вписать предыдущий.
В результате экспериментов, удалось выявить следующую закономерность:
последовательность вышеописанных преобразований (выходная строка преобразуется ещё раз в выход2, выход2 в выход3, и т. д.) -
эта последовательность зацикливается, выдавая изначальную двоичную строку
- за количество шагов, равное 2^x-1, где x - некое число.
При этом, в списке значений, образуются данные либо с наибольшим,
либо с наименьшим количеством единичных бит, а значит изменяется информационная энтропия.
Дальше уже, эти данные можно подвергнуть негации,
их можно пропустить через преобразование Барроуза-Уиллера, чтобы повысить сжимаемость их,
и конечно же - пожать префиксным кодированием.
Маняматик, смотри что я напистонил! https://rextester.com/WRGJ65269
Есть идея сжать данные так:
1. Берём блок данных, пусть это будет двоичная строка: 1101101010010100010001
Считаем количество единичных бит: 10
Делим это число (10 бит) на длину двоичных данных (22 бита): 10 / 22 = 0.4545454545...
Если результат больше 0.5 - негация и + бит 1,
иначе оставить как есть и + бит 0 (этот случай).
Результат: 01101101010010100010001 (23 бита)
Таким образом, для блока данных в N бит,
количество значений уменьшается до 2^(N-1),
часть из которых представляет из себя несжимаемые данные
(значения, с биномиальным распределением бит, единичных бит в которых ровно 50%).
Этих данных - ровно половина из диапазона 2^N.
Остальные возможные значения содержат меньшее число бит.
2. Нумеруем позиции бит по порядку:
01101101010010100010001
01234567890123456789012 - индекс
0`````````1`````````2`` - второй разряд, чтобы вместить индексы - в одну цифру
3. Пишем позиции единичных бит:
1 2 4 5 7 9 12 14 18 22 - значения растут
4. Двигаем указатель на +1 от текущей позиции, и пишем расстояние к следующему биту:
1 0 1 0 1 1 2 1 3 3 - расстояние от последней позиции +1 до следующего единичного бита - это количество нулей до следующей единицы.
Как видим, вторая последовательность содержит более повторяющиеся значения.
Максимальное значение - 3, три нуля максимум, между единицами.
5. Считаем количество повторов:
0 - 2
1 - 5
2 - 1
3 - 2
6. Сортируем по количеству повторов:
1 - 5
0 - 2
3 - 2
2 - 1
7. Формируем префиксный код:
1 - 0
0 - 10
3 - 110
2 - 111
8. Кодируем последовательность с шага 4 префиксным кодом:
0 10 0 10 0 0 111 0 110 110
В одну строк всё это:
010010001110110110 - 18 бит.
изначальная строка:
01101101010010100010001 - 23 бита.
Сжатие 5 бит получилось.
Для длинных двоичных строк должно бы прокатить, даже если прицепить к сжатым данным, в виде избыточной инфы - таблицу с префиксным кодом.
Упор сдесь делается на то, что в данных из пункта 4: [1 0 1 0 1 1 2 1 3 3]
должно бы быть много одинаковых повторов,
даже для несжимаемых данных - данных с биномиальным распределением бит.
Иначе, чем меньше бит, тем меньше единичных бит, тем короче эта последовательность,
тем меньше вариантов чисел в этой последовательности,
и тем более коротким префиксным кодом можно закодировать эти варианты.
>Иначе, чем меньше бит
Тут немного по другому хотел написать:
>Иначе, чем меньше энтропия, и чем меньше частота встречаемости единичного бита, тем...
1. Количество чисел на шаге 4 - равно количеству единичных бит, и наличие шага 1 - уменьшает это количество.
2. Префиксный код можно формировать так, по убыванию количества повторов чисел в массиве на шаге 4:
0 (самое часто-повторяющееся число)
10
110
1110
...
11111...10
11111...110
11111...1110
11111...11110
11111...11111 (самое редко-повторяющееся число)
При этом невъебенно большое, но редко-повторяющееся количество нулей, скажем 100 нулей подряд,
может иметь код 1111111110 (10 бит всего), 10 бит, а не 100 бит.
Сжатие - 1000%, нахой!
3. Наконец, можно применить схему отсюда: https://libraryofbabel.info/bookmark.cgi?ehtkdtq96
То есть либо писать сжатые данные с битом 1, либо писать несжимаемые данные как они были - с битом 0 (если сжатие не удалось).
>>63945
Анон, а можно ли реализовать lossless compression (сжатие без потерь),
при помощи lossy compression (сжатие с потерями),
то есть просто обнуляя по пару бит в определённых местах,
чтобы повысить сжимаемость данных,
а потом восстанавливая эти биты - корректирующими кодами, которые используются для помехоустойчивости:
https://ru.wikipedia.org/wiki/Обнаружение_и_исправление_ошибок
Есть, например данные вида: 00000000 00100000 00000100
один бит обнулили: 00000000 00000000 00000100 - два повторяющихся байта 00 00 04 - получили,
сжимаемость повысили, сжали и так - до бесконечности.
>>64284
Немного разовью єту идею.
Префиксный код формируется так:
0 (наибольшая частота повторов чисел в массиве)
10
110
1110
11110
11111 (наименьшая частота повторов чисел в массиве)
А что, если вместо нуля - гамма-код эллиаса для единиц прописать?
Ведь когда в массиве [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3]
много нулей подряд, (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
это значит что там нет нулей, между единицами и идут сплошные единицы, подряд: 111111111111
Массив этот - образуется из значения: 1111111111110111110001 (если его биты не инвертировать),
и в точности отражает количество нулей, перед следующей единицей.
Если использовать гамма-код Элиаса, то эти нули, можно записать не так:
000000000000 (12 бит)
а так
00001100 (8 бит)
Очевидно, что в значении с малым количеством единиц,
могут быть большие расстояния между ними, в виде нулей.
Их количества будут велики.
Вероятность нахождения же большого числа единиц рядом - мала.
Но всё-же. Их может быть много по две. По три, по пять, по десять.
Тем не менее, можно было бы делать переключения префиксный код, замкнуты на ноль, исключив при этом - сам ноль.
01 - ноль и следующий префиксный код.
001 - по одному нулю дальше, до единицы.
0001 - дальше - следует код Элиаса, обозначающий количество нулей.
00001 - код Элиаса, для повтора предыдущего кода.
Например, один ноль.
0 != 0 = 01
00 != 00 = 0010
0000000000000000000000000 != 0000000000000000000000000 = 00010000011001
2222222 != 11111111111111 = 1100001000101
11 выбрано для префиксного кода (0 - 0, 1 - 10, 2 - 11)
>Тем не менее, можно было бы делать переключения через префиксный код, замкнутый на ноль, исключив при этом - сам ноль.
Залил этот код - сюда: https://github.com/username1565/incompressible_data
и прицепил теги.
Быть может, сообщество погроммистов с github, глядя на это вот всё,
начнут разработку более эффективных алгоритмов,
снижающих информационную энтропию Шеннона у несжимаемых данных,
чтобы повысить их сжимаемость и дожать потом их.
Также, можно было бы эту задачу выставить для студентов вузов,
на олимпиаду по математике, инорматике, программированию, и так далее...
>>64273
>>64284
>>64296
Алсо, оставлю здесь этот вот код: https://rextester.com/XSMSF58499
Кто хочет, и у кого есть время, чисто по фану - можете поиграться с ним.
Гарантированно уменьшить количество единичных бит на 1,
в любом двоичном значении (кроме 0),
может операция
>x &= x-1; #removes a 1 in a bit string.
При этом, удаляется один ближайший бит, справа.
Например:
> 10100
>& 10011
>= 10000
Конечно, эта операция эта - необратима, потому что где имеенно удалился этот бит - хрен поймёшь.
Но корректирующие коды для помехоустойчивости - должны бы распознать и восстановить этот бит.
Ты всегда берешь первый элемент фиксированным? Тогда пусть первый всегда 1:
11 00 10 01 10 01 - вот она зациклилась и не вернёт мне 11
Что я делаю не так?
Ну и в любом случае без оценки х от длины последовательности, даже если все, что ты написал, правда, пользы считай нет. Если размер одной группы 2^х, то тебе надо передать число от нуля до 2^х-1, т.к. ты не знаешь, какое число из группы тебе нужно.
По сути это анонимно тому, чтобы разбить числа на какие-то группы, и передавать их как сумму базы и номера в группе. Скажем как передать число 987654321 как 900000000 и 87654321, потому что 900000000 хорошо сжимается. В твоём варианте к тому же не факт что группы будут сжиматься одинаково хороши, о значит если в одной группе больше элементов, чем в другой, то ей понадобится лишний разряд для записи порядкового номера элемента в группе
>Ты всегда берешь первый элемент фиксированным?
Да. Это бит со значением "0". Вот же код, тут: >>64071
>Тогда пусть первый всегда 1:
>11 00 10 01 10 01 - вот она зациклилась и не вернёт мне 11
>Что я делаю не так?
Ты про зацикливание последовательности изменения первых двух бит что-ли?
Не пойму где ты там группы увидел...
Со стартовым битом 0, оно первые два бита зацикливаются как-то так:
>11 10 11 10 11 10, и никаких выебонов.
>Ну и в любом случае без оценки х от длины последовательности,
>даже если все, что ты написал, правда, пользы считай нет.
Я увидел пользу этого простого преобразования в следующих двух свойствах:
1. Оно реверсивно и его можно обратить, получив на выходе изначальное значение,
по строке результату, числу, которое не так уж и велико (из-за зацикливания).
2. Это преобразование ИЗМЕНЯЕТ количество единичных бит,
а значит изменяет информационную энтропию Шеннона.
Это значит, что в результате подсчёта бит,
среди множества значений, последовательных преобразований этих,
можно выбрать значение с минимальным количеством единичных бит,
или же - инвертированное значение с максимальным количеством единиц,
а после дополнительного пропускания через преобразование Барроуза-Уиллера,
оно должно будет содержать дофига нулевых бит, подряд идущих,
частота повторов которых будет выше,
а значит эти данные, с более низкой энтропией будут более сжимаемы,
так как эти образовавшиеся, подряд идущие нулевые биты,
их можно сжать при помощи методов энтропийного кодирования,
тем же префиксным кодом - кодом Хаффмана,
или применив то же арифметическое кодирование
(эффективность которого зависит от энтропии данных).
>Если размер одной группы 2^х, то тебе надо передать число от нуля до 2^х-1, т.к. ты не знаешь, какое число из группы тебе нужно.
>По сути это анонимно тому, чтобы разбить числа на какие-то группы, и передавать их как сумму базы и номера в группе.
>Скажем как передать число 987654321 как 900000000 и 87654321, потому что 900000000 хорошо сжимается.
>В твоём варианте к тому же не факт что группы будут сжиматься одинаково хороши,
>о значит если в одной группе больше элементов, чем в другой, то ей понадобится лишний разряд для записи порядкового номера элемента в группе
На самом деле, ТАМ НАМНОГО КОРОЧЕ размер цикла, если стартовым значением взять нулевой бит.
Как видишь, каждый раз, 32-битное значение, выдаёт себя же, через 31 шаг.
>i = 31 True
>строка 124
Возьми код тот, поменяй значения на свои, внутри него (строка 98),
и перезапусти его пару раз, в общем поиграйся, и поймёшь.
Может даже новые закономерности увидишь какие-нить.
>Ты всегда берешь первый элемент фиксированным? Тогда пусть первый всегда 1:
>11 00 10 01 10 01 - вот она зациклилась и не вернёт мне 11
Вообще-то так:
>11 00 10 01 11 ... - вот она зациклилась и вернула снова 11.
В коде https://rextester.com/WRGJ65269
стартовый бит ты можешь изменить в строке 59, и посмотреть на результат - самостоятельно.
>>64440
Да, что-то я ночью невнимательно посчитал, есть цикл
Насчёт групп, я не в смысле как группа в алгебре, хотя при желании можно определить и как группу в алгебре, получится примерно то же, что и сложение по модулю.
Вот у тебя есть начальная последовательность. Через какое-то количество N повторений операции она повторяется. Значит, есть N уникальных строк, которые оно подходит в этом цикле. Очевидно, эти циклы разобьют все строки на несколько непересекающихся множеств. Если цикл содержит все возможные подстроки, то это сразу значит, что данное преобразование не несёт никакой пользы для сжатия. Если таких групп несколько, то тут уже сложнее, но как я писал выше, это аналогично просто выделению целых тысяч. Вместо тысяч можно взять любое другое представление, хоть по степеням двойки как 2^k + m.
Я просто не вижу, за счёт чего ты тут предлагаешь что-то убрать и где выигрываешь в количестве передаваемых символов
>Если цикл содержит все возможные подстроки, то это сразу значит, что данное преобразование не несёт никакой пользы для сжатия.
Как я уже написал здесь: >>64070
>В результате экспериментов, удалось выявить следующую закономерность:
>последовательность вышеописанных преобразований (выходная строка преобразуется ещё раз в выход2, выход2 в выход3, и т. д.) -
>эта последовательность зацикливается, выдавая изначальную двоичную строку
>- за количество шагов, равное 2^x-1, где x - некое число.
То есть, цикл намного короче ВСЕХ ВОЗМОЖНЫХ ПОДСТРОК.
Это же очевидно и из результата исполнения того кода: https://rextester.com/WRGJ65269
>i = 31 True
для 4-х байтного числа (8 бит/байт x 4 байта = 32 бита)
То есть цикл замыкается не через 2^32 ВСЕХ ВОЗМОЖНЫХ ЗНАЧЕНИЙ, а лишь через 31 значение, в том числе и нулевое,
а это - 32 значений максимум (если брать стартовым битом - бит 0),
или же 64 значения максимум (если брать стартовым битом - бит 1).
Для всех ли чисел это так - не знаю, надо протестить, и судя по всему - для всех.
Для 16-ти байт (2^(16x8) значений!) , цикл замыкается уже через 127 преобразований (тоже небольшое число)
Количество байт сгенерированных, можешь в строке 98 отрегулировать,
или же сделай нечто вроде:
>import math;
>number_of_bits = 32
>x = (bin(random.randrange(0, math.pow(2, number_of_bits)))[2::]).zfill(number_of_bits);
>print("x", x);
чтобы генерировать значения с нужным количеством бит, длина которых определена побитово.
>Я просто не вижу, за счёт чего ты тут предлагаешь что-то убрать и где выигрываешь в количестве передаваемых символов
Я вкинул этот алгоритм и код как демонстрацию способа снижения энтропии информационной,
для повышения сжимаемости данных, то есть просто как пример.
Возможно, математики распознают закономерность какую-то, и подберут какие-то теоремы доказанные,
а потом - запилят более охуенные и эффективные алго, для этой задачи, нежели этот примитивный код.
Поэтому, я его не доводил до рабочей системы, да и лень как-то.
А так-то, если именно на нём базировать сжатие,
то:
1. Берём блок двоичных данных, какое-то значение - от 0 до 2^32-1
2. пропускаем через алго.
3. Берём строку с наименьшим количеством единиц (или строку с наибольшим количеством единиц, которую подвеграем негации, и получаем строку с ещё меньшим количеством единиц).
4. Приписываем дополнительные данные для восстановления (число от 0 до 31).
5. Пропускаем строку с малым количеством нулей - через преобразование Барроуза-Уилера
(тем самым упорядочивая нули, и повышая частоту встречаемости двух нулей).
6. Жмём результат - префиксным кодом, кодом Хаффмана, как тут: >>64331
7. Возможно в несколько раундов, так как методы энтропийного кодирования - повышают информационную энтропию,
в то время как этот алго, по идее, её понижает.
Но с закинутым мною алгоритмом, сжимаемость будет не велика,
так как, тыкая код этот, ты сам можешь убедиться в том,
что при больших и длинных значениях двоичных данных,
падение количества единиц от этого преобразования - не особо существенно.
Где-то видел сжатие - алгоритмом формирования моделей бозонных и фермионных конденсатов, при гравитационном коллапсе чёрных дыр.
Почти годик сему треду про сжатие несжимаемых данных. Бампану-ка его.
Судя по всему, не существует годных алгоритмов, для сжатия несжимаемых данных,
потому что к существенным успехам и прорывам, я так и не пришёл, в этом нелёгком деле.
ОП
Не прошло и года. Лучше б ты сразу нам поверил и этот год на изучение чего полезного потратил.
Например чего? Я вот крипту решил изучить, в параллель, пока всё не спиздили там.
Слышал, что различные модели данных, ну там иерархическая модель, сетевая модель - можно сконвертить в реляционную модель данных, а потом провести её нормализацию. Хуй знает, возможно нормализация каким-то образом оптимизирует структуру данных чтобы они не дублировались например.
Если да, то, наверняка, можно представить произвольные двоичные данные - в виде базы данных, задать отношения, а затем нормализовать, и таким образом сжать.
Хуй знает, можно ли сжать таким образом АБСОЛЮТНО ЛЮБЫЕ НЕСЖИМАЕМЫЕ ДАННЫЕ,
но возможно да,
в том плане что можно добавить лишь один бит к ним,
в котором обозначить сжаты были ли они сжаты, или прописаны "как есть", потому что сжатие дало данные более ебической длины.
Итак, на данный момент,
основным вектором развития
алгоритмов сжатия несжимаемых данных,
является поиск алгоритмов,
снижающих максимальную информационную энтропию несжимаемых данных,
в частности биномиальное распределение бит этих данных,
а именно,
алгоритмов,
способных изменить соотношение 50:50 для единичных бит к нулевым,
в этих вот несжимаемых данных,
коих, на деле - подавляющее большинство,
из всей битовой последовательновательности,
всех возможных комбинаций бит, заданной длины.
Мне эту хуйню сложно объяснить одним постом, и проще наверное, нарисовать,
но если кто либо из вас вникнет, или уже вникнули в это,
то знайте, что найдя алгоритм,
который сможет сдвинуть это вот соотношение,
в распределении единиц и нулей,
в сторону либо увеличения, либо уменьшения
(на деле не имеет значения, ведь в конце концов, есть инверсия бит - негация),
тогда,
вы сможете сжать НЕСЖИМАЕМЫЕ НИКЕМ, НАХУЙ, ДАННЫЕ, вы станете СЖИМАТЕЛЯМИ ДАННЫХ НЕСЖИМАЕМЫХ, которые никто не может СЖАТЬ, А ВЫ МОЖЕТЕ, вы будете сжимать всё, нахуй, всё, абсолютно всё,
и хранить
ебические тонны и зеттабайты прона
на подобной,
маллллллллюсенькой MicroSD (пикрелейтед).
У меня другой фирмы карточка памяти, от ScanDisk.
Я хотел бы уместить хотя-бы 1 зеттабайт в неё,
но я не знаю как.
Мне кажется, лучше, использовать ДНК-флешки,
но всё-же, я не побрезгую, и не буду гнушаться зашквариться, об этот стародревний тред,
являющийся для меня, прогрессивного человека 21-го века, ничем иным как бесполезным говном мамонта.
Посему, я добавлю, чисто от себя, что было бы лучше, наверное (ведь я не уверен высокоточно), было бы лучше использовать, в качестве алгоритмов, снижающих энтропию биномиального распределения бит внутри несжимаемых данных, использовать алгоритмы самоорганизации, способные организовывать энтропию на принципах экстропианства, то есть используя экстропианские программы, применительно к двоичным данным, являющимся отождествлением основ бинарного кода всея бионейрохемоинформатики.
Ну... Давай так... Всю эту хуйню можно смоделировать? Можно.
А математическая модель разве не абстрактна, и не описывается математическими законами? То-то же...
ведь 100 можно записать как
0110 0100 в двоичной
100 в десятичной
64 в 16-ричной записи
вот наглядно видно как уменьшается место в которое можно записать число 100
То есть всегда можно придумать символ в который можно записать большее число, и где-то будет хранится таблица символов, куда алгоритм будет лезть для расшифровки
Любое целое, большее 0.
>>78828
Так а толку от этого?
Если в 10-ти ричной, ты хранишь по 10 состояний на разряд, и три цифры,
то в 16-ричной, уже по 16 состояний на разряд, хоть и две цифры,
в двоичной же - 2 состояния на разряд, и 8 цифр.
Три разряда в десятичном числе (103 = 1000 - включая 0, то есть - максимум 999),
два разряда в 16-ричном числе (162 = 256, включая 0, то есть максимум FF)
и 8 разрядов в 2-чном числе (2^8 = 256, включая 0, то есть 11111111), суть одно и то же, ведь инфы меньше не стало,
число как было 100, так и находится в пределах от 0 до 256, а то и до 1000, как его не запиши.
Если число больше 256, очевидно, то для 16-ти ричной и 2-чной записи, число разрядов прибавится, а для 10-чной нет,
но пофигу, ведь число от этого не уменьшается.
Я же, думаю над тем, как рассмотреть пиздатую шестнадцатиричну последовательность, в качестве числа,
с последующим его разложением или уменьшением так,
чтобы его МОЖНО БЫЛО ВОССТАНОВИТЬ, а в крайнем случае ПОДОБРАТЬ БРУТФОРСОМ, используя вычислительные мощности.
Тогда, можно было бы записать хэши, или контрольные суммы, или ещё чо, и дальше уже сбрутить секторы-кластеры целые, пиздатые, похуй когда, со временем, но главное чтобы не хранить это говно, а сбрутить потом уже, когда-нибудь, когда надо будет, через год скажем.
>Я же, думаю над тем, как рассмотреть пиздатую шестнадцатиричную последовательность, в качестве числа,
>с последующим его разложением или уменьшением так,
>чтобы его МОЖНО БЫЛО ВОССТАНОВИТЬ,
>а в крайнем случае ПОДОБРАТЬ БРУТФОРСОМ, используя вычислительные мощности.
Сначала, чё-то взбрело в голову, тупо нарезать данные на блоки, ограниченной длины,
и вычислять из них хэши, каким-нибудь алгоритмом хэширования.
Тогда, любой блок данных, можно запхнуть в хэш-таблицу, читай в JSON-объект,
где эти данные будут доступны по хэшу, как по ключу.
Но что если эти данные могут быть потеряны, а хэши останутся?
Тогда, их, наверное, можно было бы, тупо - сбрутфорсить.
И из-за ограниченной длины данных, количество комбинаций брутфорса было бы снижено.
Но в памяти всплывают сразу же коллизии к хэшам...
И если взять пример с CRC-32 суммами контрольными, то схема сразу же идёт по пизде.
Потому что, вот что: https://ru.wikipedia.org/wiki/Сжатие_без_потерь#Сжатие_и_комбинаторика
>Легко доказывается теорема.
>Для любого N > 0 нет алгоритма сжатия без потерь, который:
>Любой файл длиной не более N байт или оставляет той же длины, или уменьшает.
>Уменьшает некоторый файл длиной не более N хотя бы на один байт.
То есть, результат применения такого алгоритма (читай к хэшу, как к результату применения хэш-функции),
может выдавать данные (хэш), которые могут быть развёрнуты в исходные данные, МНОГОЗНАЧНО
(да-да, есть коллизии хэш функции).
И некоторые данные, определённый алгоритм сжатия, может уменьшить, а вот некоторые данные - может и УВЕЛИЧИТЬ.
Поэтому, чуток ниже, есть приписочка:
>Впрочем, данная теорема нисколько не бросает тень на сжатие без потерь.
>Дело в том, что любой алгоритм сжатия можно модифицировать так,
>чтобы он увеличивал размер не более чем на 1 бит:
>если алгоритм уменьшил файл, пишем «1», потом сжатую последовательность, если увеличил — пишем «0», затем исходную.
Если же результатом применения такого алгоритма сжатия, будет ХЭШ, ограниченной длины,
то хэш этот может иметь, две, три, пять, сто пять коллизий, в пределе определённого блока данных.
А это значит, что при попытке развёртки данных, при брутфорсе этих данных из имеющегося хэша,
можно получить, внезапно, ДРУГИЕ ДАННЫЕ, которые могут иметь такой же хэш.
Возможно они могут быть более длинными, нежели исходные данные,
и тогда, в этом случае, имело бы смысл, указать ДЛИНУ исходных данных, вместе с хэшем,
для однозначного нахождения исходных данных, по хэшу, без коллизий,
а также имело бы смысл РАЗРАБОТАТЬ алгоритмы хэширования,
позволяющие хэшировать ОДНОЗНАЧНО, данные определённой длины в хэш (блять, а так разве возможно?),
так, чтобы, путь даже и приложив вычислительные мощности,
зная хэш и длину, опять же, ОДНОЗНАЧНО - восстановить данные из более короткой их записи (хэш+ДлинаДанных).
Всё это кажется абсурдны, но мне чё-то кажется, что данные, несжимаемые данные,
можно таки сжать, если каким-то алго, можно было бы,
сдвинуть их биномиальное распределение бит 50%/50% в какую-либо сторону,
скажем 80% нулевых бит к 20-ти % единичных, а потом сжать нули,
и приписать ещё один бит,
мол сырые ли это данные (0), или же данные, которые следует конвертнуть назад, через алго (1).
Натуральные числа - мощности конечных множеств.
Пустое множество - конечное.
0 является натуральным числом.
Немного не по теме, но интересно.
Ты дал кратчайшее определение, через мощность множеств,
но моё определение по-моему более краткое, и может быть модифицировано, включая ноль.
Погуглил на тему нуля немного, и нашёл кучу срачей.
Например:
>ноль не является натуральным, потому что это не природное число, ноль конфет нельзя съесть, а одну конфету - можно.
>номера домов не начинаются с нуля, потому что первый дом - имеет номер 1, и нет нулевого дома. Ноль - означает отсутствие дома, это не натурально, и не природно (nature).
И тому подобное...
https://ru.wikipedia.org/wiki/Натуральное_число#Место_нуля
Здесь, расписано о двух определениях ряда натуральных чисел, один из которых включает в себя ноль.
Мне кажется, что чтобы разобраться в том, является ли число ноль - числом натуральным,
надо взять ВСЕ СВОЙСТВА НАТУРАЛЬНЫХ ЧИСЕЛ:
https://scienceland.info/algebra8/natural-number
и проверить, не нарушаются ли они, если включить в них ноль?
Например, если взять такое вот,
простое и краткое определение целых чисел:
"целые числа - это натуральные, а также натуральные - со знаком минус..."
И 0 если включить в натуральные, то соответствующее ему число со знаком минус, будет -0,
что уже как-бы не совсем то, ведь это два числа, которые равны.
Надо посмотреть, не нарушаются ли другие, более фундаментальные свойства и определения, не только натуральных чисел, но и чисел связанных с натуральными,
если включить ноль в натуральные, и если его не включать.
Ну и, наконец, следовало бы дать чёткое и однозначно определение, безо всех этих вот, расхождений.
Также, ноль, число особенное, на него делить нельзя.
И ещё... Мне кажется, что ряд натуральных чисел, начинается с 1, просто потому что этот ряд можно представить группой, в которой порождающий элемент 1, а любое следующее - есть прибавление 1 к предыдущему.
0, как порождающий элемент, уже не канает,
потому что сколько не прибавляй 0 к 0, будет 0,
а даже если к другому числу прибавить 0, будет оно же, и группа не будет порождаться.
Короче, какой-то сдвиг во свойствах начинается, если включить 0, и если это не какие-то фундаментальные сфойства, которые расхуячат всю арифметику и алгебру, и математику, и матан,
то 0 можно включить, банальной коррекцией определений,
безо всяких расхождений, неоднозначных.
>надо взять ВСЕ СВОЙСТВА НАТУРАЛЬНЫХ ЧИСЕЛ:
Полностью описаны аксиомами Пеано.
Аксиомы Пеано допускают использование в качестве стартового элемента как 1, так и 0. Следовательно, спор о том, натурален ли 0, не имеет смысла.
Аксиомы Пеано можно "начинать" и из $\sqrt{2}$, если хочется, это не аргумент
мимо проходил
Тогда аргумент в том, что функцию Пеано можно применять к начальному элементу ноль раз.
Аксиомы Пеано не имеют смысла т.к. не являются определением.
>Аксиомы Пеано не имеют смысла т.к. не являются определением.
Так это ты утверждал что дал определение, тебе и доказывать.
https://www.youtube.com/watch?v=M3vzrrPIhVg
>для хентая
Не совсем понятно, к чему это здесь.
Ты чё хентай сжимать хочешь, а он несжимаем?
Задача о сжатии несжимаемых данных,
то есть данных, в которых,
вероятность встречаемости различных бит,
подвержена биномиальному распределению
(50% единиц и 50% нулей, находящихся хуй знает где),
эта задача сводится к выработке,
некоего универсального алгоритма,
который снизил бы, вероятность распределения,
этих ебучих обконченных обмудошных и дебилистических бит.
Ясен хуй, что если в данных 51% единиц и 49% нулей,
то можно сделать просто негацию всего этого порноархива,
получить на выходе 49% единиц и 51% нулей,
и затем пожать нули, и архив станет меньше.
А вот когда 50% единиц и 50% нулей - тогда уже негация не проканает, блядь. Оттогои прон несжимаемый.
А если это зеттабайт прона, что тогда, блядь? Датацентр свой заводить, и машинами пиздатыми прон возить, блядь?
То-то же. Давайте выдумывайте ёба-алго этот.
Хуле вы тут годами сидите и нихуя не делаете, а?
Только пучкаете и никакого прогресса.
Прон сам по себе не сожмётся, от вашего пучканья.
Чё делать с этими ебучими несжимаемыми данными, блядь?
Существует ли какая-либо закономерность их появления?
Судя по распределению их - хуй проссышь где они есть, а где их нет.
Может можно как-то, каким-то универсальным образом, сдвинуть число, чтобы из несжимаемых данных получились сжимаемые?
Или как-то биты поменять, а потом взять и спресовать.
Или поксорить на что-то вроде 1010101010101010 ?
Чтобы гарантированно сместить число единиц и нулей, в несжимаемых данных?
Не, хуй. Ксор их тоже не берёт. Вот блядище-то какое, ты смотри.
Я пытался найти эту последовательность в OEIS, но так и не нашёл.
Похоже, что я открыл нечто новое, что требовалось бы исследовать.
Исследовать, как при помощи вычислительных мощностей (тупо пробрутить, скажем, до дохуллиона, с хуем значений),
так и исследовать, при помощи специалистов,
пытаясь распознать закономерности,
и пытаясь найти способы преобразования этих значений,
в какие-нибудь другие, сворачиваемые ряды.
Итак, представляю вашему вниманию, эту последовательность.
Она имеет следующий вид:
>1, 2, 3, 5, 6, 9, 10, 12, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120, 135, 139, 141, 142, 147, 149, 150, 153, 154, 156, 163, 165, 166, 169, 170, 172, 177, 178, 180, 184, 195, 197, 198, 201, 202, 204, 209, 210, 212, 216, 225, 226, 228, 232, 240, ...
и она была сгенерирована этим кодом на JavaScript:
>//count number of 1-bits, and 0-bits.
>function count10(str){
> var _1 = _0 = 0;
> for(var i=0; i<str.length; i++){
> if(str==='1'){_1++;}else{_0++;}
> }
> return [_1, _0];
>}
>
>var s = '';
>for(var len=0; len<=8; len++){
> for(var val=0; val<Math.pow(2, len); val++){
> var value = val.toString(2).padStart(len, '0');
> var OnesAndNulls = count10(value);
> console.log('val', val, 'value', value, 'count10(value): '+count10(value));
> if(OnesAndNulls[0] === OnesAndNulls[1]){
> s+=val.toString()+', ';
> }
> }
>}
>console.log(s);
Как можно видеть, это числа, у которых число единичных бит, равно числу нулевых бит.
То есть числа, которые являют собой несжимаемые данные.
Негация этих чисел - даёт такж несжимаемые данные, с тем же числом единиц и нулей.
Первое, что взбрело в голову, это выставить len<=16, вместо 8, и получив 17576 чисел на выходе,
сунуть их в массив, сделав доступными по индексам, являющимся номером по порядку.
Как-бы полагая, индексы, идущие по порядку, будут являть собой, в большинстве своём - сжимаемые данные,
в которые можно биективно преобразовать эти вот, несжимаемые данные,
а потом сжать уже сжимаемые данные, которые должны сжаться.
Похуй на то, что где-то единиц больше чем нулей, а где-то меньше чем нулей,
негация может свести это дело к меньшему числу единиц, и большему числу нулей,
с возможностью сжать потом нули.
Вводя в гуголь последовательность, я вижу какие-то другие последовательности, с похожими числами.
Воможно, эту последовательность можно свести к ним. А быть может она и уникальна.
Подумайте, что можно сделать с этой хуйнёй,
ведь прон сам по себе не сожмётся, если будете сидеть и пучкать попусту, блядь.
>if(str==='1'){_1++;}else{_0++;}
->
>if(str==='1'){_1++;}else{_0++;}
вот так.
эстиар + left square bracket + i + right square bracket три равно и дальше тот же говнокод, сукаблядь.
Что с этими ебучими скобками делает эта вакаба, ты только посмотри.
>if(str==='1'){_1++;}else{_0++;}
->
>if(str==='1'){_1++;}else{_0++;}
>Как можно видеть, это числа, у которых число единичных бит, равно числу нулевых бит.
Нет. Последовательность чисел, у которых единиц в двоичном представлении ровно столько же, сколько нулей, вот: https://oeis.org/A031443
А у тебя какая-то хуйня, которую ты даже не проверил походу (сколько у тройки в двоичном представлении нулей?), поэтому ничего и не находит хотя похоже на A072601.
>Нет.
>Последовательность чисел,
>у которых единиц в двоичном представлении ровно столько же, сколько нулей, вот: https://oeis.org/A031443
Заебись, то что искал.
Но судя по всему, у меня этих несжимаемых чисел, намного - НАМНОГО больше получилось.
>А у тебя какая-то хуйня, которую ты даже не проверил походу
Проверил же, там же вон функция-хуюнкция.
>сколько у тройки в двоичном представлении нулей?
А ты видишь как оно генерится?
len=4;
3(10) -> 11(2);
padding нулями до 4 бит: '11'.padStart(4, '0') -> 0011;
два нуля, две единички.
Оттого 7, после 2 идёт, хотя оно и меньше:
len = 4; 12(10) -> '1100'(2);
len=5; нечетное число бит, значит больше либо единиц либо нулей.
len = 6; 7(10) -> '111'(2);
padding нулями до 6-ти бит: '111'.padStart(4, '0') -> '000111';
И так далее.
>поэтому ничего и не находит хотя похоже на A072601.
Вот оно самое! Да, это оно: https://oeis.org/A072601
И оно даже ещё пижже чем у меня, так как здесь - намного больше чисел.
И как терь этой хуйнёй проны мои пожать?
Вы, Бабушкину, уже показывали аналитические, комплексные, и интегральные аппроксимации,
разложений сумм рядов из фрагментов этих последовательности?
У него там архиватор бабушкина, заебато hexadecimal строчки считает, вроде,
пускай оно терь посжимает мне проны везде.
Существует ли хэш-функция, которая не имеет коллизий?
Я знаю, что хэши данных, они намного короче самих данных,
и как-бы сжимают данные в хэш.
Но глядя на это: >>78834
>Легко доказывается теорема.
>Для любого N > 0 нет алгоритма сжатия без потерь, который:
>Любой файл длиной не более N байт или оставляет той же длины, или уменьшает.
>Уменьшает некоторый файл длиной не более N хотя бы на один байт.
очевидно, что сжать данные невозможно,
так как хэш по-любому будет иметь кучу коллизий.
Поэтому, чё-то взбрела в голову мысль.
Что если сжимать данные не в хэш, а например, в хэш + кусок начала + кусок конца + кусок данных?
С возможностью брут-форса самих данных?
Такая комбинация, как-бы, позволила бы однозначно идентифицировать данные - идентификатором: "хэш + кусок начала + кусок конца + кусок данных, значит, таки-сжать их, с возможностью однозначной развёртки - подбором самих данных, с помощью вычислительных мощностей, скажем.
Или такое - невозможно в принципе?