레벤슈타인 거리

레벤슈타인 거리
	교체 비용을 1로, 삭제 또는 삽입 비용을 0.5로 설정했을 때 두 단어에 대한 편집 거리 행렬
분류	두 서열 사이의 차이 측정

정보 이론, 언어학, 컴퓨터 과학에서 레벤슈타인 거리(영어: Levenshtein distance)는 두 서열 사이의 차이를 측정하기 위한 문자열 거리 함수이다. 두 낱말 사이의 레벤슈타인 거리는 한 낱말을 다른 낱말로 바꾸는 데 필요한 최소한의 단일 문자 편집(삽입, 삭제 또는 교체) 횟수를 의미한다. 이 지표는 1965년에 이를 정의한 소련의 수학자 블라디미르 레벤시테인의 이름을 따서 명명되었다.^[1]

레벤슈타인 거리는 편집 거리라고도 불리지만, 이 용어는 더 넓은 의미의 거리 지표 군집을 의미하기도 한다.^[2]^: 32 이는 쌍별 문자열 정렬과 밀접한 관련이 있다.

정의

두 문자열 $a,b$ (각각의 길이는 $|a|$ 와 $|b|$ ) 사이의 레벤슈타인 거리는 $\operatorname {lev} (a,b)$ 로 주어지며, 다음과 같이 계산된다.

\operatorname {lev} (a,b)={\begin{cases}|a|&{\text{ if }}|b|=0,\\|b|&{\text{ if }}|a|=0,\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}&{\text{ if }}\operatorname {head} (a)=\operatorname {head} (b),\\1+\min {\begin{cases}\operatorname {lev} {\big (}\operatorname {tail} (a),b{\big )}\\\operatorname {lev} {\big (}a,\operatorname {tail} (b){\big )}\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}\\\end{cases}}&{\text{ otherwise}}\end{cases}}

여기서 어떤 문자열 $x$ 의 $\operatorname {tail}$ 은 첫 번째 문자를 제외한 나머지 문자열을 의미하며(즉, $\operatorname {tail} (x_{0}x_{1}\dots x_{n})=x_{1}x_{2}\dots x_{n}$ ), $\operatorname {head} (x)$ 는 $x$ 의 첫 번째 문자를 의미한다(즉, $\operatorname {head} (x_{0}x_{1}\dots x_{n})=x_{0}$ ). 문자열 $x$ 의 $n$ 번째 문자를 나타내기 위해 0부터 세어 $x[n]$ 또는 $x_{n}$ 표기법을 사용하므로, $\operatorname {head} (x)=x_{0}=x[0]$ 이 된다.

최솟값 항의 첫 번째 요소는 삭제( $a$ 에서 $b$ 로), 두 번째는 삽입, 세 번째는 교체에 해당한다.

이 정의는 나이브한 재귀 구현에 직접적으로 대응한다.

예시

예를 들어, "kitten"과 "sitting" 사이의 레벤슈타인 거리는 3이다. 다음의 3가지 편집을 통해 한 단어를 다른 단어로 바꿀 수 있으며, 3번보다 적은 편집으로는 불가능하기 때문이다.

kitten → sitten ("k"를 "s"로 교체)
sitten → sittin ("e"를 "i"로 교체)
sittin → sitting (끝에 "g" 삽입)

삭제의 간단한 예는 "uninformed"와 "uniformed"에서 볼 수 있으며, 이들의 거리는 1이다.

uninformed → uniformed ("n" 삭제)

상한 및 하한

레벤슈타인 거리는 몇 가지 간단한 상한과 하한을 가진다.

최소한 두 문자열 크기 차이의 절대값 이상이다.
최대한 더 긴 문자열의 길이 이하이다.
두 문자열이 같을 때만 0이 된다.
두 문자열의 크기가 같을 경우, 해밍 거리는 레벤슈타인 거리의 상한이 된다. 해밍 거리는 두 문자열에서 서로 다른 심볼이 있는 위치의 개수이다.
두 문자열 사이의 레벤슈타인 거리는 제3의 문자열로부터의 레벤슈타인 거리 합보다 크지 않다(삼각 부등식).

