Edit distance - a little more sophisticated

d(i,j)= min

{

d(i-1,j)+ 1

d(i,j-1)+ 1

d(i-1,j-1) + t(vi,wj)

d(i,0) = i

d(0,j) = j

Given two strings V=v1..vi and W=w1..wj

t(vi,wj) = 0 if vi=wj

t(vi,wj) = 1 if vi ? wj

(We can now alter penalties for character mismatches)

Naive implementation: complexity exponential in i and j

Previous slide

Next slide

Back to first slide

View graphic version