О сжатии, информационной энтропии и искусственном интеллекте

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

Забавно, у xzip получился 50МБ файл.

http://en.wikipedia.org/wiki/Comparison_of_archive_formats

http://en.wikipedia.org/wiki/Comparison_of_file_archivers

А ничего, что твоя программа на разных платформах может сгенерить разные файлы? Архиватор должен учитывать все варианты реализации функции sin на всех платформах?

все варианты реализации функции sin

Внезапно, платформозависимый синус!

Я про ошибки округления.

//К. О.

Вот скажи, ты наверняка же РПЦ за мракобесие критикуешь? И угараешь над тупостью политиков и чиновников?) Если нет, то извини за критику. Но ты написал просто дикое мракобесие.

Это пока не критика. Критика будет, когда будет конкретика. Какой конкретно пункт не устраивает? Метод генетического программирования не сможет по набору данных определить, что это синус? Или он будет эффективно работать на реальных данных для сжатия? Или он не является методом оптимизации?

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

да. В 70..80х годах прошлого века многие делали, но профита не получилось. IRL такие последовательности почти не встречаются, а то что встречается, описывается формулами намного сложнее самого сообщения.

Дополнение: вспоминать об аудиокодеках не стоит, т.к. речь идет о сжатии без потерь.

и что? Звук тоже сжимают без потерь. ape,flac,wavepack... Только у вас не звук, а регулярные обрывки синусоиды. Такое очень тяжело угадать. Потому-что встречается только в подобных программах. Потому-и gzip не берёт.

И да, попробуйте bzip2, там BWT, он иной раз вытаскивает такие хитрые контексты.

Скажем, то же генетическое программирование в данном случае бы нашло тот самый синус

это если-бы ты научил его искать синусы.

Но если бы сигнал был сложнее, поиск мог бы затянуться на неопределённое время.

ВНЕЗАПНО: поиск и так _может_ затянутся на ЛЮБОЕ время.

существуют ли ... универсальные алгоритмы... для сжатия?

Спектральное сжатие, основанное на преобразовании Карунена-Лоэва, базисные функции которого есть собственные векторы ковариационной матрицы входного сигнала.

Внезапно, платформозависимый синус!

смирись. оно так. даже 1/3 и то платформозависима.

Ну и в догонку посмотри на алгоритмически неразрешимые задачи, идеальный архиватор одна из них, правда сформулирована она замысловато (ирония), в терминах колмогоровской сложности.

Но ты написал просто дикое мракобесие.

ты не в теме. Написан научный метод сжатия. Известный более полувека.

это если-бы ты научил его искать синусы.

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

ВНЕЗАПНО: поиск и так _может_ затянутся на ЛЮБОЕ время.

Может. Вопрос в вероятности затягивания.

Вот эта софтина мне в своё время нравилась для подобных вычислений: http://formulize.nutonian.com/ .

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

Метод генетического программирования не сможет по набору данных определить, что это синус?

это сложный вопрос. Можно сделать ГА который распознаёт синусы/косинусы. Но он сломается на логарифме и даже на прямой. ВСЕ функции ты по любому не вобьёшь. Даже не думай.

Или он будет эффективно работать на реальных данных для сжатия?

может будет, а может и не будет. Если будет, то время работы неопределено.

это сложный вопрос. Можно сделать ГА который распознаёт синусы/косинусы. Но он сломается на логарифме и даже на прямой. ВСЕ функции ты по любому не вобьёшь. Даже не думай.

Очевидно, самая обычная дилемма между скоростью работы/качеством сжатия и размером словаря. Например, ту же синусоиду можно аппроксимировать прямыми с какой угодно точностью. Но результат может весить больше, чем исходный файл при условии сохранения всех бит сообщения.

Ну и в догонку посмотри на алгоритмически неразрешимые задачи, идеальный архиватор одна из них, правда сформулирована она замысловато (ирония), в терминах колмогоровской сложности.

