Gestalt pattern matching, also Ratcliff/Obershelp pattern recognition, 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.National Institute of Standards and Technology Ratcliff/Obershelp pattern recognition
Algorithm The similarity of two strings and is determined by this formula: twice the number of matching characters divided by the total number of characters of both strings. The matching characters are defined as some longest common substringWhile two strings may have several longest common substrings, Ratcliff (1988) apparently assumes that there is only one. plus recursively the number of matching characters in the non-matching regions on both sides of the longest common substring:Ilya Ilyankou: Comparison of Jaro-Winkler and Ratcliff/Obershelp algorithms in spell check, May 2014 (PDF)
where the similarity metric can take a value between zero and one:
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 S1WIKIMEDIAS2WIKIMANIA The longest common substring is WIKIM (light 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:
Properties The Ratcliff/Obershelp matching characters can be substantially different from each longest common subsequence of the given strings. For example and have as their only longest common substring, and no common characters right of its occurrence, and likewise left, leading to . However, the longest common subsequence of and is , with a total length of .
Complexity The execution time of the algorithm is in a worst case and in an average case. By changing the computing method, the execution time can be improved significantly.
Commutative property The Python library implementation of the gestalt pattern matching algorithm is not commutative:How does Pythons SequenceMatcher work? at stackoverflow.com
Sample For the two strings
and
the metric result for is with the substrings GESTALT P, A, T, E and for the metric is with the substrings GESTALT P, R, A, C, I.
Applications The Python difflib library, which was introduced in version 2.1,difflib — Helpers for computing deltas inside the Python documentation implements a similar algorithm that predates the Ratcliff-Obershelp algorithm. 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. The fastest variant only compares the length of the two substrings:Borrowed from Python 3.7.0, difflib.py Lines 38–41 and 676–686
,
The second upper bound calculates twice the sum of all used characters which occur in divided by the length of both strings but the sequence is ignored.
# Dqr Implementation in Python import collections
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: and .
References
Further reading
See also Pattern matching