Step 1: Similarity and Distance Measures

• For strings x, y:

  • Hamming distance: dH(x,y)= | {i | xi = yi } |
  • Edit distance: de(x,y)= mini {x ? i y },
    • where x ? x’ if x becomes x’ by deleting, replacing, or adding one character

Previous slide

Next slide

Back to first slide

View graphic version