Technopedia Center
PMB University Brochure
Faculty of Engineering and Computer Science
S1 Informatics S1 Information Systems S1 Information Technology S1 Computer Engineering S1 Electrical Engineering S1 Civil Engineering

faculty of Economics and Business
S1 Management S1 Accountancy

Faculty of Letters and Educational Sciences
S1 English literature S1 English language education S1 Mathematics education S1 Sports Education
teknopedia

teknopedia

teknopedia

teknopedia

teknopedia
  • Registerasi
  • Brosur UTI
  • Kip Scholarship Information
  • Performance
  1. Weltenzyklopädie
  2. Gestalt Pattern Matching – Wikipedia
Gestalt Pattern Matching – Wikipedia
aus Wikipedia, der freien Enzyklopädie

Gestalt Pattern Matching[1], auch Ratcliff/Obershelp Pattern Recognition[2], 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.[2]

Algorithmus

[Bearbeiten | Quelltext bearbeiten]

Die Ähnlichkeit zweier Zeichenketten S 1 {\displaystyle S_{1}} {\displaystyle S_{1}} und S 2 {\displaystyle S_{2}} {\displaystyle S_{2}} wird dadurch bestimmt, dass die doppelte Anzahl der übereinstimmenden Zeichen K m {\displaystyle K_{m}} {\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]

D r o = 2 K m | S 1 | + | S 2 | {\displaystyle D_{ro}={\frac {2K_{m}}{|S_{1}|+|S_{2}|}}} {\displaystyle D_{ro}={\frac {2K_{m}}{|S_{1}|+|S_{2}|}}}[3]

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

0 ≤ D r o ≤ 1 {\displaystyle 0\leq D_{ro}\leq 1} {\displaystyle 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

[Bearbeiten | Quelltext bearbeiten]
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:

2 K m | S 1 | + | S 2 | = 2 ⋅ ( | ''WIKIM'' | + | ''IA'' | ) | S 1 | + | S 2 | = 2 ⋅ ( 5 + 2 ) 9 + 9 = 14 18 = 0. 7 ¯ {\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}}} {\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

[Bearbeiten | Quelltext bearbeiten]

Komplexität

[Bearbeiten | Quelltext bearbeiten]

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

Kommutativgesetz

[Bearbeiten | Quelltext bearbeiten]

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

D r o ( S 1 , S 2 ) ≠ D r o ( S 2 , S 1 ) . {\displaystyle D_{ro}(S_{1},S_{2})\neq D_{ro}(S_{2},S_{1}).} {\displaystyle D_{ro}(S_{1},S_{2})\neq D_{ro}(S_{2},S_{1}).}
Beispiel

Für die beiden Zeichenketten

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

und

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

ergibt sich für

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

Anwendungsbereiche

[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus wurde zur Grundlage der difflib-Bibliothek in Python, welche mit der Version 2.1 eingeführt wurde.[1] 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.[1] Die schnellste Variante vergleicht lediglich die Länge der beiden Teilstrings:[5]

D r q r = 2 ⋅ min ( | S 1 | , | S 2 | ) | S 1 | + | S 2 | {\displaystyle D_{rqr}={\frac {2\cdot \min(|S1|,|S2|)}{|S1|+|S2|}}} {\displaystyle D_{rqr}={\frac {2\cdot \min(|S1|,|S2|)}{|S1|+|S2|}}},
# Drqr Implementierung in Python
def real_quick_ratio(s1: str, s2: str) -> float:
    """Return an upper bound on ratio() very quickly."""
    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 S 1 {\displaystyle S_{1}} {\displaystyle S_{1}}, die in S 2 {\displaystyle S_{2}} {\displaystyle S_{2}} vorkommen, ins Verhältnis zur Länge beider Zeichenketten. Die Zeichenfolgen bleiben dabei unberücksichtigt.

D q r = 2 ⋅ | { | S 1 | } ∩ { | S 2 | } | | S 1 | + | S 2 | {\displaystyle D_{qr}={\frac {2\cdot {\big |}\{\!\vert S1\vert \!\}\cap \{\!\vert S2\vert \!\}{\big |}}{|S1|+|S2|}}} {\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:
    """Return an upper bound on ratio() relatively quickly."""
    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:

0 ≤ D r o ≤ D q r ≤ D r q r ≤ 1 {\displaystyle 0\leq D_{ro}\leq D_{qr}\leq D_{rqr}\leq 1} {\displaystyle 0\leq D_{ro}\leq D_{qr}\leq D_{rqr}\leq 1} und
0 ≤ K m ≤ | { | S 1 | } ∩ { | S 2 | } | ≤ min ( | S 1 | , | S 2 | ) ≤ | S 1 | + | S 2 | 2 {\displaystyle 0\leq K_{m}\leq |\{\!\vert S1\vert \!\}\cap \{\!\vert S2\vert \!\}{\big |}\leq \min(|S1|,|S2|)\leq {\frac {|S1|+|S2|}{2}}} {\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

[Bearbeiten | Quelltext bearbeiten]

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

Belege

[Bearbeiten | Quelltext bearbeiten]
  1. ↑ a b c d e difflib — Helpers for computing deltas in der Python-Dokumentation
  2. ↑ a b c 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

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

Siehe auch

[Bearbeiten | Quelltext bearbeiten]
  • Pattern Matching
Abgerufen von „https://de.teknopedia.teknokrat.ac.id/w/index.php?title=Gestalt_Pattern_Matching&oldid=237587562“
Kategorien:
  • Suchalgorithmus
  • Informationstheorie
  • Quantitative Linguistik
  • Rekursion
  • Klassifikationsverfahren

  • indonesia
  • Polski
  • العربية
  • Deutsch
  • English
  • Español
  • Français
  • Italiano
  • مصرى
  • Nederlands
  • 日本語
  • Português
  • Sinugboanong Binisaya
  • Svenska
  • Українська
  • Tiếng Việt
  • Winaray
  • 中文
  • Русский
Sunting pranala
Pusat Layanan

UNIVERSITAS TEKNOKRAT INDONESIA | ASEAN's Best Private University
Jl. ZA. Pagar Alam No.9 -11, Labuhan Ratu, Kec. Kedaton, Kota Bandar Lampung, Lampung 35132
Phone: (0721) 702022
Email: pmb@teknokrat.ac.id