Statistically fuzzy version of a checksum for file text signature

Question

Background: Often I end up downloading the same pdf article twice since I do not remember I've already downloaded it. One way around is to maintain an index of cheksums (say md5 etc.) based on the plaintext conversion of a pdf and if a match is found do not re-download.

Problem is online downloaded papers often have a timestamp, IP, or other embedded information in the footers or an extra beggining page from the downloading service. This precludes an exact checksum. Further if the pdf consists of scanned images an OCR pre-processing step is needed and the output might vary a tiny bit every time. Even the pdf->plaintext conversion utilities are not error free and might add some noise while converting formatting, equations, tables etc.

The Statistics:

What might be a good way to signature an article's text that is robust to such small noise? One option I can think of is, say, the frequency spectrum of the top 20 most common words in any given paper. But that is prone to get diluted by "the, a" and all the common words.

What else might be good ideas for a fuzzy variant of a cheksum? By design for md5sum etc. the output changes drastically for even tiny changes in input. I don't want this property.

Answer 1

You might use SimHash for that, I've successfully implemented a version of it to detect similar texts in a fairly large set. Here is a nice description of how it works SimHash Algorithm. It's basically a hash, but in "reverse", two similar strings A and B will result in simhashes with a small hamming distance.