Table of contents

1. History
2. The different versions of the program

What language	The license under which it's distributed
Latest Python version	Copyright (C) Dan Stromberg, available under the GPL, v2, or any later version, at your option
Original Python version	Copyright (C) The university of California, Irvine - it specifically is not available any version of the GPL.
Perl version	Copyright (C) Dan Stromberg, available under the GPL, v2, or any later version, at your option
Java version	Copyright (C) Dan Stromberg, available under the GPL, v2, or any later version, at your option
C++ version	Copyright (C) Dan Stromberg, available under the GPL, v2, or any later version, at your option
Haskell version (planned)
Eiffel/Sather version (planned)

I first learned how useful dividing files up into equivalence classes can be, when I happened upon the classify program by Mark-Jason Dominus. Basically, this sort of program just divides up a bunch of files into "equal groups", where equality can be defined in a variety of ways, like bit for bit identical, or the same except whitespace, or the same except ignoring upper and lower case distinctions.

But classify, for all its really nice, convenient options, is a bit slow on large collections of files, and (years ago) I wanted to look at a collection of "fortune cookie" messages and eliminate duplicates. First, I added a "-" option to classify, to make it able to read a list of files from stdin to get around the argv limit. But it was still pretty slow going for this (at the time) large collection of files and my poor little linux machine. So to handle those cookie files, I wrote a similar program, I've named equivs. equivs, like classify, is O(c*n^2), but unlike classify, equivs uses a sort of incremental md5 digesting algorithm to get a far smaller "c", frequently giving much better run time at the expense of having far fewer convenient options.

But for years, it'd been in the back of my mind that I should redo my equivs program so it would have a running time of O(n*log(n)). And I finally did it. The new program is called equivs2.

"New and Improved" python version

equivs3d is a new python version that uses a still-better algorithm.

The run time has dropped from O(nlogn) to O(n + mlogm) where n is the total number of files and m is the number of files in the longest hashbucket that suffers an md5 collision - IOW, it's normally O(n).

For a collection of n duplicate files there will typically be O(2n) full file reads (unless the files are hard linked, in which case things are faster), and unique files are typically read once at most (often they won't need to be read fully even once).

As with equivs2, MD5 is trusted to tell files apart, but when files have the same md5 hash, it is not assumed that they must be equal; they almost certainly are, but it remains possible that they are not.

This is probably the fastest version on this page despite (or you could even say "because of") the implementation language because it uses a better algorithm.

equivs2, is the python version, and it totally blows the doors off of my old equivs program in terms of performance, but like equivs, it doesn't have the array of convenience features that classify does. They'd be pretty trivial to add though.

However, lacking the convenience options of classify doesn't always have to be a show stopper. Sometimes what I do is use find and tr to create a shadow directory that has a modified copy of each file I'm interested in, with an identical directory hierarchy, and then use equivs or equivs2 on that directory hierarchy. Then you get a bunch of relative paths, that apply to either directory hiearchy, with the net effect being the same as with classify, but actually more flexibly - but it's also more time consuming.

equivs2 usage is like:

$ equivs2 -h
Usage: /Dcs/seki/strombrg/bin/equivs2 [-v] [-s] [-0] [-h] [-f file1 file2 ... filen]
-v says to operate verbosely
-s says to get filenames from stdin instead of from the command line
-0 says that when getting filenames from stdin, assume null termination, not newline termination
   Also changes the default output delimeter to a null byte, because some shells cannot handle that
-h says to give this help message
-f file1 file2 ... filen says to use the listed files, not files fromstdin
-p bytes says to cache this many bytes of each file for faster comparisons (may be 0)
-d delim says to use "delim" as the output delimeter character within a line
-c says to not do full comparisions - instead trust hash comparisons.
   Faster at the expense of some accuracy
seki-strombrg:~ i386-redhat-linux-gnu 18834 - above cmd done Sat Apr 22 10:24 PM

$

If perl is what floats your boat, here's a perl implementation of equivs2, called "equivs2-p". The perl version is actually slightly faster-running, but I just don't care for perl much - too many ways of doing the same thing (outside of algorithm differences, which are of course essential), and the OOP felt rather bolted on after-the-fact. I wrote it mostly to prove to myself that I could take a semi-serious programming task and code it in perl.

You can get the java version here.

It has Makefile's for both OpenJDK and gcj. The OpenJDK Makefile will probably work fine with Sun Java.

Note that you may have to install an en_US.ISO-8859-1 locale on your system for it to work; this is because in java (and other languages?) en_US.ISO-8859-1 is a locale that is guaranteed to give good roundtrip filename conversions from 8 bit to 16 bit characters and back to 8 bit, as the program reads 8 but filenames from stdin, converts them to 16 bit internally, and then converts them back to 8 bit again for opening. You can find information about how to configure the en_US.ISO-8859-1 locale on an Ubuntu system here.

It was fun doing the java version, though the locale stuff was a larger hurdle than usual.

The java version doesn't have the device/inode number optimization. Java doesn't appear to expose that, probably because not all OS's have it.

Here's a C++ version. It should be pretty fast, but I haven't tested that.