Решаем задачу уровня «Невозможно». Сжатие хаотического бинарного кода. Суперпозиционные системы счисления29.06.2024 16:30

Для наилучшего восприятия выделим основные пункты изложенного материала:

1. Для чего необходимо сжатие информации и увеличение плотности записи.

2. Проблемы в покорение хаоса, нерешенные математиками и ими же созданные.

3. Простое решение проблемы сжатия абсолютно любого бинарного кода.

4. Пути и методы дальнейшего развития сжатия бинарного кода.

1. Для чего необходимо сжатие информации и увеличение плотности записи

В современном информационном мире увеличение плотности записи позволит:

1. Записывать и хранить на порядки больше информации без увеличения и совершенствования технических средств хранения этой информации.

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

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

4. Поднять уровень шифрования данных до недосягаемых высот даже при современном уровне математической мысли.

5. Увеличить точность расчетов ЭВМ за счет:

   • улучшения способов хранения и алгоритмов вычисления чисел с плавающей точкой и в целом дробных чисел;

   • изменение стандартов записи данных в память ЭВМ;

   • разгрузка оперативной памяти ЭВМ при больших вычислениях, что даёт в целом увеличение скорости работы процессоров ЭВМ.

6. Качественно улучшить работу с большими данными за счет более тонкой настройки алгоритмов и процессов обработки больших данных.

7. Создать новые протоколы передачи информации (связи), одновременно решающие проблему и с шифрованием, и со скоростью передачи больших данных.

8. Улучшение алгоритмов работы нейронных сетей за счет решения, которое будет ниже представлено.

2. Проблемы в покорение хаоса, нерешенные математиками и ими же созданные

На протяжении последних нескольких столетий выдающимися математиками мира было решено и представлено огромное количество задач, теорем, правил и математических приемов. Практически каждый из них в своих работах и размышлениях ставил задачу покорения хаоса и бесконечностей, описания приемов и решений принуждения хаоса к порядку. Благодаря их трудам современная математика опирается на такие инструменты, как бесконечности, неопределенности, пространства, величина, пределы, векторы, функции, константы, системы счисления, математические действия (в том числе и формулы). Однако по-настоящему до сегодняшнего дня все усилия математиков по принуждению хаоса и неопределенностей к порядку сводились к описанию масштабов «проблемы», выводу усредненных формул и теорем. Общая «болезнь» математиков проявляется в поиске «волшебного элексира» — разбиение числа на множители. И если вдруг кому-нибудь удастся найти этот неуловимый способ разложить абсолютно любое число на множители, то тогда он станет «покорителем» вселенной, хаоса.

Но мы ерундой заниматься не будем, мы пойдем другим путём. Тем более и задача у нас посложнее — сжать «уже максимально возможно» сжатый двоичный код (бинарный). Математики утверждают, что еще троичный код также является максимально ёмким. А эмпирически доказано, что самая ёмкая запись числа находится в позиционной системе счисления с основанием е = 2,71828 (приблизительно). Но это не про математику целых чисел. Значит выходит, что сжать абсолютно любой двоичный код без потерь не получится?

Это у них не получится, а у нас в России возможно всё. Приступаем к решению задачи сжатия абсолютно любого хаотичного двоичного кода. Который после сжатия снова можно сжать, так как он в ЭВМ будет записан в бинарной системе. И это можно сжимать столько раз, пока не придем к минимально возможным пределам сжатия.

3. Простое решение проблемы сжатия абсолютно любого бинарного кода 

Для решения этой задачи воспользуемся рядом математических приемов и инструментов:

1. Решением «от противного» («от обратного»).

2. Асимметрией.

3. Факториалом и субфакториалом.

4. Принципом вынесения общего множителя.

5. Принципом суперпозиции числа в числе.

6. Созданием суперпозиционной системы счисления.

Как всем уже известно, самая плотная запись точных данных получается в позиционных системах счисления с основаниями 2 или 3. В недостижимом идеале — в системе счисления с основанием иррационального числа е.

