Python SequenceMatcher.ratio Similarity Metric

Python’s difflib.SequenceMatcher.ratio() computes a similarity score between two sequences based on the Ratcliff-Obershelp algorithm, commonly known as Gestalt Pattern Matching. This article explores how this metric works, the mathematical formula behind it, how matching blocks are determined, and how it differs from traditional edit-distance metrics.

The Metric: Ratcliff-Obershelp Algorithm

The metric produced by SequenceMatcher.ratio() is an implementation of the Ratcliff-Obershelp algorithm, developed in 1988 by John W. Ratcliff and David E. Obershelp. Instead of calculating the minimum number of edits required to transform one string into another, it measures the proportion of shared characters found in common contiguous subsequences.

The returned score is a floating-point value between 0.0 (completely different) and 1.0 (identical sequences).

Mathematical Formula

The similarity ratio is calculated using the formula:

\[\text{Similarity Ratio} = \frac{2 \times M}{T}\]

Where:

• \(M\) (Matches): The total number of elements shared between both sequences as determined by the matching process.
• \(T\) (Total): The combined length of both sequences, defined as len(sequence1) + len(sequence2).

Because \(M\) can never exceed the length of the shorter sequence, \(2 \times M\) is always less than or equal to \(T\), ensuring the result stays between 0.0 and 1.0.

How the Matches (\(M\)) Are Determined

To compute \(M\), SequenceMatcher uses a recursive greedy approach:

1. Find Longest Contiguous Match: The algorithm identifies the longest contiguous common subsequence between the two inputs.
2. Recursive Partitioning: Once the longest match is identified, the elements to the left and right of this match in both sequences are processed independently to find further non-overlapping matching segments.
3. Summation: The process repeats recursively until no common subsequences remain. The lengths of all identified matching blocks are added together to produce \(M\).

Python Example

from difflib import SequenceMatcher

s1 = "kitten"
s2 = "sitting"

matcher = SequenceMatcher(None, s1, s2)
ratio = matcher.ratio()

print(f"Similarity: {ratio:.3f}")
# Output: Similarity: 0.615

In this example:

• len(s1) = 6, len(s2) = 7, so \(T = 13\).
• The longest matching blocks found are "itt" (length 3) and "n" (length 1), giving \(M = 4\).
• The formula computes: \((2 \times 4) / 13 = 8 / 13 \approx 0.6154\).

Difference from Levenshtein Distance

A common misconception is that difflib.SequenceMatcher calculates Levenshtein distance. They differ significantly:

• Levenshtein Distance: Calculates the absolute minimum number of single-character edits (insertions, deletions, substitutions) needed to change one string into another.
• Ratcliff-Obershelp (difflib): Rewards sequences that share large contiguous blocks, regardless of their position. It tends to produce higher similarity scores for strings that share common phrases or chunks that have been rearranged.