Levenstein distance limit

Question

If I have some distance which I do not want to exceed. Example = 2. Do I can break from algoritm before its complete completion knowing the minimum allowable distance?

Perhaps there are similar algorithms in which it can be done.

It is necessary for me to reduce the time of work programs.

Answer 1

Yes you can and it does reduce the complexity.

The main thing to observe is that levenstein_distance(a,b) >= |len(a) - len(b)| That is the distance can't be less than the difference in the lengths of the strings. At the very minimum you need to add characters to make them the same length.

Knowing this you can ignore all the cells in the original matrix where |i-j| > max_distance. So you can modify your loops from

for (i in 0 -> len(a))
   for (j in 0 -> len(b))

to

for (i in 0-> len(a))
   for (j in max(0,i-max_distance) -> min(len(b), i+max_distance)) 

You can keep the original matrix if it's easier for you, but you can also save space by having a matrix of (len(a), 2*max_distance) and adjusting the indices.

Once every cost you have in the last row > max_distance you can stop the algorithm.

This will give you O(N*max_distance) complexity. Since your max_distance is 2 the complexity is almost linear. You can also bail at the start is |len(a)-len(b)| > max_distance.