.TH squeeze 1 .SH NAME \fBsqueeze\fR - Finds the best subset, of the specified files, which fits into a given space. .SH SYNOPSIS \fBsqueeze\fR [\fIOPTIONS\fR] \fIFILE\fR ... .SH DESCRIPTION .PP Finds the subset of the named \fIFILE\fRs, which fits into \fIBYTES\fR, with least room to spare, whilst meeting \fBminimumUsageRatio\fR. .PP Any directories amongst the specified \fIFILE\fRs are treated as atomic units, & therefore only solutions which involve either all or none of the files in that directory, are returned. .PP Because of its exponential time-complexity, solutions of increasing suitability are continuously returned, rather than waiting until the optimal solution is known; which might take an inordinately long time. .SH OPTIONS .SS "Selection" .TP \fB-b\fR, \fB--bisectionRatio=\fR\fILHS/Total\fR Defines the ratio (in the unit interval [0 .. 1], defaulting to 1/2), at which the file-list will be bisected. The first of the combinations generated from the LHS, is then concatenated with each of the combinations generated from the RHS. The same operation is then performed on subsequent combinations from the LHS. This alters the order in which file-combinations are assessed, & so the set of suitable combinations returned may differ, though the optimum value remains the same. .TP \fB-M\fR, \fB--maximumBytes=\fR\fIBYTES\fR Define the maximum available space, in bytes, defaulting to the space available on a DVD; i.e. \fB4700000000\fR bytes. .TP \fB-m\fR, \fB--minimumUsageRatio=\fR\fIRATIO\fR Define the minimum acceptable usage-ratio of \fBmaximumBytes\fR, from 0 .. 1, defaulting to \fB99/100\fR, i.e. 99%. .TP \fB-q\fR, \fB--runQuickChecks\fR Run Quick-checks using arbitrary data & then exit. .TP \fB--testPerformance\fR='(, \fBPoissonDistribution\fR \fIlambda\fR | \fBNormalDistribution\fR \fImean\fR \fIvariance\fR)' Measure the CPU-time required to find the best fit, for the specified number of randomly generated, virtual files, the size of which conform to the required probability-distribution, and the names of which reflect their size, & then exit. .TP \fB--graphPerformance\fR='\fBPoissonDistribution\fR \fIlambda\fR | \fBNormalDistribution\fR \fImean\fR \fIvariance\fR' Measure the CPU-time required to find the best fit, for a linearly increasing number of randomly generated, virtual files, the size of which conform to the required probability-distribution, and the names of which reflect their size. Doesn't normally terminate. .TP \fB-v\fR, \fB--verbose\fR Produce additional explanatory output where appropriate. This option, if required, may need to precede other options. .SS "Generic Program-information" .TP \fB--version\fR Output version-information & exit. .TP \fB-?\fR, \fB--help\fR Display help & exit. .SS "File-list" .TP When a \fIFILE\fR is defined as a single hyphen-minus (\fB-\fR), replace it with the list of file-names read from standard-input. .SH EXIT-STATUS \fB0\fR on success, & >\fB0\fR if an error occurs. .SH EXAMPLES .SS Trial 1 Say we've a directory of audio-files, categorised by artist. .TP \fBls -p\fR ArabStrap/ BobDylan/ JeffBuckley/ JohnMartyn/ JoniMitchell/ ReservoirDogsOST/ RichardThompson/ SethLakeman/ SusheelaRaman/ TeddyThompson/ Vangelis/ .PP .TP \fBsqueeze -M 700000000 -m 0.999 *\fR 699871313 ["BobDylan","RichardThompson","SethLakeman","TeddyThompson"] .br 699893320 ["ArabStrap","BobDylan","JeffBuckley","JohnMartyn","SethLakeman","SusheelaRaman"] .br \fI699998310\fR ["ArabStrap","BobDylan","JoniMitchell","ReservoirDogsOST","SethLakeman","TeddyThompson","Vangelis"] .PP Note that the proposed solutions don't split any of the directories, into their constituent files. .PP We can confirm the validity of the optimal result: .TP \fBfind ArabStrap BobDylan JoniMitchell ReservoirDogsOST SethLakeman TeddyThompson Vangelis -type f -print | perl -e 'use List::Util qw(sum); printf(qq(%d\\n), sum map { chomp; (stat)[7] } <>);'\fR 699998310 .PP NB: \fBdu\fR will return a slightly larger size, since it includes the space required for directory-structures. .SS Trial 2 We can improve on that result if we're prepared to split some of the artist-specific directories into individual albums. .TP \fBsqueeze -M 700000000 -m 0.99999 ArabStrap BobDylan/* JeffBuckley JohnMartyn JoniMitchell ReservoirDogsOST RichardThompson SethLakeman SusheelaRaman TeddyThompson Vangelis\fR 699995815 ["ArabStrap","BobDylan/BlondeOnBlonde","BobDylan/Highway61Revisited","BobDylan/ModernTimes","BobDylan/StreetLegal","BobDylan/SubterraneanHomesickBlues","JoniMitchell","RichardThompson","SusheelaRaman","TeddyThompson","Vangelis"] .br 699998578 ["BobDylan/Desire","BobDylan/Highway61Revisited","BobDylan/Infidels","BobDylan/StreetLegal","JeffBuckley","JohnMartyn","JoniMitchell","RichardThompson","SethLakeman","SusheelaRaman","TeddyThompson","Vangelis"] .br \fI699999112\fR ["BobDylan/BlondeOnBlonde","BobDylan/Desire","BobDylan/Highway61Revisited","BobDylan/Infidels","BobDylan/ModernTimes","JeffBuckley","JohnMartyn","ReservoirDogsOST","RichardThompson","SusheelaRaman","TeddyThompson","Vangelis"] .SS Trial 3 If we're prepared to add individual files from another artist: .TP \fBsqueeze -M 700000000 -m 0.9999999 ArabStrap BobDylan/* JeffBuckley JohnMartyn JoniMitchell ReservoirDogsOST $(find RichardThompson -type f) SethLakeman SusheelaRaman TeddyThompson Vangelis\fR 699999964 ["ArabStrap","BobDylan/Desire","BobDylan/Infidels","BobDylan/ModernTimes","BobDylan/OhMercy","BobDylan/SubterraneanHomesickBlues","BobDylan/TimeOutOfMind","JeffBuckley","JohnMartyn","JoniMitchell","ReservoirDogsOST","RichardThompson/FrontParlourBallads/RichardThompson-06-MySoulMySoul.ogg","RichardThompson/RumorAndSigh/RichardThompson-12-MotherKnowsBest.ogg","RichardThompson/TheOldKitBag/RichardThompson-01-Gethsemane.ogg","RichardThompson/TheOldKitBag/RichardThompson-11-OutsideOfTheInside.ogg","SethLakeman","SusheelaRaman","TeddyThompson","Vangelis"] .br 699999987 ["BobDylan/BlondeOnBlonde","BobDylan/BloodOnTheTracks","BobDylan/Desire","BobDylan/ModernTimes","BobDylan/OhMercy","BobDylan/StreetLegal","BobDylan/SubterraneanHomesickBlues","BobDylan/TimeOutOfMind","JoniMitchell","ReservoirDogsOST","RichardThompson/FrontParlourBallads/RichardThompson-01-LetItBlow.ogg","RichardThompson/IWantToSeeTheBrightLightsTonight/RichardAndLindaThompson-13-TheCalvaryCross[Live-Bonus].ogg","RichardThompson/TheOldKitBag/RichardThompson-01-Gethsemane.ogg","RichardThompson/TheOldKitBag/RichardThompson-06-FirstBreath.ogg","RichardThompson/TheOldKitBag/RichardThompson-11-OutsideOfTheInside.ogg","SethLakeman","SusheelaRaman","TeddyThompson","Vangelis"] .br \fI700000000\fR ["ArabStrap","BobDylan/Desire","BobDylan/Highway61Revisited","BobDylan/Infidels","BobDylan/ModernTimes","BobDylan/StreetLegal","BobDylan/SubterraneanHomesickBlues","BobDylan/TimeOutOfMind","JeffBuckley","JoniMitchell","ReservoirDogsOST","RichardThompson/FrontParlourBallads/RichardThompson-01-LetItBlow.ogg","RichardThompson/RumorAndSigh/RichardThompson-08-BacklashLoveAffair.ogg","RichardThompson/RumorAndSigh/RichardThompson-12-MotherKnowsBest.ogg","RichardThompson/TheOldKitBag/RichardThompson-01-Gethsemane.ogg","RichardThompson/TheOldKitBag/RichardThompson-04-ALoveYouCantSurvive.ogg","RichardThompson/TheOldKitBag/RichardThompson-06-FirstBreath.ogg","SusheelaRaman","TeddyThompson","Vangelis"] .PP ^C .PP The exact match isn't unexpected, given the 2^71 possible combinations. The process was terminated after this solution was found, though where time permits, one may choose to wait for alternative exact matches. .SH AUTHOR Written by Dr. Alistair Ward. .SH BUGS .SS "REPORTING BUGS" Report bugs to \fBsqueeze\fR \fIat\fR \fBfunctionalley\fR \fIdot\fR \fBeu\fR .PP Home page: \fBhttp://functionalley.eu\fR .SH COPYRIGHT Copyright \(co 2010 Dr. Alistair Ward .PP This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. .PP This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. .PP You should have received a copy of the GNU General Public License along with this program. If not, see \fB\fR. .SH "SEE ALSO" The full documentation for \fBsqueeze\fR is generated by \fBHaddock\fR, & is available in the distribution.