최소 편집 거리 (Minimum Edit Distance) 알고리즘

Joohyun·2022년 3월 5일

알고리즘

목록 보기

3/3

Minimum Edit Distance Algorithm

2개의 문자열이 같아지기 위한 최소 수정 횟수(Add, Delete, Edit) 를 구하는 알고리즘
두 문자열의 유사도를 수치화 (ex. 문서 표절 검사 프로그램)

Dynamic Programming (동적 프로그래밍)

Minimum Edit Distance Algorithm은 DP를 이용
특정한 문제를 잘게 쪼개어 작은 부분부터 천천히 해결
나중에 커다란 문제를 해결할 때에는 이미 구해진 작은 부분 문제를 이용해 해결
주로 M X N의 2차원 매트릭스 형태를 이용

동작 방식

'cat'(기준) 과 'cake' 의 최소 편집 거리를 구해보자.

1. '아무것도 없는 상태 - 나머지'의 거리를 구한다.

⌀ 와 ⌀ 사이의 거리 : 0
⌀ 와 c 사이의 거리 : 1
⌀ 와 cak 사이의 거리 : 3
cat 와 ⌀ 사이의 거리 : 3

2. 서로 같은 문자인 경우 왼쪽 위의 값을 가져온다.

a 와 a 사이의 거리 : 0 (⌀ - ⌀)
ca 와 ca 사이의 거리 : 0 (a - a)

3. 나머지 빈 곳은 해당 빈 칸 기준 왼쪽, 왼쪽 위, 위 중 가장 작은 숫자에 1을 더해 넣는다.

c 와 cak 사이의 거리를 구해보자

왼쪽 : 1
왼쪽 위 : 2
위 : 3

3가지 중 가장 작은 수는 왼쪽(1) 이므로 c와 cak 사이의 거리는 1+1 = 2 이다.

왼쪽에 1을 더하는 경우 : 단어 추가 (Add)

c 와 ca 사이의 거리 : 1 (c -> ca)
c 와 cak 사이의 거리 : 2 (c -> ca -> cak)

위쪽에 1을 더하는 경우 : 단어 삭제 (Delete)

ca와 c 사이의 거리 : 1 (ca -> c)
cat와 c 사이의 거리 : 2 (cat -> ca -> c)

왼쪽 위에 1을 더하는 경우 : 단어 편집 (Edit)

cat와 cak 사이의 거리 : 1 (cat -> cak)

4. cat과 cake 사이의 거리를 구한다.

cat와 cake 사이의 거리 : 2

Swift Code

func editDistance(from a: String, to b: String) -> Int {
    let m = a.count
    let n = b.count
    var matrix = [[Int]](repeating: [Int](repeating: 0, count: n + 1), count: m + 1)
    
    // '⌀ - 나머지 문자' 사이의 거리를 구한다.
    for index in 1...m {
        matrix[index][0] = index
    }
	
    // '나머지 문자 - ⌀' 사이의 거리를 구한다.
    for index in 1...n {
        matrix[0][index] = index
    }
    
    // 본격적으로 최소 편집 거리를 구한다.
    for (i, selfChar) in a.enumerated() {
        for (j, otherChar) in b.enumerated() {
            if otherChar == selfChar {
                // 동일한 문자 사이의 거리는 왼쪽 위 거리와 같다.
                matrix[i + 1][j + 1] = matrix[i][j]
            } else {
                // 서로 다른 문자 사이의 거리는 왼쪽, 왼쪽위, 위쪽 중 최소값 + 1 이다.
                matrix[i + 1][j + 1] = min(matrix[i][j] + 1, matrix[i + 1][j] + 1, matrix[i][j + 1] + 1)
            }
        }
    }
    
    return matrix[m][n]
}