Мой алгоритм (почти не шутка)
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}
no subject
Алгоритм, который всегда сжимает сколь угодное количество информации невозможен из-за принципа Дирихле (если n голубей залетает в k голубятен, где n>k, то по крайней мере два голубя залетают в одну и ту же голубятню, и по номеру голубятни нельзя восстановить номер голубя). Это значит, что любой алгоритм сжатия информации или совсем не сожмет большинство случайных строк, или даже удлинит их.
Сжатие информации в программах типа gzip, bzip2 основано на том, что не все строки длиной n символов одинаково вероятны. Реальные файлы, которые даются gzip - английский текст, битмапы, машинный код х86 - совсем не случайны. Они имеют много статистических свойств - повторяющихся длинных сегментов (напр. " the " в английском тексте), очень разной частоты различных байтов (напр. пробел в английском тексте встречается значительно чаще, чем буква x) - отличающих их от случайных строк. Алгоритмы, использующиеся gzip и подобными программами сильно сжимают такие строки, удлиняя случайные - но так, как случайные строки маловероятны, в среднем строки сжимаются.
Если перед сжатием над строкой провести преобразование с помощью какой-то книги кодов (например, двоичного разложения числа пи), а после сжатия обратное преобразование - то предпочтение передастся другим строкам (напр. строкам, встречающимся в начале двоичного разложения числа пи), которые будут сжиматься хорошо - а остальные строки, включая строки, встречающиеся в реальном мире, будут увеличиваться. В любом случае, благодаря принципу Дирихле бесплатного ланча не бывает.
no subject
Date: 2002-07-12 11:11 am (UTC)Я думаю Миша хочет чтобы ему показали конкретное место где не так. В целом оно понятно, что работать не должно.
Мне кажется странным вот это:
offset этой подстроки в числе пи + длина двоичного представления offset’а + длина подстроки в двоичном виде + длина двоичного представления этой длины хотя бы на один бит короче, чем сама подстрока
Offset ведь может быть и длиннее подстроки.
Re:
Date: 2002-07-12 11:16 am (UTC)Re:
Date: 2002-07-12 04:09 pm (UTC)no subject
Date: 2002-07-12 03:55 pm (UTC)Интересно, что на опыте я это как раз и увидел.
Бесплатный ланч бывает !
Date: 2002-07-12 03:56 pm (UTC)(или в голубятне :)
no subject
Date: 2002-07-12 07:36 am (UTC)она является наиболее длинным (желательно, но необязательно) началом (префиксом) моей информации, которая удовлетворяет следующему условию:
offset этой подстроки в числе пи + длина двоичного представления offset’а + длина подстроки в двоичном виде + длина двоичного представления этой длины хотя бы на один бит короче, чем сама подстрока.
А если такой подстроки (в хранящемся у отправителя и получателя конечном числе знаков разложения Пи) не будет?
Встречное предложение:
Пусть тебе надо зашифровать информацию длины N. Тогда, при условии, что и у тебя и у получателя есть таблица всех возможных строк такой длины - ты просто передаёшь ему номер твоей строки в этой таблице.
Как только ты начинаешь работать с доступом к бесконечному количеству информации - ты действительно можешь сделать всё, что угодно - за бесконечное время.
no subject
Бесплатного ланча не бывает.
Тормозим, бывает...
То есть мы говорим об одном и том же: ближе к началу кодирующей информации - лучшее сжатие.
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)Актуальная бесконечность
а известно, что это приводит к логическим парадоксам.
Анекдот №18236754323465798905643221112385600079!
Date: 2002-07-12 09:59 am (UTC)Re: Анекдот №18236754323465798905643221112385600079!
Re: Анекдот №18236754323465798905643221112385600079!
Date: 2002-07-12 03:46 pm (UTC)С другой стороны, не нужно числа пи. Напечатайте много толстых книг, состоящих из всех возможных сочетаний букв. Там-то все знания и ещё неизвестные истины и будут заложены.
Re: Анекдот №18236754323465798905643221112385600079!
Date: 2002-07-14 03:38 am (UTC)