String similarity score/hash

text similarity

hash functions

string matching

algorithm

computer science

String similarity score/hash

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Algorithms

Introduction

String similarity scoring quantifies how alike two strings are, returning a value between 0 (completely different) and 1 (identical). Common approaches include edit distance (Levenshtein), token-based similarity (Jaccard, cosine), phonetic matching (Soundex, Metaphone), and hash-based techniques (SimHash, MinHash). The right choice depends on whether you need exact character matching, semantic similarity, or fuzzy deduplication at scale.

Levenshtein Distance (Edit Distance)

The minimum number of single-character edits (insert, delete, substitute) to transform one string into another:

python

1def levenshtein(a, b):
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            if a[i-1] == b[j-1]:
13                dp[i][j] = dp[i-1][j-1]
14            else:
15                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
16
17    return dp[m][n]
18
19# Convert to similarity ratio (0 to 1)
20def similarity(a, b):
21    dist = levenshtein(a, b)
22    return 1 - dist / max(len(a), len(b))
23
24print(levenshtein("kitten", "sitting"))  # 3
25print(similarity("kitten", "sitting"))   # 0.571

Python's difflib (Built-In)

python

1from difflib import SequenceMatcher
2
3def similar(a, b):
4    return SequenceMatcher(None, a, b).ratio()
5
6print(similar("apple", "appel"))     # 0.8
7print(similar("hello", "world"))     # 0.2
8print(similar("python", "python"))   # 1.0

SequenceMatcher uses the Ratcliff/Obershelp algorithm — it finds the longest common subsequences and computes a ratio based on matched characters.

Jaccard Similarity (Token-Based)

Compares sets of tokens (words, n-grams) rather than characters:

python

1def jaccard(a, b):
2    set_a = set(a.lower().split())
3    set_b = set(b.lower().split())
4    intersection = set_a & set_b
5    union = set_a | set_b
6    return len(intersection) / len(union) if union else 0
7
8print(jaccard("the quick brown fox", "the quick red fox"))   # 0.6
9print(jaccard("hello world", "world hello"))                  # 1.0 (order ignored)

Jaccard is good for comparing documents or sentences where word order does not matter.

Cosine Similarity (TF Vectors)

Treats strings as vectors of term frequencies and measures the angle between them:

python

1from collections import Counter
2import math
3
4def cosine_similarity(a, b):
5    vec_a = Counter(a.lower().split())
6    vec_b = Counter(b.lower().split())
7
8    intersection = set(vec_a) & set(vec_b)
9    dot_product = sum(vec_a[w] * vec_b[w] for w in intersection)
10
11    mag_a = math.sqrt(sum(v**2 for v in vec_a.values()))
12    mag_b = math.sqrt(sum(v**2 for v in vec_b.values()))
13
14    return dot_product / (mag_a * mag_b) if mag_a and mag_b else 0
15
16print(cosine_similarity("the cat sat on the mat", "the cat sat on a mat"))
17# 0.913

SimHash (Locality-Sensitive Hashing)

SimHash creates a fingerprint where similar strings produce similar hashes. Two strings' similarity is estimated by comparing their hash bits:

python

1import hashlib
2
3def simhash(text, hash_bits=64):
4    tokens = text.lower().split()
5    v = [0] * hash_bits
6
7    for token in tokens:
8        h = int(hashlib.md5(token.encode()).hexdigest(), 16)
9        for i in range(hash_bits):
10            if h & (1 << i):
11                v[i] += 1
12            else:
13                v[i] -= 1
14
15    fingerprint = 0
16    for i in range(hash_bits):
17        if v[i] > 0:
18            fingerprint |= (1 << i)
19
20    return fingerprint
21
22def hamming_distance(h1, h2):
23    return bin(h1 ^ h2).count('1')
24
25def simhash_similarity(a, b, bits=64):
26    h1 = simhash(a, bits)
27    h2 = simhash(b, bits)
28    return 1 - hamming_distance(h1, h2) / bits
29
30print(simhash_similarity("the quick brown fox", "the quick red fox"))
31# ~0.9 (similar documents produce close hashes)

