есть ли архиватор для маленьких файлов??
Если у всех файлов одинаковый размер, то склей все в один и zip-ом пожми. После распаковки - порежь.
А так, как ты себе представляешь, что пожмутся?
Если длина файла 400бит = 50байт, из них 1-5+байт уйдет на имена файлов, плюс сколько то на словарь данных.
Если файлов будет много, то пожмется и zip-ом. Если нет, то можно и обломиться.
А так, как ты себе представляешь, что пожмутся?
Если длина файла 400бит = 50байт, из них 1-5+байт уйдет на имена файлов, плюс сколько то на словарь данных.
Если файлов будет много, то пожмется и zip-ом. Если нет, то можно и обломиться.
Дело в том, что мне нужно сжать только один файл такого размера. zip таскает словарь, и не дает сжатие.
у данных нет каких-то гарантированных закономерностей, это координаты объектов.
1 сетевой байт = 10 бит (8 + 2 стопбита)
у данных нет каких-то гарантированных закономерностей, это координаты объектов.
1 сетевой байт = 10 бит (8 + 2 стопбита)
ну напиши свой архиватор. Выдели старшие и младшие частоты и соответствующий константный словарь и жми арифметикой. Но мне кажется, что лушче вообще не жать такие данные
классическое арифметическое я пробовал, стабильно увеличивает файл на пару байтов.
у данных нет каких-то гарантированных закономерностей, это координаты объектов
координаты объектов и являются некоторой закономерностью, как лучше запаковать данные
вот у нас 40 байт = 320 битов. есть уверенность, что все биты реально будут использоваться? каково среднее кол-во использования каждого бита? если все биты будут использоваться, то сжатия скорее всего не будет (скорее наоборот можно метнуться в сторону адаптивных алгоритмов (логика строится на предыдущих пакетах, типа кодеков но я сомневаюсь, что реально нужно соваться в такие дебри
Чтобы гарантированно не было увеличения используй тождественное преобразование.
А если серьёзно - все архиваторы заточены под какие-то виды данных. Их они жмут, а всё остальное - раздувают (пусть немножко). Поэтому пока ты не определишься, на какого рода избыточности в твоих данных можно сыграть, вопрос не имеет особого смысла.
Если координаты - то в каком формате, что можно сказать о взаимном расположении объектов, и т.п.?
А если серьёзно - все архиваторы заточены под какие-то виды данных. Их они жмут, а всё остальное - раздувают (пусть немножко). Поэтому пока ты не определишься, на какого рода избыточности в твоих данных можно сыграть, вопрос не имеет особого смысла.
Если координаты - то в каком формате, что можно сказать о взаимном расположении объектов, и т.п.?
Во-первых, "чтобы гарантировано не было увеличения" не получится, как тебе попытался намекнуть Влад: хоть один бит (типа, uncompressed flag) но придётся добавить.
Алсо, я затрудняюсь представить ситуацию, в которой тебе было бы полезно скомпрессить ~40 байт, это же и так очень мало! И не вижу, как это возможно, по крайней мере если не знать внутренней структуры. Чисто адаптивный алгоритм не успеет настроиться, добавление какого-нибудь словаря тут же сожрёт львиную часть посылки...
Если ты знаешь структуру, то есть варианты. Для начала, раз ты знаешь, что там есть старт-стоп биты, можешь их смело выкинуть, 20% профита сразу! Потом, ну, стандартная идея: с одной стороны, если там координаты, и они все приблизительно похожи, то можно их декодировать в координаты и дальше хранить дельты. Типа, первую координату сохраняешь как есть, дальше сохраняешь разницы между координатами. Это даст тебе данные в которых большинство значений сравнительно маленькие.
С другой стороны, делаешь кодировку в которой маленькие значения занимают мало бит — http://en.wikipedia.org/wiki/Prefix_code, дальше тебе нужно посмотреть на типичные данные и прикинуть что лучше — выбрать какую-то одну кодировку которая их хорошо жмёт, или может быть несколько таких кодировок и добавить селектор вначале. Как я сказал выше, стандартные подходы с адаптивным энкодером (который вначале сжирает немножко некодированных данных и строит статистику, потом раскодирует ещё немножко данных ей и строит новую статистику, и так далее) или с сохранением словаря, не подходят, слишком маленький размер исходных данных.
Так что вот как-то так. Алсо, разумеется, тебе придётся сжимать именно не байты, а уже распарсенные из них координаты.
Ещё меня как-то смущает то, что ты хочешь сжимать "файлы". Ты в курсе, что один файл не может занимать меньше четырёх килобайт на диске обычно?
Ещё можешь почитать вот это: http://fgiesen.wordpress.com/2011/01/24/x86-code-compression..., но оно практически наверняка не подойдёт, разве что в качестве источника вдохновения.
Алсо, я затрудняюсь представить ситуацию, в которой тебе было бы полезно скомпрессить ~40 байт, это же и так очень мало! И не вижу, как это возможно, по крайней мере если не знать внутренней структуры. Чисто адаптивный алгоритм не успеет настроиться, добавление какого-нибудь словаря тут же сожрёт львиную часть посылки...
Если ты знаешь структуру, то есть варианты. Для начала, раз ты знаешь, что там есть старт-стоп биты, можешь их смело выкинуть, 20% профита сразу! Потом, ну, стандартная идея: с одной стороны, если там координаты, и они все приблизительно похожи, то можно их декодировать в координаты и дальше хранить дельты. Типа, первую координату сохраняешь как есть, дальше сохраняешь разницы между координатами. Это даст тебе данные в которых большинство значений сравнительно маленькие.
С другой стороны, делаешь кодировку в которой маленькие значения занимают мало бит — http://en.wikipedia.org/wiki/Prefix_code, дальше тебе нужно посмотреть на типичные данные и прикинуть что лучше — выбрать какую-то одну кодировку которая их хорошо жмёт, или может быть несколько таких кодировок и добавить селектор вначале. Как я сказал выше, стандартные подходы с адаптивным энкодером (который вначале сжирает немножко некодированных данных и строит статистику, потом раскодирует ещё немножко данных ей и строит новую статистику, и так далее) или с сохранением словаря, не подходят, слишком маленький размер исходных данных.
Так что вот как-то так. Алсо, разумеется, тебе придётся сжимать именно не байты, а уже распарсенные из них координаты.
Ещё меня как-то смущает то, что ты хочешь сжимать "файлы". Ты в курсе, что один файл не может занимать меньше четырёх килобайт на диске обычно?
Ещё можешь почитать вот это: http://fgiesen.wordpress.com/2011/01/24/x86-code-compression..., но оно практически наверняка не подойдёт, разве что в качестве источника вдохновения.
FJ , спасибо.
Вот ещё немножко идей:
Если тебе не важен порядок координат или ты можешь его надёжно восстановить как-нибудь, то можешь их отсортировать перед сжатием, тогда дельты получатся ещё меньше. Или скажем может оказаться, что выгодней записать среднюю координату и потом дельты от неё, а не начальную и дельты между ней и последующими.
Если ты знаешь ещё что-нибудь интересное про координаты, например, что они описывают какой-то замкнутый регион, то можно выйти на следующий уровень и добавить предиктор: по двум или нескольким последним координатам вычисляешь предсказание новой координаты которое обычно будет ближе к истинной новой координате, чем просто последняя обработанная координата, и записываешь дельту от неё. Так дельты получатся ещё меньше.
Да, и в конце концов, если действительно соберёшься это писать и тестить с разными вариантами настроек (ну, там, какой префиксный код выбрать, как предиктор работает, всё такое то это тоже следует делать по Науке! А именно: набираешь типичных данных и делишь их на
1) 80% training set
2) 20% testing set
Потом подбираешь параметры, которые дают наилучшее сжатие на training set, и смотришь, действительно ли эти параметры позволяют хорошо сжать и testing set. Если эффективность приблизительно одинаковая, то всё отлично, если нет, то это означает, что у тебя оказалось достаточно параметров кодирования чтобы невзначай удалось закодировать в них часть информации из training set, это называется overfitting. Тогда нужно набирать ещё в несколько раз больше данных, либо заняться особой чёрной магией. Главное что ни в коем случае нельзя использовать testing set для выбора параметров, он должен быть чисто для проверки.
Если тебе не важен порядок координат или ты можешь его надёжно восстановить как-нибудь, то можешь их отсортировать перед сжатием, тогда дельты получатся ещё меньше. Или скажем может оказаться, что выгодней записать среднюю координату и потом дельты от неё, а не начальную и дельты между ней и последующими.
Если ты знаешь ещё что-нибудь интересное про координаты, например, что они описывают какой-то замкнутый регион, то можно выйти на следующий уровень и добавить предиктор: по двум или нескольким последним координатам вычисляешь предсказание новой координаты которое обычно будет ближе к истинной новой координате, чем просто последняя обработанная координата, и записываешь дельту от неё. Так дельты получатся ещё меньше.
Да, и в конце концов, если действительно соберёшься это писать и тестить с разными вариантами настроек (ну, там, какой префиксный код выбрать, как предиктор работает, всё такое то это тоже следует делать по Науке! А именно: набираешь типичных данных и делишь их на
1) 80% training set
2) 20% testing set
Потом подбираешь параметры, которые дают наилучшее сжатие на training set, и смотришь, действительно ли эти параметры позволяют хорошо сжать и testing set. Если эффективность приблизительно одинаковая, то всё отлично, если нет, то это означает, что у тебя оказалось достаточно параметров кодирования чтобы невзначай удалось закодировать в них часть информации из training set, это называется overfitting. Тогда нужно набирать ещё в несколько раз больше данных, либо заняться особой чёрной магией. Главное что ни в коем случае нельзя использовать testing set для выбора параметров, он должен быть чисто для проверки.
> я затрудняюсь представить ситуацию, в которой тебе было бы
> полезно скомпрессить ~40 байт, это же и так очень мало!
RFC 1035 (STD 0013 4.1.4. Message compression.
---
"Narrowness of experience leads to narrowness of imagination."
> полезно скомпрессить ~40 байт, это же и так очень мало!
RFC 1035 (STD 0013 4.1.4. Message compression.
---
"Narrowness of experience leads to narrowness of imagination."
Это ж примитивнейший вариант LZ. Для координат, которые не повторяются в точности, он ничего не даст.
А координаты имеют свойство повторяться, так уж протокол устроен.
Так или иначе, протоколом описывается сжатие пакетов короче 512
октетов, что меньше фрагмента файловой системы и меньше страницы
памяти на многих платформах.
---
"Не надо читать много книг."
Так или иначе, протоколом описывается сжатие пакетов короче 512
октетов, что меньше фрагмента файловой системы и меньше страницы
памяти на многих платформах.
---
"Не надо читать много книг."
Оставить комментарий
Annaa
Всем привет!Подскажите, есть ли готовые архиваторы с открытым кодом, которые будут эффективны для сжатия файла маленького размера (40 байт=400бит, 1 сетевой байт = 8 + 2 стопбита). Или есть алгоритм, который может позволить сжать такой файл, но чтобы гарантировано не было увеличения?
Спасибо!