[알고리즘] 스트링 편집거리 (Levenshtein Distance)

스트링 편집거리 (Levenshtein Distance)

• 두 스트링의 유사도를 측정하기 위해 사용
• Levenshtein Distance(LD)라고도 함
• 원래의 스트링을 𝑆(source), 편집하고자 하는 목표 스트링을 𝑇(target), 각각의 문자열의 길이를 𝑚,𝑛
• 𝛿_𝐼는 삽입 연산의 비용
• 𝛿_𝐷는 삭제 연산의 비용
• 𝛿_S는 교환 연산의 비용
• 편집 거리 : 𝑆를 𝑇로 변환하는데 필요한 삽입,삭제,대치연산의 최소 비용
  • 𝑆 = “test”, 𝑇=“test” → LD(𝑆, 𝑇) = 0
  • 𝑆 = “test”, 𝑇=“tent” → LD(𝑆, 𝑇) = 1
• 편집 거리가 커질수록, 두 스트링의 유사도는 낮아지게 됨
• 𝐷[𝑖][𝑗]를 𝑆=𝑠1𝑠2 ...𝑠𝑗와 𝑇=𝑡1𝑡2 ...𝑡𝑖 사이의 편집 거리라고 할 때, 𝐷[𝑖][𝑗]의 점화식 (Recursive Property)은 아래와 같다.

recursive property

 

 

---

 

실습 및 코드는 아래 GitHub를 참고해주세요!

https://github.com/oneonlee/Computer-Science/tree/main/3.%20Algorithms/05.%20Dynamic%20Programming/Levenshtein%20Distance

GitHub - oneonlee/Computer-Science: Introduction to Computer Science