편집 거리

전산언어학 및 컴퓨터 과학에서 **편집 거리**()는 문자열 (예: 단어) 사이의 불일치 정도를 정량화하는 문자열 측정 방식으로, 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 연산 횟수를 세어 측정한다. 편집 거리는 자연어 처리 분야에서 응용되는데, 예를 들어 자동 맞춤법 검사기는 오타가 발생한 단어와 거리가 가까운 단어들을 사전에서 선택하여 교정 후보를 결정할 수 있다. 생물정보학에서는 A, C, G, T 문자의 문자열로 볼 수 있는 DNA 서열의 유사성을 정량화하는 데 사용될 수 있다.

편집 거리의 정의에 따라 허용되는 연산의 집합이 달라진다. 레벤슈타인 거리 연산은 문자열 내 문자의 삭제, 삽입 또는 치환이다. 이것이 가장 일반적인 측정 방식이기 때문에 '레벤슈타인 거리'라는 용어는 종종 '편집 거리'와 혼용되어 사용된다.

## 편집 거리의 종류
편집 거리의 유형에 따라 허용되는 문자열 연산 집합이 달라진다. 예를 들어,

일부 편집 거리는 허용된 특정 편집 연산 집합으로 계산되는 매개변수화 가능한 측정 항목으로 정의되며, 각 연산에는 비용(무한대일 수 있음)이 할당된다. 이는 스미스-워터먼 알고리즘과 같은 DNA 서열 정렬 알고리즘에 의해 더욱 일반화되는데, 이 알고리즘은 연산이 적용되는 위치에 따라 연산 비용이 달라지게 한다.

## 공식 정의 및 속성
알파벳  (예: ASCII 문자 집합, 바이트 집합 [0..255] 등) 위의 두 문자열 와 가 주어졌을 때, 편집 거리 는 를 로 변환하는 최소 가중치 편집 연산의 연속이다. 가장 간단한 편집 연산 집합 중 하나는 1966년 레벤슈타인이 정의한 것이다.

:단일 기호의 **삽입**. 만약  = 라면, 기호 를 삽입하여 를 만든다. 빈 문자열을 나타내는 ε를 사용하여 ε→로 표기할 수도 있다.
:단일 기호의 **삭제**는 를 로 바꾼다 (→ε).
:단일 기호 를  ≠ 인 기호로 **치환**하면 가 로 바뀐다 (→).

레벤슈타인의 원래 정의에서 각 연산은 단위 비용을 가지며(문자를 동일한 문자로 치환하는 비용은 0인 경우 제외), 따라서 레벤슈타인 거리는 를 로 변환하는 데 필요한 최소 연산 횟수와 같다. 더 일반적인 정의는 연산에 비음수 가중치 함수 ins(), del() 및 sub(,&nbsp;)를 연관시킨다.

추가적인 기본 연산들이 제안되기도 했다. 다메라우-레벤슈타인 거리는 흔한 실수인 인접한 두 문자의 **전치**를 단일 편집으로 계산하며, 이는 공식적으로 를 로 바꾸는 연산으로 특징지어진다.
광학 문자 인식(OCR) 출력 교정 작업의 경우, 단일 문자를 한 쌍의 문자로 바꾸거나 그 반대로 바꾸는 **병합**(merge) 및 **분할**(split) 연산이 사용되어 왔다.

다른 변형된 편집 거리들은 연산 집합을 제한함으로써 얻어진다. 최장 공통 부분 수열(LCS) 거리는 삽입과 삭제만을 두 가지 편집 연산으로 사용하며, 둘 다 단위 비용을 갖는 편집 거리이다. 마찬가지로 치환만을 허용하면(마찬가지로 단위 비용) 해밍 거리를 얻을 수 있으며, 이는 길이가 같은 문자열로 제한되어야 한다. 자로-윈클러 거리는 전치만 허용되는 편집 거리에서 파생될 수 있다.

### 예시
"kitten"과 "sitting" 사이의 레벤슈타인 거리는 3이다. 전자를 후자로 바꾸는 최소 편집 스크립트는 다음과 같다.

# **k**itten → **s**itten ("k"를 "s"로 치환)
# sitt**e**n → sitt**i**n ("e"를 "i"로 치환)
# sittin → sittin**g** (끝에 "g" 삽입)

LCS 거리(삽입 및 삭제만 가능)는 다른 거리와 최소 편집 스크립트를 제공한다:

# **k**itten → itten (0번째 위치의 "k" 삭제)
# itten → **s**itten (0번째 위치에 "s" 삽입)
# sitt**e**n → sittn (4번째 위치의 "e" 삭제)
# sittn → sitt**i**n (4번째 위치에 "i" 삽입)
# sittin → sittin**g** (6번째 위치에 "g" 삽입)

