Мой алгоритм (почти не шутка)
Jul. 12th, 2002 11:10 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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.
Алгоритм можно усовершенствовать и дальше: например, взять много разных генераторов случайных чисел под номерами (и добавлять еще номер генератора), можно сочетать поиск в случайных числах с поиском в константах и т.д.
С каждым таким усовершенствованием, мы, конечно же, жертвуем еще дополнительными битами, но значительно расширяем возможности поиска.
В конце концов, можно добиться такого баланса возможностей и потраченных битов, чтобы выигрыш был на нашей стороне. Я думаю, что это достижимо, потому что, с одной стороны, мы тратим только минимум информации на различные номера генераторов, трансцендентных чисел и тому подобного (то есть на нумерацию возможностей), с другой же стороны, мы выбираем из бесконечного числа возможностей поиска, используя любые эвристики.
Опять же, все основано на том, что обе стороны имеют доступ к бесконечному количеству общей информации, которая «уже передана».
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Тормозим, бывает...
То есть мы говорим об одном и том же: ближе к началу кодирующей информации - лучшее сжатие.
Re: Тормозим, бывает...
Date: 2002-07-12 08:21 am (UTC)Все эти вопросы были решены в конце 1950х гениями типа Шеннона. Бесплатного ланча нет.
Кто-то пытался сказать,
Date: 2002-07-12 08:25 am (UTC)На всякий случай
Мы пока действительно говорим об одном и том же.
Re: На всякий случай
Date: 2002-07-12 03:49 pm (UTC)А вот и нет ! Моя идея была как раз основана на "шуме", то есть на случайном распределении последовательностей, и даже более того - на случайном выборе случайных последовательностей.
Тогда есть шанс.
Re: На всякий случай
Date: 2002-07-13 01:11 am (UTC)Re: На всякий случай
Date: 2002-07-13 01:15 am (UTC)Re: Тормозим, бывает...
Date: 2002-07-12 03:34 pm (UTC)Я тогда вот что хотел попробовать, но не смог:
найти такую двоичную строку наименьшего размера, в которой были бы сочетания всех возможных подстрок данной длины длины. Тогда, если повезёт с информацией, оффсеты действительно часто будут меньше, чем сама информационная подстрока, и сжатие, возможно, получится неплохим.
Но это, конечно, если повезёт.
no subject
Date: 2002-07-13 10:29 pm (UTC)