Gestaltová shoda - Gestalt Pattern Matching - Wikipedia

Gestaltová shoda,^[1] taky Ratcliff / Obershelp rozpoznávání vzorů,^[2] je algoritmus shody řetězců pro stanovení podobnost ze dvou struny. Byl vyvinut v roce 1983 společností John W. Ratcliff a John A. Obershelp a zveřejněna v Dr. Dobb's Journal v červenci 1988.^[2]

Algoritmus

Podobnost dvou řetězců ${ displaystyle S_ {1}}$ a ${ displaystyle S_ {2}}$ je určeno vzorcem, který počítá dvojnásobný počet shody postavy ${ displaystyle K_ {m}}$ děleno celkovým počtem znaků obou řetězců. Odpovídající znaky jsou definovány jako nejdelší společný podřetězec (LCS) plus rekurzivně počet odpovídajících znaků v neshodných oblastech na obou stranách LCS:^[2]

${ displaystyle D_ {ro} = { frac {2K_ {m}} {| S_ {1} | + | S_ {2} |}}}$^[3]

kde metrika podobnosti může nabývat hodnoty mezi nulou a jednou:

${ displaystyle 0 leq D_ {ro} leq 1}$

Hodnota 1 znamená úplnou shodu dvou řetězců, zatímco hodnota 0 znamená, že neexistuje shoda a dokonce ani jedno společné písmeno.

Vzorek

Nejdelší běžný podřetězec je WIKIM (šedá) s 5 znaky. Vlevo není další podřetězec. Neshodné podřetězce na pravé straně jsou EDIA a ANIA. Opět mají nejdelší společný podřetězec IA (tmavě šedá) s délkou 2. Metrika podobnosti je určena:

${ displaystyle { frac {2K_ {m}} {| S_ {1} | + | S_ {2} |}} = { frac {2 cdot (| { text {'' WIKIM ''}} | + | { text {'' IA ''}} |)} {| S_ {1} | + | S_ {2} |}} = { frac {2 cdot (5 + 2)} {9 + 9 }} = { frac {14} {18}} = 0. { overline {7}}}$

Vlastnosti

Složitost

Čas provedení algoritmu je ${ displaystyle O (n ^ {3})}$ v nejhorším případě a ${ displaystyle O (n ^ {2})}$ v průměrném případě. Změnou výpočetní metody lze významně zlepšit dobu provádění.^[1]

Komutativní vlastnost

Je možné ukázat, že algoritmus pro porovnávání vzorů Gestalt není komutativní: ^[4]

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

Vzorek

Pro dva řetězce

${ displaystyle S_ {1} = { text {GESTALT PATTERN MATCHING}}}$

a

${ displaystyle S_ {2} = { text {GESTALT PRACTICE}}}$

metrický výsledek pro

${ displaystyle D_ {ro} (S_ {1}, S_ {2})}$ je ${ displaystyle { frac {24} {40}}}$ s podřetězci GESTALT P, A, T, E a pro

${ displaystyle D_ {ro} (S_ {2}, S_ {1})}$ metrika je ${ displaystyle { frac {26} {40}}}$ s podřetězci GESTALT P, R, A, C, Já.

Aplikace

Algoritmus se stal základem Krajta difflib knihovna, která byla představena ve verzi 2.1.^[1] Kvůli nepříznivému běhovému chování této metriky podobnosti byly implementovány tři metody. Dva z nich vrátí horní hranice v rychlejší době provedení.^[1] Nejrychlejší varianta porovnává pouze délku dvou podřetězců:^[5]

${ displaystyle D_ {rqr} = { frac {2 cdot min (| S1 |, | S2 |)} {| S1 | + | S2 |}}}$,

# Implementace Drqr v Pythonudef real_quick_ratio(s1: str, s2: str) -> plovák:    "" "Vrácení horní hranice poměru () velmi rychle." ""    l1, l2 = len(s1), len(s2)    délka = l1 + l2    -li ne délka:        vrátit se 1.0    vrátit se 2.0 * min(l1, l2) / délka

Druhá horní hranice vypočítá dvojnásobný součet všech použitých znaků ${ displaystyle S_ {1}}$ které se vyskytují v ${ displaystyle S_ {2}}$ děleno délkou obou řetězců, ale sekvence je ignorována.

${ displaystyle D_ {qr} = { frac {2 cdot { big |} {! vert S1 vert ! } cap {! vert S2 vert ! } { velký |}} {| S1 | + | S2 |}}}$,

# Implementace Dqr v Pythonudef quick_ratio(s1: str, s2: str) -> plovák:    "" "Pomalu rychle vrátí horní mez poměru ()." ""    délka = len(s1) + len(s2)    -li ne délka:        vrátit se 1.0    protínají = sbírky.Čelit(s1) & sbírky.Čelit(s2)    zápasy = součet(protínají.hodnoty())    vrátit se 2.0 * zápasy / délka

Zásadně platí následující:

${ displaystyle 0 leq D_ {ro} leq D_ {qr} leq D_ {rqr} leq 1}$ a

${ displaystyle 0 leq K_ {m} leq | {! vert S1 vert ! } cap {! vert S2 vert ! } { big |} leq min (| S1 |, | S2 |) leq { frac {| S1 | + | S2 |} {2}}}$.

Reference

Další čtení

• John W. Ratcliff a David Metzener: Matching Pattern: The Gestalt Approach, Dr. Dobb's Journal, číslo 46, červenec 1988

Viz také

• Porovnávání vzorů