총 비용/거리는 5회의 연산이 된다.

### 속성
비음수 비용을 갖는 편집 거리는 다음 조건이 충족될 때 거리의 공리를 만족하며, 문자열의 거리 공간을 형성한다.

* 모든 편집 연산은 양의 비용을 갖는다.
* 모든 연산에 대해 비용이 동일한 역연산이 존재한다.

이러한 속성을 통해 거리 공리는 다음과 같이 충족된다:

:(, ) = 0인 것은 a=b인 것과 필요충분조건이다. 왜냐하면 각 문자열은 정확히 0회의 연산을 사용하여 자기 자신으로 변환될 수 있기 때문이다.
: ≠ 일 때 (, ) > 0이다. 이는 0이 아닌 비용을 가진 연산이 최소 하나 이상 필요하기 때문이다.
:각 연산과 그 역연산의 비용이 같으므로 (, ) = (, )이다.
:삼각 부등식: (, ) ≤ (, ) + (, ).

레벤슈타인 거리와 단위 비용을 갖는 LCS 거리는 위의 조건들을 만족하며, 따라서 거리 공리를 만족한다. 적절한 거리가 아닌 편집 거리의 변형들도 문헌에서 고려된 바 있다.

단위 비용 편집 거리의 다른 유용한 속성은 다음과 같다.

* LCS 거리는 두 문자열의 길이 합에 의해 상한이 정해진다.
* LCS 거리는 레벤슈타인 거리의 상한이다.
* 길이가 같은 문자열의 경우, 해밍 거리는 레벤슈타인 거리의 상한이다.

비용/가중치에 관계없이 모든 편집 거리에는 다음과 같은 속성이 유지된다.

* 와 가 공통 접두사를 공유할 때, 이 접두사는 거리에 영향을 미치지 않는다. 공식적으로  = 이고  = 일 때, (, ) = (, )이다. 이를 통해 공통 접두사와 접미사를 선형 시간에 건너뛸 수 있으므로 편집 거리 및 편집 스크립트와 관련된 많은 계산을 가속화할 수 있다.

## 계산
한 쌍의 문자열 사이의 최소 편집 거리를 계산하는 최초의 알고리즘은 1964년 다메라우에 의해 발표되었다.

### 일반적인 알고리즘

레벤슈타인의 원래 연산을 사용하면, a = a_1\ldots a_m에서 b = b_1\ldots b_n까지의 (비대칭) 편집 거리는 다음과 같은 재귀식에 의해 정의되는 d_{mn}으로 주어진다.

:\begin{align}d_{i0} &= \sum_{k=1}^{i} w_\mathrm{del}(a_{k}), & & \quad  \text{for}\; 1 \leq i \leq m \\
d_{0j} &= \sum_{k=1}^{j} w_\mathrm{ins}(b_{k}), & & \quad \text{for}\; 1 \leq j \leq n \\
d_{ij} &= \begin{cases} d_{i-1, j-1} & \text{for}\; a_{i} = b_{j}\\ \min \begin{cases} d_{i-1, j} + w_\mathrm{del}(a_{i})\\ d_{i,j-1} + w_\mathrm{ins}(b_{j}) \\ d_{i-1,j-1} + w_\mathrm{sub}(a_{i}, b_{j}) \end{cases} & \text{for}\; a_{i} \neq b_{j}\end{cases} & & \quad  \text{for}\; 1 \leq i \leq m, 1 \leq j \leq n.\end{align}
이 알고리즘은 재귀 절의 최소화 부분에 다른 항을 추가함으로써 전치를 처리하도록 일반화될 수 있다.

이 재귀식을 평가하는 단순한 재귀적 방식은 지수 시간이 걸린다. 따라서 보통 바그너-피셔 알고리즘으로 흔히 알려진 동적 계획법 알고리즘을 사용하여 계산되는데, 이 알고리즘은 여러 사람에 의해 독자적으로 발명된 역사가 있다. 바그너-피셔 알고리즘이 완료된 후, d_{mn}에서 시작하여 동적 계획법 알고리즘 중에 사용된 연산을 역추적(backtrace)함으로써 최소 편집 연산 시퀀스를 읽어낼 수 있다.

