거리 편집

컴퓨터 언어학 및 컴퓨터 과학에서 편집 거리는 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 연산 수를 세어 두 문자열(예: 단어)이 서로 얼마나 다른지 수량화하는 방법입니다.거리 편집은 자연어 처리에서 응용 프로그램을 찾습니다. 여기서 자동 철자 수정은 해당 단어와 거리가 짧은 단어를 사전에서 선택하여 철자가 틀린 단어의 수정 후보를 결정할 수 있습니다.생물정보학에서는 A, C, G, T의 문자열로 볼 수 있는 DNA 배열의 유사성을 정량화하는 데 사용할 수 있다.

편집 거리에 대한 다른 정의는 다른 문자열 연산 세트를 사용합니다.Levenshtein 거리 연산은 문자열 내의 문자를 제거, 삽입 또는 치환하는 것입니다.가장 일반적인 측정 기준인 Levenshtein distance라는 용어는 편집 ^[1]거리와 교환할 수 있게 사용됩니다.

편집 거리 유형

다른 유형의 편집 거리에 따라 다른 문자열 작업 세트가 허용됩니다.예:

Levenshtein 거리는 삭제, 삽입 및 치환을 허용합니다.
최장 Common Succession(LCS; 공통서브시퀀스) 거리에서는 삽입과 삭제만 허용되며 치환은 허용되지 않습니다.
Hamming 거리는 치환만 허용하기 때문에 길이가 같은 문자열에만 적용됩니다.
Damerau-Levenshtein 거리는 인접한 두 문자를 삽입, 삭제, 치환 및 전치할 수 있습니다.
자로의 거리는 이동만 허용한다.

일부 편집 거리는 허용되는 특정 편집 작업 세트를 사용하여 계산된 매개 변수화 메트릭으로 정의되며 각 작업에는 비용이 할당됩니다(무한할 수도 있음).이것은 Smith-Waterman 알고리즘과 같은 DNA 염기서열 정렬 알고리즘에 의해 더욱 일반화되며, 이 알고리즘은 수술 비용을 어디에 적용하느냐에 따라 다르게 만든다.

정식 정의 및 속성

알파벳 $δ$ 의 2개의 $문자열$ $a$ 와 b(예를 들어 ASCII 문자 집합, 바이트 집합 [0])가 지정됩니다.255] 등), 편집거리 d( $a$ , $b$ )는 a를 $b$ 로 $변환$ 하는 편집 조작의 최소 가중치 계열이다.편집 조작의 가장 간단한 세트 중 하나는 1966년 ^[2]Levenshtein에 의해 정의된 것입니다.

단일 기호 삽입

a

= uv인

경우

기호

x를 삽입하면

uxv

가 생성됩니다.빈 문자열을 나타내는

to

을 사용하여 →x로 나타낼 수도 있습니다.

단일 기호를 삭제하면

uxv

가 uv(

x

→160)로 변경됩니다.

단일

기호

x

를 기호 y

δ

x로 치환하면

uxv

가

uyv

(

x

→

y

)로 바뀝니다.

Levenshtein의 원래 정의에 따르면, 이러한 연산에는 각각 단가가 있으므로(문자 치환 자체는 비용이 0이라는 점을 제외하고), Levenshtein 거리는 a를 $b$ 로 $변환$ 하는 데 필요한 최소 연산 횟수와 같다.보다 일반적인 정의는 음이 아닌 무게 $함수$ _ins w( $x$ ), $w$ _del( $x$ ) $및$ _sub w( $x$ , $y$ )를 연산과 ^[2]관련짓습니다.

추가적인 원시 작업이 제안되었습니다.Damerau-Levenshtein 거리는 하나의 편집으로 카운트됩니다. 즉, $uxyv$ 를 ^[3]^[4] $uyxv$ 로 변경하는 연산에 의해 공식적으로 특징지어지는 인접한 두 문자의 전치입니다.OCR 출력을 수정하는 작업에서는 단일 문자를 한 쌍의 문자로 치환하는 병합 ^[4]및 분할 연산이 사용되었습니다.

편집 거리의 다른 변형은 조작 세트를 제한함으로써 얻을 수 있습니다.최장 Common Succession(LCS; 공통서브시퀀스) 거리는 삽입 및 삭제가 있는 편집 거리입니다.단위는 둘 다 ^[1]^{: 37}단가가 됩니다.마찬가지로 치환만 허용하면(단위로 다시), 해밍 거리가 얻어집니다.이것은 같은 길이의 ^[1]문자열로 제한해야 합니다.자로-윙클러 거리는 트랜스포지션만 허용되는 편집 거리에서 얻을 수 있습니다.

