Pull to refresh

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

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

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-битных размеров занимает больше времени).
Если чего-то не хватает – пишите, сделаю, если получится.
Tags:
Hubs:
+2
Comments 18
Comments Comments 18

Articles