길이가 같은 두 문자열 사이의 레벤슈타인 거리가 해밍 거리보다 엄격히 작은 예로 "flaw"와 "lawn" 쌍이 있다. 여기서 레벤슈타인 거리는 2(앞의 "f" 삭제, 끝에 "n" 삽입)이지만, 해밍 거리는 4이다.

응용

근사 문자열 매칭에서 목표는 적은 수의 차이가 예상되는 상황에서 긴 텍스트들 속의 짧은 문자열에 대한 매칭을 찾는 것이다. 예를 들어 짧은 문자열은 사전에서 온 것일 수 있다. 여기서 한 문자열은 보통 짧고 다른 하나는 임의로 길다. 이는 맞춤법 검사기, 광학 문자 인식 보정 시스템, 번역 메모리에 기반한 자연어 번역 보조 소프트웨어 등 광범위한 분야에 응용된다.

레벤슈타인 거리는 두 긴 문자열 사이에서도 계산될 수 있지만, 두 문자열 길이의 곱에 대략 비례하는 계산 비용 때문에 비실용적이다. 따라서 레코드 연결과 같은 애플리케이션에서 퍼지 문자열 검색을 돕는 데 사용될 때, 비교되는 문자열은 비교 속도를 높이기 위해 대개 짧은 편이다.

언어학에서 레벤슈타인 거리는 두 언어가 서로 얼마나 다른지, 즉 언어적 거리를 정량화하는 지표로 사용된다.^[3] 이는 상호 의사소통성과 관련이 있는데, 언어적 거리가 멀수록 상호 의사소통성이 낮아지고, 거리가 가까울수록 상호 의사소통성이 높아진다.

레벤슈타인 거리는 언어 청각 검사(speech audiometry)와 같은 다양한 응용 분야에서 음성 식별 테스트 중 청취자의 성과를 정량화하는 데 사용될 수 있다. 이 문맥에서 레벤슈타인 거리는 청취자에게 제시된 자극과 식별된 음소 서열 사이의 거리를 정량화하기 위해 계산된다. 음소 교체와 관련된 비용은 고정되거나 교체된 두 음소 간의 음운론적 특징 차이에 따라 달라질 수 있다.^[4]

생물정보학에서 레벤슈타인 거리와 유사한 알고리즘은 DNA 및 단백질과 같은 생물학적 서열 간의 차이를 측정한다. 알고리즘에서의 편집은 유전적 돌연변이에 대응한다: 뉴클레오타이드(DNA) 또는 아미노산(단백질)의 삽입, 삭제 또는 교체. 두 서열 사이의 거리가 짧을수록 더 밀접한 진화적 또는 기능적 관계를 나타낼 수 있다.^[5]

다른 편집 거리 지표와의 관계

허용되는 편집 연산의 집합에 따라 계산되는 다른 대중적인 편집 거리 측정법들이 있다. 예를 들면 다음과 같다.

다메라우-레벤슈타인 거리는 삽입, 삭제, 교체와 함께 인접한 두 문자의 전치를 허용한다.
최장 공통 부분 수열 (LCS) 거리는 삽입과 삭제만 허용하며 교체는 허용하지 않는다.
해밍 거리는 교체만 허용하므로 길이가 같은 문자열에만 적용된다.
자로 거리는 전치만 허용한다.

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

계산

재귀 방식

다음은 두 문자열 s, t와 그 길이를 받아 그들 사이의 레벤슈타인 거리를 반환하는 lDistance 함수의 직관적이지만 비효율적인 하스켈 재귀 구현이다.

