Comments 79
Я такой архиватор в молодости на ASM-е написал. Но разархиватор к нему не успел. На работу устроился.
Да чтож такое!!! Я тоже студентом делал. Тогда только только появились первые модемы на 1200 бод и размер файлов был очень актуальной метрикой...
Да вообщем то есть продукты которые такую архивацию используют. Вот только работают в распределенном режиме и по блокам - зачем подбирать хеш индивидуально если можно спросить через DHT узлы, не знает ли кто то из них блоки подходящие под конкретный хеш. Вот только Злые Силы активно противодействую внедрению прогрессивных технологий, пробуют запретить (с переменным успехом) хеши соответствующие и софт.
Предлагаю сократить сжатие до одного бита - так ещё эффективнее)
Наконец то настоящий CS на портале!
Для особо ценных данных можно использовать sha512.
Сегодня ж не 1 апреля.... А не, 1 апреля :)
А если я возьму все возможные хеши, положу их в файлы, он на выходе по сути даст мне все эти ключи но в другом порядке, а вы говорите что я фильм Шрек получу на одном из них. Нестыковочка
А, вижу там еще длина файла участвует, ну если есть гарантия что sha256 на одной длине файла всегда даст разный результат, то в принципе вариант рабочий. Но это если очень смущает
Есть вариант получения Шрека из любого хэша, пусть распакованный файл будет такого вида:
4 байта - длина файла
~60ГБ - полезные данные (Шрек 2)
32 байта Nonce (случайное число)
В таком случае даже из хэша 0xFFFFFFFF... рано или поздно можно распаковать и Shrek 2 и Мадагаскар и Тачки 3.
Однако, кажущейся проблемой неоднозначность распаковки (когда одному архиву соответствует несколько выходных файлов) на деле ей не является, что будет рассмотрено в следующем разделе.
тогда вот этот кусок я не понял, получается неоднозначность все же есть
Так в этом и плюс, разве нет?) Можно распаковать несколько файлов из одного архива, в какой то момент даже может быть сюжетный поворот которого не было в оригинальном фильме (вероятность этого бесконечно мала, но не 0)
на минус случайно нажал
Я бы не стал ограничиваться только снятыми фильмами.
Так мы можем распаковать и фильмы неснятые, и фильмы утраченные.
Более того - это реальный способ восстановить все книги Александрийской библиотеки и все утраченные книги Помпей!
И даже селфи динозавров!
Так это вообще демон Максвелла второго рода получается.
Демон этот магичен, термодинамичен, неклассичен и статистичен, и станет он из старого бочонка или из чиханья экстрагировать и доставлять тебе информацию обо всем, что было, что есть, что может быть и что будет.
(...)
Проблема, однако, стоит вот как: в каждой щепотке воздуха действительно складываются из атомных брыканий и кувырканий важные истины и глубокие сентенции, но вместе с тем возникают совершенно бессмысленные скачки и отскоки, и этих последних в тысячи раз больше, чем первых. Хоть и в прежние времена было известно, что вот сейчас перед твоим носом-пилой в каждом миллиграмме воздуха в любую долю секунды возникают отрывки тех поэм, которые будут написаны только через миллионы лет, и фрагменты возвышенных истин, и разгадки всех загадок Бытия и тайн его, все ж не имелось способа выделить всю эту информацию, тем более что едва лишь атомы лбами столкнутся и в какую-то осмысленную фигуру уложатся, как тут же разлетятся, а вместе с ними и смысл пропадает, быть может, навеки.
Значит, вся хитрость в том, как построить селектор, который будет отбирать только то, что в беготне атомов осмысленно. Вот и вся идея Демона Второго Рода.
(С. Лем. Кибериада, цикл «Семь путешествий Трурля и Клапауция», Путешествие шестое, или Как Трурль и Клапауций Демона Второго Рода создали, дабы разбойника Мордона одолеть.)
А если всмонить, про закон Мура про удваивание количества транзисторов на чипе каждые два года, то время распаковки существенно снижается!
Все что нужно, это во время распаковки каждые 2 года менять компьютер. При этом нужно будет сохранять где-то состояние, на котором остановились, но это это уже мелочи.
Можно улучшить распаковку - сохранять индекс на котором получили файл, и запускать повторно с этого места по запросу пользователя, тогда через X попыток распаковки гарантированно получим исходный файл. Правда, временные метрики придётся поднять до 2^N лет, но это пустяки
У вашего алгоритма может на выходе получиться не тот файл что зашифровывали, есть алгоритм куда лучше:
в файл записываем
1. номер алгоритма генерации псевдослучайных чисел
2. seed для него
3. офсет с какого числа начинать (F)
4. сколько случайных чисел генерировать (N)
При распаковке создаем генератор чисел, с нужным seed, пропускаем первые F чисел и в результирующий файл складываем следующие N чисел в виде байт, всё.
В вашем алгоритме F может оказаться слишком большим и архиватор вместо сжатия будет увеличивать файл.
Эта интересная статья навела меня на мысли...
Вот даже ваша реализация, можно же не только использовать не только seed, а в целом коэффициенты ГСПЧ. Думаю это реально посчитать для небольших файликов. Может для игр это был бы оверкил, где много маленьких файликов...
Если идея в том, чтобы использовать словарь алгоритмов рандомизации, подбирая к ним коеффициенты таким образом, чтобы на выходе получался результирующий файл - то её можно упростить до использование просто словаря с переменной длинной. Всё равно чтобы этим пользоваться вам надо столько алгоритмов и параметров, чтобы иметь возможность закодировать любую последовательность определённой длинны, иначе найдутся файлы которые вы не сможете сжать. А вообще это похоже на кадирование аудио через дискретное преобразование фурье - раскладываем сигнал на синусоиды и записываем их параметры вместо сигнала.
Вместо гспч можно использовать цифры числа пи
Так уже. https://github.com/philipl/pifs
у меня в голове вертится упрощенно такое:
> алгоритм:число итераций:метки блоков
* алгоритм - на какой основе например число Пи и длина блока
без него не получить данных, то есть очень защищено.
размер мизерный. но "высокий расход на упаковку/распаковку"
_у меня отсутствуют фундаментальные знания по информатике и математике._
и подобное наверняка уже реализовано, но почему не встречается на практике
Архиватор Бабушкина? Код на Github
Берём много-много кубитов, закидываем в коробку из-под кота, трясём и, когда хэш сошёлся (они все выпали в состояния битов исходного файла или коллизии хэша) - разархивация состоялась.
Ха! может, кто из "олдов" вспомнит - ходил году в 1993 т.н. "фрактальный архиватор". Тоже жал любой файл в 32 байта, чтоль... (на самом деле писал файл то-ли в скрытый файл, то-ли как-то по другому в файловой системе скрывал архив - а в 32 байтах просто ссылка была). Но многие на него повелись... пытались дизассемблировать и разобраться в алгоритме...
В наше время содержимое данные принято прикапывать в облаке.
А ещё много приколов было когда появилась NTFS с альтернативными потоками на файловой системе.
В наше время содержимое данные принято прикапывать в облаке.
Это, кстати, реализовано в OneDrive, но, конечно, не анонсируется как "архиватор": Экономия места на диске с функцией "Файлы из OneDrive по запросу" для Windows - Служба поддержки Майкрософт (microsoft.com)
Я сам такой делал, чтобы удивить одногруппников, мы как раз фракталами занимались. Не знал, что ещё такие были, хотя как не быть...
Кроме шуток, у меня есть похожая идея, возникшая в результате вполне реального кейса.
Сжатие - считаем хеш, смотрим в DHT (торренты и прочие p2p сети), если файл там есть - считаем что он сжат и включаем в архив хеш файла. Если нет - сжимаем как обычно.
Распаковка - если в архиве хеш, то ищем в DHT и скачиваем, если не хеш - распаковываем обычным образом.
Для всяких там дистрибутивов наверняка будут фантастические коэффициенты сжатия, потому что большинство файлов как правило не меняется.
А идея возникла вот на каком месте. На компьютерах тем или иным образом появляется множество файлов, о назначении которых пользователи могут забыть или не знать (обычно - файлопомойка в папке Downloads, но бывают и более экзотические случаи). Хорошо бы иметь сервис типа Virustotal, который по хешу файла говорил бы, что это вообще такое.
Эммм... IPFS?
Имхо, фатальный недостаток IPFS: разбиение и адресация по блокам, что большинству типов данных (обычно запакованных) не подходит.
Почему?
вот IPFS-cid копии этой страницы (с внедренными картинками и прочим) QmQTQYD8iguKBkJttaZDpjTt8Zo4aYp6mQDgNsqm43vzyE
если нет клиента то через публичные gateway'и можно проверить, например
Потому что большинство (форматов) данных переменной длины. Самый банальный пример: если я добавлю один байт в начало Войны и Мира, то все последующие блоки съедут. Только в лучшем случае я допишу байт в конец и изменится всего один блок.
Это же касается большинства сжатых данных и их архивов. Хотя вроде ради rsync какой-то архиватор в Linux добавлял опцию, чтобы у измененного архива был меньший diff, теоретически в этом направлении можно развиваться, но на сегодня это не практично.
Компромиссом было бы иметь data format aware разбиение на блоки, но тут во весь рост встала бы проблема разницы имплементаций, когда кто-то уже успел внедрить извлечение встроенных объектов в PDF (типа картинок), а другие ещё нет.
PS: Это на основе того, какая у стандартной реализации IPFS сейчас проблема с масштабированием, особенно по занимаемой оперативке.
Можно брутфорсом exe файл генерить и проверять получился архиватор или нет)))))
Надо просто пережить этот день.
Можно методом колеса, самый эффективный способ во вселенной, на данный момент. Хранить вообще особо ничего не нужно, можно всё получить на ходу. И сжатый файл, и разжатый, и хеш, и кеш, и даже имя человека что этот файл сжимал. Достаточно школьных знаний о том что число Пи содержит в себе все возможные последовательности чисел и если взять колесо и начать считать длину его окружности, то можно извлечь все данные вселенной, через некоторое время…
Все ок, но ведь главный ответ 42, столько байт и должно быть
ChatGPT4 мне отвечает примерно так же, как в начале статьи написано. Я даже сначала подумал, что сгенерирован текст.
18 байт достаточно для чего угодно, доказано на сайте https://t.ly
Предлагаю показать алгоритм провайдерам и ФСБ для более эффективной реализации закона Яровой.
Ну чисто технически да вполне себе рабочий алгоритм. Из минусов, не очень быстрый. А по поводу неоднозначности, можно сделать итоговый размер побольше, если использовать несколько типов хешей, т.е. md5, crc и т.д. таким образом при распаковке мы сможем сверять несколько контрольных сумм, это убережёт нас от неоднозначности результатов распаковки.
Вот вы все ржёте, а алгоритмы экстримального сжатия реально существуют. Например почти любой текст можно сжать всего до нескольких бит на слово, и это далеко не первоапрельская шутка.
Просто в наше время уже как-то не принято меряться архиваторами.
Помню в шараге учился, там какой-то гений записал все части GTA на оптический диск в 4ГБ. Был правда один нюанс, я попытался установить с того образа GTA 4 и на моём Core2Duo чотатам оно 2 дня распаковывалось.
Тот кто нарезал болванку хвалился что нашёл какой-то математический алгоритм который представлял файл как точку на отрезке [1:0] + таблицы + какая-то магия.
опять первоапрельская шутка?
А можно еще так. Любой файл конечного размера по определению уже находится в числе Пи, которое бесконечно. Нужно всего лишь при запаковке найти номер позиции в числе Пи с которой начинается непрерывная последовательность байт, соотвествующих файлу.
А потом взять хеш от числа номера позиции. И хеш от числа Пи (на всякий случай :D)
Не на всякий случай, а потому что номер позиции в числе Пи может быть сильно больше, чем искомый файл, а с хешом проблема решена)
Здесь еще один момент, связанный с безопасностью. Злоумышленники могут подменить число Пи и тогда мы получим неправильный результат. Вот для чего нужна контрольная сумма числа Пи.
Скептики могут возразить, что число Пи - это бесконечный ряд цифр, как же мы можем вычислить его контрольную сумму. Кто не хочет, тот ищет оправдания, а кто хочет, ищет возможности. Нужно просто сесть и подумать :)
Есть теорема, которая описывает сжатие без потерь
С этой теоремой у меня связано одно из детских воспоминаний.
Прочёл я в детстве статью, где некий журналист обзирал идеи Станислава Лема. Не могу поручиться, что «з», а не «с» это были идеи именно Лема, а не «Мойша напел», но это неважно. Одной из идей [якобы] была т.н. эволюционная декомпрессия. Мол, если взять семечко и посадить в землю, из него вырастет дерево. Семечко простое, а дерево — сложное. Как так? А вот так. Эволюция, оказывается, научилась компрессировать данные в семечко, чтобы оно развилось в дерево, а тупые люди — пока ещё нет, но рано или поздно догадаются, и здравствуй, гигазип, и сжатие в десятки тысяч раз.
Что-то в этом показалось мне глубоко неправильным. Я думал-думал, и решил оценить, как же соотносится число возможных вариантов файлов данного размера и число файлов в 10000 раз больше. И понял, что… как говорит Википедия, «функция декомпрессии неоднозначна». Так я в детстве переоткрыл принцип Дирихле. (Гордиться тут нечем, потому что надо быть олигофреном, чтобы не додуматься до принципа Дирихле. Скорее, удивляет, как эта статья вообще прошла мимо редактора).
И только после того, как я созрел из семечка во взрослого дяденьку и ознакомился с основами биологии, генетики и теории эволюции, до меня вдруг дошло: а в каком месте превращение семечка в дерево вообще считается декомпрессией и разворачиванием из простого в сложное?!
Ну в том-то и дело что семечка это текст написанный 1м кеглем, а дерево это тотже текст написанный 120 кеглем. Визуально отличаются, но по содержимому - нет
Что вы несете? Семечко это описание структуры “вот там внизу корень, там вот такие клетки, посередине ствол, там такие, сверху — листья, там такии и такие”. А в итоговом дереве клеток много-много, поэтому оно кажется больше (но сложность самих клеток не изменилась), а большая часть сложности того, как эти клетки друг с другом соединяются — задается рандомом/ветром/етс и в семечке не описана.
Такое люди уже давно изобрели. Семечко - проект на бумаге (папочка с листочками), дерево - построенный по проекту небоскреб. По аналогии можно и фильм упаковать. Текстовое описание заархивировать, а на выходе на основе текста ИИ генерирует фильм +- похожий на оригинал.
Надо бы ещё сравнить с Пи-архиватором.
Надо радужные таблицы, для всех файлов сделать. Тогда распаковаваться будет мгновенно :)
что-то попахивает старьем. Сейчас на дворе 2024, архив должен представлять из себя промпт для chatGPT в ответ на который он сгенерит нужный файл. Не благодарите
Вот вам версия 2022 года - https://arstechnica.com/information-technology/2022/09/better-than-jpeg-researcher-discovers-that-stable-diffusion-can-compress-images/
По сути используется доработанная Stable Diffusion для архивации картинок. Качество правда страдает ну так картинке же. Ну и модель надо за собой таскать.
А зря смеетесь. Именно так архивы и делаются. Например есть такое понятие как дедубликация. Когда некому хешу устанавливается в соответствие блоб. В этом случае в архиве хранятся ссылки на хеши. Вот сами прикиньте, пользователи часто льют одни и те же данные типа инсталляторов, фильмов, и прочего, и смысла хранить это во многих экземплярах нет никакого. И в Яндекс диске такое используется. Они даже не отправляют файл, если файл с таким хешом существует.
Давеча помнится байка ходила про запись любого объема информации на деревянной палке. Нужно просто перевести файл в десятичное число, поставить перед ним 0. И разделить палку на 2 отрезка в соответствующей пропорции.
Такая распаковка будет эффективно работать на квантовом компьютере с достаточным количеством кубитов. Единственное она будет распаковывать в один из возможных вариантов (а их огромное количество) и поэтому нужны будут алгоритмы, которые научат квантовый компьютер отсекать неверные (маловероятные) варианты исходного файла.
Проблема квантовых компьютеров, в том, что хотя внутри он просчитал все возможные варианты исходных данных, за раз вы можете извлечь из него только какой один случайный вариант исходных данных.
Если вы научите квантовый компьютер ПРАВИЛЬНО оценивать вероятности того или иного исходного файла, то это сильно поможет, потому что наиболее вероятные варианты чаще всего и извлекаются за раз.
Есть проблема в виде коллизии хэша.
Однажды вы захотите распаковать своему ребëнку мультик, а там жëсткое порно с клоунами...
Алгоритм интересный, но я бы использовал MD5 вместо SHA - меньше вероятность коллизий
Этот алгоритм уже очень давно и весьма успешно используется в программе "Архиватор Бабушкина" от талантливого российского разработчика
Дайте 32!
Супер-эффективная архивация — сжимаем все что угодно до 32 байт