Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am looking for a way to compare a set of files against a given file with each comparison giving me a "closeness" metric. I should then be able to order based upon the metric to find the closest file. I considered using diff, but afaik this only provides a yes or no on whether a particular line matches, which is too large a scale for my purposes as for my purposes a word change in a line of text is closer than a completely different line whereas diff returns no-match for both cases.

Would I be able to use a soundex effectively on a 100 or more line file or is there a better algorithm? Also is there a metric which would provide a positive match if the lines which were similar were on drastically different line numbers?

Thanks

share|improve this question
    
Thanks for the replies so far, I'll have a play about this evening and comment accordingly. –  Gruffputs Jan 18 '11 at 16:08

5 Answers 5

I've used Levenshtein distance before to good effect. You can find examples in several languages here: http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance.

This algorithm gives you a number greater than 0 to show how far apart the two sets of data are, with 0 meaning the sets are identical.

share|improve this answer

You could use diff and count the number of lines that differ:

diff f1.txt f2.txt | wc -l

This will give you a numeric range

share|improve this answer

Vector Space Model

A common method for comparing whole documments is a Vector Space Model which represents each word as a vector and then makes it possible to compare those vectors with another document to measure similarity

That gives you more documents with similar content though and not necessarily similar text. For that you typically use something called Levenshtein distance, not sure if it's feasible for whole documents though (it's mostly used on strings)

Also see this

share|improve this answer
    
I've used Levenstein Distance on fairly large text files before, though I was actually using it to find out if a source file had a block of text similar to our copyright statement template. –  JohnL Jan 18 '11 at 13:51

I would believe you could go a long way with diff. If you take a look at the Diff algorithms it might be extensible to be more fine grained than per line level

http://c2.com/cgi/wiki?DiffAlgorithm

share|improve this answer

You can still use diff if you alter its inputs so that every character appears on a separate line:

diff <(sed 's/\(.\)/\1\n/g' <file1) <(sed 's/\(.\)/\1\n/g' <file2) | wc -l

The <(...) syntax requires bash and conceptually means "run ..., directing its output to a temporary file somewhere, and replace the <(...) construct with the name of this temporary file, deleting it afterwards" (although it will use FIFOs if available instead of actual temporary files). It's a nice way to use the output of a process as a named input file for a program, which is necessary when the consuming program can't read from stdin or requires 2 separate sources of input (as is the case with diff here).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.