콘텐츠로 건너뛰기
Home » 편집거리 (단어의 유사도 분석)

편집거리 (단어의 유사도 분석)

편집거리 구하기

편집거리(edit distance)는 단어의 유사도를 측정하는 방법 중 하나이다. 한 단어에서 글자를 추가/제거/교체하여 다른 단어로 바꿀 때 필요한 최소한의 편집 액션의 횟수로 결정한다.  computer라는 단어와 commuter라는 단어는 매우 유사한데, p -> m으로 한글자만 변경하면 처음 단어에서 두 번째 단어로 바뀌게 된다. 비슷하게 sport라는 단어는 sort라는 단어로 바꾸기 위해서는 p 한글자를 지우면 된다. 혹은 sort에서 p한 글자를 추가하면 된다.

단어의 유사도를 측정하는 방법에는 편집 거리외에도 자카드 유사도 등의 여러 방법이 있다.

편집거리는 두 문자열 s1, s2에서 몇 번의 추가/삭제/변경으로 변환할 수 있는가를 나타내는 개념이다. 이러한 변경에는

  1. 글자를 교환하기
  2. 글자를 삽입하기
  3. 글자를 삭제하기

의 세 종류의 변경 연산을 할 수 있다. 이를 이용해서 두 단어 사이의 편집거리를 구하는 재귀 함수를 생각해보자.

d('', '') = 0 -- 빈 문자열은 0번
d(s, '') = d('', s) = |s| -- 빈문자열로 변경하는데는 s의 길이만큼의 삭제필요
d(s1+ch1, s2+ch2)
 = min( d(s1, s2) + if ch1 = ch2 then 0 else 1, -- 교환
        d(s1+ch1, s2) + 1, -- 삽입
        d(s2, s2+ch2) + 1  -- 삭제
      )

먼저 빈 문자열 두 개 사이의 편집거리는 0이다. 그리고 한글자로 된 문자열과 빈 문자열 간의 편집거리는 당연히 1이다. 그렇다면 빈 문자열과 길이가 n인 문자열의 편집 거리는 n이 된다.
이제 길이가 0이 아닌 두 문자열의 편집거리를 보자. 두 단어 springprint를 예로 들어보겠다.

  1. 변경: sprin + gprin + t로 볼 때 sprin -> prin으로 변경한 후 g -> t로 바꾸는 변경을 1회 수행한다. 이 때 편집거리는 d(sprin, print) + 1이 될 수 있다. 만약 마지막 글자가 동일하다면 1이 아닌 0을 더한다.
  2. 추가: 혹은 springprint + t로 본다면 spring -> prin으로 변경한 후 t를 추가하는 것이므로 편집거리에 1을 더한 d(spring, prin) + 1이 될 수도 있다.
  3. 삭제: 반대로 sprin + gprint로 본다면 sprin -> print로 변경한 후 g를 삭제하는 것이므로 d(sprin, print) + 1이 될 수 있다.

결국 두 단어의 최소 편집 거리는 변경, 추가, 삭제에 의한 결과 중에서 최소값을 사용한다. 그리고 이는 점점 작은 단위로 내려가서 비교하게 되기에 동적계획법으로 풀어낼 수 있다. 이 단계를 추적해보자.
각 단어에 맨 앞에 공백을 추가한 후 각 원래 단어는 글자를 세로로, 목적지가되는 단어는 가로로 배치하면 아래와 같은 표가 나온다.

# | #  p  r  i  n  t
--------------------
# | 0
s |
p |
r |
i |
n |
g |

이 표의 처음 등장하는 0은 바로 빈 문자열에서 빈 문자열로 바꿀 때의 편집거리이다. 그리고 그 오른쪽으로 빈 문자열에서 각 글자까지의 단어로 변경하는데 필요한 편집거리는 ‘추가’의 케이스만 있으므로 1씩 증가한다.

# | #  p  r  i  n  t
--------------------
# | 0  1  2  3  4  5  ==> 빈 문자열에서 print를 만드는 과정
s |
p |
r |
i |
n |
g |

이번에는 0의 아래방향을 보자. 이 열에서 표시될 숫자들은 각 칸에서 왼쪽에 있는 단어가 위쪽에 있는 단어가 되기위해 필요한 편집거리이다. 여기서 위쪽의 칸은 빈 문자열이므로,  아래로 내려가면서 s, sp, spr, spri, sprin, spring이 각각 빈 문자열이 되는데 필요한 편집의 횟수를 구하게된다. 이 때 가능한 액션은 한 글자씩 지우는 것이기 때문에 아래와 같이 첫 열이 완성된다.

# | #  p  r  i  n  t
--------------------
# | 0  1  2  3  4  5
s | 1  *
p | 2
r | 3
i | 4
n | 5
g | 6

이제 위의 표에서 *가 위치한 곳을 보자, 여기는 s -> p로의 편집거리를 쓴다. 여기에는 세 경우가 있다.

  1. s를 삭제한 후 p를 추가한다. => 1 + 1 (표에서는 왼쪽칸 + 1)
  2. p를 추가한 후 s를 삭제한다. => 1 + 1 (표에서는 위쪽칸 + 1)
  3. s -> p로 치환한다. => 0 + 1 (표에서는 대각선 왼쪽위 + 1)

이 중 최소거리는 1이므로 *의 자리에는 1이 들어간다. 그 오른쪽으로도 계속 진행한다. 단, 오른쪽으로 진행 시에는 글자를 하나씩 덧붙이는 것이기 때문에 그 결과는 항상 왼쪽칸의 값에 +1한 값이 될 것이다.

