Парадигмы эмо-программирования

[RayShade]

Вон с российской эстрады!

На*** с пляжа!

[jangle]

Фу, как нецивилизовано, надо проявлять больше толерастии!

[jangle]

А-а-а! Жесть! В недрах моей нездоровой фантазии был рожден данный эмоциональный код. Запускаем и плавно фигеем

Код: Выделить всё

#Compile Exe
#Dim All

Function PBMain () As Long
  Local R As Long

  Randomize Cvs(Chr$(4,250,69,45))
     For  r = 1 To 6
         Print Chr$(Rnd(65,88));
     Next r
     Print " "

    Randomize Cvs(Chr$(1,64,241,237))
      For  r = 1 To 5
           Print Chr$(Rnd(65,83));
       Next r
     Print " "
 
   Randomize Cvs(Chr$(2,210,122,195))
      For  r = 1 To 6
           Print Chr$(Rnd(65,88));
       Next r
      Print " "
  WaitKey$

End Function

Кто-нибудь хочет об этом поговорить? Объяснить суть явления...

[jangle]

Вот тут товарищ, называет это методом Денисова, с таким же успехом, можно назвать методом Jange.
Поскольку до этой "светлой" идеи, додумался самостоятельно. Мысли у дураков сходятся

http://samara.chat.ru/

Я не математик, так что извините, если что не так Метод был придуман в начале 90-х годов Денисовым В.Е. И первая реализация была осуществлена коллективом ТОО "Гамма-фильм тем самым, чьи игры выходили из издательства Gamos.
Идея метода проста - представить последовательность байт a1,a2,?an. Как результат работы некоторой функции F(x1,x2,..xn).
То есть:
F1(x1...xn)=a1
F2(x1..xn)=a2
и т.д. в итоге Fn(x1..xn)=an. Если набор аргументов x1..xn в памяти компьютера занимает объём меньше чем a1..an то на лицо происходит сжатие данных.
В качестве функции был взят генератор случайных чисел, который по Кнуту имеет вид:
Хn=(a*Xn-1 +с) mod m.
Данная функция давала возможность при использовании аргументов получать последовательности по размеру больше размера аргументов. Первоначально данный метод применялся на 286-х для сжатия картинок. Тогда он полностью провалился, так как либо подбор аргументов происходил слишком долго, либо коэффициент сжатия был слишком низкий. Да и идеальная картинка для этого метода должна выглядеть как набор случайных пикселей. В таком случае последовательности достигали длинны в 70-80 байт притом, что в качестве аргументов использовались 4-х байтные числа. А подбор таких последовательностей шёл несколько суток.
Прошло 10 лет и вот долго собираясь, решил я проверить этот метод на моём PII-450.
И так метод является методом ?сжатия? без потерь. Идеально должен работать на файлах с минимальным кол-вом повторяющихся элементов - я пробовал на *.png.
В качестве первого приближения взял в качестве генератора стандартный перловский rand.
Алгоритм такой:
1) Задаётся $KS отвечающее за коэффициент сжатия и соответственно за время работы
2) Из исходного файла берём $KS байт
3) Генерируем случайным образом начальное значение $Start
4) Генерируем последовательности длинной $KS с srand($Start)
5) Если последовательности совпадают, записываем $Start в конечный файл, иначе возвращаемся в пункт 3
6) Если не конец файла возвращаемся в пункт 2
На выходе имеем файл, состоящий из начальных значений.
Результаты тестирования такие:
Последовательность в 3 байта ($KS=3) подбирается от 20с до 2 -х минут при длине $Start в 2 байта. На более длинные последовательности у меня не хватает терпения:)

Где можно применять данный метод?

Я пока вижу две области:
1) прямое назначение - компрессия. Но применять его надо поверх любого алгоритма, который уменьшает кол-во повторяющихся элементов, например LZW.
2) Криптография - представим, что в формуле из Кнута начальное X0 достаточно длинное число, например в 256 бит, тогда изъяв его из конечного файла, мы получаем файл, раскрыть который достаточно сложно, тем более что на входе мы работаем не с исходными данными, а обработанными и приведёнными к виду с наименьшим числом повторений.
3) При применении повторно снова можно получать компресиию. В теории вообще получается что если неоднократно применять данный метод то можно получить в конечном итоге одно стартовое значение, кожффициент сжатия и кол-во применений алгоритма к файлу.

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

[jangle]

Вероятно с помощью этого алгоритма, можно сжать "Войну и Мир", в одно число

[Debugger]

Конечно.
Сжатие до 1 числа - это такой бред. Попробуйте запихнуть rar-ку в rar-ку и так далее. Сжатие будет сильнее? Сомневаюсь.

