[Algorithm] 편집 거리 문제 : 동적계획알고리즘

❓문제

• 삽입, 삭제, 대체 연산을 사용하여 문자열 S를 문자열 T로 변환 시키는데 필요한 최소의 편집 연산 횟수, 즉 편집거리를 찾아라!

동적계획 알고리즘 Remind
- 작은문제에 대한 모든 가능성을 고려해서 다음 크기의 문제에 대한 최적해를 결정 -> 항상 최적해를 구할 수 있음
- 해당 문제에서, 최적성의 원리는 만족됨!

 

💡생각해야할 것

• 문자열을 바꾸는데, 어떤 연산을 어느 문자에 수행하는가에 따라 편집 연산 횟수가 달라진다.

 

💡동적 계획 알고리즘으로 해결하려면 부분 문제들을 어떻게 표현?

• 만약 접두부에 대한 편집거리를 알고있다면 (최적성의 원리 만족), 각 스트링의 나머지 부분에 대해서 편집거리를 찾음으로써 주어진 입력에 대한 편집거리를 구할 수 있다.
• 부분 문제 정의
  • E[i,j] : S의 접두부의 i개의 문자를 T의 접두부 j개의 문자로 변환시키는데 필요한 최소 편집 연산 횟수, 즉 편집 거리이다.
  • 'strong' -> 'stone'으로 바꾸는데, 점진적으로 E[6,5]를 해결하면 문제의 해를 찾게 된다.

예제)

 

 

일반화

• E[i,j]는 E[i-1, j], E[i,j-1], E[i-1,j-1]의 해가 미리 계산되어 있으면 계산 가능하다
• 그러므로, 편집 거리 문제의 부분 문제간의 함축적인 순서는 다음과 같다.

  

• 위의 3가지 경우 중, 가장 작은 값을 E[i,j]의 해로서 선택한다.
  • E[i,j] = min{E[i,j-1] + 1, E[i-1,j] + 1, E[i-1,j-1]+a} 
  • 단, si != ti 일때 a=1, 그렇지 않으면 a=0

 

초기화

 

 

💡 편집 거리 계산 알고리즘 (EditDistance)

• 입력 : string S,T ( S의 길이 = m, T의 길이 = n)
• 출력 : S를 T로 변환하는 편집거리, E[m,n]

• for i to m E[i,0]=i	// 0번 열의 초기화
  for j to n E[0,j]=j	// 0번 행의 초기화
  for i=1 to m
  	for j=1 to n
      	E[i,j] = min[E[i,j-1]+1, E[i-1,j]+1, E[i-1,j-1]+a}
  return E[m,n]

 

⏰ 시간복잡도

• O(mn) : m,n은 각 두 문자열의 길이
• 이유 : 총 부분 문제의 수가 배열의 원소 수인 m x n이고, 각 부분 문제를 계산하기 위해서 주위 3개의 부분문제들의 해를 참조한 후 최솟값을 찾는 데는 O(1)의 시간이 걸린다.

 

응용

• 생물 정보 공학 및 의학분야에서 두 개의 유전자가 얼마나 유사한가를 측정하는데 활용
• 철자 오류 검색
• 광학 문자 인식의 보정시스템
• 자연어 번역 소프트웨어 등

 

---

Reference

• 서울과학기술대학교 컴퓨터공학과 알고리즘 수업
• 알기쉬운 알고리즘 도서