Edit Distance

Edit Distance

Edit distance is ...

... given two character strings \(s_1\)

How to compute edit distance?

Dynamic Programming

A tabular omputation \(D(n, m)\)

Compute \(D(i, j)\) for all \(i\) (\(0<i<n\) ) and \(j\) (\(0<i<m\) ).

Minimun Edit Distance (levinshtein)