Для наилучшего восприятия выделим основные пункты изложенного материала:
Для чего необходимо сжатие информации и увеличение плотности записи.
Проблемы в покорение хаоса, нерешенные математиками и ими же созданные.
Простое решение проблемы сжатия абсолютно любого бинарного кода.
Пути и методы дальнейшего развития сжатия бинарного кода.
1. Для чего необходимо сжатие информации и увеличение плотности записи
В современном информационном мире увеличение плотности записи позволит:
Записывать и хранить на порядки больше информации без увеличения и совершенствования технических средств хранения этой информации.
Увеличить скорость передачи данных за счет ее сжатия, а также открыть возможности получения информации там, где слабые пропускные каналы связи, расширить возможности уже существующих больших каналов связи.
Передавать и получать кратно больше информации устройствами для этого не предназначенными.
Поднять уровень шифрования данных до недосягаемых высот даже при современном уровне математической мысли.
-
Увеличить точность расчетов ЭВМ за счет:
улучшения способов хранения и алгоритмов вычисления чисел с плавающей точкой и в целом дробных чисел;
изменение стандартов записи данных в память ЭВМ;
разгрузка оперативной памяти ЭВМ при больших вычислениях, что даёт в целом увеличение скорости работы процессоров ЭВМ.
Качественно улучшить работу с большими данными за счет более тонкой настройки алгоритмов и процессов обработки больших данных.
Создать новые протоколы передачи информации (связи), одновременно решающие проблему и с шифрованием, и со скоростью передачи больших данных.
Улучшение алгоритмов работы нейронных сетей за счет решения, которое будет ниже представлено.
2. Проблемы в покорение хаоса, нерешенные математиками и ими же созданные
На протяжении последних нескольких столетий выдающимися математиками мира было решено и представлено огромное количество задач, теорем, правил и математических приемов. Практически каждый из них в своих работах и размышлениях ставил задачу покорения хаоса и бесконечностей, описания приемов и решений принуждения хаоса к порядку. Благодаря их трудам современная математика опирается на такие инструменты, как бесконечности, неопределенности, пространства, величина, пределы, векторы, функции, константы, системы счисления, математические действия (в том числе и формулы). Однако по-настоящему до сегодняшнего дня все усилия математиков по принуждению хаоса и неопределенностей к порядку сводились к описанию масштабов «проблемы», выводу усредненных формул и теорем. Общая «болезнь» математиков проявляется в поиске «волшебного элексира» - разбиение числа на множители. И если вдруг кому-нибудь удастся найти этот неуловимый способ разложить абсолютно любое число на множители, то тогда он станет «покорителем» вселенной, хаоса.
Но мы ерундой заниматься не будем, мы пойдем другим путём. Тем более и задача у нас посложнее – сжать «уже максимально возможно» сжатый двоичный код (бинарный). Математики утверждают, что еще троичный код также является максимально ёмким. А эмпирически доказано, что самая ёмкая запись числа находится в позиционной системе счисления с основанием е = 2,71828 (приблизительно). Но это не про математику целых чисел. Значит выходит, что сжать абсолютно любой двоичный код без потерь не получится?
Это у них не получится, а у нас в России возможно всё. Приступаем к решению задачи сжатия абсолютно любого хаотичного двоичного кода. Который после сжатия снова можно сжать, так как он в ЭВМ будет записан в бинарной системе. И это можно сжимать столько раз, пока не придем к минимально возможным пределам сжатия.
3. Простое решение проблемы сжатия абсолютно любого бинарного кода
Для решения этой задачи воспользуемся рядом математических приемов и инструментов:
Решением «от противного» («от обратного»).
Асимметрией.
Факториалом и субфакториалом.
Принципом вынесения общего множителя.
Принципом суперпозиции числа в числе.
Созданием суперпозиционной системы счисления.
Как всем уже известно, самая плотная запись точных данных получается в позиционных системах счисления с основаниями 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! :
Номер блока-тройки |
1 |
2 |
3 |
4 |
5 |
Итого бит |
Значений по месту/не по месту |
2 |
2 |
2 |
2 |
2 |
|
Значений в конечном блоке-тройке |
4 |
4 |
4 |
4 |
4 |
|
Всего бит |
3 |
3 |
3 |
3 |
3 |
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) полученных выборок, чтобы увидеть сколько это занимает места в двоичном коде:
Номер блока-тройки |
1 |
2 |
3 |
4 |
5 |
Итого бит |
Выборка из |
15 |
12 |
9 |
6 |
3 |
|
сколько выбираем |
3 |
3 |
3 |
3 |
3 |
|
|
|
|
|
|
|
|
Значения C(n,k) = |
455 |
220 |
84 |
20 |
1 |
|
лог 2 |
8,829723 |
7,78136 |
6,392317 |
4,321928 |
0 |
27,32533 |
Пусть Вас не пугают дроби в обозначении числа бит, в общей итоговой записи они суммируются, но это здесь мы не будем доказывать.
Теперь подведем промежуточные итоги:
У нас получилось записать число вариантов, ограниченных 15! на 42,32 битах (15+27,32), а это немного больше, чем 40,25 бита, которыми записывается в позиционной двуричной системе счисления 15! (1307674368000 значений).
Значит надо что-то делать.
Помните, мы выделили определители (типа множители) на первом этапе работы с блоками-тройками?
Так вот – используем их тогда сначала перед определением конкретных сочетаний элементов в каждом блоке, и автоматически они в том же значении будут выполнять вторую роль на втором этапе уточнения конкретного положения каждого элемента в блоке-тройке.
Вот она суперпозиция числа!
У нас одно число (определитель значений по месту в блоке) имеет больше одного значения и влияет сразу на две записи в числе. У нас таких определителей обозначено столько же сколько и блоков троек. В примере их 5.
Теперь, когда мы первыми включили в работу определители блоков троек, мы можем отсечь лишние для записи варианты, сократив немного саму запись.
Для этого я сначала выложу таблицу перестановок 3 элементов из чисел элементов кратных 3, начиная с 3 до 60 для понимания закономерностей.
Часть 1 таблицы:
Количество блоков-троек |
Факториальная система счислений (ФСС) |
Общее число значений ФСС |
Блок 1 |
Блок 2 |
Блок 3 |
Блок 4 |
Блок 5 |
Блок 6 |
|
1 |
3 |
6 |
1 |
|
|
|
|
|
|
2 |
6 |
720 |
20 |
1 |
|
|
|
|
|
3 |
9 |
362880 |
84 |
20 |
1 |
|
|
|
|
4 |
12 |
479001600 |
220 |
84 |
20 |
1 |
|
|
|
5 |
15 |
1,30767E+12 |
455 |
220 |
84 |
20 |
1 |
|
|
6 |
18 |
6,40237E+15 |
816 |
455 |
220 |
84 |
20 |
1 |
|
7 |
21 |
5,10909E+19 |
1330 |
816 |
455 |
220 |
84 |
20 |
|
8 |
24 |
6,20448E+23 |
2024 |
1330 |
816 |
455 |
220 |
84 |
|
9 |
27 |
1,08889E+28 |
2925 |
2024 |
1330 |
816 |
455 |
220 |
|
10 |
30 |
2,65253E+32 |
4060 |
2925 |
2024 |
1330 |
816 |
455 |
|
11 |
33 |
8,68332E+36 |
5456 |
4060 |
2925 |
2024 |
1330 |
816 |
|
12 |
36 |
3,71993E+41 |
7140 |
5456 |
4060 |
2925 |
2024 |
1330 |
|
13 |
39 |
2,03979E+46 |
9139 |
7140 |
5456 |
4060 |
2925 |
2024 |
|
14 |
42 |
1,40501E+51 |
11480 |
9139 |
7140 |
5456 |
4060 |
2925 |
|
15 |
45 |
1,19622E+56 |
14190 |
11480 |
9139 |
7140 |
5456 |
4060 |
|
16 |
48 |
1,24139E+61 |
17296 |
14190 |
11480 |
9139 |
7140 |
5456 |
|
17 |
51 |
1,55112E+66 |
20825 |
17296 |
14190 |
11480 |
9139 |
7140 |
|
18 |
54 |
2,30844E+71 |
24804 |
20825 |
17296 |
14190 |
11480 |
9139 |
|
19 |
57 |
4,05269E+76 |
29260 |
24804 |
20825 |
17296 |
14190 |
11480 |
|
20 |
60 |
8,32099E+81 |
34220 |
29260 |
24804 |
20825 |
17296 |
14190 |
Закономерность уже видна, поэтому для экономии времени средние значения опущу и выложу последние. А закономерность такова: значений не по месту при определении блока-тройки ровно столько же как и значений выборки всех перестановок из числа на 3 элемента меньше рассматриваемого.
Количество блоков-троек |
Факториальная система счислений (ФСС) |
Общее число значений ФСС |
Блок 15 |
Блок 16 |
Блок 17 |
Блок 18 |
Блок 19 |
Блок 20 |
|
1 |
3 |
6 |
|
|
|
|
|
|
|
2 |
6 |
720 |
|
|
|
|
|
|
|
3 |
9 |
362880 |
|
|
|
|
|
|
|
4 |
12 |
479001600 |
|
|
|
|
|
|
|
5 |
15 |
1,30767E+12 |
|
|
|
|
|
|
|
6 |
18 |
6,40237E+15 |
|
|
|
|
|
|
|
7 |
21 |
5,10909E+19 |
|
|
|
|
|
|
|
8 |
24 |
6,20448E+23 |
|
|
|
|
|
|
|
9 |
27 |
1,08889E+28 |
|
|
|
|
|
|
|
10 |
30 |
2,65253E+32 |
|
|
|
|
|
|
|
11 |
33 |
8,68332E+36 |
|
|
|
|
|
|
|
12 |
36 |
3,71993E+41 |
|
|
|
|
|
|
|
13 |
39 |
2,03979E+46 |
|
|
|
|
|
|
|
14 |
42 |
1,40501E+51 |
|
|
|
|
|
|
|
15 |
45 |
1,19622E+56 |
1 |
|
|
|
|
|
|
16 |
48 |
1,24139E+61 |
20 |
1 |
|
|
|
|
|
17 |
51 |
1,55112E+66 |
84 |
20 |
1 |
|
|
|
|
18 |
54 |
2,30844E+71 |
220 |
84 |
20 |
1 |
|
|
|
19 |
57 |
4,05269E+76 |
455 |
220 |
84 |
20 |
1 |
|
|
20 |
60 |
8,32099E+81 |
816 |
455 |
220 |
84 |
20 |
1 |
Далее выкладываю таблицу перестановок 3-х элементов из чисел элементов кратных 3, начиная с 3 до 60 с разбивкой на присутствие в блоках-тройках значений по месту и их отсутствие значений на своем месте.
Количество блоков-троек |
Факториальная система счислений (ФСС) |
Всего выборок для определения блока-тройки |
Значение в блоке-тройке ДА |
Значение в блоке-тройке НЕТ |
|
1 |
3 |
1 |
1 |
0 |
|
2 |
6 |
20 |
19 |
1 |
|
3 |
9 |
84 |
64 |
20 |
|
4 |
12 |
220 |
136 |
84 |
|
5 |
15 |
455 |
235 |
220 |
|
6 |
18 |
816 |
361 |
455 |
|
7 |
21 |
1330 |
514 |
816 |
|
8 |
24 |
2024 |
694 |
1330 |
|
9 |
27 |
2925 |
901 |
2024 |
|
10 |
30 |
4060 |
1135 |
2925 |
|
11 |
33 |
5456 |
1396 |
4060 |
|
12 |
36 |
7140 |
1684 |
5456 |
|
13 |
39 |
9139 |
1999 |
7140 |
|
14 |
42 |
11480 |
2341 |
9139 |
|
15 |
45 |
14190 |
2710 |
11480 |
|
16 |
48 |
17296 |
3106 |
14190 |
|
17 |
51 |
20825 |
3529 |
17296 |
|
18 |
54 |
24804 |
3979 |
20825 |
|
19 |
57 |
29260 |
4456 |
24804 |
|
20 |
60 |
34220 |
4960 |
29260 |
Тут к ранее подмеченной закономерности отмечаем, что с ростом выборки перестановок 3-х элементов из N, начиная с 6 блоков-троек (ФСС 18!) число значений, где все элементы находятся не на своих местах начинает превышать число выборок, где есть хоть один элемент на своем месте.
Теперь приступаем к созданию сжатой системы счисления, отбрасывая лишние для записи элементы. Подчеркиваю, точной записи без всяких потерь.
В записи количества значений перестановок блоков троек резервируем максимальное число значений: до ФСС 15! (5 блоков-троек) включительно это максимум для значений по месту, начиная с ФСС 18! (6 блоков-троек) это максимум для значений не по месту.
Соответственно, если определитель блоков-троек будет указывать на меньшую область значений, то автоматически общая запись всего искомого числа дополнительно уменьшится. Для полной записи в самых неэкономичных случаях резервируем максимальной число описаний блоков-троек независимо по месту элементы или не по месту.
Тот же пример, с максимальными выборками блоков-троек, в которых присутствуют значения элементов по месту:
Номер блока-тройки |
1 |
2 |
3 |
4 |
5 |
Итого бит |
Определение значений по месту |
да |
да |
да |
да |
да |
5 |
Выборка из |
15 |
12 |
9 |
6 |
3 |
|
сколько выбираем |
3 |
3 |
3 |
3 |
3 |
|
Значения C(n,k) = |
235 |
136 |
64 |
19 |
1 |
|
лог 2 |
7,876517 |
7,087463 |
6 |
4,247928 |
0 |
25,21191 |
Значений в конечном блоке-тройке |
4 |
4 |
4 |
4 |
4 |
|
лог 2 |
2 |
2 |
2 |
2 |
2 |
10 |
ИТОГО бит |
|
|
|
|
|
40,21191 |
В этом сжатом без потерь виде мы получили запись ФСС 15! вариантов на 40,21 бита, классическая запись в двоичной системе счисления занимает 40,25 бита. Получили сжатие 0,04 бита или в 1,000951 раза.
Далее при росте факториальной системы счисления, растет и коэффициент сжатия. Например, при ФСС 60! Мы получаем сжатую запись на 265,3711 бит против двуричной на 272,13293 бита с коэффициентом сжатия уже 1,0254805.
Особо важно упомянуть, что это минимальные коэффициенты сжатия, так как хаотические непредсказуемые значения в больших рядах бинарного кода гарантируют нам благодаря заложенной нами асимметричности дополнительную экономию записи.
Вот такова конструкция простейших суперпозиционных систем счисления.
И самое приятное в том, что мы уже можем сжимать любой хаотический двоичный код, а значит сжимать дальше уже сжатый нами код до минимально допустимых пределов.
4. Пути и методы дальнейшего развития сжатия бинарного кода.
Даже самое незначительное сжатие абсолютно хаотического двузначного кода открывает безграничные возможности для усиления этого сжатия. Вот несколько возможных приемов усиления сжатия выше показанных суперпозиционных систем счисления:
Обозначение сжатыми блоками элементов (множителей) позиционных систем счисления с основаниями больших порядков.
Используя асимметричность в записи перестановок блоков-троек можно внешними поправочными коэффициентами и приемами менять в меньшую сторону длину записи самих блоков-троек.
Для поиска минимальных значений длины кода в асимметричной записи перестановок блоков-троек можно использовать запись не последовательных значений, а через интервалы как равные, так и с неравномерными значениями, как, например, цифры в бесконечной дроби числа Пи.
Использование разных по разрядности факториальных систем счисления на всей длине сжимаемого кода.
Приемов, как можно сжать вышеуказанные суперпозиционные системы счисления, подсчитать и предугадать не представляется возможным.
Комментарии (28)
wataru
29.06.2024 14:24+19Математики утверждают, что еще троичный код также является максимально ёмким. А эмпирически доказано, что самая ёмкая запись числа находится в позиционной системе счисления с основанием е = 2,71828 (приблизительно)
Раз математики утверждают, то дайте ссылку на утверждения. А вообще - бред же. Что за емкость вы тут берете? Как будто на этом утверждении у вас вся идея завязана, но само утверждение не доказано, да и не формализовано вообще. Вся статья дальше сразу становится под вопрос.
А что касается сути статьи, то это очередной "вечный двигатель" от самоучки-инженера, применительно к математике. И силь соответствующий: тут и "актуальность" проблемы разжовывается, и все математики-ученые как бы обзываются неумехами. А вот автор-то додумался, а эти очкарики яйцеголовые - никак не могут.
Не существует алгоритма, который сжимает любые данные. Это элементарно доказывается: рассмотрим множество всех возможных файлов длины до n включительно -
, рассмотрим множество из их "запакованных" версий - 
. Чтобы файлы можно было распаковать обратно, 
. Но, если все запакованные файлы короче входных данных, то 
. Отсюда и получается, что алгоритм не может сжимать все. Более простое доказательство "на пальцах" - если алгоритм так шикарен, то его можно применять повторно, и сжать вообще все данные до одного бита (а один бит - до нуля!).
А так, какие-то таблицы кучу каких-то чисел автор вывалил, а алгоритм так не расписал.
arkuvschinov Автор
29.06.2024 14:24Сколько эмоций на горячую голову: "Раз математики утверждают, то дайте ссылку на утверждения. А вообще - бред же."
Странные слова для человека, зарегистрированном на Habr-е. Стоит ли на них обращать внимание? Будем делать Вас лучше, поэтому дам ссылку-ответ не где-нибудь, а именно на статью на Habr-е.
https://habr.com/ru/articles/427969/
Далее Вы опять куда-то спешите: "Вся статья дальше сразу становится под вопрос. " Пока что Ваш комментарий под вопросом.
Идем дальше:
"А что касается сути статьи, то это очередной "вечный двигатель" от самоучки-инженера, применительно к математике. И силь соответствующий: тут и "актуальность" проблемы разжовывается, и все математики-ученые как бы обзываются неумехами. А вот автор-то додумался, а эти очкарики яйцеголовые - никак не могут. "
Ну даже если предположить, что тут Вы почти не ошиблись. Это только предположение, чтобы Вас немного вернуть на землю, то что это меняет? Суть перестанет быть сутью?
Дальше Вас уже не остановить: "Не существует алгоритма, который сжимает любые данные."
Теперь Ваша очередь доказать свои слова, я же напротив - показал обратное.
Этот портал для людей думающих, а не для выражения своих голых негативных эмоций, если кто-то что-то не понял. Вы кинули какое-то доказательство не подумавши. В нем формула, выраженная "2 в степени n". А это характеристика позиционных систем счисления, а не суперпозиционных.
Нельзя килограммами измерять время, а секундами длину.
Я с пониманием, отношусь к Вашему непониманию. Доброго Вам здоровья!"
wataru
29.06.2024 14:24+22Во-первых, когда вы пишите "математики утверждают", надо бы дать ссылку на математиков, а не статью на сайте без peer review.
Ну да, минимум функции x^n/x достигается при x=е. Эту задачку ученики старшей школы решат запросто. Но как это относится к "емкости" системы счисления? Определите, таки, емкость. Там весьма произвольная оценка "стоимости" записи - основание системы, умноженное на число разрядов. Эти самые пресловутые разноцветные "камушки", которые нам почему-то надо зарезервировать на все разряды всех цветов. К собственно записи данных это не имеет никакого отношения. Не важно, скоклько суммарно возможных состояний у ячеек, которые вы используете для записи данных. Важно только количество ячеек памяти.
Теперь Ваша очередь доказать свои слова,
Я доказательство прям там же и привел. Оно достаточно простое, чтобы уместиться в пару абзацев. Ну, разве что, можно было бы расписать, что различных файлов размера меньше n - всего суммарно 2^n-1. Но раз уж вы математикам вызов бросаете, то вы это и сами понять могли бы.
А это характеристика позиционных систем счисления, а не суперпозиционных.
В компьютере, даже буть он тернарный, хоть суперпозиционных, все данные занимают какое-то место. Покудо он дискретный, у вас будут ячейки - "биты", хоть бы и тернарные, хоть бы и с переменным количеством состояний. И размер данных будет описываться именно количеством использованных битов. А сжатие будет подразумевать уменьшение этого количества.
Замените 2^n на какое-нибудь D(n) ~= n!/e для вашей субфакториальной системы. Суть доказательства останется той же: чем меньше длина кода, тем меньше возможных кодов. В любой системе счисления, не обязательно позиционной. Поэтоме, если вы уменьшаете все коды, то у вас множество возможных выходных данных оказывается меньше множества входных данных, а значит переобразование не инъективное, и несколько входных кодов переводятся в один и тот же выходной. А значит, распаковка таких данных не возможна.
ivanstor
29.06.2024 14:24+6За комментарии спасибо от нематематика.
Но, похоже, зря тратите время. Автор в своей вселенной...
arkuvschinov Автор
29.06.2024 14:24Ну можно же было сразу без вранья: "Ну да, минимум функции x^n/x достигается при x=е. "
Ваш следующий вопрос: "Но как это относится к "емкости" системы счисления? " Тут надо бы закругляться с такими дискуссиями. Вы раньше дали на него ответ, не понимая последующего вопроса. Это, конечно, жестко. Сегодня Вы не в форме.
Предвкушая винегрет в Вашей голове помноженный на Ваши эмоции, отвечу (повторю из прошлого ответа) - Вы сейчас измеряете емкость позиционных систем счисления, а есть еще и непозиционные и комбинированные. А системы счисления с суперпозициями чисел Вас вообще добивают. Внимательно посмотрите, что у статьи уровень сложности - "максимальный".
В этом Вашем абзаце есть дельные мысли вперемешку с заблуждениями: "Там весьма произвольная оценка "стоимости" записи - основание системы, умноженное на число разрядов. Эти самые пресловутые разноцветные "камушки", которые нам почему-то надо зарезервировать на все разряды всех цветов. К собственно записи данных это не имеет никакого отношения. Не важно, скоклько суммарно возможных состояний у ячеек, которые вы используете для записи данных. Важно только количество ячеек памяти. "
Это не годится: "Там весьма произвольная оценка "стоимости" записи". Оценка записи точнее некуда - количество бит, байт и т. д.
И Вы свою фразу расшифровываете: "основание системы, умноженное на число разрядов." Опять двадцать пять. Это измерение в позиционных системах счисления!
Сил на подумать у Вас сегодня не хватило, зато поставить минус моему ответу Вам хватило))) В начале статьи был указан уровень сложности "максимальный" ))
Ну и горделиво Ваше: "Я доказательство прям там же и привел." Доказательство чего?
Тут Вас похвалю: "все данные занимают какое-то место. ... И размер данных будет описываться именно количеством использованных битов. А сжатие будет подразумевать уменьшение этого количества. "
Еще немного похвалю: "Суть доказательства останется той же: чем меньше длина кода, тем меньше возможных кодов. " Но тут необходимо пояснение: при идеально максимальной плотности записи данных. При неэкономичной записи данных это утверждение неверно.
И опять))))) спешите:
"А значит, распаковка таких данных не возможна. "
Гонять Вас нужно, пока толк не выйдет)))
wataru
29.06.2024 14:24+9Внимательно посмотрите, что у статьи уровень сложности - "максимальный".
Это аргумент, да.
Вы сейчас измеряете емкость позиционных систем счисления, а есть еще и непозиционные и комбинированные. А системы счисления с суперпозициями чисел Вас вообще добивают.
Ну так объясните мне, несмышленому, почему в качестве емкости системы счисления берется x^(n/x)? Какой смысл у этого значения?
Оценка записи точнее некуда - количество бит, байт и т. д.
Когда я пишу про 2^n кодов для n бит вы возражаете, что, мол - система-то непозиционная. А тут уже сами к битам возвращаетесь. Вы или крестик снимите, или трусы наденьте, как говориться.
И Вы свою фразу расшифровываете: "основание системы, умноженное на число разрядов." Опять двадцать пять. Это измерение в позиционных системах счисления!
Это про ту статью, которую вы дали. Там позиционные системы счисления! И вы сами тут приводите факт, что e - самое емкое основание позиционной системы счисления. Следите хоть немного за дискуссией-то.
чем меньше длина кода, тем меньше возможных кодов. " Но тут необходимо пояснение: при идеально максимальной плотности записи данных.
Бред. что за "плотность записи"? n бит записывают 2^n различных кодов.
А еще, я смотрю, в аргументы скобочки пошли. У вас логические доводы кончились? Сочуствую...
arkuvschinov Автор
29.06.2024 14:24"Ну так объясните мне, несмышленому, почему в качестве емкости системы счисления берется x^(n/x)? Какой смысл у этого значения? "
До сих пор считалось, что максимальная плотность записи чисел в позиционных системах счисления, поэтому этим математическим инструментом пока и измеряется емкость записи. И дальше будет так измеряться как от эталонной точки отсчета. Вы же не удивляетесь, что есть отрицательные числа. А 250 лет назад за это (отрицательные числа) могли и на костре сжечь))))
"Вы или крестик снимите, или трусы наденьте, как говориться. " Вам явно хочется укусить))) Помните - все равно в итоге мы пока битами информацию измеряем. Ну и Вам домашнее задание: "Сколько людей носящих крестик ходит без трусов?"
"Следите хоть немного за дискуссией-то. "
Да, откуда ж Вы миленький такой взялись))))))) А серьезно - Вы молодец, Вы не побоялись поболтать (конструктива мало у Вас) на серьезную тему, обозначить свое непонимание. То есть Вы выразили мнение определенной выборки людей со схожим типом восприятия, задали рядом вопросов.
Тут в который раз Вы измеряете "килограммами километры":
"Бред. что за "плотность записи"? n бит записывают 2^n различных кодов. "
Столько пояснений, а воз и ныне там. Закончу Вашим же последним словом:
"Сочуствую... ".
Juggernaut
29.06.2024 14:24+13Автор, может быть вместо фонтана неуклюжего сарказма запилите код, реализующий алгоритм сжатия? Мы проверим на практике и сравним со стандартными архиваторами? К чему это нагромождение теории без единой строчки кода?
arkuvschinov Автор
29.06.2024 14:24Вы про сарказм говорите, а как отвечать на неадекватные вопросы?
Все расчеты я выложил, механику расписал. Оказывается и этого мало.
Алгоритм сжатия я уже делаю, но более сложный. На основании выше указанного. Код связан с шифрованием и не будет опубликован. Простой вариант возможно дам.
wataru
29.06.2024 14:24+5Вы механику так и не расписали. У вас там какая-то таблица нагромаждена, вроде как выделяются тройки чисел, но как именно оно записывается в битах - непонятно.
Почему у вас там 4 варианта, например, стоит, если варианта расположить три числа - 6? Почему вы там считаете только варианты, что хотя бы одно число в тройке на своем месте? Почему перебираете только варианты выбрать из 15 чисел 3 так, что бы хотя бы одно было из {1, 2, 3}? Как записываются перестановки, где ни одно число не на своем месте?
arkuvschinov Автор
29.06.2024 14:24"Почему у вас там 4 варианта, например, стоит, если варианта расположить три числа - 6? "
Да, этот момент не достаточно ясно расписан, хотя и показан. Мы определитель каждой тройки СНАЧАЛА указываем, у него всего два значения - есть в блоке-тройке элемент факториального обозначения исходного числа или нет. И это определитель влияет сразу на два элемента уже записываемого (сжатого числа):
1) на определение состава конкретных чисел из выборки НЕПОВТОРЯЮЩИХСЯ элементов (которая определена нами так по умолчанию) в блоке-тройке без указания точных мест этих элементов. Еще остается неолределённость. И
2) на следующем этапе мы в каждом блоке тройке, зная уже какие элементы в нем есть определяем их места. В неопределенной ситуации вариантов, конечно 6. Но у нас ранее определитель отсеил нам ненужные варианты, а значит сократил выборку до максимум 4 (4 или 2). И соответственно сократил запись.
Вот это и есть экономия, когда на двух этапах мы в формуле выборки отсеиваем для записи ненужные варианты. В позиционных системах счисления одно число только один раз влияет, а в нашем случае - два раза влияет. Вот поэтому формулы, характеризующие позиционные системы счисления, здесь не совсем уместны.
Еще важное уточнение - на первом этапе формула отбора НЕ ПЕРЕСТАНОВКИ, а СОЧЕТАНИЯ. Количество сочетаний гораздо меньше, чем перестановок (и это экономия записи). В нашем примере из 15 элементов для первой тройки это 3 сочетания из 15 - вариантов 455. А перестановок без повторений (принято называть размещения без повторений) 3 из 15 будет 2730 вариантов. То есть 2730/455 = 6. А благодаря разбиению на два этапа нахождения точного размещения элементов и выноса определителя (по месту и не по месту) нам достаточно уже всего 4 варианта на втором этапе точного определения.
Также еще отмечу, что перестановки в комбинаторике - это выборки с указанием точных мест элементов в выборке. Но такие формулы имеют на порядки больше вариантов и поэтому мы их отбрасываем, и через определители (если удобно для понимания - множители) вынесенные как множители (но принцип немного другой) сокращаем эти записи.
Второй Ваш вопрос: "Как записываются перестановки, где ни одно число не на своем месте? "
В этом случае на первом этапе определения значения в первом блоке тройке в нашем примере из факториальной выборки 15 элементов нам достаточно 220 значений вместо 455, во втором блоке-тройке всего 84 значения вместо 220 и т. д. Данные я в таблице указал. Проверяется формулой "Количество сочетаний из n по k" - общее количество сочетаний, а значений не по месту формулой "Количество сочетаний из n-3 по k". (n-3) потому что на этих трех местах не будет ни одного значения по месту.
wataru
29.06.2024 14:24+4Так, еще раз повторите. Вот этот "определитель" - это бит. поскольку у вас там фигурирует число 225, то он, во-первых, означает, что среди 15 чисел мы в сочетание по 3 взяли не любые три в первую тройку, а так, чтобы хотя бы одно число было из этой тройки (1,2 или 3). Я правильно понял? Или как у вас 225 получается-то?
И второе, этот же определитель говорит нам, что в этой тройке ни одно число не стоит на своем месте, поэтому там 2 варианта получается (или 4, если хотя бы одно стоит на своем месте).
Тут вообще не на своем месте имеется ввиду (в смысле 1 не на первом месте в перовой тройке, 4 не на первом месте во второй тройке) или только относительный порядок (если вы взяли числа 1,7 и 8 в первую тройку, то 7 не стоит на 2-ом месте, а 8 на 3-ем)?Как вы запишите, например, первую тройку (1,2,3), а как (15,14,13)? Судя по таблице, каждая такая тройка у вас должна описываться набором {d, n, k}, где d=1..2, n=1..225, k=1..4. Вы логарифмы вот этих чисел суммируете в вашей таблице. d - ваш определитель, n как-то определяет сочетание, а k - порядок чисел в тройке.
artptr86
29.06.2024 14:24+12Всё по классике гениальных алгоритмов, которые уже не единожды были тут на Хабре:
Алгоритм я вам расписан, что ещё вам, собаки, надо? У меня реализации нет, да и мне некогда её делать, я уже занят более сложными вещами.
artptr86
29.06.2024 14:24Вот нашёл удалённые статьи:
https://archive.ph/2015.04.03-101515/http://habrahabr.ru/post/254809/
artptr86
29.06.2024 14:24+2Дальше Вас уже не остановить: "Не существует алгоритма, который сжимает любые данные."
Теперь Ваша очередь доказать свои слова, я же напротив - показал обратное.
Нет, не показали. Более того, вы сами и в статье указали, что есть теоретический предел сжатия. То есть никакие данные сжать дальше предела не получится. Ниже в комментариях вы ещё раз явно это указываете: https://habr.com/ru/articles/825536/comments/#comment_26987138
Этот портал для людей думающих, а не для выражения своих голых негативных эмоций, если кто-то что-то не понял. Вы кинули какое-то доказательство не подумавши. В нем формула, выраженная "2 в степени n". А это характеристика позиционных систем счисления, а не суперпозиционных.
Всё правильно. Формула 2^n применима как раз для двоичной системы счисления, которая является и исходной для кодирования сжимаемой информации, и целевой. Опять таки, цитируя вашу статью, «так как он в ЭВМ будет записан в бинарной системе».
Это означает, что после работы вашего алгоритма получится двоичная последовательность, которая, скорее всего, уже не подвергнется сжатию повторно. То есть на выходе получится последовательность не короче получившейся на первом шаге. Именно об этом теорема и её доказательство, поскольку любой алгоритм сжатия без потерь даёт ваимно однозначное соответствие между двоичными последовательностями.
kia00000
29.06.2024 14:24+2Не понял статью. Жду обсуждения, и хотя бы оценку силы и скорости сжатия, жду программу хотя бы на питоне, даже медленную.
CitizenOfDreams
29.06.2024 14:24+2Клод Шеннон и его теорема: ну да, пошли мы на хрен.
arkuvschinov Автор
29.06.2024 14:24Ничего подобного. Клод Шеннон прав в своей теории. Противоречий нет.
michael_v89
29.06.2024 14:24Вот есть двоичная последовательность 10001001. Покажите пожалуйста последовательность шагов вашего алгоритма со всеми промежуточными результатами, как ее сжать на 1 бит.
arkuvschinov Автор
29.06.2024 14:24Вы читали статью?
По этому приведенному алгоритму в примере сжатие начинается только с 41 бит до 40,21 бита, и в дальнейшем нарастает.
В конце статьи я намекнул, какими приемами и комбинациями приемов можно кратно повышать сжатие. Этот принцип для больших данных.
artptr86
29.06.2024 14:24Так показали бы хотя бы на примере 64-битной последовательности. Теоретически должно 63 бита как раз получиться.
michael_v89
29.06.2024 14:24+3Читал, вы не умеете излагать мысли, и поэтому ничего непонятно. Поэтому я и задал вопрос в комментариях.
В вашей статье не указано, что сжатие начинается только с 41 бит. Вы просто взяли пример от балды 15! и для него получили 41 бит.Хорошо, вот есть двоичная последовательность длиной 43 бита
1000010111101101100011011111100010001011101. Покажите пожалуйста последовательность шагов вашего алгоритма со всеми промежуточными результатами, как ее сжать на 1 бит.
wanomgn
29.06.2024 14:24+2ну написал же вам человек: этот очушительный алгоритм будет применен в криптографии.. и вообще он слишком прост что бы сидеть его расписывать таким неблагодарным как хабровчане.. так что никаких вам последовательных шагов. вам как не объясняй - вы все равно не поймете /s
;)
murkin-kot
29.06.2024 14:24+2Общая проблема наивного подхода к сжатию данных состоит в отвлечении внимания от сопутствующих действий. Таковыми являются, например, вычисления, производимые над сжимаемыми и разжимаемыми данными. Если же обратить внимание на вычисления, то мы заметим небольшую проблему - для сжатия произвольного файла нам потребуется что-то вроде вычислительной мощности, какой нет во всей вселенной.
Но само по себе сжатие на порядки произвольного (и при этом достаточно длинного) файла вполне возможно.
Идея такого сжатия тривиальна - сопоставим выбранному файлу число 1. Ну вот - мы сжали выбранный файл до одного бита. Кто-то будет спорить?
Но есть здесь та самая проблема. Для сжатия второго файла потребуется сопоставить ему другое число, например 2. Для третьего - 3, ну и так далее. Только произвольных файлов , длиной N бит, может быть два в степени N. Значит нам придётся каким-то из них сопоставлять значения из N бит, то есть сжатие куда-то потеряется.
На этом простом примере мы поняли, что сжать все произвольные файлы мы не можем. Но это не значит, что мы не можем сопоставить одному из этих файлов число 1. То есть если мы забудем про общий подход (сжатие всех файлов), то очень большой коэффициент сжатия становится вполне возможным. Да, математики своим генеральным методом несколько обеднили возможные математические же результаты.
Кто-то когда-то предлагал сжатие на основе числа пи. Там всё просто - вбрасываем в игру бесконечные вычислительные мощности и затем играючи находим адрес в бесконечной последовательности знаков числа пи, начиная с которого наш сжимаемый файл в точности повторяется в числе пи. Берём этот адрес и длину файла - вуаля, мы сжали файл до некого меньшего числа. Но возможен нюанс, нет гарантий, что адрес файла в числе пи не окажется по размеру больше самого файла. Опять проблема.
Автор уже столкнулся с подобной нестыковкой, когда понял, что сжатие его способом получается лишь при больших размерах файлов. А при малых получается лишь увеличение размера. То же самое характерно и для числа пи, как и для любой другой достаточно длинной псевдослучайной последовательности.
Собственно вывод:
Да, сжатие на много порядков вполне возможно. Но для этого получатель должен уже обладать оригинальным файлом, то есть без сжатия, хотя и в зашифрованном виде (число пи, например). Далее мы передаём получателю номер файла и он "разжимает" файл в гигабайты из нескольких бит. Вычислительные сложности, разумеется, в полном соответствии с привычкой математиков решать проблемы в общем виде, мы оставляем прикладникам. Альтернатива - способ создания хранилища всех файлов в несжатом виде (дабы "сжимать" их указанием номера) мы тоже оставляем чумазым механикам, ведь наше дело стратегия, правильно?
amishaa
29.06.2024 14:24Ну, вообще говоря, есть целая область theoretical computer science, посвященная оптимальным вычислимым сжатиям, искать можно по ключевому слову "Колмогоровская сложность".
wataru
29.06.2024 14:24Автор, вы перестали отвечать на комментарии. Нашли ошибку? Если еще нет, я вам подскажу - ваш "опеределитель" нельзя использовать одновременно для уменьшения количества возможных сочетаний из n по 3 и для уменьшения количества перестановок из трех элементов с 6 до 4. Если вы добавите вторые определители, то у вас появятся еще 5 бит, которые вы потеряли, и ваша схема станет хуже обычной двоичной записи.
Нельзя, ну потому что представьте что у вас в первой тройке числа {1,2,3}. Эта троица однозначно задает вам определитель, ведь тут взяты числа из первого блока. Определитель фиксирован. Но все еще эти 3 числа можно расположить 3!=6 вариантами. Вы же считаете, что из всего 4, а оставшиеся 2 вы получите поменяв "определитель". Но определитель менять нельзя, иначе вы множество чисел уже не закодируете, ибо для другого значения определителя у вас возможны только тройки чисел не из первого блока.
Ну и, не ищите как исправить ошибку, это невозможно: 2^5*235*136*64*19*4^5 = 2^40,21191 < 2^40,25 = 15! Т.е. ваша схема назначает каждой перестановке из 15 элементов какой-то код, но этих выходных кодов меньше. А значит каким-то входным перестановкам оно назначает один и тот же код, а значит однозначно восстановить исходные данные нельзя.
Какую бы вы схему не придумали, если вы насчитаете в итоге сжатие и меньше бит, чем в исходных данных - то вы получите это же противоречие. Сжатие возможно только если оно какие-то входные данные сжимает, а какие-то, наоборот - увеличивает (возможно лишь на 1 бит).
artptr86
Только не в России же, а в Польше: https://en.wikipedia.org/wiki/Asymmetric_numeral_systems
wataru
Не, там, в отличии от авторских супер-пупер идей, все не "революционно" и вполне стандартно. Сжатие просиходит за счет низкой энтропии входных данных - из-за не равномерного распределения символов во входных данных.