편집거리 알고리즘 Levenshtein Distance(Edit Distance Algorithm)

[[펌]https://madplay.github.io/post/levenshtein-distance-edit-distance

편집거리 알고리즘 Levenshtein Distance(Edit Distance Algorithm)

 

러시아 과학자 블라디미르 리벤슈테인(Vladimir Levenshtein)가 고안한 알고리즘입니다. 편집 거리(Edit Distance) 라는 이름으로도 불립니다. Levenshtein Distance는 두 개의 문자열 A, B가 주어졌을 때 두 문자열이 얼마나 유사한 지를 알아낼 수 있는 알고리즘입니다. 그러니까, 문자열 A가 문자열 B와 같아지기 위해서는 몇 번의 연산을 진행해야 하는 지 계산할 수 있습니다.

여기서의 연산이란, 삽입(Insertion), 삽입(Deletion), 대체(Replacement)를 말합니다.

 

간단한 예시를 통해 리벤슈테인 거리를 이해해봅시다. 문자열 A가 ‘대표자’ 라는 뜻을 가진 ‘delegate’ 라고 가정하고 문자열 B는 ‘삭제’ 라는 뜻을 가진 ‘delete’ 라고 가정합니다.

문자열 A에서 5번 째 문자 g와 6번 째의 문자 a가 삭제되면 문자열 B가 동일해집니다. 즉, 여기서의 연산 횟수는 2가 되는 것이지요.