lDistance :: Eq a => [a] -> [a] -> Int
lDistance [] t = length t -- s가 비어 있으면 거리는 t의 문자 수임
lDistance s [] = length s -- t가 비어 있으면 거리는 s의 문자 수임
lDistance (a : s') (b : t')
  | a == b = lDistance s' t' -- 첫 문자가 같으면 무시할 수 있음
  | otherwise = 1 + minimum -- 그렇지 않으면 세 가지 가능한 동작을 모두 시도하고 최적을 선택함
      [ lDistance (a : s') t' -- 문자가 삽입됨 (b 삽입)
      , lDistance s' (b : t') -- 문자가 삭제됨 (a 삭제)
      , lDistance s' t' -- 문자가 교체됨 (a를 b로 교체)
      ]

이 구현은 동일한 부분 문자열의 레벤슈타인 거리를 여러 번 다시 계산하기 때문에 매우 비효율적이다.

더 효율적인 방법은 동일한 거리 계산을 반복하지 않는 것이다. 예를 들어, 모든 가능한 접미사의 레벤슈타인 거리를 배열 $M$ 에 저장할 수 있다. 여기서 $M[i][j]$ 는 문자열 s의 마지막 $i$ 개 문자와 t의 마지막 $j$ 개 문자 사이의 거리이다. 이 표는 0행부터 시작하여 한 번에 한 행씩 구성하기 쉽다. 전체 표가 작성되면 원하는 거리는 s와 t의 모든 문자 사이의 거리를 나타내는 마지막 행과 열에 있게 된다.

전체 행렬을 이용한 반복 방식

이 섹션에서는 0 기반 문자열 대신 1 기반 문자열을 사용한다. m이 행렬인 경우, $m[i,j]$ 는 행렬의 i번째 행과 j번째 열이며, 첫 번째 행의 인덱스는 0, 첫 번째 열의 인덱스도 0이다.

레벤슈타인 거리를 계산하는 것은 첫 번째 문자열의 모든 접두사와 두 번째 문자열의 모든 접두사 사이의 레벤슈타인 거리를 저장하기 위해 행렬을 확보하면, 동적 계획법 방식으로 행렬의 값을 계산할 수 있고, 따라서 마지막으로 계산된 값으로 두 전체 문자열 사이의 거리를 찾을 수 있다는 관찰에 기반한다.

상향식 동적 계획법의 한 예인 이 알고리즘은 1974년 로버트 A. 와그너와 마이클 J. 피셔의 논문 문자열 대 문자열 보정 문제에서 변형들과 함께 논의되었다.^[6]

다음은 길이 m인 문자열 s와 길이 n인 문자열 t를 받아 그들 사이의 레벤슈타인 거리를 반환하는 LevenshteinDistance 함수에 대한 간단한 의사코드 구현이다.

function LevenshteinDistance(char s[1..m], char t[1..n]):
  // 모든 i와 j에 대해, d[i,j]는 s의 처음 i개 문자와
  // t의 처음 j개 문자 사이의 레벤슈타인 거리를 유지함
  declare int d[0..m, 0..n]

  set each element in d to zero

  // 소스 접두사는 모든 문자를 삭제함으로써
  // 빈 문자열로 변환될 수 있음
  for i from 1 to m:
    d[i, 0] := i

  // 타겟 접두사는 빈 소스 접두사에서
  // 모든 문자를 삽입함으로써 도달할 수 있음
  for j from 1 to n:
    d[0, j] := j

  for j from 1 to n:
    for i from 1 to m:
      if s[i] = t[j]:
        substitutionCost := 0
      else:
        substitutionCost := 1

      d[i, j] := minimum(d[i-1, j] + 1,                   // 삭제
                         d[i, j-1] + 1,                   // 삽입
                         d[i-1, j-1] + substitutionCost)  // 교체

  return d[m, n]

결과 행렬의 두 가지 예(태그된 숫자 위에 마우스를 올리면 해당 숫자를 얻기 위해 수행된 연산이 나타남):

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1	2	3	4	5
t	3	3	2	1	2	3	4
t	4	4	3	2	1	2	3
i	5	5	4	3	2	2	3
n	6	6	5	4	3	3	2
g	7	7	6	5	4	4	3

		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

