Можно ли использовать PRNG для магического сжатия материала?

38

Эта идея пришла мне в голову, когда я учился программировать и впервые столкнулся с PRNG. Я до сих пор не знаю, насколько это реалистично, но сейчас происходит обмен стека.

Вот схема 14-летнего ребенка для удивительного алгоритма сжатия:

Возьмите PRNG и начните его с seed, sчтобы получить длинную последовательность псевдослучайных байтов. Чтобы передать эту последовательность другой стороне, вам нужно только передать описание PRNG, соответствующее начальное число и длину сообщения. Для достаточно длинной последовательности это описание будет намного короче, чем сама последовательность.

Теперь предположим, что я могу инвертировать процесс. Если бы у меня было достаточно времени и вычислительных ресурсов, я мог бы выполнить поиск методом «грубой силы» и найти начальное число (и PRNG, или, другими словами: программу), которое дает желаемую последовательность (скажем, забавное фото озорных кошек).

PRNG повторяются после генерации достаточно большого числа битов, но по сравнению с «типичными» циклами мое сообщение довольно короткое, поэтому это не кажется большой проблемой.

Вуаля, эффективный (если рубин-голдбергский) способ сжатия данных.

Итак, предполагая:

  • Последовательность, которую я хочу сжать, конечна и известна заранее.
  • У меня не хватает денег или времени (до тех пор, пока требуется ограниченное количество обоих)

Я хотел бы знать:

  • Есть ли фундаментальный недостаток в обосновании схемы?
  • Какой стандартный способ анализа подобных мысленных экспериментов?

Резюме

Часто хорошие ответы проясняют не только ответ, но и то, что я действительно спрашивал. Спасибо всем за терпение и подробные ответы.

Вот моя n-я попытка краткого изложения ответов:

  • PRNG / начальный угол ничего не дает, это всего лишь программа, которая выдает желаемую последовательность в качестве выходных данных.
  • Принцип "голубиных отверстий": сообщений с длиной> k гораздо больше, чем (генерирующих сообщения) программ с длиной <= k. Таким образом, некоторые последовательности просто не могут быть результатом программы, короче, чем сообщение.
  • Стоит отметить, что интерпретатор программы (сообщения) обязательно фиксируется заранее. И его дизайн определяет (небольшое) подмножество сообщений, которые могут быть сгенерированы, когда получено сообщение длиной k.

На данный момент оригинальная идея PRNG уже мертва, но есть еще один последний вопрос:

  • В: Могу ли я получить удачу и обнаружить, что мое длинное (но конечное) сообщение просто является результатом программы длиной <k бит?

Строго говоря, это не случайность, поскольку значение каждого возможного сообщения (программы) должно быть известно заранее. Либо это значение некоторого сообщения от <K битов или нет .

Если я выберу случайное сообщение случайным образом> = k бит (зачем мне?), У меня в любом случае будет исчезающая вероятность того, что я смогу отправить его, используя меньше чем k бит, и почти наверняка не смогу отправить это вообще использует меньше чем k бит.

OTOH, если я выберу определенное сообщение из> = k битов из тех, которые являются выходом программы менее чем k бит (при условии, что такое сообщение есть), то в действительности я использую преимущества битов, уже переданных в получатель (дизайн переводчика), который считается частью передаваемого сообщения.

В заключение:

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

DW
источник
6
Немного измените свой вопрос, и вы все еще не можете сжать каждую строку (как описано в ответах ниже), но вы получаете Алгоритмическую теорию информации ( en.wikipedia.org/wiki/Kolmogorov_complexity ). Замените «PRNG» на «универсальная машина Тьюринга», а «seed» на «входную ленту, содержащую программу, которая генерирует нужный мне вывод». Большинство входных лент длиннее, чем генерируемые ими выходы, но для каждого выхода существует хотя бы один вход, который генерирует этот выход.
Блуждающая логика
Нет, но сжатый размер является энтропией источника ^ _ ^
Navin
5
Если вы на самом деле реализуете это, вы обнаружите интересную вещь: для восстановления произвольного ввода вам понадобится seed + rng, который в среднем на каждый бит больше исходных данных. К сожалению.
Марк
Другой способ понять, почему это не сработает: даже если PRNG может генерировать произвольно длинный вывод, он не может генерировать произвольный вывод. (Выход PRNG всегда будет фиксированным циклом или шаблоном, ограниченным размером его состояния.)
Pi Delport
@PietDelport, для любого n есть PRNG, цикл которого гораздо больше, а поставленный вопрос заранее известен. Так что я не уверен, что сам факт, что PRNG являются циклическими, непосредственно решает вопрос.