ты всё перепутал. У меня вот в компьютере есть архиватор, который сжимает ЛЮБОЙ файл в 32 байта.

У меня вот в компьютере есть архиватор, который сжимает ЛЮБОЙ файл в 32 байта.

Теперь бы научить его разжимать.

Очевидно, самая обычная дилемма между скоростью работы/качеством сжатия и размером словаря. Например, ту же синусоиду можно аппроксимировать прямыми с какой угодно точностью. Но результат может весить больше, чем исходный файл при условии сохранения всех бит сообщения.

тут дело не в этом. Посмотри внимательно на код ТСа: он берёт синусы от целого числа радиан. Вот что получается:

$ for ((i=0; i<17; i++)); do echo "s($i)" | bc -l; done
0
.84147098480789650665
.90929742682568169539
.14112000805986722210
-.75680249530792825137
-.95892427466313846889
-.27941549819892587281
.65698659871878909039
.98935824662338177780
.41211848524175656975
-.54402111088936981340
-.99999020655070345705
-.53657291800043497166
.42016703682664092186
.99060735569487030787
.65028784015711686582
-.28790331666506529478

У меня вот в компьютере есть архиватор, который сжимает ЛЮБОЙ файл в 32 байта.

Теперь бы научить его разжимать.

считатели биткоинов этим и занимаются. Архиватор называется sha256.

тебе ещё надо, что-бы ГА распарсил, что это действительно синусоида. Функция рваная, и ГА тут будет несколько тысяч лет копаться, если ручками не подсказать.

Проверил. Эврика справилась за секунду.

считатели биткоинов этим и занимаются. Архиватор называется sha256.

Да я понял. Но распаковка подразумевает однозначность, потому нет.

Метод генетического программирования это наукообразие, использованный тобою для красного словца. Ты хотел сказать, что нам нужно просто выбрать некий набор функций, определить их возможные композиции, а потом на этом пространстве произвести поиск такой комбинации, которая лучшим способом описывает входную последовательность, например минимизируя квадратичную невязку. Вот как ее минимизировать, хоть приблизительно — это вопрос. И если не получается найти метод, который это делает хотя бы с гарантией сходимости и оценкой зазора между найденным оптимум и истинным, вот тогда начинают использовать всякую хреновую муть, как генетическая оптимизация.

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

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

Я не уловил, о чем ты.

если ручками не подсказать.

Проверил. Эврика справилась за секунду.

подсказали.

Она у тебя наверняка натаскана на элементарные функции. Вот только функция не обязана быть элементарной, и даже вообще функцией.

Да я понял. Но распаковка подразумевает однозначность, потому нет.

где там «не однозначность»? Даже к md5 коллизию никто не подобрал, а уж с sha256 и гадать нечего.

Почему ты считаешь, что последовательность, к которой поэлементно применены элементарные функции(выбранные человеком) будет для природы менее случайной?)

Ну хоть кто-то про Kolmogorov complexity вспомнил, которая невычислима.

Метод генетического программирования это наукообразие

ГА это самый обычный численный метод.

Ведь генетический алгоритм на практике никогда не найдет описанный ОПом ряд, если у него в множестве операторов нету тригонометрических функций(они же ряды на самом деле).

нет. Тригонометрические функции это НЕ ряды. Это вращение. ГА _может_ найти синусоиду без всяких рядов.

Да, именно тот «метод сжатия Бабушкина», которого во всех интернетах любят опускать и стебать.

и кстати зря быдло смеётся. Бабушкин описывает самый обычный арифметик. Только он там нихрена не понял, когда ему кто-то рассказывал. Ну и не знает, болезный, что методу 100 лет в обед. А метод на самом деле годный.

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

О сжатии, информационной энтропии и интеллекте

Человек. Например, сейчас он сжал 77Мб информации в 374 байта.

Я не уловил, о чем ты.

