edit distance edit distance, a.k.a. Levenshtein distance The minimum number of edit operations(insertions, deletions and substitutions) of single characters needed to transform the string SI into $2 E xample SI: unne cessarily Edit distance(s1, s2)=3 S2: un escessaraly O(SI, S2D Problem last names first names and street names that did not agree on a character-by- character basis For example: Similarity (John R Smith, Johathan Richard Smith)=11Edit distance ◼ Edit distance, a.k.a. Levenshtein distance The minimum number of edit operations (insertions, deletions, and substitutions) of single characters needed to transform the string S1 into S2. ◼ Problem: last names, first names, and street names that did not agree on a character-by￾character basis For example: Similarity(John R.Smith,Johathan Richard Smith)=11 ◼ Example1: S1：unne cessarily Edit distance(S1,S2)=3 S2：un escessaraly O(|S1| ,|S2|)