Как стать автором
Обновить

Комментарии 18

На всякий случай, контрольные суммы, если что-то не скачается:

Saro v0.98.rar, 86829 байт (с данными для восстановления)
md5: 07f84ef44f4d2d1206edd60a87a9b4b6
sha-1: c70a9c0d71f33e543f3a8e600a03847cc2a0538d

Saro v0.98.7z, 45338 байт
md5: 1fb45d1b489ceae59e0ffd58309a4751
sha-1: 05c3d47e57a65a056d687c0eb9649f8e782e76a4
То есть эффективность ~2%. Это действительно кому-то нужно?
Это зависит от файлов, в одном случае размер уменьшился на 700 Мб (и архив поместился на DVD). Может, кому-нибудь пригодится.
Но да, чудес она не совершает.
Нужно! Так как на разных данных будет разный %, уверен, что на специфичных данных + будет не маленький.
Автору отдельное спасибо! Для моей задачи идеально подходит, будто для меня писал =)
Пожелаю автору успехов в развитии программы и выпуске финальной версии.
А поставить степень сжатия в архиваторе побольше никак нельзя? Это же тоже самое.

И если у вас известные специфичные данные, то их и надо сортировать специфично, а не методом тыка.
Никак нельзя, и так на максимум =)
А тут что-то вроде сортировки по энтропии. Только доработать нужно.
Спасибо, да, хотелось сортировать по подобности. Правда, когда в «словарь» помещается больше чем 2 файла, видимо, архиваторы находят уже другие схожие фрагменты, и наилучшая последовательность меняется.
Вроде бы наиболее близкий к расчётному вариант получается у 7-Zip'а.
У RAR'а меньший размер архива может выйти при меньшем размере окна, но определить это, наверное, можно только сжатием всего архива.

В общем, пока ничего лучшего не придумалось, это вспомогательный инструмент, автоматически идеал не достигается.
Обновил:
- всё-таки сделал почти 64-битной (размер файлов до 4 294967295 999999999 байт);
- исправил ошибку, из-за которой сортировка могла закончиться раньше;
- добавил автоматическое сжатие всех имеющихся вариантов сортировки;
- перетаскивание файлов на окно оказалось удобнее списков, пусть будет. :)
А каков алгоритм сравнения (спрашиваю тут, чтоб в ассемблере не ковыряться)? Просто попарно все файлы пакуем и смотрим, получилось ли короче? Это ж сколько оно будет работать при количестве файлов этак тысяч в 60?
Добавил картинки по алгоритму, спасибо.

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

Количество файлов ограничено в районе 15000 (но скорее всего, памяти программе может быть выделено меньше 2 Гб, поэтому предел ещё ниже).
Больше 1000 файлов я пока не проверял.

Не говоря о том, что тест сжимаемости 1000 (миллион комбинаций, соответственно) даже довольно мелких файлов занимает на моём компьютере 2 суток.
Автору стоит попробовать сжатие с помощью lrzip (Long Range ZIP or Lzma RZIP) от Con Kolivas (австралийский анестезиолог и автор множества патчей для ядра Линукс):
ck.kolivas.org/apps/lrzip/

ck.kolivas.org/apps/lrzip/README
This is a compression program optimised for large files.… Lrzip uses an extended version of rzip which does a first pass long distance
redundancy reduction. The lrzip modifications make it scale according to memory size.… The data is then either: Compressed by lzma / ZPAQ / LZO / gzip / bzip2 / uncompressed

ck.kolivas.org/apps/lrzip/README.benchmarks
linux-2.6.37.tar - These are benchmarks performed on a 3GHz quad core Intel Core2 with 8GB ram 
using lrzip v0.612 on an SSD drive.
Compression	Size		Percentage	Compress	Decompress
None		430612480	100
7z		63636839	14.8		2m28s		0m6.6s
xz		63291156	14.7		4m02s		0m8.7
lrzip		64561485	14.9		1m12s		0m4.3s
lrzip -z	51588423	12.0		2m02s		2m08s
lrzip -l	137515997	31.9		0m14s		0m2.7s
lrzip -g	86142459	20.0		0m17s		0m3.0s
lrzip -b	72103197	16.7		0m21s		0m6.5s
bzip2		74060625	17.2		0m48s		0m12.8s
gzip		94512561	21.9		0m17s		0m4.0s

Rzip — en.wikipedia.org/wiki/Rzip — семейство словарных фильтров с сверхбольшими окнами (сотни мегабайт), сходные проекты — REP, SREP. В lrzip немного изменен алгоритм rzip и при компрессии могут использоваться современные алгоритмы lzma и ZPAQ
Спасибо, очень интересно, обязательно посмотрю.
Оказалось, что в RK (на 2002 год) есть подбор порядка файлов в архиве. Вот из описания первой версии PAQ1:

compression.ru/download/articles/cm/shelwien_2002_paq1b.txt
> RK — это основанный на PPMZ архиватор, который подбирает порядок файлов для оптимизации сжатия.
> Rk — лучший из 157 компрессоров, согласно статистике ACT от 6/24/2001 (Gilchrist, см. compression.ca/act-calgary.html),

PS:
> Оказалось удивительно сложно обнаруживать случайные данные среди вполне сжимаемых, не жертвуя способностью адаптироваться к изменяющейся статистике.
Здорово, «всё уже придумано до нас». :)
Да, адаптация к изменяющемуся порядку файлов получается только частичная – в пределах окна, но полный перебор без окна занял бы невозможно долгое время.

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

По идее, если предварительно отсортировать файлы «по подобности», RZIP сможет найти похожие данные при меньшем размере окна.

Либо же использовать RZIP как «определитель энтропии» – может быть, он окажется эффективнее встроенных в архиваторы алгоритмов (то есть проверять сжимаемость при помощи RZIP'а, а сжимать уже как обычно – RAR'ом, 7-Zip'ом, NanoZip'ом, ZPAQ'ом и т. п.).

p.s. Кстати, о ZPAQ'е: как-то я про него забыл, а он жмёт сравнимо с NanoZip'ом – чтобы его использовать, достаточно задать командные строки наподобие:
"zpaq.exe" a "*o" "*1" -fragment 6 -method 57 -threads 1
"zpaq.exe" a "*o" "*1" "*2" -fragment 6 -method 57 -threads 1
И включить «сжатие переименованных копий».
*«где бы они ни находились»

И с ZPAQ'ом придётся переименовывать файлы перед сжатием (так же, как с NanoZip'ом и 7-Zip'ом) и после распаковки восстанавливать имена.
Версия 0.99: sourceforge.net/projects/saro-vks/files/v0.99

Saro v0.99.rar, 113717 байт, с данными для восстановления
md5: 5bd8f1dc803a3527769456d7054d7238
sha-1: 7995b907fc1d6d56f08fb267f34e09ed5d2826ff

Saro v0.99.7z, 59649 байт
md5: bdcd79b24c3a0d192b4d7e3697d81a26
sha-1: 4d6fc504dd87fd0939e9459d06a9feab4c98f640
И ещё небольшое исправление – при остановке авто-сжатия (если надоест ждать) показывается лучший результат из тех, что успели найтись.
«Машинка для гадания на размерной гуще» v0.99.1:

Saro v0.99.1.rar, 117461 байт
md5: 4119efb33483afda0ac5e057b7a21073
sha-1: 7290272c0110c3781a1834dafc4f7067dba3e952

Saro v0.99.1.7z, 61571 байт
md5: bf1585a244a08696a5abc2776f998bae
sha-1: e71ba6bac0e1b6691ff806feb75be9cdf8b2f8e6
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории