[알고리즘] 스트링 편집 거리

스트링 편집 거리(string edit distance)

• 두 스트링의 유사도를 측정하기 위해 사용
• Levenshtein distance(LD)라고도 함
• 원래 스트링을 S, 목표 스트링을 T
• S를 T로 변환하는 데 필요한 삽입, 삭제, 대치 연산의 최소 비용
• 편집 거리가 커질수록, 두 스트링의 유사도는 낮아지게 됨
  • 논문이나 보고서의 표절 검사, DNA 염기 서열의 유사도 검사 등에 사용됨
• 동적 계획법의 적용

 

스트링 편집 거리 예시를 들어 설명하겠습니다. 

S = GUMBO

T = GAMBOL

 

1.  U -> A 로 교체
2.  L 을 추가

따라서, GUMBO를  GAMBOL로 변경하는 최소 편집 거리는 2임을 알 수 있습니다.

---

스트링 편집 거리를 구하기 위해선, 간단히 표로 작성하여 구할 수 있습니다.

 

 

1. 초기 테이블을 작성합니다. (흰색 글자부분을 미리 작성해두기)

2. 우리가 사용할 수 있는 연산 키로는 교체, 삽입, 삭제가 있습니다.

아래의 그림을 옆에 두고, 표를 채우면 쉽게 작성할 수 있습니다. 

 

3. 위에 표를 이용하여 가장 작은 값이 무엇인지 확인하고, i행 문자와 j행 문자가

같으면 교체 vs 삽입, 삭제 중 최소 값 + 1 둘 중에 더 작은 값, 

다르면 교체, 삽입, 삭제 중 최소 값 +1

을 하여 표를 채워줍니다. 

 

 

작성 예시입니다.

교체, 삽입, 삭제 중 최소 숫자 = 0

A 와 U 가 다른 문자이므로, +1 을 해주어 1을 채워 줍니다.

 

교체, 삽입, 삭제 중 최소 숫자 = 1

A 와 M 가 다른 문자이므로, +1 을 해주어 2를 채워 줍니다.

교체, 삽입, 삭제 중 최소 숫자 = 2

A 와 B 가 다른 문자이므로, +1 을 해주어 3을 채워 줍니다.

 

교체, 삽입, 삭제 중 최소 숫자 = 3

A 와 O 가 다른 문자이므로, +1 을 해주어 4를 채워 줍니다.

 

---

위와 같은 방식대로 표를 채워나가게 되면, 아래와 같은 표를 완성할  수 있습니다. 

 

 

표를 이용하여, 스트링 편집 거리를 구하는 방식을 알아보았습니다.

 

틀린 점이나 궁금하신 점이 있다면 댓글 남겨주세요😀