알고리즘 전체에서 유지되는 불변량은 초기 세그먼트 s[1..i]를 최소 d[i, j]번의 연산을 사용하여 t[1..j]로 변환할 수 있다는 점이다. 마지막에 배열의 오른쪽 아래 요소가 정답을 담고 있다.

두 개의 행만을 이용한 반복 방식

편집된 입력 문자열을 재구성할 필요가 없다면, 구성을 위해 두 개의 행 – 이전 행과 현재 계산 중인 행 – 만 있으면 된다는 것이 밝혀졌다.

레벤슈타인 거리는 다음 알고리즘을 사용하여 반복적으로 계산할 수 있다.^[7]

function LevenshteinDistance(char s[0..m-1], char t[0..n-1]):
    // 정수 거리를 저장할 두 개의 작업 벡터 생성
    declare int v0[n + 1]
    declare int v1[n + 1]

    // v0 초기화 (이전 행의 거리)
    // 이 행은 A[0][i]: 빈 s에서 t까지의 편집 거리임.
    // 이 거리는 t를 만들기 위해 s에 추가해야 하는 문자 수임.
    for i from 0 to n:
        v0[i] = i

    for i from 0 to m - 1:
        // 이전 행 v0로부터 v1(현재 행 거리) 계산

        // v1의 첫 번째 요소는 A[i + 1][0]임
        // 편집 거리는 빈 t와 일치시키기 위해 s에서 (i + 1)개의 문자를 삭제하는 것임
        v1[0] = i + 1

        // 수식을 사용하여 행의 나머지 부분을 채움
        for j from 0 to n - 1:
            // A[i + 1][j + 1]에 대한 비용 계산
            deletionCost := v0[j + 1] + 1
            insertionCost := v1[j] + 1
            if s[i] = t[j]:
                substitutionCost := v0[j]
            else:
                substitutionCost := v0[j] + 1

            v1[j + 1] := minimum(deletionCost, insertionCost, substitutionCost)

        // 다음 반복을 위해 v1(현재 행)을 v0(이전 행)으로 복사
        // v1의 데이터는 항상 무효화되므로 복사 없이 교체(swap)하는 것이 더 효율적일 수 있음
        swap v0 with v1
    // 마지막 교체 후 v1의 결과는 이제 v0에 있음
    return v0[n]

허슈버그 알고리즘은 이 방법과 분할 정복 알고리즘을 결합한다. 이는 동일한 점근적 시간 및 공간 복잡도 내에서 단순한 편집 거리뿐만 아니라 최적의 편집 서열을 계산할 수 있다.^[8]

자동 기계

레벤슈타인 자동 기계는 문자열이 주어진 문자열로부터 주어진 상수보다 낮은 편집 거리를 갖는지 여부를 효율적으로 판별한다.^[9]

근사

길이 $n$ 인 두 문자열 사이의 레벤슈타인 거리는 시간 O(n^{1 + ε}) 내에 다음 인자 범위 내에서 근사화될 수 있다.

(\log n)^{O(1/\varepsilon )},

여기서 ε > 0은 조정 가능한 자유 매개변수이다.^[10]

계산 복잡도

길이 $n$ 인 두 문자열의 레벤슈타인 거리는 강한 지수 시간 가설이 거짓이 아닌 한, 0보다 큰 임의의 ε에 대해 O(n^{2 − ε}) 시간 내에 계산될 수 없음이 증명되었다.^[11] 이 문제의 복잡도에 대한 또 다른 (무조건적) 하한은 문자열의 심볼에 대한 유일한 쿼리가 두 심볼의 비교인 모델에서 $\Omega (mn)$ 이다.^[12]

같이 보기

각주

