Мой алгоритм (почти не шутка)

[catpad]

Год назад я придумал алгоритм для сжатия сколь угодно большой информации в сколь угодно малый объем. Я его даже реализовал, но результата, как легко догадаться не добился. Может быть, кто-нибудь объяснит, в чем ошибка ?



Допустим, что мне (отправителю) и получателю информации известно огромное число знаков двоичного разложения числа пи. Причем время компрессии для меня значения не имеет, главное информацию передать; зато время декомпрессии линейно.
Моя информация представлена в двоичном виде. Я начинаю искать в числе пи подстроку так, что:
она является наиболее длинным (желательно, но необязательно) началом (префиксом) моей информации, которая удовлетворяет следующему условию:
offset этой подстроки в числе пи + длина двоичного представления offset’а + длина подстроки в двоичном виде + длина двоичного представления этой длины хотя бы на один бит короче, чем сама подстрока. Тогда вместо
substring (длиной N) получается
length_of_offset offset length_of_length length (длиной M).
При этом M < N.

Это дает возможность восстановить substring, зашифрованный с помощью меньшего числа бит, чем сам этот substring.

Найдя такую подстроку, я продолжаю поиск с нового места в моей строке, и так далее, до окончания информации.

После этой итерации у меня есть новая двоичная строка информации, длиной меньше, чем начальная строка (хотя бы на один бит).

Как нетрудно догадаться, я повторяю итерации до тех пор, пока мне удается сократить текущую информацию, хотя бы на один бит в каждой итерации.
Теоретически, в конце я должен получить строку вида
length_of_offset offset length_of_length length number_of_iterations, которая при удачно сложившихся обстоятельствах во много раз меньше, чем начальная длина строки, и к тому же позволяет полностью восстановить первоначальную информацию.

В принципе, это не так уж смешно, и не противоречит закону сохранения вещества во вселенной, так как мы исходим из того, что и отправителю и получателю заранее известно огромное количество «shared information» - разложение числа пи.
Алгоритм просто «структурирует шум» уже заложенный в числе пи и известный обеим сторонам.

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

Вместо числа пи, возьмем детерминистский генератор псевдослучайных чисел, так, чтобы по одному seed он всегда давал одну и ту же последовательность чисел. Этот генератор известен обеим сторонам. В предыдущем алгоритме, вместо поиска наилучшей подстроки в числе пи, будем испытывать разные seeds для генератора, пока не получим случайное двоичное число, в котором подстрока, удовлетворяющая необходимым условиям, не будет найдена. Здесь мы ищем подстроку, которая была бы наибольшей с наименьшим offsetом внутри случайного числа. Правда, в этом случае к зашифрованной подстроке надо еще прибавить сам seed.
Алгоритм можно усовершенствовать и дальше: например, взять много разных генераторов случайных чисел под номерами (и добавлять еще номер генератора), можно сочетать поиск в случайных числах с поиском в константах и т.д.
С каждым таким усовершенствованием, мы, конечно же, жертвуем еще дополнительными битами, но значительно расширяем возможности поиска.
В конце концов, можно добиться такого баланса возможностей и потраченных битов, чтобы выигрыш был на нашей стороне. Я думаю, что это достижимо, потому что, с одной стороны, мы тратим только минимум информации на различные номера генераторов, трансцендентных чисел и тому подобного (то есть на нумерацию возможностей), с другой же стороны, мы выбираем из бесконечного числа возможностей поиска, используя любые эвристики.
Опять же, все основано на том, что обе стороны имеют доступ к бесконечному количеству общей информации, которая «уже передана».

Comments

Re: На всякий случай

[catpad.livejournal.com]

...таблица с упорядоченными строками ничем не хуже "таблицы" в виде числа Пи

А вот и нет ! Моя идея была как раз основана на "шуме", то есть на случайном распределении последовательностей, и даже более того - на случайном выборе случайных последовательностей.
Тогда есть шанс.

Re: На всякий случай

[stas]

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

Re: На всякий случай

[catpad.livejournal.com]

Они - случайно выбранные таблицы, в этом их преимущество.