Comments 28
Это у них не получится, а у нас в России возможно всё.
Только не в России же, а в Польше: https://en.wikipedia.org/wiki/Asymmetric_numeral_systems
Математики утверждают, что еще троичный код также является максимально ёмким. А эмпирически доказано, что самая ёмкая запись числа находится в позиционной системе счисления с основанием е = 2,71828 (приблизительно)
Раз математики утверждают, то дайте ссылку на утверждения. А вообще - бред же. Что за емкость вы тут берете? Как будто на этом утверждении у вас вся идея завязана, но само утверждение не доказано, да и не формализовано вообще. Вся статья дальше сразу становится под вопрос.
А что касается сути статьи, то это очередной "вечный двигатель" от самоучки-инженера, применительно к математике. И силь соответствующий: тут и "актуальность" проблемы разжовывается, и все математики-ученые как бы обзываются неумехами. А вот автор-то додумался, а эти очкарики яйцеголовые - никак не могут.
Не существует алгоритма, который сжимает любые данные. Это элементарно доказывается: рассмотрим множество всех возможных файлов длины до n включительно -
, рассмотрим множество из их "запакованных" версий - 
. Чтобы файлы можно было распаковать обратно, 
. Но, если все запакованные файлы короче входных данных, то 
. Отсюда и получается, что алгоритм не может сжимать все.
Более простое доказательство "на пальцах" - если алгоритм так шикарен, то его можно применять повторно, и сжать вообще все данные до одного бита (а один бит - до нуля!).
А так, какие-то таблицы кучу каких-то чисел автор вывалил, а алгоритм так не расписал.
Сколько эмоций на горячую голову: "Раз математики утверждают, то дайте ссылку на утверждения. А вообще - бред же."
Странные слова для человека, зарегистрированном на Habr-е. Стоит ли на них обращать внимание? Будем делать Вас лучше, поэтому дам ссылку-ответ не где-нибудь, а именно на статью на Habr-е.
https://habr.com/ru/articles/427969/
Далее Вы опять куда-то спешите: "Вся статья дальше сразу становится под вопрос. " Пока что Ваш комментарий под вопросом.
Идем дальше:
"А что касается сути статьи, то это очередной "вечный двигатель" от самоучки-инженера, применительно к математике. И силь соответствующий: тут и "актуальность" проблемы разжовывается, и все математики-ученые как бы обзываются неумехами. А вот автор-то додумался, а эти очкарики яйцеголовые - никак не могут. "
Ну даже если предположить, что тут Вы почти не ошиблись. Это только предположение, чтобы Вас немного вернуть на землю, то что это меняет? Суть перестанет быть сутью?
Дальше Вас уже не остановить: "Не существует алгоритма, который сжимает любые данные."
Теперь Ваша очередь доказать свои слова, я же напротив - показал обратное.
Этот портал для людей думающих, а не для выражения своих голых негативных эмоций, если кто-то что-то не понял. Вы кинули какое-то доказательство не подумавши. В нем формула, выраженная "2 в степени n". А это характеристика позиционных систем счисления, а не суперпозиционных.
Нельзя килограммами измерять время, а секундами длину.
Я с пониманием, отношусь к Вашему непониманию. Доброго Вам здоровья!"
Во-первых, когда вы пишите "математики утверждают", надо бы дать ссылку на математиков, а не статью на сайте без peer review.
Ну да, минимум функции x^n/x достигается при x=е. Эту задачку ученики старшей школы решат запросто. Но как это относится к "емкости" системы счисления? Определите, таки, емкость. Там весьма произвольная оценка "стоимости" записи - основание системы, умноженное на число разрядов. Эти самые пресловутые разноцветные "камушки", которые нам почему-то надо зарезервировать на все разряды всех цветов. К собственно записи данных это не имеет никакого отношения. Не важно, скоклько суммарно возможных состояний у ячеек, которые вы используете для записи данных. Важно только количество ячеек памяти.
Теперь Ваша очередь доказать свои слова,
Я доказательство прям там же и привел. Оно достаточно простое, чтобы уместиться в пару абзацев. Ну, разве что, можно было бы расписать, что различных файлов размера меньше n - всего суммарно 2^n-1. Но раз уж вы математикам вызов бросаете, то вы это и сами понять могли бы.
А это характеристика позиционных систем счисления, а не суперпозиционных.
В компьютере, даже буть он тернарный, хоть суперпозиционных, все данные занимают какое-то место. Покудо он дискретный, у вас будут ячейки - "биты", хоть бы и тернарные, хоть бы и с переменным количеством состояний. И размер данных будет описываться именно количеством использованных битов. А сжатие будет подразумевать уменьшение этого количества.
Замените 2^n на какое-нибудь D(n) ~= n!/e для вашей субфакториальной системы. Суть доказательства останется той же: чем меньше длина кода, тем меньше возможных кодов. В любой системе счисления, не обязательно позиционной. Поэтоме, если вы уменьшаете все коды, то у вас множество возможных выходных данных оказывается меньше множества входных данных, а значит переобразование не инъективное, и несколько входных кодов переводятся в один и тот же выходной. А значит, распаковка таких данных не возможна.
За комментарии спасибо от нематематика.
Но, похоже, зря тратите время. Автор в своей вселенной...
Ну можно же было сразу без вранья: "Ну да, минимум функции x^n/x достигается при x=е. "
Ваш следующий вопрос: "Но как это относится к "емкости" системы счисления? " Тут надо бы закругляться с такими дискуссиями. Вы раньше дали на него ответ, не понимая последующего вопроса. Это, конечно, жестко. Сегодня Вы не в форме.
Предвкушая винегрет в Вашей голове помноженный на Ваши эмоции, отвечу (повторю из прошлого ответа) - Вы сейчас измеряете емкость позиционных систем счисления, а есть еще и непозиционные и комбинированные. А системы счисления с суперпозициями чисел Вас вообще добивают. Внимательно посмотрите, что у статьи уровень сложности - "максимальный".
В этом Вашем абзаце есть дельные мысли вперемешку с заблуждениями: "Там весьма произвольная оценка "стоимости" записи - основание системы, умноженное на число разрядов. Эти самые пресловутые разноцветные "камушки", которые нам почему-то надо зарезервировать на все разряды всех цветов. К собственно записи данных это не имеет никакого отношения. Не важно, скоклько суммарно возможных состояний у ячеек, которые вы используете для записи данных. Важно только количество ячеек памяти. "
Это не годится: "Там весьма произвольная оценка "стоимости" записи". Оценка записи точнее некуда - количество бит, байт и т. д.
И Вы свою фразу расшифровываете: "основание системы, умноженное на число разрядов." Опять двадцать пять. Это измерение в позиционных системах счисления!
Сил на подумать у Вас сегодня не хватило, зато поставить минус моему ответу Вам хватило))) В начале статьи был указан уровень сложности "максимальный" ))
Ну и горделиво Ваше: "Я доказательство прям там же и привел." Доказательство чего?
Тут Вас похвалю: "все данные занимают какое-то место. ... И размер данных будет описываться именно количеством использованных битов. А сжатие будет подразумевать уменьшение этого количества. "
Еще немного похвалю: "Суть доказательства останется той же: чем меньше длина кода, тем меньше возможных кодов. " Но тут необходимо пояснение: при идеально максимальной плотности записи данных. При неэкономичной записи данных это утверждение неверно.
И опять))))) спешите:
"А значит, распаковка таких данных не возможна. "
Гонять Вас нужно, пока толк не выйдет)))
Внимательно посмотрите, что у статьи уровень сложности - "максимальный".
Это аргумент, да.
Вы сейчас измеряете емкость позиционных систем счисления, а есть еще и непозиционные и комбинированные. А системы счисления с суперпозициями чисел Вас вообще добивают.
Ну так объясните мне, несмышленому, почему в качестве емкости системы счисления берется x^(n/x)? Какой смысл у этого значения?
Оценка записи точнее некуда - количество бит, байт и т. д.
Когда я пишу про 2^n кодов для n бит вы возражаете, что, мол - система-то непозиционная. А тут уже сами к битам возвращаетесь. Вы или крестик снимите, или трусы наденьте, как говориться.
И Вы свою фразу расшифровываете: "основание системы, умноженное на число разрядов." Опять двадцать пять. Это измерение в позиционных системах счисления!
Это про ту статью, которую вы дали. Там позиционные системы счисления! И вы сами тут приводите факт, что e - самое емкое основание позиционной системы счисления. Следите хоть немного за дискуссией-то.
чем меньше длина кода, тем меньше возможных кодов. " Но тут необходимо пояснение: при идеально максимальной плотности записи данных.
Бред. что за "плотность записи"? n бит записывают 2^n различных кодов.
А еще, я смотрю, в аргументы скобочки пошли. У вас логические доводы кончились? Сочуствую...
"Ну так объясните мне, несмышленому, почему в качестве емкости системы счисления берется x^(n/x)? Какой смысл у этого значения? "
До сих пор считалось, что максимальная плотность записи чисел в позиционных системах счисления, поэтому этим математическим инструментом пока и измеряется емкость записи. И дальше будет так измеряться как от эталонной точки отсчета. Вы же не удивляетесь, что есть отрицательные числа. А 250 лет назад за это (отрицательные числа) могли и на костре сжечь))))
"Вы или крестик снимите, или трусы наденьте, как говориться. " Вам явно хочется укусить))) Помните - все равно в итоге мы пока битами информацию измеряем. Ну и Вам домашнее задание: "Сколько людей носящих крестик ходит без трусов?"
"Следите хоть немного за дискуссией-то. "
Да, откуда ж Вы миленький такой взялись))))))) А серьезно - Вы молодец, Вы не побоялись поболтать (конструктива мало у Вас) на серьезную тему, обозначить свое непонимание. То есть Вы выразили мнение определенной выборки людей со схожим типом восприятия, задали рядом вопросов.
Тут в который раз Вы измеряете "килограммами километры":
"Бред. что за "плотность записи"? n бит записывают 2^n различных кодов. "
Столько пояснений, а воз и ныне там. Закончу Вашим же последним словом:
"Сочуствую... ".
Автор, может быть вместо фонтана неуклюжего сарказма запилите код, реализующий алгоритм сжатия? Мы проверим на практике и сравним со стандартными архиваторами? К чему это нагромождение теории без единой строчки кода?
Вы про сарказм говорите, а как отвечать на неадекватные вопросы?
Все расчеты я выложил, механику расписал. Оказывается и этого мало.
Алгоритм сжатия я уже делаю, но более сложный. На основании выше указанного. Код связан с шифрованием и не будет опубликован. Простой вариант возможно дам.
Вы механику так и не расписали. У вас там какая-то таблица нагромаждена, вроде как выделяются тройки чисел, но как именно оно записывается в битах - непонятно.
Почему у вас там 4 варианта, например, стоит, если варианта расположить три числа - 6? Почему вы там считаете только варианты, что хотя бы одно число в тройке на своем месте? Почему перебираете только варианты выбрать из 15 чисел 3 так, что бы хотя бы одно было из {1, 2, 3}? Как записываются перестановки, где ни одно число не на своем месте?
"Почему у вас там 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) потому что на этих трех местах не будет ни одного значения по месту.
Так, еще раз повторите. Вот этот "определитель" - это бит. поскольку у вас там фигурирует число 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 - порядок чисел в тройке.
Всё по классике гениальных алгоритмов, которые уже не единожды были тут на Хабре:
Алгоритм я вам расписан, что ещё вам, собаки, надо? У меня реализации нет, да и мне некогда её делать, я уже занят более сложными вещами.
Вот нашёл удалённые статьи:
https://archive.ph/2015.04.03-101515/http://habrahabr.ru/post/254809/
Дальше Вас уже не остановить: "Не существует алгоритма, который сжимает любые данные."
Теперь Ваша очередь доказать свои слова, я же напротив - показал обратное.
Нет, не показали. Более того, вы сами и в статье указали, что есть теоретический предел сжатия. То есть никакие данные сжать дальше предела не получится. Ниже в комментариях вы ещё раз явно это указываете: https://habr.com/ru/articles/825536/comments/#comment_26987138
Этот портал для людей думающих, а не для выражения своих голых негативных эмоций, если кто-то что-то не понял. Вы кинули какое-то доказательство не подумавши. В нем формула, выраженная "2 в степени n". А это характеристика позиционных систем счисления, а не суперпозиционных.
Всё правильно. Формула 2^n применима как раз для двоичной системы счисления, которая является и исходной для кодирования сжимаемой информации, и целевой. Опять таки, цитируя вашу статью, «так как он в ЭВМ будет записан в бинарной системе».
Это означает, что после работы вашего алгоритма получится двоичная последовательность, которая, скорее всего, уже не подвергнется сжатию повторно. То есть на выходе получится последовательность не короче получившейся на первом шаге. Именно об этом теорема и её доказательство, поскольку любой алгоритм сжатия без потерь даёт ваимно однозначное соответствие между двоичными последовательностями.
Не понял статью. Жду обсуждения, и хотя бы оценку силы и скорости сжатия, жду программу хотя бы на питоне, даже медленную.
Клод Шеннон и его теорема: ну да, пошли мы на хрен.
Вот есть двоичная последовательность 10001001. Покажите пожалуйста последовательность шагов вашего алгоритма со всеми промежуточными результатами, как ее сжать на 1 бит.
Вы читали статью?
По этому приведенному алгоритму в примере сжатие начинается только с 41 бит до 40,21 бита, и в дальнейшем нарастает.
В конце статьи я намекнул, какими приемами и комбинациями приемов можно кратно повышать сжатие. Этот принцип для больших данных.
Так показали бы хотя бы на примере 64-битной последовательности. Теоретически должно 63 бита как раз получиться.
Читал, вы не умеете излагать мысли, и поэтому ничего непонятно. Поэтому я и задал вопрос в комментариях.
В вашей статье не указано, что сжатие начинается только с 41 бит. Вы просто взяли пример от балды 15! и для него получили 41 бит.
Хорошо, вот есть двоичная последовательность длиной 43 бита
1000010111101101100011011111100010001011101. Покажите пожалуйста последовательность шагов вашего алгоритма со всеми промежуточными результатами, как ее сжать на 1 бит.
Общая проблема наивного подхода к сжатию данных состоит в отвлечении внимания от сопутствующих действий. Таковыми являются, например, вычисления, производимые над сжимаемыми и разжимаемыми данными. Если же обратить внимание на вычисления, то мы заметим небольшую проблему - для сжатия произвольного файла нам потребуется что-то вроде вычислительной мощности, какой нет во всей вселенной.
Но само по себе сжатие на порядки произвольного (и при этом достаточно длинного) файла вполне возможно.
Идея такого сжатия тривиальна - сопоставим выбранному файлу число 1. Ну вот - мы сжали выбранный файл до одного бита. Кто-то будет спорить?
Но есть здесь та самая проблема. Для сжатия второго файла потребуется сопоставить ему другое число, например 2. Для третьего - 3, ну и так далее. Только произвольных файлов , длиной N бит, может быть два в степени N. Значит нам придётся каким-то из них сопоставлять значения из N бит, то есть сжатие куда-то потеряется.
На этом простом примере мы поняли, что сжать все произвольные файлы мы не можем. Но это не значит, что мы не можем сопоставить одному из этих файлов число 1. То есть если мы забудем про общий подход (сжатие всех файлов), то очень большой коэффициент сжатия становится вполне возможным. Да, математики своим генеральным методом несколько обеднили возможные математические же результаты.
Кто-то когда-то предлагал сжатие на основе числа пи. Там всё просто - вбрасываем в игру бесконечные вычислительные мощности и затем играючи находим адрес в бесконечной последовательности знаков числа пи, начиная с которого наш сжимаемый файл в точности повторяется в числе пи. Берём этот адрес и длину файла - вуаля, мы сжали файл до некого меньшего числа. Но возможен нюанс, нет гарантий, что адрес файла в числе пи не окажется по размеру больше самого файла. Опять проблема.
Автор уже столкнулся с подобной нестыковкой, когда понял, что сжатие его способом получается лишь при больших размерах файлов. А при малых получается лишь увеличение размера. То же самое характерно и для числа пи, как и для любой другой достаточно длинной псевдослучайной последовательности.
Собственно вывод:
Да, сжатие на много порядков вполне возможно. Но для этого получатель должен уже обладать оригинальным файлом, то есть без сжатия, хотя и в зашифрованном виде (число пи, например). Далее мы передаём получателю номер файла и он "разжимает" файл в гигабайты из нескольких бит. Вычислительные сложности, разумеется, в полном соответствии с привычкой математиков решать проблемы в общем виде, мы оставляем прикладникам. Альтернатива - способ создания хранилища всех файлов в несжатом виде (дабы "сжимать" их указанием номера) мы тоже оставляем чумазым механикам, ведь наше дело стратегия, правильно?
Автор, вы перестали отвечать на комментарии. Нашли ошибку? Если еще нет, я вам подскажу - ваш "опеределитель" нельзя использовать одновременно для уменьшения количества возможных сочетаний из 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 бит).
Решаем задачу уровня «Невозможно». Сжатие хаотического бинарного кода. Суперпозиционные системы счисления