Natural Language Processing with Probabilistic Models - Week 1

Lecture : Autocorrect and Minimum Edit Distance

Autocorrect

• spell is correct but context is incorrect

Building the model

• step 1
  - identifying the misspelled word
  

• step 2
  - finding the strings that are n edit distances away

• step 3
  - filtering the candidates that are actual words

Building the model II

Minimum edit distance

• calculate edit distance

• DNA strings by brute force(무차별) adding

  • computational complexicity increases exponentially

• Alternative : tabular approach

Minimum edit distance algorithm

• dynamic programming

• p to #

• p to s

Minimum edit distance algorithm II

• adding 1

• because a, y not changed

Minimum edit distance algorithm III

• What we used is Levenshtein distance

• saving the result and use it again