다메라우-레벤슈테인 거리

정보 이론과 컴퓨터 과학에서, 다메라우-레벤슈테인 거리(프레데릭 J. 다메라우와 블라디미르 1세의 이름을 따서 명명). Levenshtein^[1]^[2]^[3])은 두 시퀀스 간의 편집 거리를 측정하기 위한 문자열 메트릭입니다.비공식적으로, 두 단어 사이의 다메라우-레벤슈테인 거리는 한 단어를 다른 단어로 변경하는 데 필요한 최소 작업 수(단일 문자의 삽입, 삭제 또는 대체 또는 두 인접 문자의 전치)이다.

다메라우-레벤슈테인 거리는 세 개의 고전적인 단일 문자 편집 작업(삽입, 삭제 및 대체)^[4]^[2]에 더하여 허용되는 작업 중 전이를 포함시킴으로써 고전적인 레벤슈테인 거리와는 다르다.

Damerau는 그의 논문에서 ^[5]정보 검색 시스템의 철자 오류 조사에서 80% 이상이 네 가지 유형 중 하나의 오류에 의한 결과라고 말했다.Damerau의 논문은 한 번의 편집 조작으로 수정할 수 있는 오타를 검토했습니다.원래 동기는 철자 검사기와 같은 응용 프로그램을 개선하기 위해 인간의 철자 오류 사이의 거리를 측정하는 것이었지만, 다메라우-레벤슈테인 거리는 또한 생물학에서 단백질 ^[6]배열 사이의 변화를 측정하는 데 사용되었습니다.

정의.

두 $a$ 와 $a$ $b$ $사이의$ Damerau-Levenshtein $거리$ 를 표현하기 위해 함수 $d_{a,b}(i,j)$ $d_{a,b}(i,j)$ ( $d_{a,b}(i,j)$ $)$ ({ $displaystyle d_{a,b}(i,j)$ 를 $d_{a,b}(i,j)$ 정의합니다. 이 값은 $문자열$ 의 i ${displaystyle$ i $}$ 기호 $i$ 프리픽스(초기 부분 문자열 $)$ 와 표시 $스타일 사이$ 의 $a$ 거리입니다.j $j$ $\$ $displaystyle$ j \ $displaystyle$ 의 프리픽스 $b$

제한된 거리 함수는 다음과 같이 ^[7]^{: A:11}재귀적으로 정의됩니다.

\displaystyle d_{a,b}(i,j)=\min {case}0&{\text{if}}i=0,\d_{a,b}(i-1,j)+1&{\text{i}i>0,\d_{a,b}(i,j-1)+1&{\text}{text}},{text}}}}}}:0}

1_{(a_{i}\neq b_{j})}

서 1

1_{(a_{i}\neq b_{j})}

1_{(a_{i}\neq b_{j})}

1_{(a_{i}\neq b_{j})}

1_{(a_{i}\neq b_{j})}

j

)({

j}})은

1_{(a_{i}\neq b_{j})}

a_{i}=b_{j}

=

a_{i}=b_{j}

({

}=

b_{j})

일

a_{i}=b_{j}

때 0과 같고, 그렇지 않을 경우 1과 같은 표시기 함수입니다.

각 재귀 콜은 Damerau-Levenshtein 거리에 포함되는 다음 중 하나의 케이스와 일치합니다.

