4 ms·
Not sure if this is good place to ask, but is there some Unix utility to presort files, based on content, to feed them into tar or zip in correct order so they
by js8 11y ago
Not sure if this is good place to ask, but is there some Unix utility to presort files, based on content, to feed them into tar or zip in correct order so they would compress better by virtue of being similar?
I think it would be very useful if tar or zip could do that automatically, and it seems like low-hanging fruit in compression.
Actually, thinking about it, the tool could later in more general fashion rearrange the content inside the files. So it would map each file into blocks of similar characteristics that would then be compressed in correct order across files.
- castratikron 11y agoI think what you're describing is called the knapsack problem, so I'd guess the answer is no. The best you could do is randomly order the files and compress them, and do that a few times and pick the best ordering.
- js8 11y agoFirst, I am not looking for optimal solution, good approximation is perfectly valid solution. Second, what you describe is not the best you can do.
- gwern 11y agoYou can do much better than that: you can use summaries or hashes to get a short version of each file and then compare the hashes for similarity. (Much like using perceptual hashes to find similar images.) A tool that does this is 'binsort'. It's O(N^2) IIRC, because of all the pairwise comparisons, but it's usable for up to a few hundred or thousand files.
- baruch 11y agoI usually use something like the following to do it: find $DIR -type f | rev | sort | rev | tar -cv -T /dev/stdin -f $OUTPUT.tar Add a -j or -z or any other compressor you want. This will sort the files on reverse filename order so that similar sounding files will go together. It's not perfect and I had an idea to write something better but since it's usually enough I didn't really bother. Only thing that is needed is a program that takes a list of files and sets them in order for tar to do the packing and gzip/bzip2 compress the hell out of the pre-ordered files.
- js8 11y agoThanks, I am aware of tricks like that, but it gets tiring really fast, so I don't use that in practice. Why can't they just add another flag to tar to call a program that would produce the ordering, just like they have compressor flags?
- deoxxa 11y ago> Why can't they just add another flag to tar [...]? You are "they" - you can add that flag. If it turns out that it works well, it'll (probably) be taken and added to whichever `tar` implementations you submit patches for.
- baruch 11y agoDifferent people will want different sorts for different needs, you can already feed tar the list of sorted files so it only takes another program to provide the specific sorted order for you. I actually do not really know why they bothered with the -z -j and such compression options when you could already pipe to a compressor of choice.
- capitalsigma 11y agogoodtar: #!/bin/bash find $3 type -f | rev | sort | rev | tar -cv $2 -T /dev/stdin -f $1 Now put `goodtar` in `/usr/bin`. Whenever you want to compress stuff, just say: goodtar -j output.tar mydir What's making you tired?
- baruch 11y agoI just created a quick hack which is essentially at this level but I would try to improve upon it, it can be found at: https://github.com/baruch/sortedtar https://github.com/baruch/sortedtar
- capitalsigma 11y agogoodtar: #!/bin/bash find $3 type -f | rev | sort | rev | tar -cv $2 -T /dev/stdin -f $1 Now put `goodtar` in `/usr/bin`. Whenever you want to compress stuff, just say: goodtar -j output.tar mydir What's making you tired?