Поэтому мы будем использовать суперпозиционную систему счисления для более плотной записи. Не слышали о таких? Я тоже не слышал. Тогда создадим её.

Уйдем от проблем двоичной и троичной систем счисления с общими множителями (порядками) 2 и 3 (решение от обратного) и добавим хаотичности (опять решение от обратного) — то есть воспользуемся асимметрией. Для этого вспомогательной основой нашей системы счисления возьмем факториальную систему счисления. В этой системе счисления в числе всегда участвуют все элементы и всегда без повторов, то есть значение числа определяется конкретной выборкой (или перестановкой) всех элементов системы счисления. Да, такая система счисления уступает в плотности записи позиционной системе счисления с аналогичным основанием, но у нас сейчас задача придать нашему хаотичному ряду чисел определенные свойства, которыми мы сможем легко воспользоваться для более плотной записи.

Далее будем натягивать виртуальную систему счисления с основанием 2,71828 на что-то среднее между двоичным и троичным кодом. В этом нам поможет субфакториал. Это число перестановок неповторяющихся элементов в выборке, при которой все элементы находятся не на своих местах. И отношение факториала числа к собственному субфакториалу удивительным образом стремится как раз к числу е = 2,71828… Но и это не главное. А главное то, что отношение факториала числа 3 к собственному субфакториалу равно 3. И только после факториала числа 3 это отношение меньше 3 и стремиться к 2,718…. С помощью этого конкретного разбиения (по 3 элемента от всей выборки) мы будем укрупненно (не точно по месту) определять есть ли в конкретном блоке от целой выборки элементы по месту (например, 6 находится на позиции 6 или 15 на позиции 15) или в этом блоке все элементы не по месту (например, на местах с 4 по 6 находятся элементы 2, 9 и 12).

Вот поэтому мы будем разбивать нашу выборку (определяется факториальной системой счисления) на блоки только по 3 элемента, а все числа факториальной системы счисления должны состоять из кратного трем числа элементов (15,18,21 и т. д.). Тем, кто не уловил мысль, подсказываю: перестановок 3-х элементов из 3-х равно 3! = 6 вариантов.

6 делится на 2 (двоичный код) и на 3 (троичный код — количество элементов в созданном нами минимальном блоке). Кроме того, субфакториал 3 равен 2, а это 2 значения, при котором все элементы в нашем блоке-тройке находятся не на своих местах. В оставшихся 4 значениях из 6 хоть один из элементов будет находиться на своем месте.

Запись 6 значений будем формировать всего в 4 значения (2 бита) с выносом определителя значений (по месту или не по месту) за скобки (да/нет — 1 бит), то есть некое подобие выноса множителя.

Посмотрим первую часть представления на примере числа комбинаций 15! :

Опытный глаз математика увидит, что мы неэкономно 8 значениями определили всего 6 значений блока-тройки элементов. Но это только начало всей конструкции. Дальше мы это поправим.

Также мы пока не знаем, в каком порядке находится вся наша перестановка (число) из 15 элементов, поэтому согласно делению на блоки-тройки определим содержание каждого блока (далее — блок) без указания точного места, для экономии места в записи. Это мы будем делать сначала для блока 1, потом для блока 2 и т. д. В этом нам поможет самая незатратная по емкости записи формула комбинаторики — количество сочетаний из n по k.

Ищем все возможные значения в блоке 1:

— количество сочетаний из 15 по 3 равно 455.

Далее ищем все возможные значения в блоке 2:

— количество сочетаний из оставшихся 12 по 3 равно 220.

Далее ищем все возможные значения в блоке 3:

— количество сочетаний из оставшихся 9 по 3 равно 84.

Далее ищем все возможные значения в блоке 4:

— количество сочетаний из оставшихся 6 по 3 равно 20.

Далее ищем все возможные значения в блоке 5:

— их можно не искать, остались последние 3 элемента, не вошедшие в первые блоки.

