Introduction

There is no single string "distance" or "similarity" measure that is best for every problem. The right metric depends on what kinds of differences matter: character typos, swapped words, missing tokens, or approximate phonetic matches. A good answer starts by matching the metric to the error pattern in your data instead of blindly picking one formula.

Levenshtein Distance Is the Default for Typo-Like Errors

Levenshtein distance counts the minimum number of insertions, deletions, and substitutions needed to change one string into another. It is a strong default when you care about spelling-like edits.

1def levenshtein(a: str, b: str) -> int:
2    m, n = len(a), len(b)
3    dp = [[0] * (n + 1) for _ in range(m + 1)]
4
5    for i in range(m + 1):
6        dp[i][0] = i
7    for j in range(n + 1):
8        dp[0][j] = j
9
10    for i in range(1, m + 1):
11        for j in range(1, n + 1):
12            cost = 0 if a[i - 1] == b[j - 1] else 1
13            dp[i][j] = min(
14                dp[i - 1][j] + 1,
15                dp[i][j - 1] + 1,
16                dp[i - 1][j - 1] + cost,
17            )
18
19    return dp[m][n]
20
21
22print(levenshtein("kitten", "sitting"))

This gives a distance, not a similarity score. Lower is more similar.

Normalize If Lengths Differ a Lot

Raw edit distance is hard to compare across strings of very different lengths. Turning it into a normalized score is often more useful for thresholds.

1def normalized_similarity(a: str, b: str) -> float:
2    distance = levenshtein(a, b)
3    scale = max(len(a), len(b), 1)
4    return 1.0 - (distance / scale)
5
6
7print(normalized_similarity("kitten", "sitting"))

This produces a score between 0 and 1, where higher means more similar.

Token-Based Similarity Helps with Word Reordering

If you are comparing names, titles, or short phrases, token overlap may matter more than exact character position. Jaccard similarity is a simple token-based option.

1def jaccard_similarity(a: str, b: str) -> float:
2    tokens_a = set(a.lower().split())
3    tokens_b = set(b.lower().split())
4
5    if not tokens_a and not tokens_b:
6        return 1.0
7
8    return len(tokens_a & tokens_b) / len(tokens_a | tokens_b)
9
10
11print(jaccard_similarity("new york city", "new city"))

This ignores repeated words and token order, which is sometimes exactly what you want.

Character N-Gram Similarity Handles Noisy Partial Matches

For noisy text where exact tokens are unreliable, character n-grams often work well. One common choice is cosine similarity over character bigrams or trigrams.

1from collections import Counter
2from math import sqrt
3
4
5def char_ngrams(text: str, n: int = 2):
6    text = text.lower()
7    if len(text) < n:
8        return [text]
9    return [text[i:i+n] for i in range(len(text) - n + 1)]
10
11
12def cosine_similarity(a: str, b: str) -> float:
13    freq_a = Counter(char_ngrams(a))
14    freq_b = Counter(char_ngrams(b))
15    keys = set(freq_a) | set(freq_b)
16
17    dot = sum(freq_a[k] * freq_b[k] for k in keys)
18    norm_a = sqrt(sum(v * v for v in freq_a.values()))
19    norm_b = sqrt(sum(v * v for v in freq_b.values()))
20
21    if norm_a == 0 or norm_b == 0:
22        return 0.0
23
24    return dot / (norm_a * norm_b)
25
26
27print(cosine_similarity("night", "nacht"))

This often captures "looks similar" better than raw token overlap.

Pick the Metric Based on the Task

A practical rule:

• use Levenshtein for spelling mistakes and short string edits
• use Jaccard for bag-of-words style overlap
• use n-gram cosine when you want softer partial matching

If you are building production matching logic, test several metrics on labeled examples rather than assuming one metric is universally correct.

Thresholds Matter as Much as the Formula

A similarity score is only useful if you know what score counts as "close enough". That threshold depends on your error tolerance.

Examples:

• customer search may favor recall
• identity matching may favor precision
• deduplication may need a review band rather than one hard cutoff

So do not copy thresholds from another dataset without validation.

Common Pitfalls

• Treating one metric as universally best across all domains.
• Comparing raw edit distance across strings of very different lengths.
• Forgetting preprocessing such as lowercasing, whitespace normalization, or tokenization.
• Using token overlap when character-level typos are the main problem.
• Confusing lexical similarity with semantic equivalence.

Summary

• String distance and similarity measures must match the kind of errors you expect.
• Levenshtein is a strong choice for typo-like character edits.
• Jaccard is useful for token overlap problems.
• Character n-gram cosine similarity handles softer partial matches well.
• Good thresholds come from validation data, not from guesswork.