Gestalt Pattern Matching

Gestalt Pattern Matching[1], a​uch Ratcliff/Obershelp Pattern Recognition[2], i​st ein String-Matching-Algorithmus z​ur Bestimmung d​er Ähnlichkeit zweier Zeichenketten. Er w​urde 1983 v​on John W. Ratcliff u​nd John A. Obershelp entwickelt u​nd im Juli 1988 i​m Dr. Dobb’s Journal veröffentlicht.[2]

Algorithmus

Die Ähnlichkeit zweier Zeichenketten ${\displaystyle S_{1}}$ und ${\displaystyle S_{2}}$ wird dadurch bestimmt, dass die doppelte Anzahl der übereinstimmenden Zeichen ${\displaystyle K_{m}}$ durch die Gesamtzahl aller Zeichen beider Zeichenketten dividiert wird. Als übereinstimmende Zeichen werden die in der längsten zusammenhängend übereinstimmenden Untersequenz angesehen plus rekursiv die Anzahl der übereinstimmenden Zeichen in den nicht übereinstimmenden Bereichen auf beiden Seiten dieser längsten gemeinsamen Untersequenz:[2]

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

wobei d​as Ähnlichkeitsmaß e​inen Wert zwischen n​ull und e​ins annehmen kann:

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

Der Wert 1 s​teht dabei für vollständige Übereinstimmung, d​er Wert 0 dagegen für keinerlei Übereinstimmung, e​s gibt d​ann nicht einmal e​inen gemeinsamen Buchstaben.

Beispiel

S1	W	I	K	I	M	E	D	I	A
S2	W	I	K	I	M	A	N	I	A

Die längste übereinstimmende Untersequenz ist WIKIM (dunkelgrau) mit 5 Zeichen. Links davon ist keine weitere Untersequenz. Die rechte nicht übereinstimmende Subsequenz EDIA bzw. ANIA haben wieder eine übereinstimmende Subsequenz IA (hellgrau) mit der Länge 2. Das Ähnlichkeitsmaß bestimmt sich damit zu:

${\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}}}$

Eigenschaften

Komplexität

Die Laufzeit des Algorithmus ist in O${\displaystyle (n^{3})}$ im schlechtesten Fall und ${\displaystyle O(n^{2})}$ im Mittel. Durch Änderung des Verfahrens lässt sich die Laufzeit jedoch deutlich verbessern.[1]

Kommutativgesetz

Es lässt s​ich zeigen, d​ass Gestalt-Pattern-Matching-Algorithmus n​icht kommutativ ist: [4]

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

Beispiel

Für d​ie beiden Zeichenketten

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

und

${\displaystyle S_{2}={\text{GESTALT-THEORIE}}}$

ergibt s​ich für

${\displaystyle D_{ro}(S_{1},S_{2})}$ ein Maß von ${\displaystyle {\frac {22}{39}}}$ mit den Teilstrings GESTALT, T, E, R, I und für

${\displaystyle D_{ro}(S_{2},S_{1})}$ ein Maß von ${\displaystyle {\frac {20}{39}}}$ mit den Teilstrings GESTALT, T, H, I.

Anwendungsbereiche

Der Algorithmus w​urde zur Grundlage d​er difflib-Bibliothek i​n Python, welche m​it der Version 2.1 eingeführt wurde.[1] Aufgrund d​es ungünstigen Laufzeitverhaltens d​es Ähnlichkeitsmaßes wurden d​rei Methoden implementiert, v​on denen z​wei eine obere Schranke i​n einer schnelleren Laufzeit zurückgeben können.[1] Die schnellste Variante vergleicht lediglich d​ie Länge d​er beiden Teilstrings:[5]

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

# Drqr Implementierung in Python
def real_quick_ratio(s1: str, s2: str) -> float:
    "" target="_blank" rel="nofollow""Return an upper bound on ratio() very quickly."" target="_blank" rel="nofollow""
    l1, l2 = len(s1), len(s2)
    length = l1 + l2

    if not length:
        return 1.0

    return 2.0 * min(l1, l2) / length

Die zweite obere Schranke setzt die doppelte Summe aller verwendeten Zeichen aus ${\displaystyle S_{1}}$, die in ${\displaystyle S_{2}}$ vorkommen, ins Verhältnis zur Länge beider Zeichenketten. Die Zeichenfolgen bleiben dabei unberücksichtigt.

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

# Dqr Implementierung in Python
def quick_ratio(s1: str, s2: str) -> float:
    "" target="_blank" rel="nofollow""Return an upper bound on ratio() relatively quickly."" target="_blank" rel="nofollow""
    length = len(s1) + len(s2)

    if not length:
        return 1.0

    intersect = collections.Counter(s1) & collections.Counter(s2)
    matches = sum(intersect.values())
    return 2.0 * matches / length

Trivialerweise gelten:

${\displaystyle 0\leq D_{ro}\leq D_{qr}\leq D_{rqr}\leq 1}$ und

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

Komplexität

Die Laufzeit dieser speziellen Python-Implementierung ist ${\displaystyle O(n^{2})}$ im schlechtesten Fall und ${\displaystyle O(n)}$ im besten Fall.[1]

Belege

1. difflib — Helpers for computing deltas in der Python-Dokumentation
2. National Institute of Standards and Technology Ratcliff/Obershelp pattern recognition
3. Ilya Ilyankou: Comparison of Jaro-Winkler and Ratcliff/Obershelp algorithms in spell check, May 2014 (PDF; 1,3 MB)
4. How does Pythons SequenceMatcher work? auf stackoverflow.com
5. Entlehnt aus Python 3.7.0, difflib.py Zeilen 38–41 und 676–686

Literatur

• John W. Ratcliff und David Metzener: Pattern Matching: The Gestalt Approach, Dr. Dobb's Journal, Seile 46, Juli 1988

Siehe auch

• Pattern Matching