Does anyone know of a simple way to compare two strings together to generate the "amount of difference" between the two? (in a numeric value) I have been crawling google with little luck on this. And after doing some coding it's not as simple as I had thought. Any clues?
Asked
Active
Viewed 1,193 times
4 Answers
5
Are you talking about the "Edit Distance"? Do a search on "Levenshtein Distance", on SO or Google. I use the version posted on Stephen Toub's blog
Danimal
- 7,530
- 8
- 43
- 57
-
Upmod for being faster than me. :) – Bill the Lizard Oct 09 '08 at 18:18
-
that's one of the great things about SO -- I saw an earlier post on the topic, and it was immediately useful for me. Glad I could return the favor! – Danimal Oct 09 '08 at 18:20
2
You're looking for the Levenshtein distance.
Bill the Lizard
- 386,424
- 207
- 554
- 861
-
By 10 seconds. That's actually a lot considering the Levenshtein distance between what we each typed. – Bill the Lizard Oct 09 '08 at 18:21
1
You might want to look into the Levenshtein and Hamming distances. One calculates edit distance (insert, delete, modify) and the other bit flips.
Aaron Maenpaa
- 113,855
- 10
- 93
- 108
0
You would need to very clearly define "amount of difference". There's a lot of wiggle room in there.
For example, the old C/C++ function strcmp() function compared character by character and returned the difference the first time they didn't match.
On the other hand, the diff program provides a comprehensive list of differences between two files (which, in once sense, are also strings). How would you quantify that?
Joel Coehoorn
- 380,066
- 110
- 546
- 781