Оптимальная сортировка непрерывного архива

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

sourceforge.net/projects/saro-vks
Если кому надо – берите.

В общем-то, мысль не нова – например, WinRAR пятой версии может находить дубликаты и сохранять их в архиве как ссылки.
Здесь похожий принцип – «подобность» файлов определяется проверкой сжатия.

Лучше всего результат получается с большими файлами, когда размер пары файлов больше объёма «словаря» архива.
Например, 1.5 Гб исполняемых файлов, примерно по 50 Мб каждый, ужались с 709 до 696 Мб, а архив с 25 Мб MIDI файлов, 30..300 кб каждый, уменьшился с 5.55 до 5.51 Мб, по сравнению с «заводской» сортировкой.

Пара картинок по алгоритму, для наглядности.

Сначала проверяется сжимаемость пар – заполняется матрица N*N файлов (ромбом – если удалить из списка последние файлы, уже полученные для первых файлов результаты сохранятся).



Дальше последовательность сортируется «окном» – в пределах окна перебираются все возможные комбинации файлов без дублирования (факториал N), и оставляется комбинация с минимальным размером.
Окно постепенно сдвигается по всему списку, пока размер продолжает уменьшаться.
Когда меньший размер нигде не находится, сортировка завершена.



p.s. Извиняюсь за сыроватую версию, но «допиливание» идёт медленно, и когда будет окончательный вариант – неизвестно, а пользоваться ей уже вполне можно.
Пока есть существенный минус – размер архивов с парами файлов ограничен 4 Гб (очень большие файлы были не нужны, а обработка 64-битных размеров занимает больше времени).
Если чего-то не хватает – пишите, сделаю, если получится.

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

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

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

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

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

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

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

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

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

              Не говоря о том, что тест сжимаемости 1000 (миллион комбинаций, соответственно) даже довольно мелких файлов занимает на моём компьютере 2 суток.
              0
              Автору стоит попробовать сжатие с помощью 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
                0
                Спасибо, очень интересно, обязательно посмотрю.
                  0
                  Оказалось, что в 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:
                  > Оказалось удивительно сложно обнаруживать случайные данные среди вполне сжимаемых, не жертвуя способностью адаптироваться к изменяющейся статистике.
                    0
                    Здорово, «всё уже придумано до нас». :)
                    Да, адаптация к изменяющемуся порядку файлов получается только частичная – в пределах окна, но полный перебор без окна занял бы невозможно долгое время.

                    Надо будет придумать более совершенный алгоритм начальной сортировки, т. к. после неё файлы могут перемещаться, только если «зацепит» окно.
                    Например, сортировать по содержимому файла – вариантов тут много.
                  0
                  Посмотрел – насколько понимаю, это 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
                  И включить «сжатие переименованных копий».
                    0
                    *«где бы они ни находились»

                    И с ZPAQ'ом придётся переименовывать файлы перед сжатием (так же, как с NanoZip'ом и 7-Zip'ом) и после распаковки восстанавливать имена.
                  0
                  Версия 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
                    0
                    И ещё небольшое исправление – при остановке авто-сжатия (если надоест ждать) показывается лучший результат из тех, что успели найтись.
                    «Машинка для гадания на размерной гуще» 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

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое