9

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.

user2274879
  • 211

1 Answers1

8

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.

rrenaud
  • 1,088
  • 5
  • 11
  • 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? – user2274879 Apr 23 '13 at 15:18
  • 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. – rrenaud Apr 23 '13 at 15:23
  • 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. – user2274879 Apr 23 '13 at 15:30