[iGrok]

Конечно.
Сжатие до 1 числа - это такой бред. Попробуйте запихнуть rar-ку в rar-ку и так далее. Сжатие будет сильнее? Сомневаюсь.

И правильно делаешь. А вот с помощью этого алгоритма ДЕЙСТВИТЕЛЬНО можно сжать войну и мир в одно число.
Только вот процесс "сжатия" займёт несколько лет...

[jangle]

Конечно.
Сжатие до 1 числа - это такой бред. Попробуйте запихнуть rar-ку в rar-ку и так далее. Сжатие будет сильнее? Сомневаюсь.

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

Вот ниже примерчик, при 8 байтах входных параметров, генератор выдает 10 байтную строчку HELLO WORLD
Это уже компрессия! Причем подбирается такая последовательность всего пару минут.
Можно вообще сжимать - уже сжатый архив, который обычными методами, невозможно уменьшить даже на 1 бит (!)
А этому алгоритму по-фигу, он просто ищет нужную последовательность гаммы, перебирая сотни миллионов вариантов входных параметров для генератора.
Единственное, что нужно для создания такого супер архиватора - неисчерпаемые вычислительные ресурсы, т.е. квантовый компьютер.
Но если это удасться сделать, это будет как полет со сверхсветовой скоростью...

Код: Выделить всё

#Compile Exe
#Dim All

Function PBMain () As Long
  Local R As Long
      Randomize Cvs(Chr$(1,122,19,22))
        For  r = 1 To 5
           Print Chr$(Rnd(65,88));
        Next r
        Print " " ;

      Randomize Cvs(Chr$( 1,  74,  137,  195))
        For  r = 1 To 5
           Print Chr$(Rnd(65,88));
        Next r
        Print " "
  WaitKey$
End Function

[ANDLL]

можно найти такое стартовое число, и такой генератор,

Дык, сладкий мой, "генератор" это то же информация, которая то же имеет объем.
Сразу чувствуется гуманитарный склад ума - ни малейшей попытки анализа.
Тут уж определись - что будет в твоем "архиве"? Затравка генератора, или еще и сам генератор?

[alibek]

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

Ты просто фразу где-то услышал "квантовый компьютер", или как?

[jangle]

генератор" это то же информация, которая то же имеет объем.
Сразу чувствуется гуманитарный склад ума - ни малейшей попытки анализа.
Тут уж определись - что будет в твоем "архиве"? Затравка генератора, или еще и сам генератор?

Ты же не пересылаешь дистрибутив WinRar`a вместе с каждым архивом. У получателя информации уже установлен архиватор (генератор). По каналу связи - передаем стартовое число для генератора. Получатель генерирует с его помощью гамму - которая собственно и является передаваемым сообщением.
По моему, тут все логично.

Ты просто фразу где-то услышал "квантовый компьютер", или как?

Статья в википедии

[ANDLL]

Ты же не пересылаешь дистрибутив WinRar`a вместе с каждым архивом. У получателя информации уже установлен архиватор (генератор). По каналу связи - передаем стартовое число для генератора. Получатель генерирует с его помощью гамму - которая собственно и является передаваемым сообщением.

То есть генератор(функция) будет один для всех последовательностей? А передавать будешь одну лишь затравку?

[jangle]

То есть генератор(функция) будет один для всех последовательностей? А передавать будешь одну лишь затравку?

Ну да, к примеру передаем по каналу связи 4 байта: 1, 122, 19, 22

Они становятся стартовыми параметрами для генератора:

Код: Выделить всё

Randomize Cvs(Chr$(1,122,19,22))

Затем генерируем гамму из 5 байтов:

Код: Выделить всё

For  r = 1 To 5: Print Chr$(Rnd(65,88)):Next r

И получем строку: HELLO

В итоге, по каналу связи нам передали 4 байта, а мы восстановили из них 5 байт.

[karlex]

Вероятно с помощью этого алгоритма, можно сжать "Войну и Мир", в одно число

Одно число понятие растяжимое, сколько циферок будет в этом числе?
Так же можно и результат сжатия RAR'ом назвать "одним числом", почему бы и нет?

[ANDLL]

Ну да, к примеру передаем по каналу связи 4 байта

А развер "числа" всегда фиксированный или каждый раз разный?

[jangle]

Одно число понятие растяжимое, сколько циферок будет в этом числе?
Так же можно и результат сжатия RAR'ом назвать "одним числом", почему бы и нет?

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

[ANDLL]

Вопрос был
А размер "числа"(для данного конкретного генератора) всегда фиксированный или каждый раз разный?

[jangle]

А развер "числа" всегда фиксированный или каждый раз разный?

