게슈탈트 패턴 매칭

Gestalt 패턴 ^[1]매칭은 Ratcliff/Obershelp 패턴 ^[2]인식으로도 사용되며 두 문자열의 유사성을 확인하기 위한 문자열 매칭 알고리즘입니다.그것은 존 W. 래트클리프와 존 A에 의해 1983년에 개발되었습니다. 1988년 ^[2]7월에 닥터 돕 저널에 발표되었습니다.

알고리즘.

두 $문자열{\displaystyle {}_{}}$ $({$과$$S2({$displaystyle S_{$2$$}})의 유사성은 $일치$하는 ${\displaystyle {문자}_{}}$Km({$displaystyle K_{$m$$})의 두 배를 두 문자열의 총 문자 수로 나누어 계산하는 공식에 의해 결정됩니다.일치 문자는 가장 긴 공통 하위^[3] 문자열과 가장 긴 공통 하위 ^[2][4]문자열 양쪽의 일치하지 않는 영역에서 재귀적으로 일치하는 문자 수로 정의됩니다.

${{displaystyle D_{ro}=twfrac {2K_{m}}{S_{1} + S_{2}}}$

여기서 유사성 메트릭은 0과 1 사이의 값을 취할 수 있습니다.

$디스플레이 스타일 0\leq D_{ro}\leq 1}$

값 1은 두 문자열의 완전 일치를 나타내는 반면, 값 0은 일치하는 문자가 없고 공통 문자가 하나도 없다는 것을 의미합니다.

샘플

가장 긴 공통 부분 문자열은 다음과 같습니다.WIKIM(라이트 그레이)(5자 포함).왼쪽에는 더 이상 하위 문자열이 없습니다.오른쪽에 있는 일치하지 않는 서브스트링은EDIA그리고.ANIA그들은 다시 가장 긴 공통 부분 문자열을 가집니다.IA(진회색) 길이 2.유사성 메트릭은 다음과 같이 결정됩니다.

$display{style{frac{2K_{m}}{S_{1} + S_{2}}=sysfrac{2\cdot({\text}')WIKIM'} + {{text}}IA'}}}{S_{1}+S_{2}}={2\cdot(5+2)}{9+9}}={14}{18}}=0.({7}회선)$

특성.

Ratcliff/Obers 도움말 일치 문자는 지정된 문자열의 가장 긴 공통 하위 순서와 상당히 다를 수 있습니다.$예$를 들어 ${\displaystyle {S1\mathrm{}}_{}}$${\displaystyle {}_{}}$ ${\displaystyle q}$ ${\displaystyle \mathrm{cc}}$ ${\displaystyle \mathrm{crd}}$ ${\displaystyle ds}$ ${\displaystyle bb}$ ${displaystyle S_{1$}=$q$$\;cccc\;r\;ddd\;s\;bb\;t\;ee\;u}$ $및$ ${\displaystyle \mathrm{S2}}$ = ${\displaystyle vdddw}$는 $cz$ {$displaystyle$ $S_{$$}=\$$dd\$$cccc\$ccccccccccc$\c$\ccccccc\$c\$$c{\displaystyle }$\c\c$$\c\c\c\cccc하위 문자열 및 발생한 공통 문자가 없으며 마찬가지로 왼쪽으로 ${\displaystyle {Km}_{}}$ $= 5$({{m}=5$)$로 $이어집니다{\displaystyle {}_{}}$. 그러나 $({{1$$}})$ 및 $({2})$의 $가장{\displaystyle {}_{}}$ 긴 공통 시퀀스는${\displaystyle }$(${\displaystyle d}$) (${\displaystyle \mathrm{be})}$ (${\displaystyle d}$ ($d$ ) ($d$) ($bbbb)\(ee$$총$ 길이가$10$입니다$.$

복잡성

알고리즘의 실행 $시간$은 최악의 경우 O${\displaystyle ({n3\mathrm{}}^{}}$$)({n^{3}),$ $평균적$인 ${\displaystyle {}^{}}$ O$(n2)({n^{2$})입니다.컴퓨팅 방법을 변경함으로써 실행 시간을 ^[1]크게 향상시킬 수 있습니다.

교환 성질

게슈탈트 패턴 매칭 알고리즘의 파이썬 라이브러리 구현은 교환적이지 ^[5]않습니다.

${\displaystyle D_{ro}(S_{1}, S_{2})\neq D_{ro}(S_{2}, S_{1}).}$

샘플

두 줄에 대해

${\displaystyle S_{1}=잘못된 텍스트{GESTALT 패턴 일치}}$

그리고.

${\displaystyle S_{2}=슬립 텍스트{GESTALT PRECTION}}$

에 대한 미터법 결과

${\displaystyle {\mathrm{Dro}}_{}}$($S1$${\displaystyle {}_{}}$ $)$ {{$displaystyle D_{ro}(S_{1$$,$ $S_$${2})}$는 하위 문자열이 있는 $2440입니다.$GESTALT P,A,T,E에 대해서도

${\displaystyle {\mathrm{Dro}}_{}}$(${\displaystyle {S2\mathrm{}}_{}}$ $)$ {\$displaystyle D_{ro}(S_{2, S_{1}}}$ 메트릭은$$ ${\displaystyle \frac{\mathrm{하위}}{}}$ 문자열이 있는 ${\displaystyle \frac{2640}{}}${\$displaystyle {frac {26}{40$$}}$GESTALT P,R,A,C,I.^[why?]

적용들

파이썬 difflib버전 2.^[1]1에서 소개된 라이브러리는 Ratcliff-Obershelp 알고리즘보다 앞선 유사한 알고리즘을 구현합니다.이 유사성 메트릭의 바람직하지 않은 런타임 동작으로 인해 세 가지 방법이 구현되었습니다.그 중 두 개는 더 빠른 실행 ^[1]시간에 상한을 반환합니다.가장 빠른 변형은 두 하위 ^[6]문자열의 길이만 비교합니다.

${\displaystyle {\mathrm{Drqr}}_{}}$ $=$(${\displaystyle \frac{S1}{,}}$ ${\displaystyle \frac{\mathrm{S2})}{}}$ ${\displaystyle \frac{\mathrm{S1}}{}}$ ${\displaystyle \frac{+}{}}$ ${\displaystyle \frac{\mathrm{S2}}{}}${\displaystyle $D_{rqr$}=$displayfrac {2\cdot \min(S1, S2)}{S1$+$S2$

두 번째 상한은 $({{$${\displaystyle {displaystyle\mathrm{}}_{}}$ $S_{2})$에서 $발생$하는 모든 $사용$된 문자$$ S1({$displaystyle$ S_{$1}})$의 합의 두 배를 계산하지만 시퀀스는 무시됩니다.

$displaystyle D_{qr}=twfrac {2\cdot}\{\!\vert S1\vert \!\}\cap \{\!\vert S2\vert \!\}{\big }{S1 + S2 }}}$^{[인증 필요]}

Python에서의 Dqr 구현 디프 재빠른(s1: 스트르, s2: 스트르) -> 흘러가다:     "" 비교적 빨리 상한선()을 반환합니다."""     길이 = 렌(s1) + 렌(s2)      한다면 것은 아니다. 길이:         돌아가다 1.0      교차하는 = 소장품.계산대(s1) & 소장품.계산대(s2)     성냥 = 합(교차하는.가치())     돌아가다 2.0 * 성냥 / 길이 

일반적으로 다음 사항이 적용됩니다.

${\displaystyle {}_{}}$≤ ${\displaystyle {}_{}{}_{}}$≤ ${\displaystyle D_{}{}_{}}$≤ ${\displaystyle D_{}}$ ${\displaystyle {}_{}}$≤ D ${\displaystyle \mathrm{r}}$ $≤$ 1 { \ $displaystyle$0 \ $leq$ D_${ro}\leq$ D_${qr}\leq D_{rq}\leq$ 1$}$ 및$$

$displaystyle$$\vert S1\vert \!$$\}\cap \{\!$$\vert S2\vert \!$$\}{\big }\leq \min(S1, S2)\leq \frac {S1$+$S2}{2$

레퍼런스

진일보한 내용

• Ratcliff, John W.; Metzener, David (July 1988). "Pattern Matching: The Gestalt Approach". Dr. Dobb's Journal (46).

참고 항목

• 패턴 매칭