5
$\begingroup$

I am working on a project that involves computing similarity metrics between strings. I was would like to know whether it is possible to use hamming distance on strings with differnt length, and if possible, how to go about it. I step by step explanation would be grately appreciated.

Thanks.

$\endgroup$
  • $\begingroup$ Given that you only want a crude fast measure, why not just pad out the shorter strings with empty characters? In effect, define the Hamming distance to be the number of places in which the two strings differ plus the difference in their lengths. $\endgroup$ – whuber Apr 23 '13 at 16:15
  • $\begingroup$ Here's a search for Levenshtein on stackoverflow. $\endgroup$ – Mike Dunlavey Apr 23 '13 at 16:22
5
$\begingroup$

Hamming distance fundamentally assumes that the input strings are the same length. You can generalize hamming distance a bit to allow for insertions and deletions and arrive at the Levenshtein distance. How big are your strings? The edit distance is much harder to compute for long strings.

$\endgroup$
  • $\begingroup$ I am working on address field of a database. My strings have varying length; say 4 to 6 words. Please can you break down how to generalise the hamming distance to allow for insertion? $\endgroup$ – user2274879 Apr 23 '13 at 15:18
  • $\begingroup$ That wikipedia article does a much better job explaining it than I will. It's not a particularly simple idea, you shouldn't expect to understand it, and especially how to compute it, immediately. The basic idea is to add costs to the delete and add operations on strings. Then find the minimum cost sequence of edits between strings, which can be done with dynamic programming. You can probably find an implementation of the algorithm in your language of choice, or implement it yourself from the pseudocode on that page. $\endgroup$ – rrenaud Apr 23 '13 at 15:23
  • $\begingroup$ my aim is to use a variant of levenshtein distance that requires relatively less computational cost, thats why I opted for hamming distance. However, the variablity in string length might pose a problem. $\endgroup$ – user2274879 Apr 23 '13 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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