Естественные науки

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

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

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

Ну, а что если предложить другие методы сжатия? Например те, которые представляют собой NP задачи, требуют большого количества энергии на решение, но обеспечивают сжатие более чем в тысячу раз ? (Например, сжатие 1Гб до 1Мб).

Например, поиск наименьшего математического выражения, вычисляя которое получается исходная информация. К примеру, такое x = 999999999^999999999 (число, полученное в итоге занимает 3,5 Гб памяти) или вот такое x = (10^9 !)!.

Если разобраться, чисто теоретически можно сжать 2^2^20 различных вариантов информации весом в 1Гб до 1Мб. Это комбинаторное ограничение
Николай Попов
Николай Попов
128
Предположим, будем искать выражение только одним способом, например, в виде m^n. Тогда мы не сможем одинаково равномерно сжать все числа в заданном диапазоне. Например, простые числа при таком представлении только удлиняются. Хотя в отдельных случаях сжатие будет колоссальным, это будет достигнуто за счёт слабого сжатия в других случаях и удлинения в третьих случаях.

Если же использовать различные формулы с целью перекрыть весь диапазон чисел, то с каждым числом придётся передавать код формулы, что губит всю идею.
"Больших семь шапок из овцы не выкроишь никак".

Если интересна эта тема, копайте лучше в сторону осмысленности информации. Например, большинство гласных в тексте можно убрать и получатель сможет этот текст восстановить..
ОП
Олег Подкорытов
74 293
Лучший ответ
Вера Свистун про гласные - так именно это по факту и делают обычные архиваторы, и гораздо большее делают.
Николай Попов Почему губит всю идею? Не нужно заранее предопределять вид выражения, в которое будет разложено число, нужно лишь указать ограничения на операторы и размеры чисел, которые в этом выражении и фигурируют.

Ваша последняя фраза - теория Шеннона, читайте внисательнее
Николай Попов "Больше семи шапок из овцы не выкроишь никак" - читайте мое последнее предложение. Вы не сможете сжать все различные варианты 1Гб информации до 1Мб, есть тому комбинаторный предел. Разумеется, что 2^(8 * 2^30) вариантов информации не поместить в 2^(8 * 2^20) вариантов. Однако, даже это число комбинаций настолько велико, что меньше песчинок в океане, чем вариантов информации 1Гб, которую можно уместить в 1Мб
какие проблемы! напишите сами архиватор - многое поймете.

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

а белый шум - вообще не сожмете, что очевидно по тому, сколько есть возможных равновероятных значений.
ВС
Вера Свистун
89 543
Николай Попов Опять же, то, о чем вы говорите относится к теории Шеннона. Почитайте про алгоритмическую информацию и Колмагоровскую сложность.

Так и занимаюсь написанием такого архиватора. Речь о том, есть ли в этом смысл? Недумаю, что я такой умник, много людей этим вопросом занимались.

Приведите убедительную аргументацию)
в 2012 году срочно понадобилось с заполярья передать информацию в исходнике - ЛИС формате 600 мбайт по спутниковому. ЛИС (лабораторный измерительный формат) изначально предельно сжатый, не одна программа более чем на 10% его не сжимает. С той скоростью которая в те годы для заполярья была доступна 1,2 мбайт в час, передать его было нереально. Но мой программист выкрутился и сжал в 60 раз. Через месяц он уже стал работать в закрытой системе.
Александра Кравченко
Александра Кравченко
8 197
Вера Свистун готовые программы работают только с текстом, ни изредка - с растрами. потому, если сигнал имеет другую природу, его можно сильнее сжать своим алгоритмом. я так сжимал аналоговые сигналы для медиков.

но это никакое не суперсжатие, шеннона не обойдешь.

Похожие вопросы