Gestalt pattern matching

The similarity of two strings ${\displaystyle S_{1}}$ and ${\displaystyle S_{2}}$ is determined by the formula, calculating twice the number of matching characters ${\displaystyle K_{m}}$ divided by the total number of characters of both strings. The matching characters are defined as some longest common substring[3] plus recursively the number of matching characters in the non-matching regions on both sides of the longest common substring:[2][4]

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

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

${\displaystyle 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.

The Ratcliff/Obershelp matching characters can be substantially different from each longest common subsequence of the given strings. For example ${\displaystyle S_{1}=q\;ccccc\;r\;ddd\;s\;bbbb\;t\;eee\;u}$ and ${\displaystyle S_{2}=v\;ddd\;w\;bbbb\;x\;eee\;y\;ccccc\;z}$ have ${\displaystyle ccccc}$ as their only longest common substring, and no common characters right of its occurrence, and likewise left, leading to ${\displaystyle K_{m}=5}$. However, the longest common subsequence of ${\displaystyle S_{1}}$ and ${\displaystyle S_{2}}$ is ${\displaystyle (ddd)\;(bbbb)\;(eee)}$, with a total length of ${\displaystyle 10}$.

The Python difflib library, which was introduced in version 2.1,[1] 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.[1] The fastest variant only compares the length of the two substrings:[6]

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

The second upper bound calculates twice the sum of all used characters ${\displaystyle S_{1}}$ which occur in ${\displaystyle S_{2}}$ divided by the length of both strings but the sequence is ignored.

${\displaystyle D_{qr}={\frac {2\cdot {\big |}\{\!\vert S1\vert \!\}\cap \{\!\vert S2\vert \!\}{\big |}}{|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:

${\displaystyle 0\leq D_{ro}\leq D_{qr}\leq D_{rqr}\leq 1}$ and

${\displaystyle 0\leq K_{m}\leq |\{\!\vert S1\vert \!\}\cap \{\!\vert S2\vert \!\}{\big |}\leq \min(|S1|,|S2|)\leq {\frac {|S1|+|S2|}{2}}}$.

• Ratcliff, John W.; Metzener, David (July 1988). "Pattern Matching: The Gestalt Approach". Dr. Dobb's Journal (46).

• Pattern matching