идея «подобрать формулу для сжатия» стара как мир. Её каждый год «открывают». Это как вечный двигатель или философский камень, только в CS.

Но это еще не значит, что её не существует.

Нет не самый обычный. Если используешь его в научной работе, то это полный зашквар)

Ну и не знает, болезный, что методу 100 лет в обед. А метод на самом деле годный.

Что за метод? Что там годного?

По-моему я примерно это и описал. Значит мы пришли к консенсусу?

Бонус: сжатие и подбор правильного базиса --- почти эквивалентные понятия)

Ну хоть кто-то про Kolmogorov complexity вспомнил, которая невычислима.

на практике невычислима ТОЧНАЯ сложность. Но легко вычислить любое приближение. На сегодня предел практически достигнут. Т.ч. суперархиваторов не будет.

Но это еще не значит, что её не существует.

я тебе больше скажу: очень просто доказать, что коллизия существует(всего есть 2**256 сумм, но если в сообщении скажем 257 бит, то сообщений 2**257, т.е. в среднем коллизия есть у _каждого_ сообщения)

Вот только алгоритма подбора нет и не предвидится.

Нет не самый обычный. Если используешь его в научной работе, то это полный зашквар)

обычный. Просто его сходимость в принципе не имеет смысла. Если он сошёлся, значит тебе повезло. Если нет — может не повезло, а может просто решений нет.

Ну и не знает, болезный, что методу 100 лет в обед. А метод на самом деле годный.

Что за метод? Что там годного?

http://en.wikipedia.org/wiki/Arithmetic_coding

По-моему я примерно это и описал. Значит мы пришли к консенсусу?

угу.

Если он сошёлся, значит тебе повезло. Если нет — может не повезло, а может просто решений нет.

Вот вот, это не научный метод. Приличный метод даёт некоторые гарантии на сходимость.

http://en.wikipedia.org/wiki/Arithmetic_coding

Я знаю что такое арифметическое кодирование, но никак не приложу ума, как оно связано с «кодированием Бабушкина». Если ты предлагаешь брать иррациональное число как генериующую модель, то ладно;)

Я знаю что такое арифметическое кодирование, но никак не приложу ума, как оно связано с «кодированием Бабушкина». Если ты предлагаешь брать иррациональное число как генериующую модель, то ладно;)

я не очень понял его разъяснения, но очень похоже. Ну как мне показалось. А про модель он вроде ещё не думал :)

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

Ну хоть кто-то про Kolmogorov complexity вспомнил

+1

Она у тебя наверняка натаскана на элементарные функции. Вот только функция не обязана быть элементарной

Ну дак подними глаза и осознай, что я об этом предупреждал.

где там «не однозначность»? Даже к md5 коллизию никто не подобрал, а уж с sha256 и гадать нечего.

Подбирать не надо. По объёму данных вполне можно прикинуть их количество, чего вполне достаточно.

где там «не однозначность»? Даже к md5 коллизию никто не подобрал, а уж с sha256 и гадать нечего.

Подбирать не надо. По объёму данных вполне можно прикинуть их количество, чего вполне достаточно.

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

Даже к md5 коллизию никто не подобрал, а уж с sha256 и гадать нечего.

Где-то давно видел ссылку то ли на двойную коллизию md5, то ли на тройную - потерял... А пока имеем http://www.mscs.dal.ca/~selinger/md5collision/

А пока имеем http://www.mscs.dal.ca/~selinger/md5collision/

ничего ты не имеешь.

ты хоть по ссылке сходи, а потом подбери мне коллизию скажем к e28f0be3346162fffa121e2f768aa0aa, ну и возвращайся. Как подберёшь.

На практике всё однозначно, и коллизий не существует

Блажен кто верует.

Блажен кто верует.

я верю математикам. Они говорят, что вероятность ничтожна, и её не нужно учитывать на практике. Если уж ОЧЕНЬ хочется НАДЁЖНОСТИ, есть цифровая сигнатура, именно для этого.