$d_{a,b}(i-1,j)+1$ a $d_{a,b}(i-1,j)+1$ , $d_{a,b}(i-1,j)+1$ ( $d_{a,b}(i-1,j)+1$ - $d_{a,b}(i-1,j)+1$ , $d_{a,b}(i-1,j)+1$ ) + $d_{a,b}(i-1,j)+1$ ( { $displaystyle d$ _ { $a$ , $b$ } ( i - 1, $j$ ) + $1$ }는 $d_{a,b}(i-1,j)+1$ 삭제에 대응합니다(a에서b까지).
$d_{a,b}(i,j-1)+1$ a $d_{a,b}(i,j-1)+1$ $d_{a,b}(i,j-1)+1$ - $d_{a,b}(i,j-1)+1$ ) $d_{a,b}(i,j-1)+1$ + 1 $({displaystyle d_{a,b}(i,j-1)+1}$ 는 삽입(a에서b까지)에 대응합니다 $d_{a,b}(i,j-1)+1$ .
$d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ a $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ , $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ ( $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ - $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ , $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ - $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ ) + $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ ( $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ j $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ ) { $displaystyle$ d $_$ { $a$ , b } ( i - $1$ , $j$ - 1 ) + 1 _ { ( a _ { i } \ $neq$ b _ { $j$ } } } $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ cor 、 각 기호가 동일한지 여부에 따라 일치 또는 불일치에 대응합니다.
$d_{a,b}(i-2,j-2)+1$ a $d_{a,b}(i-2,j-2)+1$ , $d_{a,b}(i-2,j-2)+1$ ( $d_{a,b}(i-2,j-2)+1$ - $d_{a,b}(i-2,j-2)+1$ , $d_{a,b}(i-2,j-2)+1$ - $d_{a,b}(i-2,j-2)+1$ ) + $d_{a,b}(i-2,j-2)+1$ { $displaystyle d_{a,b}(i-2,j-2)+1}$ 은 $d_{a,b}(i-2,j-2)+1$ 연속되는 두 기호 사이의 전위에 해당합니다.

$a$ 와 b $사이$ 의 Damerau-Levenshtein 거리는 전체 문자열에 대한 함수 값으로 $d_{a,b}{\big (}|a|,|b|{\big )}$ 됩니다. $,$ ( $a$ , b ) { \ $big$ ( ) $d_{a,b}{\big (}|a|,|b|{\big )}$ } $=$ a { $d_{a,b}{\big (}|a|,|b|{\big )}$ $displaystyle$ i = $a$ 는 $i=|a|$ $문자열$ 의 길이를 $j=|b|$ , $=$ { $display style$ o}는 $j=|b|$ 문자열의 길이를 나타냅니다 $.$ f $b$ .

알고리즘.

여기서는 두 가지 알고리즘이 제시된다.^[8]첫 번째 알고리즘은 보다 단순한 알고리즘으로 최적 문자열 정렬 거리 또는 제한된 편집 ^[7]거리로 알려진 것을 계산하고, 두^[9] 번째 알고리즘은 인접한 전이를 사용하여 다메라우-레벤슈테인 거리를 계산한다.트랜지션을 추가하면 복잡성이 크게 증가합니다.두 알고리즘의 차이는 최적의 문자열 정렬 알고리즘이 서브스트링을 두 번 이상 편집하지 않는 조건에서 문자열을 동일하게 만들기 위해 필요한 편집 조작 수를 계산하고 두 번째 알고리즘은 이러한 제한을 제시하지 않는다는 것입니다.

CA와 ABC 사이의 편집 거리를 예로 들어 보겠습니다.다메라우-레벤슈타인 거리 LD(CA, ABC) = 2는 CA → AC → ABC이기 때문이지만, 최적 문자열 정렬 거리 OSA(CA, ABC) = 3은 연산 CA → AC가 사용되는 경우, 하위 문자열을 한 번 이상 편집하지 않아도 되기 때문에 AC → ABC를 사용할 수 없기 때문이다.배분은 CA → A → AB → ABC입니다.최적의 문자열 정렬 거리에서는 OSA(CA, AC) + OSA(AC, ABC) < OSA(CA, ABC)의 삼각 부등식은 유지되지 않으므로 진정한 메트릭이 아닙니다.

최적의 문자열 정렬 거리

최적의 문자열 정렬 거리는 Levenshtein 거리를 계산하는 Wagner-Fischer 동적 프로그래밍 알고리즘의 간단한 확장을 사용하여 계산할 수 있습니다.의사 코드:

알고리즘 OSA-distance가 입력됩니다.문자열 a [ 1 .길이(a), b[1..length(b)] 출력: 거리, 정수 let d[0..length(a), 0..length(b)]는 정수, 치수 길이(a)+1, length(b)+1 //의 2d 배열로, d는 0자리이고, a와 b는 1자리입니다.i : = 0 to length (a) include do d[i, 0] : = i : = 0 to length (b) i : = 1 to length (a) include do do d[0, j] : = 1 to length (a) i : = 1 to length (a ) include a : = a : = a : = 1 to length (i : = 1 to length (a ) tength (i : = 1 ~ b) 인clution d[i, j-1] + 1, // 삽입 d[i-1, j-1] + 비용 // 치환 i > 1 및 a [i] = b[j-1] 및 a [i-1] = b[j]일 경우 d[i, j] : = 최소값(d[i, j], d-2, j-2] + 치환 //

Levenshtein 거리 알고리즘과의 차이는 반복이 하나 더해진다는 것입니다.

i > 1 및 j > 1 및 a[i] = b[j-1] 및 a[i-1] = b[j]이면 d[i, j] : = 최소(d[i, j], d[i-2, j] + 1) // 전위

인접 트랜지션과의 거리

다음 알고리즘에서는 인접한 트랜스포지션을 사용하여 진정한 Damerau-Levenshtein 거리를 계산합니다.이 알고리즘에서는 알파벳 $δ$ 크기의 추가 파라미터가 필요합니다.따라서 배열의 $모든$ 엔트리가 [0, $δ]$ ^[7]^{: A:93}에 있어야 합니다.

알고리즘 DL-distance가 입력됩니다.문자열 a [ 1 .길이(a), b[1..length(b)] 출력: 거리, 정수 da := i := 1 ~ δ를 포함하는 δ 정수의 새로운 배열 do da[i] := 0 let d[-1..length(a), -1..length(b)]는 정수, 치수 길이(a)+2, length(b)+2의 2-d 배열입니다. 반면 a, b, da는 -1에서 시작하는 인덱스를 가집니다. maxdist : = length (a) + length (b) d[-1, -1] : do (i) : do (i ) : 0 - dist : 0 (i ) : ） : = length (a ) ） : 。gth(b) include do d[-1, j] := maxdist d[0, j] := j는 i := 1에서 길이(a)까지 do deb := 0에서 길이(b)까지 do k := da [b [j] ℓ : : : : : : : : = db [ if a ] = b [ if cost : = 1 : = 1 : = db [ if cost ]d[i, j] : = minimum(d[i-1, j-1] + cost, //construction d[i, j-1, j] + 1, //sec d[k-1] + (i-k-1) + 1 + (j-sec-1) //return da[i] returning d : [i]

제한되지 않는 Damerau-Levenshtein 거리를 계산하기 위한 적절한 알고리즘을 고안하기 위해서는 최적의 편집 조작 시퀀스가 항상 존재해야 합니다.이러한 편집 조작은 한 번 변환된 문자가 나중에 변경되지 않습니다(전송 $W_{T}$ 인 W $(\$ W_ ${T$ 가 적어도 i의 평균 비용인 한 유지됩니다).nsertion 및 삭제( $2W_{T}\geq W_{I}+W_{D}$ : 2 $2W_{T}\geq W_{I}+W_{D}$ T $2W_{T}\geq W_{I}+W_{D}$ $2W_{T}\geq W_{I}+W_{D}$ I + $2W_{T}\geq W_{I}+W_{D}$ \ $style$ 2 W $2W_{T}\geq W_{I}+W_{D}$ _ {T $}\geq W_{I}+W_{D}}).$ ^[9]따라서 서브스트링을 여러 번 변경하는 대칭적인 방법은 (1)문자를 치환하고 그 사이에 임의의 수의 문자를 삽입하는 방법과 (2)문자의 시퀀스를 삭제하고 삭제 후 인접하게 되는 문자를 치환하는 방법 두 $가지뿐$ 입니다.이 아이디어의 간단한 구현은 복잡도 입방정도의 알고리즘을 제공합니다 $O{\big (}M\cdot N\cdot \max(M,N){\big )}$ ( M $O{\big (}M\cdot N\cdot \max(M,N){\big )}$ ⋅ $O{\big (}M\cdot N\cdot \max(M,N){\big )}$ max ( $O{\big (}M\cdot N\cdot \max(M,N){\big )}$ , $O{\big (}M\cdot N\cdot \max(M,N){\big )}$ N $O{\big (}M\cdot N\cdot \max(M,N){\big )}$ ) $O{\big (}M\cdot N\cdot \max(M,N){\big )}$ \ $displaystyle$ O { \ $big$ ( $} M$ \ $cdot$ N \ $cdot \ max$ ( $M$ , N ) { \ $big$ } $O{\big (}M\cdot N\cdot \max(M,N){\big )}$ 。여기서 M과 N은 문자열 길이입니다.Lowrance와 ^[9]Wagner의 아이디어를 사용하면 이 순진한 알고리즘은 최악의 경우 O $(M n$ N $)$ 로 $O(M\cdot N)$ 개선될 수 있습니다.이것은 위의 의사 $코드$ 의 동작입니다.

비트맵 알고리즘을 변경해 전이를 처리할 수 있다는 것은 흥미롭습니다.이러한 적응의 예에 대해서는, 의 정보 검색 섹션을^[1] 참조해 주세요.

적용들

Damerau-Levenshtein 거리는 자연어 처리에 중요한 역할을 합니다.자연어에서는 문자열이 짧고 오류(오타) 수가 2를 넘는 경우는 거의 없습니다.이러한 상황에서는 제한된 편집 거리와 실제 편집 거리가 매우 드물게 다릅니다.Oommen과 Loke는^[8] 일반화된 트랜스포지션을 도입함으로써 제한된 편집 거리의 제한도 완화했습니다.그럼에도 불구하고, 제한된 편집 거리는 일반적으로 삼각 부등식을 만족시키지 못하기 때문에 미터법 트리와 함께 사용할 수 없다는 것을 기억해야 한다.

DNA

DNA는 자주 삽입, 결실, 치환 및 전이 과정을 거치고, 각각의 작업은 거의 동일한 시간 척도로 발생하기 때문에, 다메라우-레벤슈테인 거리는 DNA의 두 가닥 사이의 변화에 대한 적절한 지표이다.DNA, 단백질 및 기타 생물정보학 관련 정렬 작업에서 더 일반적인 것은 니들맨과 같은 밀접하게 관련된 알고리즘을 사용하는 것이다.Wunsch 알고리즘 또는 Smith-Waterman 알고리즘.

부정행위 검출

이 알고리즘은 벤더명 등 임의의 단어와 조합하여 사용할 수 있습니다.입력은 원래 수동이기 때문에 잘못된 벤더를 입력할 위험이 있습니다.사기꾼 종업원은, 「리치 상속자 에스테이트 서비스」와 같은 실제의 벤더를 1개 입력할 수 있습니다.거짓궂은 벤더는 「리치 히어 스테이트 서비스」입니다.그런 다음 사기범은 가짜 은행 계좌를 만들고 실제 벤더와 가짜 벤더에게 수표를 라우팅합니다.Damerau-Levenshtein 알고리즘은 전치 및 폐기된 편지를 검출하여 사기 검사자에게 항목에 대한 주의를 환기합니다.

수출관리

미국 정부는 Damerau-Levenshtein 거리를 Consolidated Screening List ^[10]API와 함께 사용합니다.

「」를 참조해 주세요.

이스펠은 다메라우-레벤슈테인 거리 1에 기초한 보정을 제안한다.
타이프 쿼팅

레퍼런스

^ Brill, Eric; Moore, Robert C. (2000). An Improved Error Model for Noisy Channel Spelling Correction (PDF). Proceedings of the 38th Annual Meeting on Association for Computational Linguistics. pp. 286–293. doi:10.3115/1075218.1075255. Archived from the original (PDF) on 2012-12-21.
^ ^a ^b 바드, 그레고리 V(2007년),"그 Damerau–Levenshteinstring-edit 거리를 통해 Spelling-error에 관대하지 않order-independent pass-phrases", 제5회 오스트랄라시아의 심포지엄 ACSW를 둔에 회보:2007년, 밸러랫:오스트레일리아 동남부, 호주, 1월 30일-2월 2일 2007년, 헌장 연구와 연습에 정보 기술, 68, Darlinghurs vol..t, 호주:호주 컴퓨터 학회, Inc.,를 대신하여 서명함. 117–124, 아이 에스비엔 978-1-920682-49-1.
^ Li; et al. (2006). Exploring distributional similarity based models for query spelling correction (PDF). Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics. pp. 1025–1032. doi:10.3115/1220175.1220304. Archived from the original (PDF) on 2010-04-01.
^ Levenshtein, Vladimir I. (February 1966), "Binary codes capable of correcting deletions, insertions, and reversals", Soviet Physics Doklady, 10 (8): 707–710, Bibcode:1966SPhD...10..707L
^ Damerau, Fred J. (March 1964), "A technique for computer detection and correction of spelling errors", Communications of the ACM, 7 (3): 171–176, doi:10.1145/363958.363994, S2CID 7713345
^ 사용하는 방법:
^ ^a ^b ^c Boytsov, Leonid (May 2011). "Indexing methods for approximate dictionary searching". Journal of Experimental Algorithmics. 16: 1. doi:10.1145/1963190.1963191. S2CID 15635688.
^ ^a ^b Oommen, B. J.; Loke, R. K. S. (1997). "Pattern recognition of strings with substitutions, insertions, deletions and generalized transpositions". Pattern Recognition. 30 (5): 789–800. Bibcode:1997PatRe..30..789O. CiteSeerX 10.1.1.50.1459. doi:10.1016/S0031-3203(96)00101-X.
^ ^a ^b ^c Lowrance, Roy; Wagner, Robert A. (April 1975), "An Extension of the String-to-String Correction Problem", J ACM, 22 (2): 177–183, doi:10.1145/321879.321880, S2CID 18892193
^ "Consolidated Screening List API". Trade.gov Developer Portal. International Trade Administration, U.S. Department of Commerce. Archived from the original on 2019-10-30.

추가 정보

Navarro, Gonzalo (March 2001), "A guided tour to approximate string matching", ACM Computing Surveys, 33 (1): 31–88, CiteSeerX 10.1.1.452.6317, doi:10.1145/375360.375365, S2CID 207551224

[1] Brill, Eric; Moore, Robert C. (2000). An Improved Error Model for Noisy Channel Spelling Correction (PDF). Proceedings of the 38th Annual Meeting on Association for Computational Linguistics. pp. 286–293. doi:10.3115/1075218.1075255. Archived from the original (PDF) on 2012-12-21.

[bard-2] 바드, 그레고리 V(2007년),"그 Damerau–Levenshteinstring-edit 거리를 통해 Spelling-error에 관대하지 않order-independent pass-phrases", 제5회 오스트랄라시아의 심포지엄 ACSW를 둔에 회보:2007년, 밸러랫:오스트레일리아 동남부, 호주, 1월 30일-2월 2일 2007년, 헌장 연구와 연습에 정보 기술, 68, Darlinghurs vol..t, 호주:호주 컴퓨터 학회, Inc.,를 대신하여 서명함. 117–124, 아이 에스비엔 978-1-920682-49-1.

[3] Li; et al. (2006). Exploring distributional similarity based models for query spelling correction (PDF). Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics. pp. 1025–1032. doi:10.3115/1220175.1220304. Archived from the original (PDF) on 2010-04-01.

[4] Levenshtein, Vladimir I. (February 1966), "Binary codes capable of correcting deletions, insertions, and reversals", Soviet Physics Doklady, 10 (8): 707–710, Bibcode:1966SPhD...10..707L

[5] Damerau, Fred J. (March 1964), "A technique for computer detection and correction of spelling errors", Communications of the ACM, 7 (3): 171–176, doi:10.1145/363958.363994, S2CID 7713345

[6] 사용하는 방법:

[Boytsov-7] Boytsov, Leonid (May 2011). "Indexing methods for approximate dictionary searching". Journal of Experimental Algorithmics. 16: 1. doi:10.1145/1963190.1963191. S2CID 15635688.

[oommen-8] Oommen, B. J.; Loke, R. K. S. (1997). "Pattern recognition of strings with substitutions, insertions, deletions and generalized transpositions". Pattern Recognition. 30 (5): 789–800. Bibcode:1997PatRe..30..789O. CiteSeerX 10.1.1.50.1459. doi:10.1016/S0031-3203(96)00101-X.

[LW75-9] Lowrance, Roy; Wagner, Robert A. (April 1975), "An Extension of the String-to-String Correction Problem", J ACM, 22 (2): 177–183, doi:10.1145/321879.321880, S2CID 18892193

[10] "Consolidated Screening List API". Trade.gov Developer Portal. International Trade Administration, U.S. Department of Commerce. Archived from the original on 2019-10-30.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[1]

[10]

v t 줄들
문자열 메트릭	대략적인 문자열 매칭 비트맵 알고리즘 다메라우-레벤슈테인 거리 거리 편집 게스탈트 패턴 매칭 해밍 거리 자로-윙클러 거리 리 거리 레벤슈테인 오토마톤 레벤슈테인 거리 바그너-피셔 알고리즘
문자열 검색 알고리즘	사도-장칼로 알고리즘 Boyer-Moore 문자열 검색 알고리즘 보이어-무어-호스풀 알고리즘 크누스-모리스-프랫 알고리즘 라빈-카르프 알고리즘
다중 문자열 검색	아호코라식 Commentz-Walter 알고리즘
정규 표현	정규 표현 엔진 비교 정규 문법 톰슨 구조 비결정론적 유한 오토마톤
시퀀스 얼라인먼트	히르슈베르크 알고리즘 니들맨분쉬 알고리즘 스미스-워터맨 알고리즘
data 구조	DAFSA 서픽스 배열 서픽스 오토마톤 접미사 트리 일반 접미사 트리 출렁 삼원 검색 트리 트리
다른.	해석 패턴 매칭 압축 패턴 매칭 최장 공통 서브시퀀스 최장 공통 서브스트링 순차적 패턴 마이닝 정렬

Search

다메라우-레벤슈테인 거리

네임스페이스

더

목차

정의.

알고리즘.

최적의 문자열 정렬 거리

인접 트랜지션과의 거리

적용들

DNA

부정행위 검출

수출관리

「」를 참조해 주세요.

레퍼런스

추가 정보

Search

다메라우-레벤슈테인 거리

정의.

알고리즘.

최적의 문자열 정렬 거리

인접 트랜지션과의 거리

적용들

DNA

부정행위 검출

수출관리

「 」를 참조해 주세요.

레퍼런스

추가 정보

「」를 참조해 주세요.