# calculating the string similarity of an optimal alignment

## description of the algorithms behavior

I have two strings s1 and s2, with $$len\_s1 <= len\_s2$$. I would like to find the substring of s2, that has the biggest similarity to s1. The following alignments are possible:

[s2[:i] for i in range(len_s1)] + [s2[i:i+len_s1] for i in range(len_s2))]


e.g. for s1="ab" and s2="abcde" the following alignments should be considered:

['', 'a', 'ab', 'bc', 'cd', 'de', 'e']


The similarity between s1 and the substring s2_substr of s2 is defined in terms of a normalized version of the InDel Distance. The InDel-Distance is a variation of the Levenshtein distance, that only allows the use of insertions and deletions (this can be e.g. achieved using a weight of 2 for substitutions). The distance is normalized in the following way: $$1 - dist / (len\_s1 + len\_s2\_substr)$$. I am using a bitparallel algorithm to calculate the InDel-Distance in $$O([len_s1/w]len_s2)$$ with the computer wordsize w (64 bit or higher when using SIMD). The algorithm is described in the paper New Bit-Parallel Indel-Distance Algorithm by Heikki Hyyrö.

### Example

Here is a small example that shows how this algorithm works: For this example I am using the same example string shown above (s1="ab" and s2="abcde"). As shown above this generates the possible substrings of s2:

['', 'a', 'ab', 'bc', 'cd', 'de', 'e']


These substrings have the following similarities to s1

s1 len_s1 s2_substr len_s2_substr distance similarity
'ab' 2 '' 0 2 DEL -> 2 1 - 2 / (2+0) = 0
'ab' 2 'a' 1 1 DEL -> 1 1 - 1 / (2+1) = 0.66
'ab' 2 'ab' 2 0 1 - 0 / (2+2) = 1
'ab' 2 'bc' 2 1 INS, 1 DEL -> 2 1 - 2 / (2+2) = 0.5
'ab' 2 'cd' 2 2 INS, 2 DEL -> 4 1 - 4 / (2+2) = 0
'ab' 2 'de' 2 2 INS, 2 DEL -> 4 1 - 4 / (2+2) = 0
'ab' 2 'e' 1 1 INS, 2 DEL -> 3 1 - 3 / (2+1) = 0

In this case the alignment 'ab' <-> 'ab' has the biggest similarity, so the function should return a similarity of 1.

## Naive solution

A naive sliding window approach could calculate the distance in the following way:

max_similarity = 0
for s2_substr in variations:
substr_similarity = similarity(s1, s2_substr)
max_similarity = max(max_similarity, substr_similarity)


However this would have to test len_s1 + len_s2 possible alignments, so it has a complexity of O([len_s1+len_s2]*[len_s1/w]*len_s2. This becomes very slow for longer strings.

## Different implementations of this algorithm

A relatively similar implementation is included e.g. in the Python library FuzzyWuzzy, which searches for the longest common substrings of s1 in s2. The starting points of those substrings are then used to calculate the best alignment. However it is not guaranteed, that the optimal alignment starts with one of the longest common substrings and therefore calculates a wrong similarity in many cases.

## Question

Is there a faster algorithm to calculate this kind of similarity? The algorithm has the following requirements:

1. defines similarity in Terms of the normalized InDel-Distance
2. allows Gaps at start and end of s2
3. when s2_substr is not placed at the start or end of s2 it requires the length len_s1

As suggested by D.W. the smallest distance with gaps at start and end can be found by making insertions to the smaller string free in the start (init first row of the distance matrix with 0 instead of insertion costs). The smallest value in the result row is the distance for the smallest alignment. However this approach has a couple of problems:

1. it does not guarantee, that the length of the substring s2_substr is len_s1 for substrings that do not start at the start or end of s2. (Maybe this could be guaranteed with a modification, that I am just not aware of)
2. it searches for the alignment with the smallest InDel Distance. However I am trying to optimize the normalized InDel Distance as described above. Since the normalization depends on the length of the substring s2_substr, which is not constant (at start/end of the string it can be smaller than len_s1), this does not always give the correct results.

I think you should be able to adapt the standard dynamic programming algorithm to this, with a minor modification: you simply treat deletions at the beginning and end of s2 as costing 0.
• The question states: defines similarity in Terms of the normalized InDel-Distance. The normalization is described in the section description of the algorithms behavior. Is there anything I should add to the question to make this more clear? Mar 12 at 21:29
• That was a bad naming convention. It represents the length of the substring, so I renamed it to s2_substr/len_s2_substr and added an example calculation of the algorithm Mar 12 at 23:01