Представим второй этап в таблице и возьмем логарифм с основанием 2 по каждому значению C (n, k) полученных выборок, чтобы увидеть сколько это занимает места в двоичном коде:

Пусть Вас не пугают дроби в обозначении числа бит, в общей итоговой записи они суммируются, но это здесь мы не будем доказывать.

Теперь подведем промежуточные итоги:

У нас получилось записать число вариантов, ограниченных 15! на 42,32 битах (15+27,32), а это немного больше, чем 40,25 бита, которыми записывается в позиционной двуричной системе счисления 15! (1307674368000 значений).

Значит надо что-то делать.

Помните, мы выделили определители (типа множители) на первом этапе работы с блоками-тройками?

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

Вот она суперпозиция числа!

У нас одно число (определитель значений по месту в блоке) имеет больше одного значения и влияет сразу на две записи в числе. У нас таких определителей обозначено столько же сколько и блоков троек. В примере их 5.

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

Для этого я сначала выложу таблицу перестановок 3 элементов из чисел элементов кратных 3, начиная с 3 до 60 для понимания закономерностей.

Часть 1 таблицы:

Закономерность уже видна, поэтому для экономии времени средние значения опущу и выложу последние. А закономерность такова: значений не по месту при определении блока-тройки ровно столько же как и значений выборки всех перестановок из числа на 3 элемента меньше рассматриваемого.

Далее выкладываю таблицу перестановок 3-х элементов из чисел элементов кратных 3, начиная с 3 до 60 с разбивкой на присутствие в блоках-тройках значений по месту и их отсутствие значений на своем месте.

Тут к ранее подмеченной закономерности отмечаем, что с ростом выборки перестановок 3-х элементов из N, начиная с 6 блоков-троек (ФСС 18!) число значений, где все элементы находятся не на своих местах начинает превышать число выборок, где есть хоть один элемент на своем месте.

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

В записи количества значений перестановок блоков троек резервируем максимальное число значений: до ФСС 15! (5 блоков-троек) включительно это максимум для значений по месту, начиная с ФСС 18! (6 блоков-троек) это максимум для значений не по месту.

Соответственно, если определитель блоков-троек будет указывать на меньшую область значений, то автоматически общая запись всего искомого числа дополнительно уменьшится. Для полной записи в самых неэкономичных случаях резервируем максимальной число описаний блоков-троек независимо по месту элементы или не по месту.

Тот же пример, с максимальными выборками блоков-троек, в которых присутствуют значения элементов по месту:

В этом сжатом без потерь виде мы получили запись ФСС 15! вариантов на 40,21 бита, классическая запись в двоичной системе счисления занимает 40,25 бита. Получили сжатие 0,04 бита или в 1,000951 раза.

Далее при росте факториальной системы счисления, растет и коэффициент сжатия. Например, при ФСС 60! Мы получаем сжатую запись на 265,3711 бит против двуричной на 272,13293 бита с коэффициентом сжатия уже 1,0254805.

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

Вот такова конструкция простейших суперпозиционных систем счисления.

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

4. Пути и методы дальнейшего развития сжатия бинарного кода.

Даже самое незначительное сжатие абсолютно хаотического двузначного кода открывает безграничные возможности для усиления этого сжатия. Вот несколько возможных приемов усиления сжатия выше показанных суперпозиционных систем счисления:

1. Обозначение сжатыми блоками элементов (множителей)  позиционных систем счисления с основаниями больших порядков.

2. Используя асимметричность в записи перестановок блоков-троек можно внешними поправочными коэффициентами и приемами менять в меньшую сторону длину записи самих блоков-троек.

3. Для поиска минимальных значений длины кода в асимметричной записи перестановок блоков-троек можно использовать запись не последовательных значений, а через интервалы как равные, так и с неравномерными значениями, как, например, цифры в бесконечной дроби числа Пи.

4. Использование разных по разрядности факториальных систем счисления на всей длине сжимаемого кода.

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

Habrahabr.ru прочитано 1160 раз