Edit distance - simplest

d(i,j)= min

{

d(i-1,j)+ 1

d(i,j-1)+ 1

d(i-1,j-1) if vi=wj

d(i,0) = i

d(0,j) = j

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

Naive implementation:complexity exponential in i and j

Previous slide

Next slide

Back to first slide

View graphic version