|
ovod
|
|
journeyman
|
|
|
|
|
|
|
Рег.: 09.12.2009
|
|
Сообщений: 56
|
|
|
|
Рейтинг: 60
|
|
есть ли архиватор для маленьких файлов??
06.12.2011 18:58
|
|
|
Всем привет!
Подскажите, есть ли готовые архиваторы с открытым кодом, которые будут эффективны для сжатия файла маленького размера (40 байт=400бит, 1 сетевой байт = 8 + 2 стопбита). Или есть алгоритм, который может позволить сжать такой файл, но чтобы гарантировано не было увеличения?
Спасибо!
Редактировал ovod (06.12.2011 19:44)
|
|
|
Zoobastik
|
|
Комок меха
|
|
|
|
|
|
|
Рег.: 18.10.2003
|
|
Сообщений: 7462
|
|
Из: За спиной
|
|
Рейтинг: 4345
|
|
Re: есть ли архиватор для маленьких файлов??
[re: ovod]
06.12.2011 19:19
|
|
|
Если у всех файлов одинаковый размер, то склей все в один и zip-ом пожми. После распаковки - порежь.
А так, как ты себе представляешь, что пожмутся?
Если длина файла 400бит = 50байт, из них 1-5+байт уйдет на имена файлов, плюс сколько то на словарь данных.
Если файлов будет много, то пожмется и zip-ом. Если нет, то можно и обломиться.
|
|
|
ovod
|
|
journeyman
|
|
|
|
|
|
|
Рег.: 09.12.2009
|
|
Сообщений: 56
|
|
|
|
Рейтинг: 60
|
|
Re: есть ли архиватор для маленьких файлов??
[re: Zoobastik]
06.12.2011 19:27
|
|
|
Дело в том, что мне нужно сжать только один файл такого размера. zip таскает словарь, и не дает сжатие.
у данных нет каких-то гарантированных закономерностей, это координаты объектов.
1 сетевой байт = 10 бит (8 + 2 стопбита)
|
|
|
ayvango
|
|
ушастый
|
|
|
|
|
|
|
Рег.: 10.01.2006
|
|
Сообщений: 27732
|
|
Из: Воронеж
|
|
Рейтинг: 11832
|
|
Re: есть ли архиватор для маленьких файлов??
[re: ovod]
06.12.2011 19:31
|
|
|
ну напиши свой архиватор. Выдели старшие и младшие частоты и соответствующий константный словарь и жми арифметикой. Но мне кажется, что лушче вообще не жать такие данные
|
Сеть темна и полна ужасов |
|
|
ovod
|
|
journeyman
|
|
|
|
|
|
|
Рег.: 09.12.2009
|
|
Сообщений: 56
|
|
|
|
Рейтинг: 60
|
|
Re: есть ли архиватор для маленьких файлов??
[re: ayvango]
06.12.2011 19:58
|
|
|
классическое арифметическое я пробовал, стабильно увеличивает файл на пару байтов.
|
|
|
horror
|
|
гонобобель
|
|
|
|
|
|
|
Рег.: 30.09.2002
|
|
Сообщений: 3784
|
|
|
|
Рейтинг: 2137
|
|
Re: есть ли архиватор для маленьких файлов??
[re: ovod]
06.12.2011 20:01
|
|
|
Quote:
у данных нет каких-то гарантированных закономерностей, это координаты объектов
координаты объектов и являются некоторой закономерностью, как лучше запаковать данные
вот у нас 40 байт = 320 битов. есть уверенность, что все биты реально будут использоваться? каково среднее кол-во использования каждого бита? если все биты будут использоваться, то сжатия скорее всего не будет (скорее наоборот), можно метнуться в сторону адаптивных алгоритмов (логика строится на предыдущих пакетах, типа кодеков), но я сомневаюсь, что реально нужно соваться в такие дебри
|
|
|
Vlad
|
|
addict
|
|
|
|
|
|
|
Рег.: 18.09.2004
|
|
Сообщений: 446
|
|
|
|
Рейтинг: 236
|
|
Re: есть ли архиватор для маленьких файлов??
[re: ovod]
06.12.2011 21:15
|
|
|
Чтобы гарантированно не было увеличения используй тождественное преобразование.
А если серьезно - все архиваторы заточены под какие-то виды данных. Их они жмут, а все остальное - раздувают (пусть немножко). Поэтому пока ты не определишься, на какого рода избыточности в твоих данных можно сыграть, вопрос не имеет особого смысла.
Если координаты - то в каком формате, что можно сказать о взаимном расположении объектов, и т.п.?
|
|
|
Fj_
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 12.09.2004
|
|
Сообщений: 8795
|
|
|
|
Рейтинг: 3287
|
|
Re: есть ли архиватор для маленьких файлов??
[re: ovod]
07.12.2011 02:28
|
|
|
Во-первых, "чтобы гарантировано не было увеличения" не получится, как тебе попытался намекнуть Влад: хоть один бит (типа, uncompressed flag) но придется добавить.
Алсо, я затрудняюсь представить ситуацию, в которой тебе было бы полезно скомпрессить ~40 байт, это же и так очень мало! И не вижу, как это возможно, по крайней мере если не знать внутренней структуры. Чисто адаптивный алгоритм не успеет настроиться, добавление какого-нибудь словаря тут же сожрет львиную часть посылки...
Если ты знаешь структуру, то есть варианты. Для начала, раз ты знаешь, что там есть старт-стоп биты, можешь их смело выкинуть, 20% профита сразу! Потом, ну, стандартная идея: с одной стороны, если там координаты, и они все приблизительно похожи, то можно их декодировать в координаты и дальше хранить дельты. Типа, первую координату сохраняешь как есть, дальше сохраняешь разницы между координатами. Это даст тебе данные в которых большинство значений сравнительно маленькие.
С другой стороны, делаешь кодировку в которой маленькие значения занимают мало бит - http://en.wikipedia.org/wiki/Prefix_code, дальше тебе нужно посмотреть на типичные данные и прикинуть что лучше - выбрать какую-то одну кодировку которая их хорошо жмет, или может быть несколько таких кодировок и добавить селектор вначале. Как я сказал выше, стандартные подходы с адаптивным энкодером (который вначале сжирает немножко некодированных данных и строит статистику, потом раскодирует еще немножко данных ей и строит новую статистику, и так далее) или с сохранением словаря, не подходят, слишком маленький размер исходных данных.
Так что вот как-то так. Алсо, разумеется, тебе придется сжимать именно не байты, а уже распарсенные из них координаты.
Еще меня как-то смущает то, что ты хочешь сжимать "файлы". Ты в курсе, что один файл не может занимать меньше четырех килобайт на диске обычно?
Еще можешь почитать вот это: http://fgiesen.wordpress.com/2011/01/24/x86-code-compression..., но оно практически наверняка не подойдет, разве что в качестве источника вдохновения.
|
The data is the error (c)IIS FTP Server. |
|
|
ovod
|
|
journeyman
|
|
|
|
|
|
|
Рег.: 09.12.2009
|
|
Сообщений: 56
|
|
|
|
Рейтинг: 60
|
|
Re: есть ли архиватор для маленьких файлов??
[re: Fj_]
07.12.2011 18:06
|
|
|
|
|
|
Fj_
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 12.09.2004
|
|
Сообщений: 8795
|
|
|
|
Рейтинг: 3287
|
|
Re: есть ли архиватор для маленьких файлов??
[re: ovod]
08.12.2011 01:46
|
|
|
Вот еще немножко идей:
Если тебе не важен порядок координат или ты можешь его надежно восстановить как-нибудь, то можешь их отсортировать перед сжатием, тогда дельты получатся еще меньше. Или скажем может оказаться, что выгодней записать среднюю координату и потом дельты от нее, а не начальную и дельты между ней и последующими.
Если ты знаешь еще что-нибудь интересное про координаты, например, что они описывают какой-то замкнутый регион, то можно выйти на следующий уровень и добавить предиктор: по двум или нескольким последним координатам вычисляешь предсказание новой координаты которое обычно будет ближе к истинной новой координате, чем просто последняя обработанная координата, и записываешь дельту от нее. Так дельты получатся еще меньше.
Да, и в конце концов, если действительно соберешься это писать и тестить с разными вариантами настроек (ну, там, какой префиксный код выбрать, как предиктор работает, все такое), то это тоже следует делать по Науке! А именно: набираешь типичных данных и делишь их на
1) 80% training set
2) 20% testing set
Потом подбираешь параметры, которые дают наилучшее сжатие на training set, и смотришь, действительно ли эти параметры позволяют хорошо сжать и testing set. Если эффективность приблизительно одинаковая, то все отлично, если нет, то это означает, что у тебя оказалось достаточно параметров кодирования чтобы невзначай удалось закодировать в них часть информации из training set, это называется overfitting. Тогда нужно набирать еще в несколько раз больше данных, либо заняться особой черной магией. Главное что ни в коем случае нельзя использовать testing set для выбора параметров, он должен быть чисто для проверки.
|
The data is the error (c)IIS FTP Server. |
|
|
KOHTPA
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 22.01.2003
|
|
Сообщений: 33647
|
|
|
|
Рейтинг: 2374
|
|
Re: есть ли архиватор для маленьких файлов??
[re: Fj_]
15.12.2011 03:51
|
|
|
> я затрудняюсь представить ситуацию, в которой тебе было бы
> полезно скомпрессить ~40 байт, это же и так очень мало!
RFC 1035 (STD 0013), 4.1.4. Message compression.
---
"Narrowness of experience leads to narrowness of imagination."
|
|
|
DeeMon
|
|
|
|
|
|
|
|
|
Рег.: 28.03.2004
|
|
Сообщений: 1746
|
|
Из: Siam gulf
|
|
Рейтинг: 3029
|
|
Re: есть ли архиватор для маленьких файлов??
[re: KOHTPA]
15.12.2011 09:24
|
|
|
Это ж примитивнейший вариант LZ. Для координат, которые не повторяются в точности, он ничего не даст.
|
|
|
KOHTPA
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 22.01.2003
|
|
Сообщений: 33647
|
|
|
|
Рейтинг: 2374
|
|
Re: есть ли архиватор для маленьких файлов??
[re: DeeMon]
15.12.2011 13:37
|
|
|
А координаты имеют свойство повторяться, так уж протокол устроен.
Так или иначе, протоколом описывается сжатие пакетов короче 512
октетов, что меньше фрагмента файловой системы и меньше страницы
памяти на многих платформах.
---
"Не надо читать много книг."
|
|
Список
Плоский
Дерево
