Gestalt pattern matching

Gestalt Pattern Matching, also Ratcliff/Obershelp Pattern Recognition, is a string-matching algorithms 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.

Algorithm

The similarity of two string $S_{1}$ and $S_{2}$ is determined by the formula, calculating twice the number of matching [[Character (symbol)|characters] $K_{m}$ 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:

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

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

$0\leq D_{ro}\leq 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 (dark grey) with 5 characters. There is no further substring on left. The non-matching substrings on right side are EDIA and ANIA. They again have a longest common substring IA (light gray) with length 2. The similarity metric is determined by:

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

Properties

Complexity

The execution time of the algorithm is O$(n^{3})$ in worst case and $O(n^{2})$ in average case. By changing the computing method the execution time can be improved significantly.

Commutative property

It can be shown, that Gestalt Pattern Matching Algorithm is not commutative:

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

Sample

For the two strings

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

and

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

the metric result for

$D_{ro}(S_{1},S_{2})$ is ${\frac {22}{39}}$ with the substrings GESTALT, T, E, R, I and for

$D_{ro}(S_{2},S_{1})$ the metric is ${\frac {20}{39}}$ with the substrings GESTALT, T, H, I.

Applications

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

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

# Drqr Implementation in Python
def real_quick_ratio(s1, s2):
    """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 $S_{1}$ which occur in $S_{2}$ divided by the lenght od both strings but the sequence is ignored.

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

# Dqr Implementation in Python
def quick_ratio(s1, s2):
    """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\leq D_{ro}\leq D_{qr}\leq D_{rqr}\leq 1$.

Complexity

The execution timr of this particular Python implementation was statet as $O(n^{2})$ in worst case and $O(n)$ in best case.

Further Reading

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

See also

• Pattern matching