Edit distance ED(r s): The minimum number of single-character edit operations(insertion/deletion/substitution )to transform r to s o For example: ED(marios, maras)=2 8012345 m101 34 Dij=min (Di l, j +1,Di,jI+1,a 2 1 substitutea-p 321 Ⅰ sert o 0 if a,=b i4321 where t lifa.≠b 5432 654332 1/28/2021 Taste@ ICDE2012 9/42 ED(r, s): The minimum number of single-character edit operations(insertion/deletion/substitution) to transform r to s.  For example: ED(marios, maras) = 2 Di,0 = i, D0,j = j, Di,j = min{Di-1, j + 1, Di, j-1 + 1, Di-1, j-1 + t i, j}, 0 if ai = bj 1 if ai  bj . Edit Distance 1/28/2021 Taste @ ICDE2012 9/42 where t i, j = Substitute a->i Insert o