Допустим фиксированный размер, всегда из 4 байтов - будем восстанавливать только 6 байтов сообщения.

В 4 байта, можно уместить 4,294,967,295 вариантов стартового числа для генератора. Т.е. с высокой степенью вероятности, можно сказать, что например для любого слова из 6 букв на английском языке (27 символов в алфавите), есть 4-байтовое стартовое число которое сгенерирует его.

[ANDLL]

То есть ты предлагаешь алгоритм сжатия шести байт в четыре?

[jangle]

То есть ты предлагаешь алгоритм сжатия шести байт в четыре?

Cжатие 6 байт в 4 - это уже 25% компрессия. Но поскольку данному алгориму плевать на энтропию, он может сжимать уже пожатые тексты. Например, сначала сжимаем текст самым лучшим классическим LZW алгоритмом, а потом уже этим.

[ANDLL]

Я надеюсь понятно, что алгоритма который сжимает произвольные 6 байтов в 4 не существует в природе?
То есть некоторые "шестерки" байтов ты будешь сжимать до четырех, а некоторые - не будешь сжимать.
Вопрос - с чего ты взял что в исходных данных(которые скажем zip-архив) "сжимаемых" шестерок окажеться сколько нибудь существенное количество?

[pronto]

Сжимаемых "шестерок" будет ровно 2^32?

[ANDLL]

По крайней мере их не может быть больше

[Debugger]

Интересно.
Когда я писал MD5 брутер, я столкнулся с одной неожиданной вещью. Закодировав одну строчку (длинную) и сбрутив ее перебором, я получил совсем другую. Причем ее хэш равнялся хэшу первоначальной строчки.
А теперь докажи, что твои 4 байта будут обязательно раскодированы как определенные 6. ИМХО, есть вероятность, что результат раскодирования будет не равен исходному. Подумаем логикой. Если ко всем 6-байтным последовательностям повесить уникальные номерки, то их количество нельзя запихать в 4 байта.
P.S. Представил себе такое: седой jangle передает дискетку в 1 Мб своим внукам и говорит: "Вот, детки, я закодировал все русскую литературу своим знаменитым алгоритмом. Это последняя копия "Войны и мира". Я поместил все сюда". Детки втыкаю дискетку и начинают раскодировать (тогда уже будут "квантовые компьютеры"). На каком-то этапе раскодирования произойдет сбой, о котором говорилось выше. И бедные детки получат не книжку, а беспорядочный набор символов.

[jangle]

Я надеюсь понятно, что алгоритма который сжимает произвольные 6 байтов в 4 не существует в природе?

Ну конечно, нельзя закодировать 6 байтов (0..255) - 4 байтами (0..255). Это понятно

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

Сжатые данные - очень похожи по статистическому распределению на псевдослучайную последовательность.
Из-за этого, такая гамма практически несжимаема обычным архиватором. Поэтому, предлагаю пытаться подбирать 4 байтовые аргументы для генерации "шестерок".

А вот несжатый текст типа: AAAAAA, BBBBBB, CCCCCC, DDDDDD - практически нереально подобрать

[RayShade]

Сложность реализации этой задачи не соответствует пользе от ее разрешения Сейчас уже архиваторы-то по моему и не так нужны, кругом и места и пропускной способности навалом Не то что раньше -- запихни побольше файлов на 1.44 дискету

[jangle]

Интересно.
А теперь докажи, что твои 4 байта будут обязательно раскодированы как определенные 6. ИМХО, есть вероятность, что результат раскодирования будет не равен исходному. Подумаем логикой. Если ко всем 6-байтным последовательностям повесить уникальные номерки, то их количество нельзя запихать в 4 байта.

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


Кстати подобрал свой ник! Из 4 байтов 1,153,128,181 генерируется 6 байтовое слово - JANGLE

Код: Выделить всё

#Compile Exe
#Dim All

Function PBMain () As Long
  Local R As Long
      Randomize Cvs(Chr$(1,153,128,181))
        For  r = 1 To 6
           Print Chr$(Rnd(65,78));
        Next r
        Print " " ;
  WaitKey$

End Function

[Debugger]

А ты напиши лучше универсальную программу. Вводишь 4 числа, вводишь длинну (кстати, это больше 4 байт тогда) и он выдает строчку.

[ANDLL]

Сжатые данные - очень похожи по статистическому распределению на псевдослучайную последовательность.

Хотелось бы увидеть обоснование

[jangle]

Хотелось бы увидеть обоснование

Cсылку искать лень, но это так.
-----------------------------------------------------------------------------------------------------
Подумал я тут немного, идея оказывается дурацкая и глупая. Короче говоря, забудьте все, что я тут написал