Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 18
На всякий случай, контрольные суммы, если что-то не скачается:
Saro v0.98.rar, 86829 байт (с данными для восстановления)
md5: 07f84ef44f4d2d1206edd60a87a9b4b6
sha-1: c70a9c0d71f33e543f3a8e600a03847cc2a0538d
Saro v0.98.7z, 45338 байт
md5: 1fb45d1b489ceae59e0ffd58309a4751
sha-1: 05c3d47e57a65a056d687c0eb9649f8e782e76a4
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'а меньший размер архива может выйти при меньшем размере окна, но определить это, наверное, можно только сжатием всего архива.
В общем, пока ничего лучшего не придумалось, это вспомогательный инструмент, автоматически идеал не достигается.
Вроде бы наиболее близкий к расчётному вариант получается у 7-Zip'а.
У RAR'а меньший размер архива может выйти при меньшем размере окна, но определить это, наверное, можно только сжатием всего архива.
В общем, пока ничего лучшего не придумалось, это вспомогательный инструмент, автоматически идеал не достигается.
Обновил:
- всё-таки сделал почти 64-битной (размер файлов до 4 294967295 999999999 байт);
- исправил ошибку, из-за которой сортировка могла закончиться раньше;
- добавил автоматическое сжатие всех имеющихся вариантов сортировки;
- перетаскивание файлов на окно оказалось удобнее списков, пусть будет. :)
- всё-таки сделал почти 64-битной (размер файлов до 4 294967295 999999999 байт);
- исправил ошибку, из-за которой сортировка могла закончиться раньше;
- добавил автоматическое сжатие всех имеющихся вариантов сортировки;
- перетаскивание файлов на окно оказалось удобнее списков, пусть будет. :)
А каков алгоритм сравнения (спрашиваю тут, чтоб в ассемблере не ковыряться)? Просто попарно все файлы пакуем и смотрим, получилось ли короче? Это ж сколько оно будет работать при количестве файлов этак тысяч в 60?
Добавил картинки по алгоритму, спасибо.
60000 файлов этот вариант обработать не сможет – размер матрицы получится 3.6 миллиарда комбинаций, и даже при 32-битном размере архивов она займёт 14 с лишним гигабайт памяти. Тогда нужен 64-битный вариант программы, либо сохранение данных на диск.
Количество файлов ограничено в районе 15000 (но скорее всего, памяти программе может быть выделено меньше 2 Гб, поэтому предел ещё ниже).
Больше 1000 файлов я пока не проверял.
Не говоря о том, что тест сжимаемости 1000 (миллион комбинаций, соответственно) даже довольно мелких файлов занимает на моём компьютере 2 суток.
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
ck.kolivas.org/apps/lrzip/README.benchmarks
Rzip — en.wikipedia.org/wiki/Rzip — семейство словарных фильтров с сверхбольшими окнами (сотни мегабайт), сходные проекты — REP, SREP. В lrzip немного изменен алгоритм rzip и при компрессии могут использоваться современные алгоритмы lzma и ZPAQ
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:
> Оказалось удивительно сложно обнаруживать случайные данные среди вполне сжимаемых, не жертвуя способностью адаптироваться к изменяющейся статистике.
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
И включить «сжатие переименованных копий».
Там ищут схожие данные по всему объёму, где бы они не находились, а здесь попытка расположить подобные файлы максимально близко друг к другу – «чтобы не пришлось долго искать».
По идее, если предварительно отсортировать файлы «по подобности», 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
И включить «сжатие переименованных копий».
Версия 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
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
«Машинка для гадания на размерной гуще» 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
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Оптимальная сортировка непрерывного архива