# | #  p  r  i  n  t
--------------------
# | 0  1  2  3  4  5
s | 1  1
p | 2  *
r | 3
i | 4
n | 5
g | 6

두 번째 줄을 계산해보자. sp -> p로 바꾸는 작업이다. 이는 위의 그림에서 *의 값에 해당한다.

  1. 먼저 *의 왼쪽에서 오른쪽으로 가면서 1을 더한다. 이는 sp -> # 변경 한 후에 p를 추가하는 것을 말하면 이 때의 편집거리는 3(2 + 1)이다.
  2. 혹은 p를 삭제한 후 s -> p 변환을 한다. 이건 2(1 + 1) 이다.
  3. p가 서로 같으므로 s만 제거하면?  sp -> ps -> #의 편집거리와 동일하다. 따라서 이 경우에는 1이다.

그리고 이 중 가장 작은 값은 1이므로 *칸에 1을 쓴다. 그리고 그 오른쪽으로는 r, i, n, t를 붙이는 작업이므로 1씩 증가한다.

# | #  p  r  i  n  t
--------------------
# | 0  1  2  3  4  5
s | 1  1  2  3  4  5
p | 2  1  2  3  4  5
r | 3  2  1  2  3  4
i | 4
n | 5
g | 6

같은 방식으로 sprp, pr, pri, prin, print로 변경하는 최소편집거리를 계산하여 다음 줄을 채운다. 당연히 같은 글자가 있으면 왼쪽 위 칸의 값과 같은 값이 최소 거리가 될 것이며, 그렇지 않은 경우에는 왼쪽칸 + 1, 위쪽 칸 + 1, 왼쪽위칸 + 1 한 값 중 가장 작은 값을 쓴다. 이 규칙을 이용해서 나머지 칸을 계속 채워나간다.

# | #  p  r  i  n  t
--------------------
# | 0  1  2  3  4  5
s | 1  1  2  3  4  5
p | 2  1  2  3  4  5
r | 3  2  1  2  3  4
i | 4  3  2  1  2  3
n | 5  4  3  2  1  2
g | 6  5  4  3  2  2

최종적으로 spring -> print의 최소편집거리는 2로 계산되었고 이 과정을 보면

  1. s를 삭제 (2행 1열)
  2. p, r, i, n는 그대로 둔다. (-> 6행 5열)
  3. g -> t로 변경 (7행 6열)

이 되는 셈이다.

최소거리로 증가하는 경로를 따를 수 있는 루트가 2개 이상이 경우도 얼마든지 있다.

두 문자열의 길이에 각 1을 더한 곱 만큼 크기의 배열이 필요한데, 어차피 맨 마지막의 두 행만 사용하게 되므로 파이썬으로 구현은 다음과 같이 작성할 수 있다.

def edit_distance(s1, s2):
    l1, l2 = len(s1), len(s2)
    if l2 > l1:
        return edit_distance(s2, s1)
    if l2 is 0:
        return l1
    prev_row = list(range(l2 + 1))
    current_row = [0] * (l2 + 1)
    for i, c1 in enumerate(s1):
        current_row[0] = i + 1
        for j, c2 in enumerate(s2):
            d_ins = current_row[j] + 1
            d_del = prev_row[j + 1] + 1
            d_sub = prev_row[j] + (1 if c1 != c2 else 0)
            current_row[j + 1] = min(d_ins, d_del, d_sub)
        prev_row[:] = current_row[:]
    return prev_row[-1]

여러 단어들을 비교할 때 각 단어간의 편집거리를 알면 단어의 유사성을 파악할 수 있다. 구글 검색 등에서 검색어에 오타를 낸 경우에 올바른 단어를 찾아줄 수 있는 것도 보통은 한 글자를 잘못 치거나 덜치거나 더친 경우이기 때문에 편집거리가 1~2로 비교적 짧은 오타단어와 정상단어 사이의 관계를 이용해서 제시할 수 있는 원리이다.
다음은 같은 알고리듬에 대한 Swift4 구현이다.


private extension String {
subscript(i:Int) -> Character {
let idx = index(startIndex, offsetBy: i)
return self[idx]
}
}
struct Array2D<T> {
let width: Int, height: Int
var length: Int { return width * height }
var data: [T?]
var last: T? { return data.last! }
init(width:Int, height: Int) {
self.width = width
self.height = height
data = Array<T?>(repeating:nil, count: width * height)
}
subscript(row: Int, col: Int) -> T? {
get {
guard case (0..<length) = row * col,
case (0..<width) = col,
case (0..<height) = row
else { return nil }
return data[row*width + col]
}
set {
guard case (0..<length) = row * col,
case (0..<width) = col,
case (0..<height) = row
else { return }
data[row*width + col] = newValue
}
}
subscript(i:Int) -> T? {
get { return data[i] }
set { data[i] = newValue }
}
}
public extension String {
func editDistance(to s: String) -> Int {
var grid = Array2D<Int>(width: s.count+1, height: count+1)
(0…count).forEach{ grid[$0, 0] = $0 }
(0…s.count).forEach{ grid[0, $0] = $0 }
for i in 1…count {
for j in 1…s.count {
if let x = grid[i, j-1],
let y = grid[i-1, j],
let z = grid[i-1, j-1]
{
grid[i, j] = Swift.min(x+1, y+1, z + (self[i-1] == s[j-1] ? 0 : 1))
}
}
}
return grid.last!
}
}
let s = "hello"
print(s.editDistance(to:"helloworld"))

view raw

main.swift

hosted with ❤ by GitHub