이 알고리즘의 시간 복잡도는 Θ()이며, 여기서 과 은 문자열의 길이이다. 전체 동적 계획법 테이블을 구축할 때 공간 복잡도 또한 이다. 어느 순간에도 알고리즘이 메모리에 두 개의 행(또는 두 개의 열)만 필요로 한다는 점을 관찰하면 이를 으로 개선할 수 있다. 그러나 이 최적화를 사용하면 최소 편집 연산 시퀀스를 읽어내는 것이 불가능해진다. 이 문제에 대한 선형 공간 해법은 허쉬버그 알고리즘에 의해 제공된다. 이러한 재귀식을 풀고 입력 크기에 선형적인 공간에서 캐시 효율적으로 최적의 연산 시퀀스를 추출하기 위한 일반적인 재귀적 분할 정복 프레임워크는 초두리(Chowdhury), 레(Le), 라마찬드란(Ramachandran)에 의해 제시되었다.

### 개선된 알고리즘
위에 설명된 바그너-피셔 알고리즘을 개선하여, 우코넨은 몇 가지 변형을 설명했다. 그중 하나는 두 문자열과 최대 편집 거리 를 입력받아 를 반환한다. 이는 동적 계획법 테이블의 대각선 주변부만 계산하고 저장함으로써 달성된다. 이 알고리즘은 의 시간이 걸리며, 여기서 과 은 문자열의 길이이다. 공간 복잡도는 편집 시퀀스를 읽어내야 하는지 여부에 따라  또는 이다.

란다우, 마이어스, 슈미트(Schmidt)의 추가 개선을 통해  시간 알고리즘이 나왔다.

유한한 알파벳과 서로의 배수인 편집 비용에 대해, 현재 알려진 가장 빠른 정확한 알고리즘은 마섹(Masek)과 패터슨(Paterson)의 알고리즘으로 최악의 경우 O(nm/logn)의 실행 시간을 갖는다.

## 응용
편집 거리는 계산생물학 및 자연어 처리 분야에서 응용된다. 예를 들어 철자 오류나 OCR 오류의 교정, 그리고 적은 수의 차이가 예상되는 상황에서 긴 텍스트들 속의 짧은 문자열과 일치하는 항목을 찾는 근사 문자열 매칭 등에 사용된다.

한 쌍의 문자열 사이의 거리를 계산하는 것 외에도, 관련된 유형의 문제를 해결하는 다양한 알고리즘이 존재한다.

* 허쉬버그 알고리즘은 편집 거리를 최소화하는 것으로 정의되는 두 문자열의 최적 서열 정렬을 계산한다.
* 근사 문자열 매칭은 편집 거리의 관점에서 공식화될 수 있다. 우코넨의 1985년 알고리즘은 패턴이라 불리는 문자열 와 상수 를 입력받아, 임의의 문자열  내에서 와의 편집 거리가 최대 인 부분 문자열을 찾는 결정론적 유한 상태 기계를 구축한다. (여러 패턴 중 하나를 검색하기 위해 유사하게 자동자를 구축하지만 편집 연산을 허용하지 않는 아호-코라식 알고리즘과 비교된다). 근사 문자열 매칭을 위한 유사한 알고리즘으로 편집 거리로 정의되는 비탭 알고리즘(bitap algorithm)이 있다.
* 레벤슈타인 자동자는 고정된 참조 문자열로부터 제한된 편집 거리 내에 있는 문자열 집합을 인식하는 유한 상태 기계이다.

## 언어 편집 거리
문자열 사이의 편집 거리를 일반화한 것이 문자열과 언어(보통 형식 언어) 사이의 언어 편집 거리이다. 한 문자열과 다른 문자열 사이의 편집 거리를 고려하는 대신, 언어 편집 거리는 고정된 문자열과 특정 문자열 집합에서 가져온 임의의 문자열 사이에서 달성할 수 있는 최소 편집 거리이다. 보다 공식적으로, 알파벳  위의 임의의 언어 L과 문자열 x에 대해, 언어 편집 거리 d(L, x)는 다음과 같이 주어진다.d(L,x) = \min_{y \in L} d(x,y)

, 여기서 d(x,y)는 문자열 편집 거리이다. 언어 L이 문맥 자유 언어일 때, 1972년 아호(Aho)와 피터슨(Peterson)이 제안한 언어 편집 거리를 계산하는 3차 시간 동적 계획법 알고리즘이 존재한다. 정규 문법과 같이 표현력이 떨어지는 문법군의 경우, 편집 거리를 계산하기 위한 더 빠른 알고리즘들이 존재한다.

언어 편집 거리는 RNA 폴딩, 오류 교정, 최적 스택 생성 문제의 해법 등 다양하게 응용되어 왔다.

## 같이 보기
* 그래프 편집 거리
* 문자열 간 교정 문제
* 문자열 측정 방식
* Time Warp Edit Distance

## 각주

분류:문자열 유사도