Generate a value that identify a string and find duplicates / nearly duplicates

tags:

.net
c#

views:

answers:

+1 Q:

Generate a value that identify a string and find duplicates / nearly duplicates

I need a table that contains information about a file, and a value that identifies the content in this file. The filetypes is primarily pdf, and i have the logic to extract content from the files in place.

Right now i create a hash value of the content and place this in the table. With this value i am able to find duplicate files. But, the customer also want to identify files that are nearly the same. For example if the copyright information is changed - or some other minor change. There is going to be a manual review of the result of this, so I don't need a 100% hit rate.

The first thing that come to my mind is to make a table that contains the 50 most popular words, and associate them with an id. Than i can use this and do a word count in each of the documents. The result will be a string like this ( where word 1 is hit 20 times, word 2 12 times ) "1:20-2:12......"

Anyone have a better suggestion on how to make a value that can identify nearly identical files / strings?

+1 A:

You may take a look at the Levenshtein distance which is used to compare similarity between sequences and here's a sample implementation in C#.

Darin Dimitrov 2010-03-09 09:30:16

As far as i can see, Levenshtein distance is only able to compare 2 values at the time? I have to generate a value for around 70 000 files and then compare this values.

Svendberg 2010-03-09 09:36:37

The `value` could be the contents of the file. So to compare if two files are identical or `close` you calculate the Levenshtein distance between their respective string contents. The closer to 0 the more identical these files are.

Darin Dimitrov 2010-03-09 09:39:36

This could absolutely be a solution, but the downside is that i have to store all document content in the database. I hoped i could use a shorter value like a hash or something. But thank you for the tip! :)

Svendberg 2010-03-09 09:56:06

Instead of storing the contents of the files into the database, store Levenshtein distances between them.

Darin Dimitrov 2010-03-09 10:01:54

Levenshtein distances is relative to a file. Do you think it would work to store the distance to a "reference" file? Will a file with a distance of 588 be nearly the same as a file with a distance of 595 compared to a reference file?

Svendberg 2010-03-09 11:48:58

Two solutions come to my mind:
1. There are many diff tools that allow the text to be compared, like WinMerge, which can also compare whole folders. You could extract pdf contents to text files, then invoke the tool from inside your program and count the number of differences, which should tell you how different the files are.
2. You are probably computing md5 or sha1 hashes, which change drastically on minor change of the input. Try to find (or create) algorithm that doesn't change the hash that much. You may have many collisions, but this should be easy to tackle.

ya23 2010-03-09 09:51:43

Solution 2 would be exactly what I am looking for. The only problem is that I am unable to find any hash algorithm that don't change that much. The word count solution i suggest in the question is an approach to create a "hash", but i don't think thats the most effective.

Svendberg 2010-03-09 10:01:59

Do you know what are the expected differences between files? If they are minor, you could just count the number of newlines and occurrences of each character and compare the results. This is very naive solution, that will likely produce some errors, but may be good enough as you do not need definite answer. And should be trivial to implement :)

ya23 2010-03-09 10:27:24

I don't know what differences to expect, but i will take i look into counting newlines! :)

Svendberg 2010-03-09 11:45:32

ansaurus

tags:

views:

answers:

Generate a value that identify a string and find duplicates / nearly duplicates

related questions