Ответы:

43

У тебя блестящая новая схема сжатия, а? Ну хорошо тогда...

♫ Давайте все играть, игра энтропии ♫

Проще говоря, я предполагаю, что вы хотите сжать сообщения ровно битов для некоторого фиксированного n . Однако вы хотите иметь возможность использовать его для более длинных сообщений, поэтому вам нужен какой-то способ отличить ваше первое сообщение от второго (оно не может быть неоднозначным в том, что вы сжали).NN

Итак, ваша схема состоит в том, чтобы определить какое-то семейство PRNG / seed так, что если вы хотите сжать, скажем, , то вы просто напишите некоторое число k , которое идентифицирует некоторую предварительно вычисленную (и совместно используемую) комбинацию seed / PRNG, которая генерирует эти биты после n запросов. Хорошо. Сколько разных битовых строк длины n ? 2 n (у вас есть n вариантов выбора между двумя пунктами; 0 и 1 ). Это означает, что вам придется вычислить 2 n этих комбинаций. Нет проблем. Тем не менее, вам нужно выписать k в двоичном для меня, чтобы прочитать его. Насколько большой может получить K ? Ну, это может быть как 201000111001КNN2N012NКК . Сколько бит мне нужно выписать 2 n ? log 2 n = n .2N2Nжурнал2Nзнак равноN

К сожалению! Ваша схема сжатия требует сообщений столько, сколько вы сжимаете!

«Ха-ха!», Говорите вы, «но это в худшем случае! Одно из моих сообщений будет сопоставлено с , для представления которого требуется всего 1 бит! Победа!»01

Да, но ваши сообщения должны быть однозначными! Как я могу сказать , кроме следует 0 из 10 ? Поскольку некоторые из ваших ключей имеют длину n , все они должны быть, иначе я не могу сказать, где вы начали и остановились.1010N

«Ха-ха!», Говорите вы, «но я могу сначала просто указать длину строки в двоичном виде! Это нужно только сосчитать до , которое может быть представлено в виде log n битов! Так что мой 0 теперь идет с префиксом только log n». биты, я все еще выигрываю!NжурналN0журналN

Да, но теперь эти действительно большие числа имеют префикс битов. Ваша схема сжатия сделала некоторые ваши сообщения еще длиннее! И половина всех ваших номеров начинаются с 1 , поэтому половина ваших сообщений намного длиннее!журналN1

Затем вы продолжаете выдвигать больше идей, таких как завершающий символ, сжатие числа и сжатие самой длины, но все они встречаются в тех случаях, когда результирующее сообщение просто длиннее. Фактически, для каждого бита, который вы сохраняете в каком-либо сообщении, другое сообщение в ответе становится длиннее. В общем, вы просто будете перемещаться вокруг «стоимости» ваших сообщений. Сокращение одних только сделает других длиннее. Вы действительно не можете разместить разных сообщений в меньшем пространстве, чем запись 2 n двоичных строк длиной n .2N2NN

«Ха-ха!», Говорите вы, «но я могу выбрать некоторые сообщения как« глупые »и сделать их незаконными! Тогда мне не нужно считать до , потому что я не поддерживаю такое количество сообщений!»2N

Ты прав, но на самом деле ты не выиграл. Вы только что сократили набор сообщений, которые вы поддерживаете. Если вы поддерживаете только и b = 111111110101000 в качестве отправляемых вами сообщений, то вы определенно можете просто получить код a 0 , b 1 , который точно соответствует тому, что я сказал. Здесь n = 1 . Фактическая длина сообщений не важна, это то, сколько их.aзнак равно0000000011010бзнак равно111111110101000a0б1Nзнак равно1

«Ха-ха!», Говорите вы, «но я могу просто определить, что эти глупые сообщения редки! Я сделаю редкие большие, а обычные - маленькими! Тогда я выиграю в среднем!»

Ага! Поздравляем, вы только что обнаружили энтропию ! Если у вас есть сообщений, где i- е сообщение имеет вероятность p i отправки, то вы можете получить ожидаемую длину сообщения до энтропии H = n i = 1 p i log ( 1 / p i ) этого набора сообщений. Это своего рода странное выражение, но все, что вам действительно нужно знать, это то, что оно самое большое, когда все сообщения одинаково вероятны, и меньше, когда одни встречаются чаще, чем другие. В крайнем случае , если вы знаете , в основном каждое сообщение будетNяпяЧАСзнак равноΣязнак равно1Nпяжурнал(1/пя) . Тогда вы можете использовать этот суперэффективный код: a 0 , x 1 x в противном случае. Тогда ожидаемая длина сообщения в основном 1 , который является удивительным, и это будет очень близко к энтропии H . Тем не менее, H является нижней границей, и вы действительно не можете победить, независимо от того, как сильно вы пытаетесь.aзнак равно000111010101a0Икс1Икс1ЧАСЧАС

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

