архиватор

rzip?

тоже примерно 50 мегов получилось в результате.

http://p7zip.sourceforge.net/

>rzip?

bzip2 даже на 10 килобайт лучше сжал

>http://p7zip.sourceforge.net/

мана нету, есть только README, и то куцое.

как его заставить жать по максимуму?

сжал как в README написано

7za a -t7z -m0=lzma -mx=9 -mfb=64 -ms=on

44М,

лучше чем 50М,
но все-таки,
может быть можно еще лучше?

Посмотри сорцы на сайте

./p7zip_4.14.01/DOCS/MANUAL

http://upx.sourceforge.net/ - правда я сам не пробовал.

>http://upx.sourceforge.net/ - правда я сам не пробовал.
Если не пробовал, то нехрен и предлагать там же написано
UPX: the Ultimate Packer for eXecutables

>Если не пробовал, то нехрен и предлагать там же написано UPX: the Ultimate Packer for eXecutables

Аффтар нихрена не написал, что ему надо жать не eXecutables.

> Аффтар нихрена не написал, что ему надо жать не eXecutables.
270 Мб чистых exe-шников? Вам не кажется слишком уж невероятная ситуация?

Кстати, UPX экзешники жмёт хуже того же bzip2. UPX вообще для другой цели был придуман, а именно для того, чтобы сделать размер запускаемого файла меньше. Полезно, если надо запускать их с какого-нибудь небольшого носителя данных.

Спасибо, не знал.

> может быть можно еще лучше?

Для каждой последовательности битов есть теоретический лимит сжатого объёма, диктуемый информационной ёмкстью и избыточностью последовательности. Лучше этого лимита не сжать (если без потерь). Подозреваю, что 7zip подошёл к черте вплотную :)

Ну эт Вы батенька мягко говоря загнули. Может всё-таки "для каждого класса последовательностей", или ещё что-нибудь в этом духе? :)

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

Только не говори что я к словам придираюсь.

>Или давай мне конкретную последовательность, и я через 10 минут предоставлю архиватор, который именно эту последовательность будет сжимать ровно в один байт

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

Легко! Проверяю контрольную сумму исходнго файла и вперёд :)

Прошу заметить, что:

1) в посте dimss твоего условия не было, так что моё предложение совершенно корректно :)

2) а в твоём посте не было ни слова про разархиватор, или как там его :) только про какие-то там библиотеки :) Правда это уже действительно придирки, но тем не менее. Учимся формулировать требования корректно и полно :)

>а в твоём посте не было ни слова про разархиватор

Да, извини, я под словом архиватор имел ввиду разархиватор.

rzip -9

> Только не говори что я к словам придираюсь.

Придираешься, причём обоснованно :) А я -- отвечаю.

Да, такой "архиватор" вполне можно соорудить, но у него будет один существенный минус -- данная последовательность должна быть заранее известна на стороне получателя. Как заметил Миша, общий размер сжатого сообщения и декодера получится всё равно большим, ведь получатель должен знать эту последовательность, кодируемую одним байтом. Такой архиватор бесцелен.

gzip и друзья не требуют заведомого знания передаваемой последовательности бит получателем. Вот что существенно. В закодированой последовательности должен быть сообщён и сам код, чтобы получатель мог обойтись только алгоритмом декодирования, ничего не зная заранее о передаваемом сообщении.

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

Кстати, на практике для определения энтропии текста можно сжать его тем же bzip2 и посмотреть, насколько он сжался.

Налицо глубокое непонимание предмета, вкупе с попытками
рассуждать о нём :)

Вот ты тут так здорово рассуждаешь об энтропии, сразу видно,
человек разбирается в предмете. Хочу задать тебе вопрос.
Написал я тут простенький фильтр под условным названием bi,
который запощу следующей мессагой. Он преобразует входящий файл
блоками по 8 байт, размера файла не меняет, а будучи поставлен в трубу
с самим собой, не меняет вообще ничего (то есть преобразование,
которое он осуществляет, возведённое в квадрат, даёт единичное
преобразование). Взял я первый попавшийся тарбол, обработал этим
фильтром, и сжал - обработанный фильтром и исходный. И получил
удивительные результаты:

