Gestalt Pattern Matching
# Gestalt Pattern Matching

Gestalt Pattern Matching, auch Ratcliff/Obershelp Pattern Recognition, ist ein String-Matching-Algorithmus zur Bestimmung der Ähnlichkeit zweier Zeichenketten. Er wurde 1983 von John W. Ratcliff und John A. Obershelp entwickelt und im Juli 1988 im Dr. Dobb’s Journal veröffentlicht.

## Algorithmus

Die Ähnlichkeit zweier Zeichenketten $S_{1}$ und $S_{2}$ wird dadurch bestimmt, dass die doppelte Anzahl der übereinstimmenden Zeichen $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:

    $D_{ro}={\frac {2K_{m}}{|S_{1}|+|S_{2}|}}$

wobei das Ähnlichkeitsmaß einen Wert zwischen null und eins annehmen kann:

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

Der Wert 1 steht dabei für vollständige Übereinstimmung, der Wert 0 dagegen für keinerlei Übereinstimmung, es gibt dann nicht einmal einen gemeinsamen Buchstaben.

### Beispiel

| $S_1$ | W | I | K | I | M | E | D | I | A |
| - | - | - | - | - | - | - | - | - | - |
| $S_2$ | 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:

    ${\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$(n^{3})$ im schlechtesten Fall und $O(n^{2})$ im Mittel. Durch Änderung des Verfahrens lässt sich die Laufzeit jedoch deutlich verbessern.

### Kommutativgesetz

Es lässt sich zeigen, dass Gestalt-Pattern-Matching-Algorithmus nicht kommutativ ist:

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

**Beispiel**

Für die beiden Zeichenketten

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

und

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

ergibt sich für

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

## Anwendungsbereiche

Der Algorithmus wurde zur Grundlage der difflib-Bibliothek in Python, welche mit der Version 2.1 eingeführt wurde. Aufgrund des ungünstigen Laufzeitverhaltens des Ähnlichkeitsmaßes wurden drei Methoden implementiert, von denen zwei eine obere Schranke in einer schnelleren Laufzeit zurückgeben können. Die schnellste Variante vergleicht lediglich die Länge der beiden Teilstrings:

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

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

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

Trivialerweise gelten:

    $0\leq D_{ro}\leq D_{qr}\leq D_{rqr}\leq 1$ und
    $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 $O(n^{2})$ im schlechtesten Fall und $O(n)$ im besten Fall.

## Belege

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