Hacker News Reader

Comment by js8 | Hacker News Reader

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.

View on HN

I 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.

Thanks, 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?

Different 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.

> 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.

goodtar:

    #!/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?

I 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

I 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.

You 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.

First, I am not looking for optimal solution, good approximation is perfectly valid solution.

Second, what you describe is not the best you can do.

Reply on news.ycombinator.com