SimHash is used by Google for web page deduplication — it scales to billions of documents.

Soundex (Phonetic Matching)

Matches strings that sound alike in English:

python

1def soundex(name):
2    if not name:
3        return ""
4    name = name.upper()
5    code = name[0]
6    mapping = {
7        'B': '1', 'F': '1', 'P': '1', 'V': '1',
8        'C': '2', 'G': '2', 'J': '2', 'K': '2', 'Q': '2', 'S': '2', 'X': '2', 'Z': '2',
9        'D': '3', 'T': '3',
10        'L': '4',
11        'M': '5', 'N': '5',
12        'R': '6'
13    }
14    for char in name[1:]:
15        digit = mapping.get(char, '0')
16        if digit != '0' and digit != code[-1]:
17            code += digit
18    code = code[0] + code[1:].replace('0', '')
19    return (code + '000')[:4]
20
21print(soundex("Robert"))    # R163
22print(soundex("Rupert"))    # R163 (same — they sound similar)
23print(soundex("Smith"))     # S530
24print(soundex("Smyth"))     # S530 (same)

Using Libraries

python

1# python-Levenshtein (fast C implementation)
2import Levenshtein
3print(Levenshtein.ratio("kitten", "sitting"))      # 0.615
4print(Levenshtein.distance("kitten", "sitting"))   # 3
5
6# fuzzywuzzy / thefuzz
7from thefuzz import fuzz
8print(fuzz.ratio("new york mets", "new york meats"))         # 96
9print(fuzz.partial_ratio("yankees", "new york yankees"))     # 100
10print(fuzz.token_sort_ratio("world hello", "hello world"))   # 100
11
12# jellyfish (phonetic + edit distance)
13import jellyfish
14print(jellyfish.soundex("Catherine"))     # C365
15print(jellyfish.metaphone("Catherine"))   # K0RN
16print(jellyfish.jaro_winkler_similarity("martha", "marhta"))  # 0.961

Comparison Table

Method	Type	Best For	Time Complexity
Levenshtein	Character	Typo detection, spell check	O(n*m)
Jaro-Winkler	Character	Name matching	O(n*m)
Jaccard	Token	Document comparison	O(n+m)
Cosine	Token	Text similarity	O(n+m)
SimHash	Hash	Large-scale deduplication	O(n) per doc
Soundex	Phonetic	Name matching (English)	O(n)
Metaphone	Phonetic	Name matching (improved)	O(n)

Common Pitfalls

Case sensitivity: Most similarity functions are case-sensitive by default. "Hello" and "hello" score less than 1.0. Normalize case before comparing.
Levenshtein on long strings: O(n*m) time and space. For strings over 10,000 characters, use approximate methods or n-gram hashing instead.
Jaccard ignoring word frequency: Jaccard treats each word as present or absent. "the the the cat" and "the cat" have Jaccard similarity 1.0. Use cosine similarity when word frequency matters.
SimHash for short strings: SimHash works well for documents but poorly for short strings (fewer than 5 tokens) because the hash bits are not sufficiently populated.
Soundex is English-only: Soundex encoding is designed for English names. It produces meaningless results for other languages. Use language-specific phonetic algorithms (Cologne phonetics for German, etc.).

Summary

Use Levenshtein/difflib.SequenceMatcher for character-level typo detection
Use Jaccard or cosine similarity for document/sentence comparison
Use SimHash or MinHash for large-scale near-duplicate detection
Use Soundex or Metaphone for phonetic (sounds-like) matching
Use thefuzz (fuzzywuzzy) for practical fuzzy string matching with multiple strategies
Always normalize case and whitespace before comparing strings

DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course

Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

String similarity score/hash

Data Structures & Algorithms practice on Codemia

Introduction

Levenshtein Distance (Edit Distance)

Python's difflib (Built-In)

Jaccard Similarity (Token-Based)

Cosine Similarity (TF Vectors)

SimHash (Locality-Sensitive Hashing)

Soundex (Phonetic Matching)

Using Libraries

Comparison Table

Common Pitfalls

Summary

Related reading

DSA Fundamentals

Track what you have practised

Data Structures & Algorithms practice on Codemia