예

"키튼"과 "앉은" 사이의 Levenshtein 거리는 3입니다.전자를 후자로 변환하는 최소 편집 스크립트는 다음과 같습니다.

kitten → sitten ("k"에 "s"를 나타냄)
sitten → sittin ("e"의 경우 "i"를 생략함)
앉은뱅이 → 앉은뱅이(마지막에 "g" 삽입)

LCS 거리(삽입 및 삭제 전용)는 다른 거리와 최소한의 편집 스크립트를 제공합니다.

kitten → itten(0에서 "k" 삭제)
iten → sitten (0에 "s" 삽입)
sitten → sittn(4에서 "e" 삭제)
sittn → sittin (4에 "i" 삽입)
앉은뱅이 → 앉은뱅이 (6에 "g" 삽입)

총 5회의 작업 비용/거리입니다.

특성.

음이 아닌 비용으로 거리를 편집하면 메트릭의 공리를 충족하므로 다음 조건이 ^[1]^{: 37}충족될 때 문자열의 메트릭 공간이 생성됩니다.

모든 편집 작업에는 플러스 비용이 있습니다.
모든 연산에 대해 동일한 비용의 역연산이 있습니다.

이러한 속성을 사용하면 메트릭 공리는 다음과 같이 충족됩니다.

d

(a,

b

) = a=b인 경우에만 0입니다. 각 문자열은 정확히 제로 연산을 사용하여 3차 변환될 수 있기 때문입니다.

d

(

a

,

b

) > 0(a, b)은 0이 아닌 비용으로 적어도1개의 조작이 필요하기 때문에 a

b

b일

경우

0이 됩니다.

d

(

a

,

b

) =

d

(

b

,

a

)는 각 연산의 비용과 그 역의 비용의 등식에 의한 것이다.

삼각 부등식:

d

