Бинарный метод кодирования информации (сжатия без потерь).

В отличие от словарных методов, которые работают с последовательностями байтов, бинарный метод, (с применением «словарей» корректоров), подразумевает операции с массивами минимальных единиц информации – битов, значение которых может быть либо «0», либо «1».

На данный момент не доказана возможность дешифрации и сжатия информации, предлагаемым мной методом экспериментально.

1. Шифрация

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

Зашифрованный файл содержит в себе:

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

б) Суммы единичных битов по линиям «таблицы» (по строкам, столбцам и прямым диагональным линиям).

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

г) Информацию о типах корректоров и их позициях в таблице.

Корректоры используются благодаря естественной энтропии в битовом массиве. Благодаря энтропии, попытки создания подобных шифраторов, по общественному мнению, обречены на провал. Лично я нигде не замечал рассмотрения её свойств в реальных битовых массивах. Рассмотреть некоторые её свойства мне помогли знакомые люди своими замечаниями, критикой, вопросами.

Минимально, без использования сумм прямых диагональных линий в массиве мы не сможем отличить:

от

С суммами по строкам, столбцам и всем прямым диагоналям в реальном массиве мы не сможем отличить:

от

и

от

Перед шифрацией массив сканируется на предмет наличия таких областей; в шифрованный файл записывается информация о типах этих областей и их координаты в массиве. Недостатком данного метода является, что на описание 1й такой области из 2х байт будет затрачено не менее 3х байт, а с разделителями не менее 5ти. В реальных массивах такие области встречаются нечасто. Моим знакомым программистом в Интернете была написана программа, которая открывала в проводнике операционной системы (MS Windows), любой файл, строилась «таблица» и создавался битовый массив. Затем, программа подсчитывала вышеописанные области, которые мы не сможем восстановить при генерации (дешифрации) по суммам линий.

Например, взяв произвольный файл, размером 4 063 527 байт и протестировав в программе, получил 1697 областей, т. е. на их описание мы затрачиваем около 8,5 килобайт. Возможно, таких типов, разновидностей областей на самом деле больше, но, думается, это не критично. Благодаря их предсказуемости и однотипности их можно сжимать традиционными, используемыми уже сегодня методами – опять же, если говорить о сжатии. Методы можно чередовать, варьировать.

2. Дешифрация

Для дешифрации создаётся пустой, (обнулённый) массив – таблица, исходя из данных в зашифрованном файле. Затем, в пустой массив заносятся «неопределённые области» - для простоты их можно называть «пазлами». Значения в этих пазлах не будут меняться во время всего процесса генерации/дешифрации массива.

Есть несколько методов генерации, и может быть найдено и интегрировано ещё больше.

1 из методов:

«перебор ячеек»

Мы берём отдельную ячейку и смотрим на суммы, которых у нас 4 – по строке, по столбцу и 2м диагоналям. Не будем заострять внимание на таких моментах, например, что в 1й ячейке значение известно на 100%, т. к. одна из диагоналей показывает 1у ячейку и 1 её значение и т. п. Предполагаемая программа дешифрации должна это учитывать.

Мы сравниваем данную из дешифруемого файла сумму с реальной суммой по горизонтали. Если она меньше реальной суммы в генерируемом массиве по горизонтали, в программном коде дешифрации это обозначается, к примеру, flag1=1, если больше, то flag1=0 и так со всеми суммами отдельно взятой ячейки. Для выставления предварительного значения в ячейке можно использовать условие:

«если flag1 + flag2 + flag3 + flag4 < 2, тогда значение в ячейке = 1

если flag1 + flag2 + flag3 + flag4 > 3, тогда значение в ячейке = 0»

Таким образом, программа подразумевает, что если сумма флагов = 2 или 3, то изменений в ячейке не происходит. Можно усложнить алгоритм, добавив флаги равенств к условию. Алгоритм всячески варьировался, и удавалось восстанавливать простые небольшие массивы, начиная с «креста из единичек», заканчивая произвольным наполнением таблицы единицами с соответствующей коррекцией сумм.

При генерации массива с «неопределёнными областями» возникала рекурсия, либо эффект, близкий к бесконечной генерации массива. Алгоритм с предварительным занесением и фиксацией «пазлов» в массиве не был испытан в связи с нехваткой свободного времени у разработчиков.

Остальные методы не опробованы и здесь не описываются.

3. Сжатие

Посчитаем, придерживаясь максимализма, сколько информации понадобится для создания зашифрованного файла. Возьмём для рассмотрения гигабайт (гибибайт) информации, пересчитанный по «старой» системе исчисления.

8*1024*1024*1024=8589934592 бит.

Битовый массив можно представить в прямоугольной таблице, приближенной к квадрату (всё кратно 8). Пойдём путём максимализма: представим, что все биты, равны «1», тогда сумма битов по вертикали/горизонтали в квадратной таблице будет корень из 8589934592 приблизительно 92682 – 5 байт – это максимум. Нам нужны суммы в таблице всех вертикалей, горизонталей и диагоналей. Расчеты неточные, но чтобы никак не ошибиться, придерживаемся всё того же максимализма:

