Hamming Distance vs. Levenshtein Distance

For the problem I'm working on, finding distances between two sequences to determine their similarity, sequence order is very important. However, the sequences that I have are not all the same length, so I pad any deficient strings with empty points such that both sequences are the same length in order to satisfy the Hamming distance requirement. Is there any major problem with me doing this, since all I care about are the number of transpositions (not insertions or deletions like Levenshtein does)?

I've found that Hamming distance is much, much faster than Levenshtein as a distance metric for sequences of longer length. When should one use Levenshtein distance (or derivatives of Levenshtein distance) instead of the much cheaper Hamming distance? Hamming distance can be considered the upper bound for possible Levenshtein distances between two sequences, so if I am comparing the two sequences for a order-biased similarity metric rather than the absolute minimal number of moves to match the sequences, there isn't an apparent reason for me to choose Levenshtein over Hamming as a metric, is there?

Solution 1:

That question really depends on the types of sequences you are matching, and what result you want.

If it's not a problem that "1234567890" and "0123456789" are considered totally different, indeed Hamming distance is fine.

Solution 2:

In addition to the right Johan answer, the padding can be problematic.

For example, when you compare 123 to 123456 it's different if you pad either at the end of the string or at the start of the string. The similarity of ___123 with 123456 is 0, but The similarity of 123___ with 123456 is 3.