Gestalt Pattern Matching

Gestalt Pattern Matching,[1] also Ratcliff/Obershelp Pattern Recognition,[2] is a string-matching algorithm for determining the similarity of two strings. It was developed in 1983 by John W. Ratcliff and John A. Obershelp and published in the Dr. Dobb's Journal in July 1988.[2]

## Contents

* 1 Algorithm
* 1.1 Sample
* 2 Properties
* 2.1 Complexity
* 2.2 Commutative property
* 3 Applications
* 4 References
* 5 Further reading
* 6 See also

## Algorithm

The similarity of two strings S1 and S2 is determined by the formula, calculating twice the number of matching characters Km divided by the total number of characters of both strings. The matching characters are defined as the longest common substring (LCS) plus recursively the number of matching characters in the non-matching regions on both sides of the LCS:[2]

Dro=2Km|S1|+|S2|[3]

where the similarity metric can take a value between zero and one:

0≤Dro≤1

The value of 1 stands for the complete match of the two strings, whereas the value of 0 means there is no match and not even one common letter.

### Sample

S1 | W | I | K | I | M  | E  | D  | I  | A

|
|
|
|
|
|
|
|
|

S2 | W | I | K | I | M  | A  | N  | I  | A

The longest common substring is `WIKIM` (grey) with 5 characters. There is no further substring on the left. The non-matching substrings on the right side are `EDIA` and `ANIA`. They again have a longest common substring `IA` (dark gray) with length 2. The similarity metric is determined by:

2Km|S1|+|S2|=2⋅(|''WIKIM''|+|''IA''|)|S1|+|S2|=2⋅(5+2)9+9=1418=0.7‾

## Properties

### Complexity

The execution time of the algorithm is O(n3) in a worst case and O(n2) in an average case. By changing the computing method, the execution time can be improved significantly.[1]

### Commutative property

It can be shown, that the Gestalt Pattern Matching Algorithm is not commutative: [4]

Dro(S1,S2)≠Dro(S2,S1).

Sample

For the two strings

S1=GESTALT PATTERN MATCHING

and

S2=GESTALT PRACTICE

the metric result for

Dro(S1,S2) is 2440 with the substrings `GESTALT P`, `A`, `T`, `E` and for
Dro(S2,S1) the metric is 2640 with the substrings `GESTALT P`, `R`, `A`, `C`, `I`.

## Applications

The algorithm became a basis of the Python `difflib` library, which was introduced in version 2.1.[1] Due to the unfavourable runtime behaviour of this similarity metric, three methods have been implemented. Two of them return an upper bound in a faster execution time.[1] The fastest variant only compares the length of the two substrings:[5]

Drqr=2⋅min⁡(|S1|,|S2|)|S1|+|S2|,

# Drqr Implementation 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

The second upper bound calculates twice the sum of all used characters S1 which occur in S2 divided by the length of both strings but the sequence is ignored.

Dqr=2⋅|{|S1|}∩{|S2|}||S1|+|S2|,

# Dqr Implementation 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

Trivially the following applies:

0≤Dro≤Dqr≤Drqr≤1 and
0≤Km≤|{|S1|}∩{|S2|}|≤min⁡(|S1|,|S2|)≤|S1|+|S2|2.

## References

1. ↑ 1.0 1.1 1.2 1.3 difflib — Helpers for computing deltas inside the Python documentation
2. ↑ 2.0 2.1 2.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)
4. ↑ How does Pythons SequenceMatcher work? at stackoverflow.com
5. ↑ Borrowed from Python 3.7.0, difflib.py Lines 38–41 and 676–686

## Further reading

* John W. Ratcliff and David Metzener: Pattern Matching: The Gestalt Approach, Dr. Dobb's Journal, Issue 46, July 1988

## See also

* Pattern matching

* v
* t
* e

Strings

String metric|

* Approximate string matching
* Bitap algorithm
* Damerau–Levenshtein distance
* Edit distance
* Gestalt Pattern Matching
* Hamming distance
* Jaro–Winkler distance
* Lee distance
* Levenshtein automaton
* Levenshtein distance
* Wagner–Fischer algorithm

String-searching algorithm|

* Apostolico–Giancarlo algorithm
* Boyer–Moore string-search algorithm
* Boyer–Moore–Horspool algorithm
* Knuth–Morris–Pratt algorithm
* Rabin–Karp algorithm

Multiple string searching|

* Aho–Corasick
* Commentz-Walter algorithm

Regular expression|

* Comparison of regular expression engines
* Regular tree grammar
* Thompson's construction
* Nondeterministic finite automaton

Sequence alignment|

* Hirschberg's algorithm
* Needleman–Wunsch algorithm
* Smith–Waterman algorithm

Data structures|

* DAFSA
* Suffix array
* Suffix automaton
* Suffix tree
* Generalized suffix tree
* Rope
* Ternary search tree
* Trie

Other|

* Parsing
* Pattern matching
* Compressed pattern matching
* Longest common subsequence
* Longest common substring
* Sequential pattern mining
* Sorting

0.00

(0 votes)

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Gestalt_Pattern_Matching&oldid=225724"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template