python-string-similarity

Shingle-based algorithms convert strings into sets of n-grams (sequences of $n$ characters). You can use them in two ways:

1. Directly: Compute distance between two strings using QGram.
2. For large datasets: Pre-compute string profiles using get_profile() and then compare profiles using similarity_profiles().

CRITICAL: You must use the same KShingling object (the same $n$ value) to parse all input strings for profile comparison to work.

# Direct distance
from strsimpy.qgram import QGram
qgram = QGram(2)
print(qgram.distance('ABCD', 'ABCE'))

# Profile comparison for large datasets
from strsimpy.cosine import Cosine
cosine = Cosine(2)
s0 = 'My first string'
s1 = 'My other string...'
p0 = cosine.get_profile(s0)
p1 = cosine.get_profile(s1)
print(cosine.similarity_profiles(p0, p1))

The library categorizes algorithms into several interfaces to help you choose the right measure for your use case:

• StringSimilarity: Algorithms that define similarity (0 means strings are completely different).
• NormalizedStringSimilarity: Algorithms that define similarity between 0.0 and 1.0 (e.g., Jaro-Winkler).
• StringDistance: Algorithms that define distance (0 means strings are identical). The maximum value depends on the algorithm.
• NormalizedStringDistance: Algorithms where the distance is always between 0.0 and 1.0 (e.g., NormalizedLevenshtein).
• MetricStringDistance: Distances that satisfy the triangle inequality ($d(x, y) \le d(x, z) + d(z, y)$). This is important for nearest-neighbor search and indexing structures. Note that while Levenshtein is a metric distance, NormalizedLevenshtein is not.

Install the strsimpy package using pip. Note that the package name strsim is deprecated and should not be used.

pip install -U strsimpy

Weighted Levenshtein allows you to define custom costs for insertions, deletions, and substitutions. This is useful for OCR (where certain character substitutions are more likely) or keyboard auto-correction (where adjacent keys have lower substitution costs).

from strsimpy.weighted_levenshtein import WeightedLevenshtein


def insertion_cost(char):
    return 1.0


def deletion_cost(char):
    return 1.0


def substitution_cost(char_a, char_b):
    if char_a == 't' and char_b == 'r':
        return 0.5
    return 1.0

weighted_levenshtein = WeightedLevenshtein(
    substitution_cost_fn=substitution_cost,
    insertion_cost_fn=insertion_cost,
    deletion_cost_fn=deletion_cost
)
print(weighted_levenshtein.distance('String1', 'String2'))

The OptimalStringAlignment class computes the number of edit operations needed to make two strings equal, with the restriction that no substring is edited more than once. Note that this is a variant of Damerau–Levenshtein and does not satisfy the triangle inequality, meaning it is not a true metric.

from strsimpy.optimal_string_alignment import OptimalStringAlignment

optimal_string_alignment = OptimalStringAlignment()
print(optimal_string_alignment.distance('CA', 'ABC'))

The LongestCommonSubsequence class finds the longest subsequence common to two sequences. Unlike substrings, subsequences do not need to be consecutive.

• distance(s1, s2): Returns n + m - 2 * |LCS(s1, s2)|.
• length(s1, s2): Returns the length of the longest common subsequence.

from strsimpy.longest_common_subsequence import LongestCommonSubsequence
lcs = LongestCommonSubsequence()
print(lcs.distance('AGCAT', 'GAC'))
print(lcs.length('AGCAT', 'GAC'))

The Levenshtein distance is the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into another. It is a metric distance and uses the Wagner–Fischer algorithm with $O(m \cdot n)$ complexity.

from strsimpy.levenshtein import Levenshtein

levenshtein = Levenshtein()
print(levenshtein.distance('My string', 'My $string'))

Damerau-Levenshtein distance includes insertions, deletions, substitutions, and the transposition of two adjacent characters. It is a metric distance. This implementation is the 'unrestricted' version, which is distinct from 'Optimal String Alignment' (where no substring can be edited more than once).

from strsimpy.damerau import Damerau

damerau = Damerau()
print(damerau.distance('ABCDEF', 'ABDCEF'))

The MetricLCS class provides a distance metric based on the Longest Common Subsequence. The distance is calculated as 1 - |LCS(s1, s2)| / max(|s1|, |s2|).

from strsimpy.metric_lcs import MetricLCS

metric_lcs = MetricLCS()
s1 = 'ABCDEFG'
s2 = 'ABCDEFHJKL'
print(metric_lcs.distance(s1, s2))

The SIFT4 class implements a general-purpose string distance algorithm inspired by Jaro-Winkler and LCS. It is designed to match human perception of string distance by accounting for character substitution, character distance, and longest common subsequence. It supports a maxoffset parameter.

from strsimpy import SIFT4

s = SIFT4()
print(s.distance('This is the first string', 'And this is another string'))
print(s.distance('Lorem ipsum...', 'Amet Lorm...', maxoffset=10))

Normalized Levenshtein distance is the Levenshtein distance divided by the length of the longest string, resulting in a value in the interval $[0.0, 1.0]$. Note that this is not a metric distance. Similarity is calculated as $1 - \text{distance}$.

from strsimpy.normalized_levenshtein import NormalizedLevenshtein

normalized_levenshtein = NormalizedLevenshtein()
print(normalized_levenshtein.distance('My string', 'My $string'))
print(normalized_levenshtein.similarity('My string', 'My $string'))

The JaroWinkler class computes a similarity score between 0.0 and 1.0. It is best suited for short strings like person names and detecting typos. It is a variation of Damerau-Levenshtein where substitutions of characters close to each other are weighted differently. To get the distance, compute 1 - similarity.

from strsimpy.jaro_winkler import JaroWinkler

jarowinkler = JaroWinkler()
print(jarowinkler.similarity('My string', 'My tsring'))
print(jarowinkler.similarity('My string', 'My ntrisg'))