GAFFitter: the Genetic Algorithm File Fitter [LWN.net]

GAFFitter is a command line utility which can be run against directory trees to create groups of files that fit on media of a specified size:

Genetic Algorithm File Fitter (gaffitter) is a command-line software written in C++ that extracts --via Genetic Algorithm-- subsets of an input list of files/directories that best fit the given volume size (target), such as CD, DVD and others. It is initially designed to run under Linux and POSIX systems, but easily portable to non-POSIX operating environment. Using GA search, gaffitter improve different combinations of the files on the list so that the lost of space will be minimized. Ideal to be used for backups/records in CD, DVD and others.

Installation of GAFFitter was easy, the software was downloaded here in tar.bz2 form. Building involved the usual bunzip2, tar, make and make install steps. This all worked without problems on an Ubuntu Edgy Eft system that had the usual software build tools installed.

The GAFFitter usage instructions give an idea of the various ways that the application can be run. An example run was tried on a collection of music files, GAFFitter did a good job of producing packed lists that would fit on a series of 700MB CDs.

Version 0.5.1 of GAFFitter was announced on March 28, 2007: "This release fixes a bug (uninitialized variable) and changes the default behavior of GAFFitter, which now extracts the volumes as much as possible (unlimited iterations)."

GAFFitter is a useful tool that can help to efficiently solve the problem of fitting large collections of files onto fixed-sized media. It is useful by itself, and can be incorporated into higher-level applications, as shown by this example integration script for the K3B multimedia utility. If you need to efficiently pack some files for archival, give it a try.

(Log in to post comments)

GAFFitter: the Genetic Algorithm File Fitter

Posted Apr 5, 2007 9:06 UTC (Thu) by Wummel (subscriber, #7591) [Link]

Nice program. I searched several years ago for such a tool when copying files to floppy disks. It turned out this bin packing problem is NP-hard. It would be interesting to know how GAFFitter and its genetic algorithm performs with large set of files.

GAFFitter: the Genetic Algorithm File Fitter

Posted Apr 7, 2007 5:22 UTC (Sat) by grouch (guest, #27289) [Link]

Thanks for the link. I didn't know it, but I guess I've been using the "First Fit Decreasing" strategy while using a bash script for stuffing CDs and DVDs since 2003. :)

Nice BASH script (off-topic)

Posted Apr 9, 2007 12:06 UTC (Mon) by pr1268 (subscriber, #24648) [Link]

What a neat, well-written script! I especially like the flowchart at the bottom. Lazy me, I just usually drag-n-drop in K3b until I approach the size limit of whatever blank media to which I'm writing (and to think that I call myself a Linux hacker!).

dirsplit

Posted Apr 12, 2007 15:24 UTC (Thu) by bryanlarsen (guest, #26230) [Link]

http://freshmeat.net/projects/dirsplit/ works great for me. I generally want to keep subdirectories together, so something that tries too hard is useless to me anyways. Dirsplit has an option to keep subdirectories together or fill better by splitting dirs. Maybe GAFFitter has the same options, but why try it out if dirsplit works great?

dirsplit

Posted Apr 16, 2007 2:53 UTC (Mon) by daa (guest, #44680) [Link]

Unless you specify the subdirectories also as input files, the GAFFitter won't break them. Suppose you have the following directory structure:

a
|-- b
`-- c

Thus, 'gaffitter -t 700 a' is different than 'gaffitter -t 700 a/*' (i.e. 'gaffitter -t 700 a/b a/c'). While the first will consider the directory 'a' as one entity (recursively including 'b' and 'c'), the second may eventually put the subdirectories 'b' and 'c' in different volumes.

Moreover, if you want to preserve the order of the given files/dirs then you may use the '--split' option. This normally doesn't produce very good fit, however.