Алексис Бессесснер
источник
13
Боже, я звучу глупо, когда ты притворяешься мной. Слава богу, я могу гордиться обнаружением энтропии. Шутки в сторону, это хороший ответ - если бы только тон не был так окрашен насмешкой.
6
Я не собирался издеваться, просто подыгрывая идее «схемы 14-летнего мальчика для потрясающего алгоритма сжатия». :)
Алексис Бессесснер
3
Мне это тоже не показалось насмешливым :) Это довольно распространенная схема объяснения проблем в популярной науке (и некоторых других областях), хотя верно то, что "спрашивающий" - это обычно Алиса или Боб, а не "настоящий" человек: D Посмотрите, как легко вы можете внезапно понять, насколько сложный вопрос на самом деле! (не говоря уже о том, что когда я обдумываю сложную проблему в моей голове, я использую тот же процесс - внутренний диалог удивительно хорош в симуляции «больше голов знает больше»)
Luaan
2
@ SteveJessop, это ложная дихотомия, и давайте не будем туда идти. Это хороший ответ, и я, возможно, слишком чувствителен, вот и все.
3
@chipmonkey, я думаю, что это все еще покрыто ответом Алексис об "игре энтропии". Возможно, количество алгоритмов, требуемых для этого, было бы настолько большим, что количество битов, необходимых для указания того, какой из них использовался, сводило на нет преимущества.
21

2N-1N2NN

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

Юваль Фильмус
источник
Я никогда не смотрел на это таким образом, но это пришло ко мне: в основном, Шеннон говорит, что даже самый лучший случай не может быть сжат произвольно, и Принцип Голубиного Отверстия гарантирует, что должен быть худший случай, который не может быть сжат вообще. Это разумная характеристика?
Йорг Миттаг,
1
Лучший вариант всегда можно сжать, так как вы можете включить некоторую строку в качестве специального случая вашего алгоритма сжатия. Этот аргумент работает не только для наихудшего случая, но и для среднего случая, показывая, что среднее сжатие составляет максимум 2 бита.
Ювал Фильмус
Ах, конечно. if input.empty? then output_very_long_stringдал бы бесконечную степень сжатия в лучшем случае. На самом деле, есть даже алгоритм сжатия, который использует это. (Я забыл название, к сожалению) . Он предназначен для очень коротких строк, и она имеет специальные кодировки для жестко закодированных подстрок , как http://, www., .comи так далее.
Йорг Миттаг
Могу ли я опровергнуть этот аргумент, если у меня есть способ спроектировать семейство PRNG таким образом, чтобы последовательности, которые они не могли выразить, были теми, которые я исключаю заранее? (шумоподавляющие источники на ум).
3
H=япяLог1/пяпяЧАС
7

sК2КN2NNs

(Как отмечается в другом ответе, это произойдет для любой выбранной вами функции сжатия.)

Луис
источник
Само по себе это не доказывает, что я не могу создать PRNG, который просто генерирует выбранную последовательность в качестве одного из возможных выходных данных, при этом для этого требуется гораздо меньше битов. Как я понимаю из других ответов, энтропия доказуемо устанавливает нижнюю границу количества требуемых битов. То есть, я просто не могу добиться сколь угодно хорошего для выбранной мной последовательности.
Все это говорит о том, что если вы создадите свой любимый PRNG, то я могу прийти к вам с последовательностью, которую он не производит, которая уже разрушает вашу идею. Более сильное утверждение состоит в том, что есть последовательности, которые вообще не создаются какой-либо более короткой программой. (Другими словами, вы все равно проиграете, даже если я позволю вам изменить свою функцию после просмотра моей последовательности. Это то, на что ссылается Ювал с «колмогоровской сложностью».)
Louis
4

Помимо других уже отвеченных пунктов, я просто хочу добавить эту ссылку: https://www.schneier.com:443/blog/archives/2009/09/the_doghouse_cr.html

Теперь годовой выход энергии нашего Солнца составляет около 1,21 × 10 41 эрг. Этого достаточно, чтобы обеспечить около 2,7 × 10 ^ 56 однобитовых изменений на нашем идеальном компьютере; достаточно изменений состояния, чтобы поставить 187-битный счетчик через все его значения. Если бы мы построили сферу Дайсона вокруг Солнца и захватили всю его энергию в течение 32 лет без каких-либо потерь, мы могли бы привести компьютер в действие до 2 ^ 192. Конечно, у него не останется энергии для выполнения каких-либо полезных вычислений с этим счетчиком.

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

