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