(

a

,

c

) (

d

(

a

, b) +

d

(

b

,

c

)^[5]

Levenshtein 거리와 LCS 거리와 단위 비용은 위의 조건을 충족하므로 메트릭 공리가 성립합니다.적절한 지표가 아닌 편집 거리의 변형도 ^[1]문헌에서 고려되었다.

단위 비용 편집 거리의 기타 유용한 속성은 다음과 같습니다.

LCS 거리는 ^[1]^{: 37}한 쌍의 문자열 길이의 합계에 의해 위쪽으로 제한됩니다.
LCS 거리는 Levenshtein 거리의 상한입니다.
길이가 같은 문자열의 경우 해밍 거리는 Levenshtein ^[1]거리의 상한입니다.

비용/중량에 관계없이 다음 속성은 모든 편집 거리를 유지합니다.

$a$ 와 b가 공통 프레픽스를 공유하는 $경우$ 이 프레픽스는 거리에 영향을 주지 않습니다. $공식적$ 으로는 a = uv $및$ b = $uw일$ $때$ d( $a$ , $b$ ) = $d$ ( $v$ , $w$ )^[4]이다.이를 통해 공통 접두사와 접미사를 선형 시간에 건너뛸 수 있기 때문에 편집 거리 및 편집 스크립트와 관련된 많은 계산 속도를 높일 수 있습니다.

계산

문자열 쌍 간의 최소 편집 거리를 계산하는 첫 번째 알고리즘은 1964년에 ^[6]Damerau에 의해 발표되었다.

공통 알고리즘

Levenshtein의 원래 연산을 사용하여 a $a=a_{1}\ldots a_{m}$ $a=a_{1}\ldots a_{m}$ … $a=a_{1}\ldots a_{m}$ {\ $displaystyle$ a $=a_{1}\ldots a_{m}$ 에서 $a=a_{1}\ldots a_{m}$ b $b=b_{1}\ldots b_{n}$ $b=b_{1}\ldots b_{n}$ 1 $b=b_{1}\ldots b_{n}$ … $b=b_{1}\ldots b_{n}$ n { $display$ b $=b1}\ldots b_$ {n $}$ 까지의 (비대칭 $b=b_{1}\ldots b_{n}$ ) 편집 거리는 $d_{mn}$ 정의됩니다 $d_{mn}$

{time}d_{i0}&={k=1}^{i}w_{\mathrm {del}(a_{k}),&\sum {text{for}\leq i\leq m\d_{0j}&={sum{k=1}^{j}{mathb}{mathb}{ins}}{ins}\\d_{i,j-1}+w_{\mathrm {ins}}(b_{j})\\d_{i-1,j-1}+w_{\mathrm {sub}}(a_{i},b_{j})\end{cases}\neq b_{j}\end{cases}\cases}\coles {text{for}\cases}\case}\coles {text{for}\card {i}\le}\card {i}\crmeq,1\le nle}.\end { aligned}

이 알고리즘은 재귀 절의 ^[3]최소화에 다른 용어를 추가하여 전이를 처리하도록 일반화할 수 있습니다.

이 반복을 평가하는 간단하고 재귀적인 방법에는 기하급수적인 시간이 걸립니다.따라서, 이것은 여러 ^[2]^[3]발명의 역사가 있지만, 일반적으로 바그너와 ^[7]피셔가 인정한 동적 프로그래밍 알고리즘을 사용하여 계산됩니다.Wagner-Fischer 알고리즘이 완료되면 $(\$ 부터 시작하는 동적 프로그래밍 알고리즘에서 사용되는 동작의 백트레이스로 최소한의 편집 조작 시퀀스를 읽을 수 있습니다.

이 알고리즘의 시간 복잡도는 δ(mn)입니다. $여기$ 서 $m$ 과 n은 문자열의 길이입니다.풀 다이내믹 프로그래밍 테이블이 구성되면 공간 복잡도도 δ( $mn$ )가 됩니다.이것은 알고리즘이 어느 순간에나 메모리에 2행(또는 2컬럼)만을 필요로 하는 것을 관찰함으로써 δ(min( $m$ , $n$ )로 개선할 수 있습니다.그러나 이러한 최적화로 인해 최소 일련의 편집 ^[3]작업을 읽어낼 수 없습니다.이 문제에 대한 선형 공간 해법은 ^[8]^{: 634}Hirschberg의 알고리즘에 의해 제공됩니다.

알고리즘의 향상

위에서 설명한 바그너-피셔 알고리즘을 개선하여 Ukkonen은 여러 변형을 ^[9]기술합니다.그 중 하나는 2개의 문자열과 최대 편집 $거리$ s를 필요로 하며 min( $s$ , $d$ )을 반환합니다.동적 프로그래밍 테이블의 대각선 주위에 있는 부분만 계산하고 저장함으로써 이를 달성할 수 있습니다.이 알고리즘에는 시간 O( $s$ ×min( $m$ , $n$ )가 소요됩니다. $여기$ 서 $m$ 과 n은 문자열의 길이입니다.편집 시퀀스를 ^[3]읽어낼 필요가 있는지 여부에 따라 공간의 복잡도는 O $또는 2$ O입니다.

Landau, Myers 및 Schmidt [1]에 의한 추가 개선은 O(s² + max( $m$ , $n$ ) 시간 ^[10]알고리즘을 제공한다.

서로 배수인 유한 알파벳 및 편집 비용의 경우, 가장 빨리 알려진 정확한 알고리즘은 최악의 경우 실행 시간이 O(nm/logn)인 Masek와 Paterson입니다^[11].

적용들

편집 거리는 적은 수의 차이가 예상되는 상황에서 철자 오류 또는 OCR 오류의 수정과 같은 계산 생물학 및 자연 언어 처리 및 근사 문자열 매칭에서 응용 프로그램을 찾습니다.

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

Hirschberg의 알고리즘은 두 문자열의 최적 정렬을 계산합니다. 여기서 최적성은 편집 거리를 최소화하는 것으로 정의됩니다.
대략적인 문자열 매칭은 편집 거리로 공식화할 수 있습니다.Ukkonen의 1985년 알고리즘, 경우, 임의의 문자열 s에서 확인 결정론적 유한 상태 automaton, 열거형이 편집 거리 p 있는 대부분의 k[12](비교하라.는 비슷한 automaton 어떤 패턴이 오는 수많은 검색하는 경지는 Aho–Corasick 알고리즘지만 재치에 부스 트링 구축하는 문자열 p, 그 패턴, 그리고 상수 k이 걸린다.hou편집 조작을 허가하지 않습니다).대략적인 문자열 매칭의 알고리즘은 비트맵알고리즘으로 편집 거리에서도 정의됩니다.
Levenshtein automata는 고정된 참조 ^[4]문자열의 경계 편집 거리 내에서 문자열 집합을 인식하는 유한 상태 기계입니다.

언어 편집 거리

문자열 간의 편집 거리를 일반화하는 것은 문자열과 언어(일반적으로 정식 언어) 사이의 언어 편집 거리입니다.언어 편집 거리는 문자열 간의 편집 거리를 고려하는 대신 고정 문자열과 문자열 집합에서 얻을 수 있는 최소 편집 거리입니다.좀 더 형식적으로 $알파벳$ an 위의 언어 L 및 문자열 x에 $d(L,x)=\min _{y\in L}d(x,y)$ 대해^[13] 언어 편집 거리 $d(L,x)=\min _{y\in L}d(x,y)$ ( $,$ x) $d(L,x)=\min _{y\in L}d(x,y)$ $d(L,x)=\min _{y\in L}d(x,y)$ y $d(L,x)=\min _{y\in L}d(x,y)$ L $d(L,x)=\min _{y\in L}d(x,y)$ ( $d(L,x)=\min _{y\in L}d(x,y)$ , y ) $display$ L d ( x , y ) = \ $min _$ { y \ $in L$ } $d$ ( x , $x$ , y ) $d(x,y)$ 。 $d(x,y)$ 서 $d(x,y)$ ( $d(x,y)$ ) $display$ ) d $style 。$ 언어 L이 문맥 자유일 때, 언어 편집 ^[14]거리를 계산하는 1972년 Aho와 Peterson에 의해 제안된 입방 시간 동적 프로그래밍 알고리즘이 있습니다.정규 문법과 같이 표현이 적은 문법 패밀리의 경우 편집 ^[15]거리를 계산하는 데 더 빠른 알고리즘이 있습니다.

언어 편집 거리는 RNA 폴딩, 오류 수정, Optimum Stack Generation(^[13]^[16]최적 스택 생성) 문제에 대한 해결책 등 다양한 응용 프로그램을 찾아냈습니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b ^c ^d ^e ^f ^g Navarro, Gonzalo (1 March 2001). "A guided tour to approximate string matching" (PDF). ACM Computing Surveys. 33 (1): 31–88. CiteSeerX 10.1.1.452.6317. doi:10.1145/375360.375365. Retrieved 19 March 2015.
^ ^a ^b ^c ^d Daniel Jurafsky; James H. Martin. Speech and Language Processing. Pearson Education International. pp. 107–111.
^ ^a ^b ^c ^d ^e Esko Ukkonen (1983). On approximate string matching. Foundations of Computation Theory. Springer. pp. 487–495. doi:10.1007/3-540-12689-9_129.
^ ^a ^b ^c ^d Schulz, Klaus U.; Mihov, Stoyan (2002). "Fast string correction with Levenshtein automata". International Journal of Document Analysis and Recognition. 5 (1): 67–85. CiteSeerX 10.1.1.16.652. doi:10.1007/s10032-002-0082-8.
^ Lei Chen; Raymond Ng (2004). On the marriage of L_p-norms and edit distance (PDF). Proc. 30th Int'l Conf. on Very Large Databases (VLDB). Vol. 30. doi:10.1016/b978-012088469-8.50070-x.
^ Kukich, Karen (1992). "Techniques for Automatically Correcting Words in Text" (PDF). ACM Computing Surveys. 24 (4): 377–439. doi:10.1145/146370.146380. Archived from the original (PDF) on 2016-09-27. Retrieved 2017-11-09.
^ R. Wagner; M. Fischer (1974). "The string-to-string correction problem". J. ACM. 21: 168–178. doi:10.1145/321796.321811. S2CID 13381535.
^ Skiena, Steven (2010). The Algorithm Design Manual (2nd ed.). Springer Science+Business Media. Bibcode:2008adm..book.....S. ISBN 978-1-849-96720-4.
^ Ukkonen, Esko (1985). "Algorithms for approximate string matching" (PDF). Information and Control. 64 (1–3): 100–118. doi:10.1016/S0019-9958(85)80046-2.
^ Landau; Myers; Schmidt (1998). "Incremental String Comparison". SIAM Journal on Computing. 27 (2): 557–582. CiteSeerX 10.1.1.38.1766. doi:10.1137/S0097539794264810.
^ Masek, William J.; Paterson, Michael S. (February 1980). "A faster algorithm computing string edit distances". Journal of Computer and System Sciences. 20 (1): 18–31. doi:10.1016/0022-0000(80)90002-1. ISSN 0022-0000.
^ Esko Ukkonen (1985). "Finding approximate patterns in strings". J. Algorithms. 6: 132–137. doi:10.1016/0196-6774(85)90023-9.
^ ^a ^b Bringmann, Karl; Grandoni, Fabrizio; Saha, Barna; Williams, Virginia Vassilevska (2016). "Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product" (PDF). 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 375–384. arXiv:1707.05095. doi:10.1109/focs.2016.48. ISBN 978-1-5090-3933-3.
^ Aho, A.; Peterson, T. (1972-12-01). "A Minimum Distance Error-Correcting Parser for Context-Free Languages". SIAM Journal on Computing. 1 (4): 305–312. doi:10.1137/0201022. ISSN 0097-5397.
^ Wagner, Robert A. (1974). "Order-n correction for regular languages". Communications of the ACM. 17 (5): 265–268. doi:10.1145/360980.360995. S2CID 11063282.
^ Saha, B. (2014-10-01). The Dyck Language Edit Distance Problem in Near-Linear Time. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. pp. 611–620. doi:10.1109/FOCS.2014.71. ISBN 978-1-4799-6517-5. S2CID 14806359.

[navarro-1] ^ ^a ^b ^c ^d ^e ^f ^g Navarro, Gonzalo (1 March 2001). "A guided tour to approximate string matching" (PDF). ACM Computing Surveys. 33 (1): 31–88. CiteSeerX 10.1.1.452.6317. doi:10.1145/375360.375365. Retrieved 19 March 2015.

[slp-2] Daniel Jurafsky; James H. Martin. Speech and Language Processing. Pearson Education International. pp. 107–111.

[ukkonen83-3] Esko Ukkonen (1983). On approximate string matching. Foundations of Computation Theory. Springer. pp. 487–495. doi:10.1007/3-540-12689-9_129.

[ssm-4] Schulz, Klaus U.; Mihov, Stoyan (2002). "Fast string correction with Levenshtein automata". International Journal of Document Analysis and Recognition. 5 (1): 67–85. CiteSeerX 10.1.1.16.652. doi:10.1007/s10032-002-0082-8.

[5] Lei Chen; Raymond Ng (2004). On the marriage of L_p-norms and edit distance (PDF). Proc. 30th Int'l Conf. on Very Large Databases (VLDB). Vol. 30. doi:10.1016/b978-012088469-8.50070-x.

[6] Kukich, Karen (1992). "Techniques for Automatically Correcting Words in Text" (PDF). ACM Computing Surveys. 24 (4): 377–439. doi:10.1145/146370.146380. Archived from the original (PDF) on 2016-09-27. Retrieved 2017-11-09.

[7] R. Wagner; M. Fischer (1974). "The string-to-string correction problem". J. ACM. 21: 168–178. doi:10.1145/321796.321811. S2CID 13381535.

[8] Skiena, Steven (2010). The Algorithm Design Manual (2nd ed.). Springer Science+Business Media. Bibcode:2008adm..book.....S. ISBN 978-1-849-96720-4.

[9] Ukkonen, Esko (1985). "Algorithms for approximate string matching" (PDF). Information and Control. 64 (1–3): 100–118. doi:10.1016/S0019-9958(85)80046-2.

[10] Landau; Myers; Schmidt (1998). "Incremental String Comparison". SIAM Journal on Computing. 27 (2): 557–582. CiteSeerX 10.1.1.38.1766. doi:10.1137/S0097539794264810.

[11] Masek, William J.; Paterson, Michael S. (February 1980). "A faster algorithm computing string edit distances". Journal of Computer and System Sciences. 20 (1): 18–31. doi:10.1016/0022-0000(80)90002-1. ISSN 0022-0000.

[12] Esko Ukkonen (1985). "Finding approximate patterns in strings". J. Algorithms. 6: 132–137. doi:10.1016/0196-6774(85)90023-9.

[:0-13] Bringmann, Karl; Grandoni, Fabrizio; Saha, Barna; Williams, Virginia Vassilevska (2016). "Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product" (PDF). 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 375–384. arXiv:1707.05095. doi:10.1109/focs.2016.48. ISBN 978-1-5090-3933-3.

[14] Aho, A.; Peterson, T. (1972-12-01). "A Minimum Distance Error-Correcting Parser for Context-Free Languages". SIAM Journal on Computing. 1 (4): 305–312. doi:10.1137/0201022. ISSN 0097-5397.

[15] Wagner, Robert A. (1974). "Order-n correction for regular languages". Communications of the ACM. 17 (5): 265–268. doi:10.1145/360980.360995. S2CID 11063282.

[16] Saha, B. (2014-10-01). The Dyck Language Edit Distance Problem in Near-Linear Time. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. pp. 611–620. doi:10.1109/FOCS.2014.71. ISBN 978-1-4799-6517-5. S2CID 14806359.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[13]

[14]

[15]

[16]

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

Search

거리 편집

네임스페이스

더

목차

편집 거리 유형

정식 정의 및 속성

예

특성.

계산

공통 알고리즘

알고리즘의 향상

적용들

언어 편집 거리

「」를 참조해 주세요.

레퍼런스

Search

거리 편집

편집 거리 유형

정식 정의 및 속성

예

특성.

계산

공통 알고리즘

알고리즘의 향상

적용들

언어 편집 거리

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.