user1186178
источник
1

Очень быстрое доказательство того, что универсальный компрессор не может существовать. Предположим, вы делаете один и сжимаете вход. Теперь итеративно сжимайте вывод вашей программы. Если вы всегда можете уменьшить размер, он будет становиться все меньше и меньше на каждом шаге, пока вы не уменьшитесь до 1 бита.

Вы можете утверждать, что, возможно, выходные данные вашего алгоритма имеют такую ​​структуру, что они не могут быть сжаты больше, но тогда вы можете просто применить детерминированный случайный порядок * перед повторным сжатием.

Сноска. Некоторые детерминированные тасования действительно помогают в некоторых схемах сжатия: http://pytables.github.io/usersguide/optimization.html?highlight=shuffling#shufflingoptim

Davidmh
источник
Я думаю, вам не хватает того, что с каждым сжатым сообщением sсвязано семя . Сообщение 01001011 с ´s´, равным 2348, будет отличаться от того же сообщения с ´s´, равным 3924. Если я сам каким-либо образом не понял алгоритм foo1899.
Азейра
1

Использование PRNG для «сжатия» в основном полезно в одной ситуации: когда необходимо использовать «случайный» набор данных и компактно записывать, какие данные были использованы. Большинство псевдослучайных генераторов могут генерировать только крошечную долю возможных последовательностей, но если нужно только небольшое или умеренное количество «случайных» последовательностей, доля возможных последовательностей, которые может генерировать PRNG, часто будет более чем адекватной.

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

Supercat
источник
Таким образом, PRNG используются для компактного представления (псевдо) случайных данных, например, для повторяемости экспериментов.
Юваль Фильмус
1
@YuvalFilmus: Точно. Они также могут быть использованы в некоторых ситуациях, таких как генерация уровней в видеоиграх, где небольшая часть сгенерированных уровней будет считаться приемлемой, но когда разработчик видеоигр может генерировать уровни случайным образом, пока он не найдет те, которые ему по вкусу, и записать семена, которые сгенерированные те. Исторически очень полезная концепция, когда кодируешь игровой автомат с 128 байтами ОЗУ, пытаясь уместить программу в картридж с 4096 байтами ПЗУ.
суперкат
Это очень хороший пример, он соответствует схеме, описанной мной для поиска «хорошего» начального числа, но использует тот факт, что в этом сценарии много возможных сообщений являются хорошими.
@ foo1899: Кстати, игра «Pitfall» en.wikipedia.org/wiki/Pitfall ! использовал вышеупомянутую технику для создания 256-экранной карты на игровом картридже 4K на машине с 128 байтами оперативной памяти.
суперкат
1

Что-то, что следует рассмотреть, чтобы добавить к какофонии ответов, которые утверждают, почему есть некоторые строки, которые не могут быть сжаты из-за, по определению, инъективной природы декомпрессии, и ограниченная вселенная сжатых строк, из которой можно выбирать для представления сообщений, такова: большинство строк не могут быть сжаты, потому что существует намного больше энтропийных, неупорядоченных строк, чем более низких энтропийных и структурированных, поэтому возникает условие, которое мы видим на практике: сжатие в большинстве случаев полезно, так как сообщения, которые мы наиболее часто желающими сжиматься являются те, которые чаще всего обладают некоторой аликвотой порядка и структуры и, таким образом, являются частью очень маленькой вселенной объектов с более низкой энтропией. Это означает, что, выбрав подходящую выходную длину, возможно, мы можем сжать все в меньшей структурированной вселенной. Термины структурированный, энтропийный и упорядоченный здесь намеренно неточны, чтобы отразить субъективные определения семантики и полезности сообщений, которые мы можем захотеть сжать.

И в прямом ответе на вопрос спрашивающего: * да, вам, конечно, может повезти, и вы обнаружите, что вывод вашего PRNG - это именно то сообщение, которое вы хотите сжать, просто вы так часто не обнаружите, что это так, потому что Само свойство, которое характеризует PRNG, а именно его способность создавать (почти) бесконечное разнообразие различных строк, делает его одновременно непривлекательным для производства вашей.

Конечно, вы можете уменьшить эту вероятность, используя PRNG для обхода «графа домена» переходов между словами, и вы значительно увеличите вероятность появления вашего сообщения, а также обнаружите, что теперь вы должны добавить граф домена в сжатое сообщение. длина.

Cris
источник