↑ В. И. Левенштейн (1965). Дво이чные коды с исправлением выпадений, вставок 및 замещений символов [Binary codes capable of correcting deletions, insertions, and reversals] (러시아어). 《Доклады Академии Наук СССР》 163. 845–848쪽. Appeared in English as: Levenshtein, Vladimir I. (February 1966). 《Binary codes capable of correcting deletions, insertions, and reversals》. 《Soviet Physics Doklady》 10. 707–710쪽. Bibcode:1966SPhD...10..707L.
↑ Navarro, Gonzalo (2001). 《A guided tour to approximate string matching》 (PDF). 《ACM Computing Surveys》 33. 31–88쪽. CiteSeerX 10.1.1.452.6317. doi:10.1145/375360.375365. S2CID 207551224.
↑ Jan D. ten Thije; Ludger Zeevaert (2007년 1월 1일), 《Receptive multilingualism: linguistic analyses, language policies, and didactic concepts》, John Benjamins Publishing Company, ISBN 978-90-272-1926-8, Assuming that intelligibility is inversely related to linguistic distance ... the content words the percentage of cognates (related directly or via a synonym) ... lexical relatedness ... grammatical relatedness .
↑ Fontan, L.; Ferrané, I.; Farinas, J.; Pinquier, J.; Aumont, X. (2016). 〈Using Phonologically Weighted Levenshtein Distances for the Prediction of Microscopic Intelligibility〉. 《Proc. INTERSPEECH ’16: 17th Proc. Annu. Conf. Int. Speech Commun. Assoc.》. INTERSPEECH 2016. San Francisco, USA. 650–654쪽.
↑ Berger, Bonnie; Waterman, Michael S.; Yu, Yun William (June 2021). 《Levenshtein Distance, Sequence Comparison and Biological Database Search》. 《IEEE Transactions on Information Theory》 67. 3287–3294쪽. doi:10.1109/TIT.2020.2996543. ISSN 1557-9654. PMC 8274556.
↑ Wagner, Robert A.; Fischer, Michael J. (1974), “The String-to-String Correction Problem”, 《Journal of the ACM》 21 (1): 168–173, doi:10.1145/321796.321811, S2CID 13381535
↑ Hjelmqvist, Sten (2012년 3월 26일), 《Fast, memory efficient Levenshtein algorithm》 .
↑ Hirschberg, D. S. (1975). 《A linear space algorithm for computing maximal common subsequences》 (PDF) (Submitted manuscript). 《커뮤니케이션스 오브 더 ACM》 18. 341–343쪽. CiteSeerX 10.1.1.348.4774. doi:10.1145/360825.360861. MR 0375829. S2CID 207694727.
↑ Schulz, Klaus U.; Mihov, Stoyan (2002). 《Fast String Correction with Levenshtein-Automata》. 《International Journal of Document Analysis and Recognition》 5. 67–85쪽. CiteSeerX 10.1.1.16.652. doi:10.1007/s10032-002-0082-8. S2CID 207046453.
↑ Andoni, Alexandr; Krauthgamer, Robert; Onak, Krzysztof (2010). 《Polylogarithmic approximation for edit distance and the asymmetric query complexity》. IEEE Symp. Foundations of Computer Science (FOCS). arXiv:1005.4033. Bibcode:2010arXiv1005.4033A. CiteSeerX 10.1.1.208.2079.
↑ Backurs, Arturs; Indyk, Piotr (2015). 《Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)》. Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC). arXiv:1412.0348. Bibcode:2014arXiv1412.0348B.
↑ Wong, C. K.; Chandra, Ashok K. (1976). 《Bounds for the string editing problem》. 《Journal of the ACM》 23. 13–16쪽. doi:10.1145/321921.321923.

외부 링크

위키책에 이 문서와
관련된 문서가 있습니다.

Strings/Levenshtein distance

Black, Paul E. 편집 (2008년 8월 14일), 〈Levenshtein distance〉, 《Dictionary of Algorithms and Data Structures [online]》, U.S. National Institute of Standards and Technology, 2016년 11월 2일에 확인함
Rosetta Code implementations of Levenshtein distance

[1] В. И. Левенштейн (1965). Дво이чные коды с исправлением выпадений, вставок 및 замещений символов [Binary codes capable of correcting deletions, insertions, and reversals] (러시아어). 《Доклады Академии Наук СССР》 163. 845–848쪽. Appeared in English as: Levenshtein, Vladimir I. (February 1966). 《Binary codes capable of correcting deletions, insertions, and reversals》. 《Soviet Physics Doklady》 10. 707–710쪽. Bibcode:1966SPhD...10..707L.

