[알고리즘]Levenshtein distance(1)

Levenshtein distance(리벤슈테인 거리)

 

---

Levenshtein distance는 러시아의 과학자인 Vladimir Levenstein에 의해 고안된 알고리즘입니다.

다른 말로는Edit distance 즉 편집 거리라는 이름으로 불립니다.

 

두 문자열이 주어졌을 때, 두 문자열에 연산을 가하여 얼마나 연산을 가해야 동일해지는지 구하는 알고리즘입니다.

                                           

                                             이때 연산은 insert, delete, replacement를 말합니다

 

 

---

위의 예시를 통해 알아보겠습니다. 

 

KITTEN과 SITTEN이라는 두 문자열이 주어졌다고 가정해보겠습니다. KITTEN- -> SITTEN을 위해서 K를 S로 바꾸는 substitution을 한번만 수행하면 됩니다.  

 

두번째 예시입니다. 

 

KITTEN과 SITTING이 주어졌습니다. 먼저 K->S로 substitution을 한 번 수행하고 E->I로 같은 연산을 반복합니다.

추가로 G를 insert해주면 총 3번의 연산을 통해 SITTING이 완성됩니다. 

 

---