$ ./bi </tmp/mdadm-1.9.0.tar |./bi |cmp - /tmp/mdadm-1.9.0.tar
$ du -bs /tmp/mdadm-1.9.0.tar*
358400 /tmp/mdadm-1.9.0.tar
358400 /tmp/mdadm-1.9.0.tar.bi
218051 /tmp/mdadm-1.9.0.tar.bi.bz2
233304 /tmp/mdadm-1.9.0.tar.bi.gz
76747 /tmp/mdadm-1.9.0.tar.bz2
95352 /tmp/mdadm-1.9.0.tar.gz

Скажи мне, откуда бы такая разница в размерах?
Неужели мой фильтр так здорово увеличивает энтропию? :-)

Или всё-таки "gzip и друзья" тоже требуют пусть не "заведомого знания
передаваемой последовательности", но некоторых предположений о ней? :)

/* 
 * Фильтр, создающий первый байт из младших битов первых восьми байтов,
 * второй - из вторых битов первых восьми байт, ..., восьмой - из
 * восьмых битов, и так далее блоками по восемь байт (последние 1-7 байт
 * не преобразуются). Повторное применение фильтра приводит преобразованную
 * последовательность обратно к исходной.
 */
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <unistd.h>
int main(int argc, char *argv[])
{
	unsigned char buffer[8];
	unsigned inbuf, i, j;

	if( argc > 1 ) {
		fputs("This filter takes no arguments\n", stderr);
		exit(EXIT_FAILURE);
	}
	
	for(;;) {
		int c;
		for(inbuf=0; inbuf<8; ++inbuf)
			if( (c=getchar()) == EOF )
				break;
			else
				buffer[inbuf]=c;
		if( inbuf < 8 ) break;
		unsigned char a=1;
		for(i=0; i<8; ++i) {
			unsigned char out=0;
			for(j=0; j<8; ++j) {
				out >>= 1;
				if( buffer[j] & a ) out |= 128;
			}
			if ( EOF == putchar(out) ) {
				fputs("Output error\n", stderr);
				exit(EXIT_FAILURE);
			}
			a <<= 1;
		}
	}
	for( i=0; i<inbuf; ++i )
		if( EOF == putchar(buffer[i]) ) {
			fputs("Could not output tail\n", stderr);
			exit(EXIT_FAILURE);
		}
	exit(EXIT_SUCCESS);
}

Прикольный фильтр, мне понравилось :)

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

Не знает её и архиватор, поэтому жмёт, как может. Ему нафиг не требуется никакое предположение о последовательности. Но он создан в _расчёте_ на некоторые особенности, при наличии которых он сжимает, а при отсутствии -- даже увеличивает размер. Т.е. не всякую избыточность он может увидеть и устранить.

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

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

Э... ы... не требуется предположений о последовательности, но создан "в расчёте"... математическая величина зависит от того, как мы сами захотим её посчитать... это граждане уже метафизика какая-то, извините за выражение, а не математика.

Ладно, все всё поняли :)

Кстати, о птиццах. Не архиватор ужимает файл, а компрессор. Архиватор соединяет файлы в архив.

Извините, что по яйцам.

А ведь верно! :)

>Не архиватор ужимает файл, а компрессор.

Компрессор - устройство для сжатия и подачи воздуха, газа под давлением. Казалось бы, причём здесь файлы?

Дабы подойти вплотную к пределу, потребуется время порядка O(2^(8n)), где n - число байт в массиве данных. Для любого другого алгоритма (не NP-полного) не будет гарантии, что предел достигнут.

Придираешься, причём крайне тупо. Считать, естественно, надо размер последовательности + распаковщика.

Сравни:

tar - архиватор
gzip, bzip2 - компрессоры
rar - компрессор, с версии 3.0 - и архиватор, и компрессор одновременно.

Потому и создаются файлы .tar.gz и tar.bz2, что нужно сначала заархивировать, потом сжать, и это две разные программы.

Ты и правда думаешь, что я не знаю, чем tar от bzip2 отличается? Просто у меня виндовая привычка осталась всё архиватором называть.