Сверх сжатие данных
 

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

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

А ты какие методы пробовал? Демомейкеры ведь каким то образом сжимают несколько мегабайт в 64 кб.
Я вижу смысл заниматься только математикой.Я все посчитал.
Обратное преобразование возможно без потери данных только если увеличить точность.(Виндовского калькулятора вполне хватает)Но как работать с числом у которого мантиса 33 символа я не знаю.
Может есть какие библиотеки? Что-нибудь посоветуешь?

Метод Хафмана или LZW не дает толком ничего.

Что за демомейкеры ?

Не правильно выразился.
Демосценеры конечно,а не мейкеры.

Где почитать можно ?

Почитать можно в FIDO,если ты про демосценеров.

В общем, это люди,которые пишут на ASM'e всякие
красивые штуки типа динамически меняющихся 3D объектов на 3D сцене.
Причем 3D объектом может быть и 3D модель чего-нибудь.
Все это крутится вертится(не хаотично) со множеством световых эффектов(зависит конечно от сценария).Все это
сопровождается неплохим стерео звуком.
Преимущественно пишут под OpenGL.
У них есть жесткое ограничение на участие в соревновании.Демка должна занимать не больше 64кило.Демка представляет из себя простой EXE-шник всего
на 64кб.

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

Вот отсюда мысль в общем то и пошла.

Ну пакуется эта демка хорошо из-за большого количества строковых данных . Обычно все простые реализации движков OpenGL базируются на обычных текстовых инструкциях aka набор координат через разделитель . Но я не понял почему на ASM'е ? 64kb программа может быть пволне написана на WinAPI . Да и все нормальные программеры пишут OpenGL на cpp инициализируя окошко через WinAPI функции .

Может быть,не спорю.Сам писал на cpp под OpenGL.
Я просто по себе смотрю.Если бы уменя было такое ограничение,то писал бы я точно на ASM'е исп. API само-собой.
Но не забывай про текстурирование и вполне качественную музыку.Не верится, что сие есть результат генерации какой-нибудь ф-ции.
Причем строковые данные как ты говоришь вполне нормально пакуются тем же ZIP'ом,а та демка(распакованная) не паковалась ничем.Вот и думай после этого.

Я тебя как-то спрашивал на счет Сишных библиотек для расчетов с повышенной точностью.Есть такие?
Я не нашел.

Т.е. по-твоему эти ребята юзают сверх секретный алгоритм сжатия доныне неизвестный науке ;)

Возможно разработанный всего лишь ими самими,или улучшенный старый.

Нужно сделать Packed binary file

Ты знаешь как его сделать?

Нету обшего модуля нужно свой

Нужно на каждый bit не integer, byte..... писать

Слышь, а ты чем их "распаковывал"???

Ты ее в *.avi файл "распаковал" что-ли? Тада конечно это не сожмет никакой архиватор.

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

Denver
Демка распаковалась сама в кучу tga'шек + муз. файло не помню какого формата.Не разу эти демки не видел что ли?

BuilderSoft
Что сие значит?Ты хочешь одним битом кодировать байт?
Или я тебя просто не понял.Не жалей клаву.Какие методы сжатия пробовал ты?

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

Нет я не пробовал сжать

Я только открывал токой

naverno rebjata ne pozhaleli paru desjatkov bajt dlja koda, kotorij pishet vsjakij musor na vint chtobi mi potom gadali ;))

Короче, ловите 3 демки.
Распаковывается только hologram_final.exe.

Все 260-килограмные TGA файлы ничем не уступают 5-килограмным JPEG со средним коэффициентом сжатия (то есть их просто сохранили как точечные рисунки)
Не знаю чего там напихано в .XM файле, но знаю что музыку такого качества слушал лет 10 назад в файлах *.mod, *.s3m - занимали по 200-300кб, т.е. вполне возможно что потоком можно их сохранить как WAV который будет хоть 50 метров занимать (и по качеству не отличаться).

Кароче, все это цирк на дроте и показуха :)

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

А теперь все перемнож и сложи.И что получится(даже по тем цифрам,что ты тут написал)?

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

Я думал,что есть библиотеки,но видно придется писать самому.
Я уже перешел на программирование сопроцессора.С++ режет точность до 64bit. А с сопроцессором можно работать и с 80bit'ой точностью.
И как они это все оптимизируют (10метров в 64кило)?Мы сли есть?

Все архиваторы стараются быть максимально универсальными. А здесь конкретно заточено под tga, xm и прочее - выигрыш в заточенности всегда есть