[navarro-2] Navarro, Gonzalo (2001). 《A guided tour to approximate string matching》 (PDF). 《ACM Computing Surveys》 33. 31–88쪽. CiteSeerX 10.1.1.452.6317. doi:10.1145/375360.375365. S2CID 207551224.

[ref05xubej-3] Jan D. ten Thije; Ludger Zeevaert (2007년 1월 1일), 《Receptive multilingualism: linguistic analyses, language policies, and didactic concepts》, John Benjamins Publishing Company, ISBN 978-90-272-1926-8, Assuming that intelligibility is inversely related to linguistic distance ... the content words the percentage of cognates (related directly or via a synonym) ... lexical relatedness ... grammatical relatedness .

[4] Fontan, L.; Ferrané, I.; Farinas, J.; Pinquier, J.; Aumont, X. (2016). 〈Using Phonologically Weighted Levenshtein Distances for the Prediction of Microscopic Intelligibility〉. 《Proc. INTERSPEECH ’16: 17th Proc. Annu. Conf. Int. Speech Commun. Assoc.》. INTERSPEECH 2016. San Francisco, USA. 650–654쪽.

[5] Berger, Bonnie; Waterman, Michael S.; Yu, Yun William (June 2021). 《Levenshtein Distance, Sequence Comparison and Biological Database Search》. 《IEEE Transactions on Information Theory》 67. 3287–3294쪽. doi:10.1109/TIT.2020.2996543. ISSN 1557-9654. PMC 8274556.

[6] Wagner, Robert A.; Fischer, Michael J. (1974), “The String-to-String Correction Problem”, 《Journal of the ACM》 21 (1): 168–173, doi:10.1145/321796.321811, S2CID 13381535

[7] Hjelmqvist, Sten (2012년 3월 26일), 《Fast, memory efficient Levenshtein algorithm》 .

[8] Hirschberg, D. S. (1975). 《A linear space algorithm for computing maximal common subsequences》 (PDF) (Submitted manuscript). 《커뮤니케이션스 오브 더 ACM》 18. 341–343쪽. CiteSeerX 10.1.1.348.4774. doi:10.1145/360825.360861. MR 0375829. S2CID 207694727.

[ssm-9] Schulz, Klaus U.; Mihov, Stoyan (2002). 《Fast String Correction with Levenshtein-Automata》. 《International Journal of Document Analysis and Recognition》 5. 67–85쪽. CiteSeerX 10.1.1.16.652. doi:10.1007/s10032-002-0082-8. S2CID 207046453.

[10] Andoni, Alexandr; Krauthgamer, Robert; Onak, Krzysztof (2010). 《Polylogarithmic approximation for edit distance and the asymmetric query complexity》. IEEE Symp. Foundations of Computer Science (FOCS). arXiv:1005.4033. Bibcode:2010arXiv1005.4033A. CiteSeerX 10.1.1.208.2079.

[11] Backurs, Arturs; Indyk, Piotr (2015). 《Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)》. Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC). arXiv:1412.0348. Bibcode:2014arXiv1412.0348B.

[12] Wong, C. K.; Chandra, Ashok K. (1976). 《Bounds for the string editing problem》. 《Journal of the ACM》 23. 13–16쪽. doi:10.1145/321921.321923.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v t e 문자열
스트링 메트릭	해밍 거리 리 거리
문자열 검색 알고리즘	보어-무어 문자열 검색 알고리즘 커누스-모리스-프랫 알고리즘 라빈-카프 알고리즘
다중 문자열 검색	아호 코라식 코멘츠-월터 알고리즘
정규 표현식	정규 문법 비결정론적 유한 상태 기계
서열 정렬	스미스-워터맨 알고리즘
자료 구조	접미사 배열 접미사 트리 로프 트라이
기타	구문 분석 패턴 매칭 압축 패턴 매칭 최장 공통 부분 수열 최장 공통 부분 문자열