Fuzzy Text Matching

To be able to find a bibtex entry submitted for a paper, when another user has the same paper, however in a slightly different version (marked up PDF, or pre-print vs publisher's version).

Extract text (for example with texttopdf), and use some kind of perceptual hash.

I got ssdeep and simhash running (both below). SSDeep was able to index 150,000 Wikipedia HTML pages in 10 minutes (using 16% CPU, could probably be parallelized and speeded up a lot), and it correctly recognized one file that had been modified in a few ways in 0.5s.

However, when comparing the output of pdftotext of a pre-print at ijCSCL with the pdftotext of the final article on Springer, it gave a 0 match, whereas Simhash gave .77.

• Ask proggit: are there any hash algorithm that can tell 0% - 100% likeness of two binary files? Let's say let's say hash 0xffffffff and 0xfffffffe means the two files are 87.5% alike : programming
• My question on StackOverflow
• math - Algorithm for finding similar images - Stack Overflow
• Looks Like It - The Hacker Factor Blog
• Simple Simhashing - Linear-time clustering for huge datasets. : programming

• Text's Source Trustworthiness Detection Based on Cognitive Hash - ACM
• Perceptual Hashing of Textual Content Biryukov Maria University - nice overview of some algorithms (slides)
• Locality-sensitive hashing - Wikipedia, the free encyclopedia
• MinHash - Wikipedia, the free encyclopedia

Developed by Google, apparently patented by them. A number of implementations.

• Original paper (ACM)
• IEEE Xplore - On the Effectiveness of Simhash for Detecting Near-Miss Clones in Large Scale Software Systems
• Semi-Supervised SimHash for Efficient Document Similarity Search (paper)
• Useful slides

• Simple Simhashing – Ryan Moulton's Articles
• simhash - about the algorithm
• Simhash in Ruby | The Tupalo.com Blog

• C# implementation of SimHash
• C implementation
• Javascript implementation
• Ruby simhash gem documentation github pages

simhash -w *.txt

write hash for each file to <file>.sim

simhash -c hashfile1 hashfile2

show distance between two hash files (normalized to 0..1)

simhash -m *.txt

output similarity matrix for all files

• Initially algorithm developed as part of Spamsum
• Project page
• redstack » Blog Archive » Ssdeep Ruby Bindings

ssdeep -p *.txt 

finds all matches among all the files selected

ssdeep *.txt > hashes.txt

writes hashes for each file to stdout (or hashes.txt with redirect)

ssdeep -m hashes.txt newfile.txt 

matches a new textfile to the list of hashes in hashes.txt

Does images, video and audio, as well as text. Has a Ruby gem. C library has a way of persisting hashes and rapidly matching large numbers, but no Ruby bridge exists.

• pHash.org: Home of pHash, the open source perceptual hash library
• Reddit discussion
• Detecting Duplicate Images with Phashion - Ruby gem that only does images
• PHash gem - does all four categories, but no persistent datastore

BibSonomy has apparently developed a way of hashing a bibtex entry to be able to deduplicate publication submissions

• Bibliographic Hash Key – Verbund-Wiki GBV
• BibSonomy - Inside BibSonomy

• Perceptual Hash Algorithm - Python Implementation
• LSHKIT: LSHKIT: A C++ Locality Sensitive Hashing Library

  ---

• andrewclegg/sketchy · GitHub