Alex_Rus
Ну как, продвигается работа?

Я что и предлагаю..... Сделать заточенный архиватор.
Но вот люди,ничего толком не попробовавшие сделать, начинают давать всякие советы. Мол ничего не получится и т.д.
Начинаешь спрашивать чего не получилось у них, так они толком сказать ничего не могут. Сразу видно,что в проблему глубоко не вникали. => получается отвлеченный базар, а вовсе не по теме.

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

Насчет 64кб демок.
Если задаться целью то можно создать(подогнать) музыкальный (графический) файл содержимое которого будет результатом мат. выражения (например (№"В;дВ * GF{}#E)^%}T, естественно это все в 256-чном исчислении) но не каждый муз. (граф) файл можно представить в лаконичном. виде мат.вычислений.

Второе.
Любая заточка имеет место там где есть закономерности.
Текстовая информация поддается закономерностям, т.к. можно сказать уверенно что большая вероятность появления "й" после "и" и очень маленькая "ь" после пробела.
(По крайней мере может иметь место повторение большого кол-ва символов).
В avi или wav файлах (также как и в rar, zip, arj...) закономерности нет в принципе. Символы равновероятны, т.е. поведение их случайное.
Подогнать можно только под определенный например wav, зная вероятности именно его символов. Но другой wav файл (если брать такуюже таблицу вероятностей) не будет сжиматься настолько (а может и увеличиться вовсе).

З.Ы. Я не верю в чудо, но мне почему-то интересно что из твоих вычислений получится. А если у тебя любые avi,mp3 файлы будут жаться то могу тебя поздравить - у тебя так же значительно (в два раза?) сожмуться и rar, и zip (что имхо неосуществимо, т.е. "сжать" можно а вот разжать нет).

Может я ошибаюсь?

На счет равновероятных символов в zip,arj и т.д., то ты в принципе прав.А вот на счет avi не совсем. Там разброс вероятностей наблюдается и иногда довольно приличный.
И в принципе я сам рассматриваю только одни avi'шки.

То,что можно подогнать(генерить с помощью формулы) под мат. формулу,то над этим я думал, даже не исключаю того,что так оно и есть в этих демках.Меня это и натолкнуло на эту тему.

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

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

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

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

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

Да примерно так и делается в основном... проблема как раз в "алгоритм запаковки, вплоть до этих самых формул" :))
А так все четко, нверное гуманитарный факультет? :))

[http://www.computerra.ru/offline/2002/447/18334/] :)

Ну генерить принято в демомейкинге все текстуры и большинство моделей (если речь о 3D). Вглядитесь - весьма нереалистичные они.

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

Тоже самое со звуком. Берем пару-тройку сэмплов байт на 300 (4bit mono) конвертим в 16 bit stereo, разделяем на каналы, подмешиваем искажений, накладываем фильтры (reverberation, "surround" и пр.).

Оптимизация демок, обычно, имеет мало общего со сжатием без потерь.

Возмите, например, тот же [hologram_final.exe], распакуйте его upx'ом (получится 380кб) и посмотрите внутрь - так и есть код и 150кб сэмплов да 50кб графики. Все.

И не майтесь дурью (см. приведенный URL).

Panorama
Любопытная статейка, но как говориться попытка не пытка...

Panorama
> Я как-то смотрел одну такую демку.Так вот, она у меня распаковалась метров на 5(говорят,что жмут даже гораздо больше 5).Все это хозяйство,которое вылезло, практически не упаковывалось никакими архиваторами.
и что, ты думаешь, она прямо при распаковке генерилась?
да и вообще, статейка конечно интересная, но, помнится, какая-то фирма, выпустив 32x CDROM, опубликовала кучу физико-математических выкладок о том, что быстрее ну никак! Тут же через несколько месяцев другая фирма выпустила сидюк на 40x...
так что сколько угодно и как угодно доказывать о "невозможности" или "несуществовании" чего-либо, как пару веков назад об "электричестве". В результате все старания консерваторов идут на свалку через те же пару столетий. И если потом вспоминаются, то только с кривой усмешкой.
Так чтааа... мы может быть и "маемся дурью", ну так нам, дуракам, невдомек.
С демками, конечно же, все так и есть, как ты сказал, но... НО! - оно всегда есть. Есть еще и теория вероятности, знаешь ли.

Можешь не сомневаться.

З.Ы. А причем сдесь теория вероятности?
Если есть теория вероятности значит есть шансы??? :))

Denver
Вероятность шанса есть всегда!!! :-)