catpad (catpad) wrote,
catpad
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.
Алгоритм можно усовершенствовать и дальше: например, взять много разных генераторов случайных чисел под номерами (и добавлять еще номер генератора), можно сочетать поиск в случайных числах с поиском в константах и т.д.
С каждым таким усовершенствованием, мы, конечно же, жертвуем еще дополнительными битами, но значительно расширяем возможности поиска.
В конце концов, можно добиться такого баланса возможностей и потраченных битов, чтобы выигрыш был на нашей стороне. Я думаю, что это достижимо, потому что, с одной стороны, мы тратим только минимум информации на различные номера генераторов, трансцендентных чисел и тому подобного (то есть на нумерацию возможностей), с другой же стороны, мы выбираем из бесконечного числа возможностей поиска, используя любые эвристики.
Опять же, все основано на том, что обе стороны имеют доступ к бесконечному количеству общей информации, которая «уже передана».

Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 22 comments