Levenshtein Distance란?

한 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 연산 수

편집 연산:

• 삽입 (Insert): a → ab
• 삭제 (Delete): ab → a
• 치환 (Substitute): ab → ac

---

동적 프로그래밍으로 계산

---

예시: "kitten" → "sitting"

---

Damerau-Levenshtein Distance

Levenshtein + 전치(Transposition)

왜 중요한가?

• 오타의 많은 부분이 전치 (타이핑 순서 실수)
• "teh" → "the" (1 전치)
• "recieve" → "receive" (1 전치)

---

유사도(Ratio)로 변환

---

가중치 Levenshtein

모든 연산이 동일 비용?

---

언제 Levenshtein을 쓰는가?

적합한 경우	부적합한 경우
짧은 문자열	긴 텍스트
단일 단어	다단어 구문
오타 탐지	동의어 매칭
철자 교정	의미적 유사도

한계:

• O(m*n) 시간 복잡도 → 긴 문자열에 느림
• 단어 순서에 민감 → "John Smith" vs "Smith John"
• 언어 독립적 → 발음/의미 무시