5*92682+5*92682+20*92682=2780460 (20*92682 -2 диагонали, диагональ почти равна 2м сторонам). Это почти 3 мегабайта в зашифрованном виде. Чтобы не ошибиться, придерживаясь максимализма, увеличим это количество вдвое на разделители и служебную информацию. Получаем 6Мб. Такой зашифрованный файл можно сжимать ещё. Стоит учесть информацию корректоров, которая может оказаться значительно больше предварительной, описанной выше.

4. Вопросы

Некоторые вопросы перефразированы и подкорректированы в виду того, что задавались в небрежном стиле переписки в Интернете:

Вопрос 1

Рассмотрим некоторую абстрактную технологию сжатия.

Исходные P бит информации сжали в Q, где P>Q.

Вариантов исходной информации 2^P, а упакованной 2^Q.

На каждый вариант упакованной информации приходится в среднем 2^(P-Q)вариантов исходной.

Для однозначного выбора из такого множества необходимо P-Q дополнительных бит информации.

В результате получили Q+(P-Q)=P бит.

Сжатия не получилось

Ответ:

В приведённом примере мы можем строить уравнения с двумя неизвестными, соответственно, можем строить графики функций. Возможно, можно представить исходную информацию, как P, а упакованную, как Q, но, мы не можем ни в каком виде приравнивать исходную информацию к сжатой, т. к. предлагаемый мной метод не обладает прямой математической обратимостью. Q=2^P и P=2^Q - возможно и справедливо, но, нам всегда известен либо исходный массив, либо закодированная информация. Вопрос составлен, исходя из абсолютизма, я предлагаю рассматривать частность случаев.

Вопрос 2

Александр: есть ячейка памяти объёмом 1 гб

Александр: сколько в ней можно разместить разных файлов по 1 гб?

Павел: Если считать по - старому (1024), то 2^8589934592

Александр: 2 ^ 1024*1024*1024

Александр: то есть 2 ^ 1073741824

Павел: 8 не дописал))

Александр: допустим, есть твой чудо-архиватор, который сжимает гигабайтные файлы до 1 мб

Александр: или до 10 мб

Александр: выбери сам допустимый объём

Павел: На одной из ступеней сжатия предполагаются такие объёмы

Александр: ну т. е. 10 мб пойдёт, да?

Александр: ок, сколько файлов можно уместить в ячейку памяти 10 мб?

Павел: Меньше, чем в гиг, это понятно

Александр: ну допустим, они все будут ровно по 1 мб, да?

Александр: ой по 10

Павел: Допустим да

Александр: тогда это 8^1024*1024*10

Александр: плюс ещё по столько же для каждого файла меньшего объёма

Александр: там по формуле геометрической прогрессии можно суммировать, всё равно получится меньше, чем в гиг

Павел: Что - то не очень понял...

Александр: ок, пусть будет ровно 10 мб

Александр: тогда это 2^1024*1024*10

Александр: это меньше, чем 2^1024*1024*1024

Александр: согласен?

Павел: 2^8*1024*1024*10

Александр: да, да

Александр: и там и сям

Александр: согласен

Александр: т. е. для 10 мб намного меньше вариантов заполнить ячейку, чем для 1 гб

Александр: это понятно?

Павел: Да

Александр: так вот, а теперь главная мысль

Александр: вот твой чудо-архиватор сжимает все гигабайтные файлы до 10 мб

Александр: так?

Павел: Да, допустим

Александр: вот он каждый из 2^8*1024*1024*10 гигабайтных файлов сожмёт и получит свой уникальный архив объёмом 10 мб, так?

Павел: Ага

Александр: А что делать с оставшимися?

Александр: 2^8*1024*1024*1024 - 2^8*1024*1024*10

Александр: вот с этими

Александр: в какие файлы они сожмутся? 10-гигабайтных больше нет

Павел: Ага, очень интересная мысль - сразу точно не отвечу

Александр: ой, 10-мегабайтных больше нет

Ответ:

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

5. Методы разработки

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

6. Работа со специалистами

Каждому программисту приходилось уделять достаточно много времени, чтобы ввести его в курс дела, затем приходилось отвечать на множество вопросов, после чего мне помогали либо написать аналитическую программу, либо выражали готовность сотрудничать. Главное препятствие – отсутствие финансирования, чтобы оплатить их работу. Не стоит давать отдельно взятому программисту большое техническое задание, вызывающее много сомнений, как в результате самого задания, так и глобальной общей цели – создания такого программного продукта, как шифратор, (архиватор данных со сжатием без потерь).

Корякин Павел Васильевич

[e-mail]

[phone]

[phone]

Дата добавления: 2015-07-11